Importance of source coding; Shannon-Fano vs BCD (four symbols)

Importance of source coding

Source coding removes redundancy from the source output so that each symbol is represented by as few bits as possible on average:

• It reduces the bit rate, so less bandwidth, power and storage are needed.
• It uses the symbol probabilities: likely symbols get short code words.
• The best possible average length is the entropy $H$; efficiency $\eta = H/\bar L$ shows how close a code comes.

Shannon–Fano code

$P = \{0.125, 0.125, 0.25, 0.5\}$ for $x_1, x_2, x_3, x_4$. In decreasing order: $x_4$ 0.5, $x_3$ 0.25, $x_1$ 0.125, $x_2$ 0.125. Splits: {0.5} | {0.25, 0.125, 0.125}; {0.25} | {0.125, 0.125}; {0.125} | {0.125}.

Entropy:

$$\begin{aligned} H &= 0.5(1) + 0.25(2) + 2(0.125)(3) = 1.75\ \text{bits/symbol} \\ \bar L_{SF} &= 0.5(1) + 0.25(2) + 0.125(3) + 0.125(3) = 1.75\ \text{bits/symbol} \\ \eta_{SF} &= \frac{1.75}{1.75} = 100\% \end{aligned}$$

Comparison with BCD

In BCD each symbol is sent as a 4-bit binary-coded-decimal word (0000, 0001, 0010, 0011), so $\bar L = 4$:

$$\eta_{BCD} = \frac{1.75}{4} = 43.75\%$$

Shannon–Fano reaches 100 % because all probabilities are powers of $\frac12$. (If "BCD" is read as the plain 2-bit binary code, $\eta = 1.75/2 = 87.5\%$; Shannon–Fano is still better.)