Huffman code for p = 0.6, 0.2, 0.1, 0.05, 0.05

Entropy is the average information content per source symbol: H = −Σ pᵢ log₂ pᵢ bits/symbol. It measures the uncertainty (randomness) of the source, and is the minimum average number of bits per symbol needed to code it without loss.

Probabilities: p(x1) = 0.6, p(x2) = 0.2, p(x3) = 0.1, p(x4) = 0.05, p(x5) = 0.05 (sum = 1).

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. x4(0.05) + x5(0.05) = 0.1
2. x3(0.1) + N1(0.1) = 0.2
3. x2(0.2) + N2(0.2) = 0.4
4. N3(0.4) + x1(0.6) = 1

Code table

Entropy, average length, efficiency

• H = −Σ p log₂ p = 1.6710 bits/symbol
• L = Σ p·l = 1.7000 bits/symbol
• Efficiency η = H/L = 1.6710/1.7000 = 98.29 % (redundancy = 1.71 %)

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

Answer: L = 1.7000 bits/symbol, η = 98.29 %