CS03-06 Computer Science Coming soon
Huffman coding
CS03-06
This lesson is coming soon.
In this lesson
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
- WHY variable-length codes are worth having: common characters get short codes, rare characters get long ones, and the total shrinks
- INTERPRETING A GIVEN TREE: start at the root and follow the branches as labelled to reach a character, reading the code off the path
- Encoding a short message from the tree, character by character, and joining the codes with nothing in between
- Decoding a bit string with the tree: walk from the root, output the character when a leaf is reached, then go back to the root and carry on
- The reason there are no separators, in plain words: no character's code is the beginning of another character's code, so the bit string can only be read one way
- CALCULATING THE COMPRESSED SIZE: for each character, its code length multiplied by how many times it occurs, all added up
- CALCULATING THE UNCOMPRESSED SIZE IN ASCII: number of characters x 7 bits, because AQA examines ASCII as 7-bit (settled in CS02-02, and the corpus records the mark being lost to 8)
- THE SAVING: uncompressed minus compressed, answered in bits unless the question says otherwise
Key words
For: AQA GCSE 8525
On the specification
| Board | Spec | Statement |
|---|---|---|
| AQA GCSE 8525 | 3.3.8 | Data 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.