ScholaFly

CS03-06 Computer Science Watch

Huffman coding

Watch on YouTube

In this lesson

Huffman coding for GCSE Computer Science. AQA 8525 GCSE. Images and sound 6 of 7. Full Images and sound playlist: {{playlist:CS03-06}} More at https://scholafly.com

By the end: Read a given Huffman tree to encode and decode a message, calculate the number of bits the data takes when compressed with Huffman coding, calculate what the same data takes uncompressed in 7-bit ASCII, and give the number of bits saved.

What it covers

  1. 0:00 Intro: huffman coding
  2. 1:00 Huffman coding: reading the tree
  3. 3:47 Huffman coding: decoding
  4. 5:27 The compressed size
  5. 7:03 Plain ASCII and the saving
  6. 8:38 Spot the mistake

Key words

About this video

Huffman coding | GCSE Computer Science

Huffman coding for GCSE Computer Science.
AQA 8525 GCSE. Images and sound 6 of 7.
Full Images and sound playlist: {{playlist:CS03-06}}
More at https://scholafly.com

Watch first: CS02-02 Character sets and ASCII, CS03-05 Why we compress data
Video code: CS03-06 (search "ScholaFly CS03-06")

Videos in this chapter:
CS03-00 Images, sound and compression - Intro: {{link:CS03-00}}
CS03-01 How an image is stored: {{link:CS03-01}}
CS03-02 From binary to bitmap and back: {{link:CS03-02}}
CS03-03 How sound is stored: {{link:CS03-03}}
CS03-04 Working out image and sound file sizes: {{link:CS03-04}}
CS03-05 Why we compress data: {{link:CS03-05}}
CS03-06 Huffman coding: {{link:CS03-06}}
CS03-07 Run length encoding: {{link:CS03-07}}

#GCSEComputerScience #ImagesAndSound #HuffmanCoding

For teachers
This GCSE Computer Science lesson teaches Huffman coding. By the end, students should be able to read a given Huffman tree to encode and decode a message, calculate the number of bits the data takes when compressed with Huffman coding, calculate what the same data takes uncompressed in 7-bit ASCII, and give the number of bits saved. It works through four worked examples and the mistakes examiners report, and suits Foundation and Higher tier students.

Exam board specification references:
AQA GCSE Computer Science (8525)
- 3.3.8 Data compression

Read the transcript

A twenty-letter message stored in ASCII takes a hundred and forty bits, seven for every letter. Can it fit in under forty bits, with not one letter lost? Squeezing it that hard sounds as if some letters must be thrown away. None are. Huffman coding gives the common letters short codes and the rare ones long codes, a trick David Huffman found as a student in nineteen fifty-one. It starts with reading a tree, one branch at a time.

Video six of seven, and the first of two named ways to compress. If the reasons for compressing still feel hazy, Why we compress data sets them out.

A Huffman tree gives every character a code made of the branches you take to reach it. On this tree, a branch to the left is a zero and a branch to the right is a one. To read a code, start at the top and walk downwards to the letter, writing each bit as you go. This method is on one exam board's course only. Other courses do not ask for it, so if yours is one of them, treat this video as background. It is also a lossless method: nothing is thrown away. This tree holds four letters. From the top, left reaches E straight away. Right leads on: then left reaches A, and right leads on again, where left is S and right is T. Never start at the letter and climb up to the top. That walk writes the code backwards. Take S. From the top, right is one, right again is one, then left is zero, so S is one one zero, three bits. Take E: one step left is zero, so E is a single bit, zero. The lengths already tell the story. E, the most common letter, gets the shortest code, and S, a rarer one, gets a longer code. Now A. Walking down from the top, what is the code for A? One zero: right for the one, then left for the zero, so A is two bits long. So the word SEA is one one zero, then zero, then one zero, written together with no gaps: one one zero zero one zero. That is six bits for three letters. One examiner's report covers this part. It is on an older version of the same course, from November twenty twenty, and the Huffman requirement has not changed since. It says: The Huffman tree was well interpreted. Reading the tree is the part students manage. The habit that keeps it that way is walking down from the top every time, and the rest of this video goes on the two counts that come after it.

Decoding runs the same tree the other way: bits in, letters out. Start at the top, follow each bit down a branch, and the moment you reach a letter, write it down and jump back to the top. Here is a string to decode: one one one zero one zero one one zero zero. From the top, one is right, one is right, and one is right, which reaches T. Write T and jump back to the top. The next bit goes left and reaches E straight away. Decode the remaining six bits yourself, before I show you. One zero is A, one one zero is S, and the final zero is E. The string spells TEASE. Now the reason. With no gaps in the string, why was only one reading possible? Because no code is the start of another code. E is zero and no other code begins with zero, so reaching a letter is always final and the decoder can never take a wrong turn.

Now the first count: how many bits the message takes with Huffman coding. The message is twenty characters long, with nine Es, five As, four Ss and two Ts. Before multiplying anything, check the counts add up to the message length. Nine plus five plus four plus two is twenty, so the count check passes. Each row of the tally is the count times that letter's code length, and the total is all the rows added together. E is nine times one bit, which is nine bits. A is five times two bits, which is ten bits. Try the S and T rows and the total on paper before I show you. The total comes to thirty-seven bits for the whole message. S is four times three bits, which is twelve. T is two times three bits, which is six. Nine plus ten plus twelve plus six is thirty-seven. One wrong route takes the four different letters times a code length. That counts letters on the tree, not letters in the message, which is why the count column comes first.

The second count is the same twenty characters stored as plain ASCII, where every character takes the same number of bits. On the course that teaches Huffman coding, ASCII uses seven bits per character, and a full answer writes that seven down before multiplying. The video Character sets and ASCII covers why. Twenty characters times seven bits is one hundred and forty bits. The same older report explains that the question expected students to know ASCII is a seven-bit representation of characters but, in its words, many students calculated an answer using eight bits per character. The habit: write seven bits per character, with your course beside it, before you multiply, so the saving rests on the right number. Now the saving. How many bits did Huffman coding save on this message? One hundred and three bits. One hundred and forty take away thirty-seven is one hundred and three. The saving is a third number, found by a subtraction, and its answer is in bits. It is neither the compressed size nor a ratio.

Some questions hand you someone else's working and ask what went wrong. That is a different job from doing the method yourself. A student's working reads: E, nine times one is nine. A, five times two is ten. S, four times three is twelve. T, two times three is six. Total, thirty-seven. Uncompressed, four letters times seven bits is twenty-eight. Saving, none, because the Huffman version is bigger. Which line of that working is wrong, and what should it say? The uncompressed line is the wrong one. It counted the four different letters, not the twenty characters. It should be twenty times seven, one hundred and forty bits, and then the saving is one hundred and three. The same older report notes this kind of question going astray. Responses for the second part of the question often described the correct order of actions rather than answering the question about mistakes in the student response given. The fix: when the question asks for the mistake, name the line, say what is wrong with it, and give the corrected value. Do not rewrite the whole method.

Four questions to close, with the twenty-letter message from the start saved for last. Which way do you walk the tree to read a code, and why? Down from the top. Walking up from the letter gives the code in reverse. Now a different message on this tree: six Es and three As. How many Huffman bits? Twelve bits. Six times one is six, and three times two is six, so twelve. Now plain ASCII. A nine-character message on this course: how many bits uncompressed? Sixty-three bits, because nine characters times seven bits each is sixty-three. Try one last twist on the twenty-letter message. With eight bits a character by mistake, what saving appears? One hundred and twenty-three bits, which is twenty too many. Seven bits a character gives one hundred and forty, and the true saving is one hundred and three. That is the twenty-letter message from the start: a hundred and forty bits in ASCII, thirty-seven with Huffman coding, and not one letter lost.

You own this one if you could take a tree and a letter count and get from the codes to the saving without stopping, and that earns it a thumbs up. If the counting still slips, save it; this kind of method often lands on a second viewing.

Next in the chapter: Run length encoding.

For more, visit scholafly.com, or watch the next video.

Related terms

For: AQA GCSE 8525

On the specification

BoardSpecStatement
AQA GCSE 85253.3.8Data compression
For teachers

This GCSE Computer Science lesson teaches Huffman coding. By the end, students should be able to read a given Huffman tree to encode and decode a message, calculate the number of bits the data takes when compressed with Huffman coding, calculate what the same data takes uncompressed in 7-bit ASCII, and give the number of bits saved. It works through four worked examples and the mistakes examiners report, and suits Foundation and Higher tier students.