Consider a discrete memoryless source with alphabet {s₀, s₁, s₂} and statistics {0·7, 0·15, 0·15} for its output.
(i) Apply the Huffman algorithm to this source. Hence, show that the average code-word length of the Huffman code equals 1·3 bits/symbol.
(ii) Let the source be extended to order two. Apply the Huffman algorithm to the resulting extended source and show that the average code-word length of the new code equals 1·1975 bits/symbol.
(iii) Compare the average code-word length calculated in part (ii) with the entropy of the original source.
20 marks · directive: Show and compare
The core of a good answer
Huffman coding gives code lengths 1, 2, 2 and L̄ = 1.3 bits/symbol; for the second order extension it gives 2.395 bits per pair, i.e. 1.1975 bits/symbol, which is closer to the source entropy H = 1.1813 bits/symbol (efficiency rises from 90.9 % to 98.6 %).
An outline written by upsc.help, not an official UPSC answer; every fact checked by a separate review. How we work
What the question asks
The question checks the Huffman procedure (repeatedly combining the two least probable symbols), computing average length, and the source coding theorem: coding the n th extension makes L̄/n approach the entropy H(S).
Answer outline
Introduction
Source probabilities: P(s₀) = 0.7, P(s₁) = 0.15, P(s₂) = 0.15. For the second order extension there are 9 pairs with probabilities equal to products.
Step 1: Huffman code for the original source, part (i)
- Combine s₁ and s₂: 0.15 + 0.15 = 0.30
- Combine 0.7 and 0.30 = 1.0
- Codes: s₀ → 0, s₁ → 10, s₂ → 11
- L̄ = 0.7 × 1 + 0.15 × 2 + 0.15 × 2 = 1.3 bits/symbol
Step 2: Second order extension probabilities
- s₀s₀: 0.49
- s₀s₁, s₀s₂, s₁s₀, s₂s₀: 0.105 each
- s₁s₁, s₁s₂, s₂s₁, s₂s₂: 0.0225 each
- Sum = 0.49 + 4(0.105) + 4(0.0225) = 1
Step 3: Huffman reductions for the extension
- 0.0225 + 0.0225 = 0.045 (twice)
- 0.045 + 0.045 = 0.09
- 0.09 + 0.105 = 0.195
- 0.105 + 0.105 = 0.21
- 0.105 + 0.195 = 0.30
- 0.21 + 0.30 = 0.51
- 0.49 + 0.51 = 1.00
Step 4: Code lengths for the extension, part (ii)
- s₀s₀: 1 bit (e.g. 0)
- three of the 0.105 pairs: 3 bits each (e.g. 100, 101, 110)
- the fourth 0.105 pair: 4 bits (e.g. 1110)
- each 0.0225 pair: 6 bits (e.g. 111100, 111101, 111110, 111111)
- L̄₂ = 0.49 × 1 + 3 × 0.105 × 3 + 0.105 × 4 + 4 × 0.0225 × 6
- L̄₂ = 0.49 + 0.945 + 0.42 + 0.54 = 2.395 bits per pair
- Per source symbol: 2.395/2 = 1.1975 bits/symbol
Step 5: Entropy of the original source, part (iii)
- H = −0.7 log₂ 0.7 − 2 × 0.15 log₂ 0.15
- H = 0.3602 + 2 × 0.4105 ≈ 1.1813 bits/symbol
Step 6: Comparison
- H ≤ L̄₂/2 < H + 1/2: 1.1813 ≤ 1.1975 < 1.6813, as the source coding theorem requires
- Redundancy falls from 1.3 − 1.1813 = 0.119 to 1.1975 − 1.1813 = 0.016 bits/symbol
- Coding efficiency H/L̄ rises from 90.9 % to 98.6 %
Conclusion
Results: 1.3 bits/symbol for the plain Huffman code, 1.1975 bits/symbol for the second order extension, against an entropy of 1.1813 bits/symbol. Extending the source brings the average length closer to the entropy, as Shannon's source coding theorem predicts.
Examples and data to cite
- Huffman's algorithm was published by David A. Huffman in 1952.
- Prefix codes of this kind serve as the back end of the DEFLATE algorithm (PKZIP) and of multimedia codecs such as JPEG and MP3.
- Grouping symbols into blocks (source extension) improves compression; as the block size grows without limit, Huffman coding approaches the entropy limit.
Facts to remember
- Huffman coding produces an optimal prefix code: no other prefix code has a smaller average length for the given probabilities.
- Entropy H(S) = −Σ pₖ log₂ pₖ bits/symbol.
- For the n th extension, H(Sⁿ) = nH(S) and nH(S) ≤ L̄ₙ < nH(S) + 1, so L̄ₙ/n → H(S).
- Code efficiency η = H(S)/L̄.
- Numbers recomputed in Python with a Huffman implementation: L̄₁ = 1.3, L̄₂ = 2.395, H = 1.18129.