Skip to main content

Huffman code for symbols A to E (0.4, 0.3, ...)

Short answer

Entropy H = -∑ p log2 p is the average information per symbol, measuring source uncertainty. Huffman coding yields A=0, B=10, C=110, D=1111, E=1110. Average code length L = 2.0500 bits/symbol, entropy H = 2.0087 bits/symbol.

What do you mean by entropy? The five symbols from a source and their probabilities are shown in the table below. By using the Huffman algorithm, find the source code for these symbols and determine the average code-word length and the entropy of the source.

SymbolProbability
A0.4
B0.3
C0.15
D0.1
E0.05

Entropy is the average information per source symbol, H = −Σ pᵢ log₂ pᵢ bits/symbol. It measures the uncertainty of the source and the minimum average bits per symbol needed to code it.

Huffman algorithm

  1. Arrange the symbols in decreasing order of probability.
  2. Combine the two least probable symbols into one with the sum of their probabilities.
  3. Repeat (re-sorting) until only one symbol of probability 1 remains.
  4. Assign 0 and 1 to the two branches at every merge.
  5. The code of a symbol is the sequence of bits read from the root back to that symbol.

Merging steps

At every step the two smallest probabilities are combined (N1, N2, ... are the new nodes):

1. E(0.05) + D(0.1) = 0.15
2. C(0.15) + N1(0.15) = 0.3
3. B(0.3) + N2(0.3) = 0.6
4. A(0.4) + N3(0.6) = 1

Code table

SymbolpCodeLength lp·l
A0.4010.4000
B0.31020.6000
C0.1511030.4500
D0.1111140.4000
E0.05111040.2000

Entropy, average length, efficiency

  • H = −Σ p log₂ p = 2.0087 bits/symbol
  • L = Σ p·l = 2.0500 bits/symbol
  • Efficiency η = H/L = 2.0087/2.0500 = 97.99 % (redundancy = 2.01 %)

Huffman codes are not unique when probabilities tie, but L and η are the same for every valid choice.

Answer: L = 2.0500 bits/symbol, η = 97.99 %

✓ Answer checked by Claude Sonnet 5.5

Related questions

All Data Communication chapter 8 questions →