Skip to main content

Huffman code for five symbols (0.2, 0.35, ...)

Short answer

Huffman coding yields average length 2.2500 bits/symbol and efficiency 97.85%.

Consider a five symbol source with probability assignment as P(X1)=0.2, P(X2)=0.35, P(X3)=0.1, P(X4)=0.2, P(X5)=0.15. By using Huffman algorithm, find the source code for these symbols and determine efficiency of the code.

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.

Probabilities: P(X1) = 0.2, P(X2) = 0.35, P(X3) = 0.1, P(X4) = 0.2, P(X5) = 0.15 (sum = 1).

Merging steps

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

1. X3(0.1) + X5(0.15) = 0.25
2. X1(0.2) + X4(0.2) = 0.4
3. N1(0.25) + X2(0.35) = 0.6
4. N2(0.4) + N3(0.6) = 1

Code table

SymbolpCodeLength lp·l
X20.351120.7000
X10.20020.4000
X40.20120.4000
X50.1510130.4500
X30.110030.3000

Entropy, average length, efficiency

  • H = −Σ p log₂ p = 2.2016 bits/symbol
  • L = Σ p·l = 2.2500 bits/symbol
  • Efficiency η = H/L = 2.2016/2.2500 = 97.85 % (redundancy = 2.15 %)

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

Answer: L = 2.2500 bits/symbol, η = 97.85 %

✓ Answer checked by Claude Sonnet 5.5

Related questions

All Data Communication chapter 8 questions →