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

Importance of source coding

Source coding is the efficient representation of the source output in bits, by removing redundancy, so that the average number of bits per symbol $\bar L$ is as close as possible to the entropy $H$.

• Reduces bit rate: fewer bits per symbol means a lower transmission rate for the same information.
• Saves bandwidth and power: a lower bit rate needs less channel bandwidth and less transmitted energy; storage space is also saved (ZIP, MP3, JPEG).
• Uses symbol statistics: frequent symbols get short code words and rare symbols long code words (variable-length coding), as in Morse code.
• Approaches the entropy limit: Shannon's source coding theorem says $\bar L \ge H$; good codes (Huffman, Shannon–Fano) reach close to $H$.
• Unique decodability: prefix codes (no code word is a prefix of another) can be decoded without separators.
• Leaves room for channel coding: the bits saved can be used for error-control redundancy.

Numerical

The seven listed probabilities add to only 0.80, so a value is missing from the printed question. The same source appears in another IOE question as $P = \{0.25, 0.2, 0.2, 0.15, 0.08, 0.07, 0.03, 0.02\}$ (a second 0.2 added), which adds to 1, so this set is used below. A fixed-length code needs 3 bits whether there are 7 or 8 symbols.

Entropy:

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

(a) Shannon–Fano coding (first split {0.25, 0.2} = 0.45 vs 0.55):

$$\begin{aligned} \bar L &= 0.25(2)+0.2(2)+0.2(2)+0.15(3)+0.08(4)+0.07(5)+0.03(6)+0.02(6) \\ &= 0.5+0.4+0.4+0.45+0.32+0.35+0.18+0.12 = 2.72\ \text{bits/symbol} \\ \eta_{SF} &= \frac{2.6640}{2.72} = 97.94\%, \qquad \gamma_{SF} = 1-\eta = 2.06\% \end{aligned}$$

(b) Fixed-length coding: $\bar L = \lceil\log_2 8\rceil = 3$ bits/symbol.

$$\eta_{FL} = \frac{2.6640}{3} = 88.80\%, \qquad \gamma_{FL} = 11.20\%$$

Comparison

Shannon–Fano coding saves $3 - 2.72 = 0.28$ bits/symbol (about 9.3 %) over fixed-length coding, because it gives short code words to the frequent symbols. Fixed-length coding is simpler and needs no code table, but wastes bits when probabilities are unequal.