Huffman Coding — Communication Systems

Huffman Coding: Building the Optimal Compression Code

Huffman coding is one of the most elegant algorithms in computer science — it creates the optimal variable-length binary code for any given set of symbol probabilities. Invented by David Huffman in 1952 as a term paper for an MIT class (beating his professor's alternative!), it remains the foundation of countless compression systems including JPEG, MP3, ZIP files, and even the DEFLATE algorithm used by virtually every web server.

The Core Idea: Short Codes for Common Symbols

Think of it this way: in Morse code, the letter E (the most common in English) is represented by a single dot, while Q (rare) requires four symbols (dash-dash-dot-dash). Huffman coding formalizes this principle — frequently occurring symbols get short codewords, rare symbols get long ones — and does so optimally.

Key property: Huffman codes are prefix-free, meaning no codeword is a prefix of any other codeword. This allows instant, unambiguous decoding without needing separators between symbols.

The Huffman Algorithm

Step-by-step procedure:

1. List all symbols with their probabilities
2. Find the two symbols with the lowest probabilities
3. Combine them into a new "super-symbol" with probability = sum of both
4. Assign 0 to one branch and 1 to the other
5. Repeat steps 2-4 until only one symbol remains (the root)
6. Read codewords by tracing from root to each leaf

Example: Source symbols with probabilities:

• A: 0.40, B: 0.20, C: 0.15, D: 0.15, E: 0.10

Construction:

1. Combine E(0.10) + D(0.15) → ED(0.25)
2. Combine C(0.15) + B(0.20) → CB(0.35)
3. Combine ED(0.25) + CB(0.35) → EDCB(0.60) [actually: combine ED(0.25) + A(0.40) → EDA(0.65), then with CB... let me redo properly]

Let me trace this carefully:

1. Sort: E(0.10), C(0.15), D(0.15), B(0.20), A(0.40)
2. Combine E+C → EC(0.25). New list: D(0.15), B(0.20), EC(0.25), A(0.40)
3. Combine D+B → DB(0.35). New list: EC(0.25), DB(0.35), A(0.40)
4. Combine EC+DB → ECDB(0.60). New list: A(0.40), ECDB(0.60)
5. Combine A+ECDB → Root(1.00)

Resulting codes:

• A → 0 (1 bit)
• B → 111 (3 bits)
• C → 101 (3 bits)
• D → 110 (3 bits)
• E → 100 (3 bits)

Average code length: L = 0.40×1 + 0.20×3 + 0.15×3 + 0.15×3 + 0.10×3 = 0.40 + 0.60 + 0.45 + 0.45 + 0.30 = 2.20 bits/symbol

Entropy: H = -(0.40×log₂0.40 + 0.20×log₂0.20 + 0.15×log₂0.15 + 0.15×log₂0.15 + 0.10×log₂0.10) = 2.12 bits/symbol

Efficiency: η = H/L = 2.12/2.20 = 96.4% — very close to optimal!

Why Huffman Codes Are Optimal

Among all prefix-free binary codes, the Huffman code has the minimum average codeword length. This is provable mathematically:

H(X) ≤ L(Huffman) < H(X) + 1

The average code length lies between the entropy and entropy plus 1 bit per symbol. For practical alphabets with many symbols, the overhead approaches zero.

Optimality conditions satisfied:

1. More probable symbols always have shorter (or equal length) codewords
2. The two least probable symbols have the same code length and differ only in the last bit
3. No other prefix code achieves a shorter average length

The Prefix Property

A prefix code (also called instantaneously decodable code) means:

• No codeword is the beginning of any other codeword
• Can decode bit-by-bit without looking ahead
• No separators needed between codewords

Example of NON-prefix code (broken!): A=0, B=01, C=1

• If you receive "01" — is it "AB" (0,1) or "B" (01)? Ambiguous!

Huffman codes are always prefix-free by construction (leaf nodes of a binary tree never share paths).

Decoding Process

Decoding uses the Huffman tree in reverse:

1. Start at root of the tree
2. Read one bit at a time
3. Go left on 0, right on 1
4. When you reach a leaf → output that symbol, return to root
5. Continue until all bits processed

This process is O(1) per bit in hardware (just walking a state machine) and extremely fast.

Limitations of Huffman Coding

1. Integer bit constraint: Codewords must be whole numbers of bits. If optimal is 1.3 bits for a symbol, Huffman rounds to 1 or 2 bits. This is why L can exceed H by up to 1 bit.

Solution: Group symbols into blocks (pairs, triples) before coding. Blocking of n symbols reduces excess to less than 1/n bit per symbol. Arithmetic coding eliminates this problem entirely.

2. Requires known probabilities: Must know (or estimate) symbol frequencies before building the code. Dynamic/adaptive Huffman updates the tree as data arrives.

3. Symbol-by-symbol coding: Cannot exploit inter-symbol correlations. Must use Markov models or pre-process (e.g., run-length encoding, BWT) for correlated sources.

Huffman vs. Arithmetic Coding

Applications

Huffman coding appears in many compression standards:

• DEFLATE (ZIP, gzip, PNG): Huffman + LZ77 dictionary compression
• JPEG: Huffman codes DCT coefficients (default mode)
• MP3/AAC: Huffman codes quantized spectral values
• HTTP/2 (HPACK): Huffman for header field compression
• Fax machines (Group 3): Modified Huffman for run-length coded scan lines

Adaptive Huffman Coding

When symbol probabilities are unknown in advance, adaptive (dynamic) Huffman coding:

1. Starts with empty or uniform tree
2. After each symbol: update frequency count, rebuild tree
3. Both encoder and decoder maintain identical trees
4. Eliminates need to transmit probability table

Algorithms: FGK (Faller-Gallager-Knuth) and Vitter's algorithm.

Key Takeaways

1. Huffman coding assigns shorter binary codes to more frequent symbols, achieving minimum average code length among all prefix codes.
2. The algorithm greedily combines the two least probable symbols at each step, building an optimal binary tree bottom-up.
3. Average code length satisfies H ≤ L < H + 1, with efficiency typically above 95% for practical sources.
4. Prefix-free property enables instantaneous bit-by-bit decoding without separators or look-ahead.
5. Huffman is foundational in JPEG, ZIP, MP3, and HTTP/2 — one of the most widely-deployed algorithms in computing.
6. For truly optimal (fractional-bit) coding, arithmetic coding surpasses Huffman, but at higher computational cost.