Skip to main content

Huffman code for eight symbols (1/2 ... 1/128)

Short answer

Huffman codes: X1=0, X2=10, X3=110, X4=1110, X5=11110, X6=111110, X7=1111110, X8=1111111. Average length L = 1.9844 bits/symbol, efficiency 100%.

A message source generates 8 symbols with the following probabilities: P(X1)=1/2, P(X2)=1/4, P(X3)=1/8, P(X4)=1/16, P(X5)=1/32, P(X6)=1/64, P(X7)=1/128 and P(X8)=1/128. Encode the message using Huffman 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.

The probabilities 1/2, 1/4, 1/8, 1/16, 1/32, 1/64, 1/128, 1/128 sum to 1.

Merging steps

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

1. X7(0.007812) + X8(0.007812) = 0.01562
2. X6(0.01562) + N1(0.01562) = 0.03125
3. X5(0.03125) + N2(0.03125) = 0.0625
4. X4(0.0625) + N3(0.0625) = 0.125
5. X3(0.125) + N4(0.125) = 0.25
6. X2(0.25) + N5(0.25) = 0.5
7. X1(0.5) + N6(0.5) = 1

Code table

SymbolpCodeLength lp·l
X11/2010.5000
X21/41020.5000
X31/811030.3750
X41/16111040.2500
X51/321111050.1562
X61/6411111060.0938
X71/128111111070.0547
X81/128111111170.0547

Entropy, average length, efficiency

  • H = −Σ p log₂ p = 1.9844 bits/symbol
  • L = Σ p·l = 1.9844 bits/symbol
  • Efficiency η = H/L = 1.9844/1.9844 = 100.00 % (redundancy = 0.00 %)

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

Answer: L = 1.9844 bits/symbol, η = 100.00 %

✓ Answer checked by Claude Sonnet 5.5

Related questions

All Data Communication chapter 8 questions →