Huffman Coding

Huffman coding is a variable-length, prefix-free lossless compression algorithm that assigns shorter codewords to more probable symbols and longer codewords to less probable ones. It is provably optimal among all single-symbol prefix-free codes, meaning no other such code can achieve a smaller average codeword length. Huffman coding is directly derived from Shannon's source coding theorem and is a core topic in GATE Digital Communications.

Core Concept Explanation

A prefix-free code (also called a prefix code or instantaneous code) is one in which no codeword is a prefix of another. This property allows a decoder to identify the boundary of each codeword in a bitstream without any delimiter, enabling instantaneous decoding. Huffman coding always produces a prefix-free code. This is guaranteed by the tree structure: codewords correspond to leaf nodes, and since no leaf is an ancestor of another leaf, no codeword can be a prefix of another.

The algorithm works by using a greedy merging strategy on a priority queue of symbols ordered by probability. At each step, the two nodes with the lowest probabilities are merged into a single parent node whose probability is their sum. A 0 is assigned to one branch and 1 to the other (the choice is arbitrary and can be consistently left-low or left-high). This process continues until a single root node remains, at which point the complete binary tree defines the codeword for each symbol by reading the branch labels from root to leaf.

The result is a variable-length code where symbols with high probability receive short codewords and symbols with low probability receive long codewords. Since high-probability symbols appear more often in the source output, the average number of bits transmitted per symbol is minimized. The Huffman code is provably optimal in the sense that no other prefix-free code for the same source achieves a lower average codeword length.

Mathematical Expression

The average codeword length of a Huffman code is L = sum_{i=1}^{M} pi * li, where pi is the probability of symbol si and li is the length of its codeword. Shannon's theorem guarantees that the entropy H(S) <= L < H(S) + 1. Huffman coding achieves this bound tightly. The coding efficiency is eta = H(S) / L. When all probabilities are exact powers of 1/2 (dyadic), Huffman coding achieves L = H(S) exactly, giving 100% efficiency.

The Kraft inequality sum_{i} 2^{-li} <= 1 is satisfied with equality for any complete binary Huffman tree. This means the code is maximally efficient in its use of the binary tree structure. There is no unused codeword space in a complete Huffman tree, which corresponds to equality in the Kraft inequality.

Practical Understanding

Huffman coding is used in formats such as JPEG (for the coefficient coding stage), MP3, and the DEFLATE algorithm inside ZIP and PNG files. However, in these practical implementations Huffman coding is often combined with other techniques because the source statistics may not be known in advance. In adaptive Huffman coding, the tree is updated as symbols are observed, allowing the code to adapt to non-stationary sources.

One practical limitation of Huffman coding is that it operates on individual symbols (or fixed-length symbol blocks), so if the source has a large alphabet or if symbols are not independent, the algorithm must be extended to blocks. Arithmetic coding overcomes this by mapping entire sequences to a single fraction, approaching entropy more closely without block size restrictions. Still, Huffman coding remains important because it is computationally simpler and hardware-friendly.

Given:
Symbols: {A, B, C, D, E}
Probabilities: p(A)=0.4, p(B)=0.2, p(C)=0.2, p(D)=0.1, p(E)=0.1

Why this formula applies:
Huffman algorithm greedily merges two lowest probability nodes to build optimal tree.
Average length L = sum pi * li confirms performance vs entropy.

Formula:
H(S) = -sum pi log2(pi)
L = sum pi * li

Huffman construction:
Step 1: Merge D(0.1) + E(0.1) = DE(0.2)
Step 2: Merge B(0.2) + C(0.2) = BC(0.4)  [or DE with B, order varies]
Actually merge DE(0.2) with B(0.2) = BDE(0.4)
Step 3: Merge A(0.4) + BC(0.4) = ABCDE(0.8) ... 

Standard result codewords:
A  = 0         (l=1)
B  = 10        (l=2)
C  = 110       (l=3)
D  = 1110      (l=4)
E  = 1111      (l=4)

Substitution:
L = 0.4*1 + 0.2*2 + 0.2*3 + 0.1*4 + 0.1*4
  = 0.4 + 0.4 + 0.6 + 0.4 + 0.4

Calculation:
L = 2.2 bits/symbol

H(S) = -(0.4*log2(0.4) + 0.2*log2(0.2) + 0.2*log2(0.2) + 0.1*log2(0.1) + 0.1*log2(0.1))
     = -(0.4*(-1.322) + 0.2*(-2.322) + 0.2*(-2.322) + 0.1*(-3.322) + 0.1*(-3.322))
     = -(-0.529 - 0.464 - 0.464 - 0.332 - 0.332) = 2.121 bits/symbol

Final Answer: L = 2.2 bits/symbol, H(S) = 2.121 bits/symbol
Efficiency eta = 2.121 / 2.2 = 96.4%  (satisfies H(S) <= L < H(S)+1)

Exam Tip: GATE frequently asks to verify that a given code is a valid Huffman code by checking both the Kraft inequality (sum 2^{-li} = 1 for complete tree) and that the average length satisfies H(S) <= L < H(S)+1. If probabilities are dyadic, the Huffman code achieves exactly H(S). Also note that Huffman codes are not unique since ties in probability can be broken in multiple valid ways.

Properties and Algorithm Steps

• Huffman coding is optimal among all single-symbol prefix-free codes. No other such code has a smaller average codeword length for the same source.
• The code is not unique: ties in probability at any merge step can be broken arbitrarily. All valid Huffman codes achieve the same average length L.
• The Kraft inequality is satisfied with equality: sum 2^{-li} = 1 for the complete binary Huffman tree.
• For dyadic probabilities, L = H(S) exactly. For non-dyadic probabilities, there is always some redundancy: L > H(S).
• Algorithm steps: (1) List all symbols with probabilities. (2) Sort by probability ascending. (3) Merge the two smallest into a combined node. (4) Repeat until one root remains. (5) Assign 0/1 to each branch. (6) Read codeword for each symbol from root to leaf.

Quick Revision

• Huffman coding assigns shorter codewords to more probable symbols. It is the optimal prefix-free code for a DMS.
• Algorithm: sort by probability, merge two lowest repeatedly, build binary tree, read codewords from root to leaf.
• Average length: L = sum pi * li. Bound: H(S) <= L < H(S) + 1.
• Coding efficiency: eta = H(S)/L. For dyadic probabilities, eta = 1 (100%).
• Kraft inequality: sum 2^{-li} = 1 for a complete binary Huffman tree.
• Huffman code is not unique when tie-breaking occurs, but all valid versions give the same average length.
• Exam trap: Do not assume the code with equal left/right branch labels is the only valid answer. Multiple Huffman trees are correct for a given source.