Huffman code for symbols A0 to A4

Note on the data: the printed probabilities {0.4, 0.3, 0.15, 0.1, 0.5} add up to 1.45, which is impossible. The last value is evidently a misprint for 0.05, since 0.4 + 0.3 + 0.15 + 0.1 + 0.05 = 1. The answer below uses p(A4) = 0.05.

The most efficient symbol-by-symbol code is the 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.

Merging steps

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

1. A4(0.05) + A3(0.1) = 0.15
2. A2(0.15) + N1(0.15) = 0.3
3. A1(0.3) + N2(0.3) = 0.6
4. A0(0.4) + N3(0.6) = 1

Code table

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 %