Importance of source coding; Huffman for eight symbols at 1000 symbols/s

Importance of source coding

Source coding represents the source output with the minimum average number of bits by removing redundancy:

• It brings the average code length $\bar L$ close to the entropy $H$ (Shannon's source coding theorem: $\bar L \ge H$).
• It lowers the bit rate, so less bandwidth, power and storage are needed.
• Variable-length prefix codes (Huffman, Shannon–Fano) give short words to likely symbols and remain uniquely decodable.

Huffman code

$P = \{0.25, 0.20, 0.2, 0.15, 0.08, 0.07, 0.03, 0.02\}$ for $x_1 \dots x_8$ (sum = 1).

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

Entropy:

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

Average length and efficiency:

$$\begin{aligned} \bar L &= \sum p_i l_i = 2.72\ \text{bits/symbol} \\ \eta &= \frac{H}{\bar L} = \frac{2.6640}{2.72} = 97.94\% \end{aligned}$$

(A fixed 3-bit code would give $2.664/3 = 88.80\%$.)

Output bit rate

$$R_b = r\bar L = 1000 \times 2.72 = 2720\ \text{bits/s}$$

(The information rate is $rH = 2664$ bits/s.)

Answer: coding efficiency = 97.94 %; output bit rate = 2720 bits/s.