Huffman Coding
Copy this iframe to your website:
1 | |
Description
This MicroSim builds a Huffman code step by step. The Source list chooses the symbol probabilities: a skewed five-symbol source, powers of 1/2, a uniform eight-symbol source, two symbols with \(p = 0.9\) and \(0.1\), approximate English letter counts per 1000 letters, or Count the characters of my message, which counts every character (spaces included) of the text in the Message box (up to 30 characters). With a preset, the box holds a sample message that is encoded with the preset's code.
Each press of Next merge joins the two least-probable nodes, ringed in gold, into a new node whose probability is their sum. Build tree does all remaining merges, Undo takes one back and Reset returns to the separate symbols. Ties are broken by a fixed rule (single symbols first, then alphabetical order, then the oldest merged node), so the tree is always the same. The table under the leaves lists \(p_i\) (or the count \(n_i\)), the ideal length \(-\log_2 p_i\), the codeword and its length \(\ell_i\). Every merge puts one bit, 0 for the left branch and 1 for the right, in front of the codeword of each symbol below it.
The side panel compares the entropy and the average code length,
and shows the efficiency \(H/L\), the fixed-length code of \(\lceil \log_2 K \rceil\) bits for \(K\) symbols, and the compression ratio (fixed-length bits divided by Huffman bits). The bottom panel encodes the message into a bit stream, counts its bits, and decodes it by walking down the tree. Point at a leaf to trace its path.
This MicroSim is used in Chapter 13: Multirate Signal Processing and Compression.
Lesson Plan
Learning Objectives
After using this MicroSim, students will be able to:
- Construct a Huffman code by repeatedly merging the two least-probable nodes and reading the codewords from the root
- Calculate the entropy \(H\), the average code length \(L\), the efficiency \(H/L\) and the compression ratio against a fixed-length code
- Verify the bound \(H \le L < H + 1\) and identify the distributions for which \(L = H\) exactly
- Explain why a prefix-free code can be decoded without separators between codewords
- Analyze why Huffman coding is inefficient for very skewed sources and how coding blocks of symbols improves it
Target Audience
Undergraduate students in a digital signal processing, communications or information theory course (junior or senior engineering or computer science). Plan 25 minutes for the activities below.
Prerequisites
- Probability of discrete events and the base-2 logarithm
- Binary numbers and binary trees
- The idea of lossless compression (Chapter 13)
Activities
Activity 1: Build the tree by hand (7 min). Choose Skewed: 5 symbols (\(p\) = 0.4, 0.2, 0.2, 0.1, 0.1) and press Reset. Before each press of Next merge, predict the next pair. The four merges are D + E → 0.2, B + C → 0.4, DE + A → 0.6 and BC + DEA → 1.0; the second and third merges are ties, settled by the tie rule. After each merge "L so far" reads 0.200, 0.600, 1.200 and 2.200: every merge adds its probability to \(L\). The final code is A = 11, B = 00, C = 01, D = 100, E = 101, with \(H = 2.122\) and \(L = 2.200\) bits/symbol, an efficiency of 96.5 % and a compression ratio of \(3/L = 1.36\). The message ACABADABCE needs 22 bits instead of \(10 \times 3 = 30\).
Activity 2: When does L equal H? (6 min). Choose Powers of 1/2. Every \(-\log_2 p_i\) (1, 2, 3, 4, 4) is an integer and equals \(\ell_i\), so \(L = H = 1.875\) bits/symbol and the efficiency is 100.0 %. Choose Uniform: 8 symbols: \(L = H = 3.000\), every codeword has 3 bits and the ratio is 1.00, so there is nothing to gain over a fixed-length code. Now choose Count the characters of my message and type ABCDEF: six equally likely symbols give \(H = 2.585\) and \(L = 2.667\) (lengths 2, 2, 3, 3, 3, 3), and the message needs 16 bits instead of 18.
Activity 3: The one-bit floor (5 min). Choose Two symbols: 0.9 and 0.1. The entropy is only 0.469 bits/symbol, but each codeword needs at least one bit, so \(L = 1.000\) and the efficiency drops to 46.9 %, with no gain over the 1-bit fixed-length code. Huffman coding loses most when one symbol is very likely.
Activity 4: English letters and your own text (7 min). Choose English letters A–Z and press Build tree. The common letters E (100) and T (000) get 3 bits, while J, Q, X and Z get 9 bits; \(H = 4.173\), \(L = 4.202\) bits/letter (99.3 %), and the ratio against 5-bit codes is 1.19. The sample SHANNON needs 28 bits (4.000 bits/letter). Type HUFFMAN: it needs 32 bits (4.571 bits/letter), because F, U and M are less common. Finally choose Count the characters of my message and type MISSISSIPPI: S = 0, I = 11, M = 100, P = 101, \(H = 1.823\), \(L = 1.909\), and the message needs 21 bits instead of 22.
Assessment
- Symbols A–E have probabilities 0.4, 0.2, 0.2, 0.1 and 0.1. What is \(L\) for the sim's Huffman code, and what is the compression ratio against a fixed-length code? Answer: lengths 2, 2, 2, 3, 3 give \(L = 0.8 + 0.4 + 0.4 + 0.3 + 0.3 = 2.2\) bits/symbol; a fixed-length code needs \(\lceil\log_2 5\rceil = 3\) bits, so the ratio is \(3/2.2 = 1.36\).
- For which probability distributions does a Huffman code reach \(L = H\) exactly? Answer: when every probability is a power of 1/2 (a dyadic distribution), because then \(-\log_2 p_i\) is an integer and Huffman's lengths equal it, as in the Powers of 1/2 preset (\(L = H = 1.875\)).
- The bit stream 110111100101 was made with the skewed code (A = 11, B = 00, C = 01, D = 100, E = 101). Decode it and explain why no separators are needed. Answer: 11 | 01 | 11 | 100 | 101 = A C A D E (12 bits). No codeword is the start of another, so the decoder knows a codeword has ended the moment it reaches a leaf; type ACADE in the Message box with the skewed preset to check.
- A source has \(p = 0.9\) and \(0.1\). Why is the Huffman efficiency only 46.9 %, and how could it be improved? Answer: \(H = 0.469\) bits/symbol, but every codeword needs at least one bit, so \(L = 1\). Coding pairs of symbols (probabilities 0.81, 0.09, 0.09, 0.01) gives lengths 1, 2, 3, 3, so \(L = 1.29\) bits per pair, or 0.645 bits/symbol; arithmetic coding gets closer still.
- With the English letter code, the message ZZZ needs 27 bits while a 5-bit fixed-length code needs 15. Does this contradict the claim that Huffman coding compresses? Answer: no. Huffman coding minimizes the average length over the source distribution (\(L = 4.202 < 5\) bits/letter); a message made of rare letters is atypical and can be longer than with a fixed-length code.
Common Misconceptions
"The Huffman code for a source is unique." The tie rule decides which of several equal-weight nodes is merged. For the skewed preset the sim gives lengths 2, 2, 2, 3, 3; preferring merged nodes in the ties gives lengths 1, 2, 3, 4, 4 instead. Both have \(L = 2.2\) bits/symbol: the codes differ, but the average length is the same minimum.
"Huffman coding always reaches the entropy." It does only when every probability is a power of 1/2. The two-symbol preset shows \(L = 1.000\) against \(H = 0.469\), and every other preset shows \(L\) inside the shaded band from \(H\) to \(H + 1\) rather than at \(H\).
References
- Huffman coding - Wikipedia - the merge algorithm, optimality among prefix codes, tie handling and minimum-variance codes
- Entropy (information theory) - Wikipedia - the definition \(H = -\sum p_i \log_2 p_i\) and its meaning as average information per symbol
- Shannon's source coding theorem - Wikipedia - why no lossless code can average fewer than \(H\) bits per symbol
- Prefix code - Wikipedia - the prefix property that lets a bit stream be decoded without separators
- Letter frequency - Wikipedia - typical relative frequencies of letters in English text, the basis of the English preset
- Arithmetic coding - Wikipedia - an entropy coder that avoids the one-bit-per-symbol floor of Huffman coding
- Chapter 27: Data Compression - Steven W. Smith, The Scientist and Engineer's Guide to Digital Signal Processing - free chapter covering Huffman coding and other compression methods