Huffman code for seven-symbol source

Huffman procedure: arrange symbols in decreasing probability; combine the two lowest probabilities into one; place the sum in the list as high as possible; repeat until one probability (1.0) is left. Then trace back, giving 0 to the upper branch and 1 to the lower branch at each combination.

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

Entropy:

$$\begin{aligned} H &= \sum p_i\log_2\frac{1}{p_i} = 2(0.25)(2) + 3(0.125)(3) + 2(0.0625)(4) \\ &= 1.0 + 1.125 + 0.5 = 2.625\ \text{bits/symbol} \end{aligned}$$

Average code length:

$$\bar L = 2(0.25)(2) + 3(0.125)(3) + 2(0.0625)(4) = 2.625\ \text{bits/symbol}$$

Efficiency:

$$\eta = \frac{H}{\bar L} = \frac{2.625}{2.625} = 100\%$$

The efficiency is 100 % because every probability is a negative power of 2 ($2^{-2}, 2^{-3}, 2^{-4}$), so each code length equals $\log_2(1/p_i)$ exactly. A fixed-length code would need 3 bits/symbol (efficiency $2.625/3 = 87.5\%$).

Answer: S0, S1 get 2-bit codes, S2, S3, S4 get 3-bit codes and S5, S6 get 4-bit codes (as in the table); $\bar L = H = 2.625$ bits/symbol, efficiency 100 %.