Pratidin
2026 · Electrical Engineering Optional Paper II · 20 marksMainsQuestion 6b

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

Answer

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)

Step 2: Second order extension probabilities

Step 3: Huffman reductions for the extension

Step 4: Code lengths for the extension, part (ii)

Step 5: Entropy of the original source, part (iii)

Step 6: Comparison

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

Facts

Facts to remember

Sources used for the explanation

Write a timed answer in the app