Huffman code for p = 0.5, 0.25, 0.125, 0.125

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. x3(0.125) + x4(0.125) = 0.25
2. x2(0.25) + N1(0.25) = 0.5
3. x1(0.5) + N2(0.5) = 1

Code table

Entropy, average length, efficiency

• H = −Σ p log₂ p = 1.7500 bits/symbol
• L = Σ p·l = 1.7500 bits/symbol
• Efficiency η = H/L = 1.7500/1.7500 = 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.7500 bits/symbol, η = 100.00 %

The probabilities are negative powers of two, so every code length equals −log₂ p, and the code is 100 % efficient (L = H).