Importance of source coding; fixed vs Shannon-Fano (five symbols)

Importance of source coding

Source coding converts the source output into a binary sequence using as few bits per symbol as possible, by removing redundancy. Its importance:

1. Lower bit rate: the average code length $\bar L$ approaches the entropy $H$, so fewer bits are sent for the same information.
2. Bandwidth saving: a lower bit rate needs less channel bandwidth, so more users or services fit in the same band.
3. Power and energy saving: fewer bits means less transmitted energy, important in mobile and satellite links.
4. Storage saving: compressed files (ZIP, JPEG, MP3) need less memory.
5. Exploits statistics: variable-length codes give short words to frequent symbols and long words to rare ones.
6. Theoretical guarantee: Shannon's source coding theorem, $H \le \bar L < H + 1$, shows how close a code can come to the limit; efficiency $\eta = H/\bar L$ measures the code.
7. Uniquely decodable prefix codes allow decoding without separators.
8. Supports channel coding: removing useless redundancy leaves room to add useful redundancy for error control.

Numerical: $P = \{0.3, 0.25, 0.2, 0.15, 0.1\}$

Entropy:

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

(a) Fixed-length coding: 5 symbols need $\lceil\log_2 5\rceil = 3$ bits each (000 to 100).

$$\eta_{FL} = \frac{H}{\bar L} = \frac{2.2282}{3} = 74.27\%$$

(b) Shannon–Fano coding: first split {0.3, 0.25} = 0.55 vs {0.2, 0.15, 0.1} = 0.45; then {0.2} vs {0.15, 0.1}.

$$\begin{aligned} \bar L_{SF} &= 0.3(2)+0.25(2)+0.2(2)+0.15(3)+0.1(3) = 2.25\ \text{bits/symbol} \\ \eta_{SF} &= \frac{2.2282}{2.25} = 99.03\% \end{aligned}$$

Comparison

Shannon–Fano uses 0.75 bit/symbol less (25 % fewer bits) and is almost at the entropy limit, while fixed-length coding wastes about a quarter of the bits.