Source coding aim; Huffman "Kun Mandir Ma Janchhau Yatri"

Aim of source coding

Source coding represents the output of an information source with as few bits as possible, while still allowing the receiver to recover it exactly (lossless coding) or acceptably (lossy coding). Its aims are:

• Remove redundancy: give short code words to frequent symbols and long ones to rare symbols, so the average code length $\bar L$ approaches the entropy $H$ (Shannon's source coding theorem: $\bar L \ge H$).
• Raise efficiency $\eta = H/\bar L$ towards 100%.
• Lower the bit rate, which saves bandwidth, storage and transmission power.
• Produce a uniquely decodable (prefix) code so the receiver can decode it without separators.

Examples are Huffman, Shannon–Fano and LZW coding, as well as speech and image compression.

Huffman coding of "Kun Mandir Ma Janchhau Yatri"

Assumptions: case is ignored, and the space is counted as a symbol. The message has 28 symbols and 14 distinct symbols.

Huffman procedure: list the symbols by probability. Repeatedly combine the two least probable entries into one node whose weight is their sum, until only one node is left. In each merge, the first group listed gets bit 0 and the second group gets bit 1. Each symbol's code word is read from the root down to that symbol.

Merge steps:

1. {d} (1) + {c} (1) → 2
2. {k} (1) + {j} (1) → 2
3. {y} (1) + {t} (1) → 2
4. {i} (2) + {h} (2) → 4
5. {r} (2) + {m} (2) → 4
6. {d, c} (2) + {u} (2) → 4
7. {y, t} (2) + {k, j} (2) → 4
8. {space} (4) + {n} (3) → 7
9. {r, m} (4) + {i, h} (4) → 8
10. {y, t, k, j} (4) + {d, c, u} (4) → 8
11. {space, n} (7) + {a} (5) → 12
12. {y, t, k, j, d, c, u} (8) + {r, m, i, h} (8) → 16
13. {y, t, k, j, d, c, u, r, m, i, h} (16) + {space, n, a} (12) → 28

Average code length:

$$\bar L = \sum p_i l_i = \frac{101}{28} = 3.6071\ \text{bits/symbol}$$

Here the numerator is the total number of bits in the encoded message: $5(2) + 4(3) + 3(3) + 2(4) + 2(4) + 2(4) + 2(4) + 2(4) + 1(5) + 1(5) + 1(5) + 1(5) + 1(5) + 1(5) = 101$ bits.

Entropy:

$$H = -\sum p_i \log_2 p_i = 3.5801\ \text{bits/symbol}$$

Efficiency:

$$\eta = \frac{H}{\bar L} = \frac{3.5801}{3.6071} = 0.9925 = 99.25\%$$

Redundancy $= 1 - \eta = 0.75\%$.

A fixed-length code for 14 symbols needs $\lceil \log_2 14 \rceil = 4$ bits/symbol ($\eta = 89.50\%$). Huffman saves 9.82% of the bits.

Answer: $\bar L = 3.607$ bits/symbol, $H = 3.580$ bits/symbol, efficiency η ≈ 99.25%. The message needs 101 bits instead of 112 bits with a 4-bit fixed code.