Huffman and Shannon-Fano coding of A0–A4

Entropy of the source $\{0.4, 0.3, 0.15, 0.1, 0.05\}$:

$$H = 2.0087\ \text{bits/symbol}$$

Huffman encoder

Combine the two lowest probabilities at each stage, place the sum as high as possible, then read the code from the final stage back to each symbol (0 = upper, 1 = lower).

Reduction (sum of two lowest moved up as high as possible):

$$\begin{aligned} \bar L_H &= 0.4(1) + 0.3(2) + 0.15(3) + 0.1(4) + 0.05(4) \\ &= 0.4 + 0.6 + 0.45 + 0.4 + 0.2 = 2.05\ \text{bits/symbol} \\ \eta_H &= \frac{2.0087}{2.05} = 97.99\% \end{aligned}$$

Shannon–Fano encoder

Divide the ordered list into two groups of nearly equal probability, 0 to the upper and 1 to the lower group, and repeat:

• {A0} = 0.4 | {A1, A2, A3, A4} = 0.6
• {A1} = 0.3 | {A2, A3, A4} = 0.3
• {A2} = 0.15 | {A3, A4} = 0.15
• {A3} | {A4}

$$\begin{aligned} \bar L_{SF} &= 0.4(1)+0.3(2)+0.15(3)+0.1(4)+0.05(4) = 2.05\ \text{bits/symbol} \\ \eta_{SF} &= \frac{2.0087}{2.05} = 97.99\% \end{aligned}$$

Comparison

For this source both encoders give the same code lengths (1, 2, 3, 4, 4), so the efficiencies are equal at 97.99 %. In general Huffman's efficiency is equal to or better than Shannon–Fano's. A fixed 3-bit code would give only 66.96 %.