Huffman coding of "Engineer Ko Betha Arulai Ke Thaha"

Assumptions: upper and lower case are treated as the same letter, and the space is counted as a symbol because it must also be sent. The message "engineer ko betha arulai ke thaha" has 33 symbols, with 14 distinct symbols.

Huffman encoding

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 (weights are counts out of 33):

1. {g} (1) + {b} (1) → 2
2. {o} (1) + {l} (1) → 2
3. {i} (2) + {u} (1) → 3
4. {n} (2) + {k} (2) → 4
5. {t} (2) + {r} (2) → 4
6. {o, l} (2) + {g, b} (2) → 4
7. {i, u} (3) + {h} (3) → 6
8. {t, r} (4) + {n, k} (4) → 8
9. {space} (5) + {o, l, g, b} (4) → 9
10. {e} (5) + {a} (5) → 10
11. {t, r, n, k} (8) + {i, u, h} (6) → 14
12. {e, a} (10) + {space, o, l, g, b} (9) → 19
13. {e, a, space, o, l, g, b} (19) + {t, r, n, k, i, u, h} (14) → 33

Average code length:

$$\bar L = \sum p_i l_i = \frac{118}{33} = 3.5758\ \text{bits/symbol}$$

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

Entropy:

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

Efficiency:

$$\eta = \frac{H}{\bar L} = \frac{3.5419}{3.5758} = 0.9905 = 99.05\%$$

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

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

Answer: average length = 3.576 bits/symbol, entropy = 3.542 bits/symbol, transmission efficiency η ≈ 99.05%.

Codeword for the received message "Engineer Ko Betha Ke Ke"

Each character (including the 4 spaces) is replaced by its code from the table above:

Full codeword (83 bits for 23 characters):

000 1010 01110 1100 1010 000
000 1001 010 1011 01100 010
01111 000 1000 111 001 010
1011 000 010 1011 000

The Huffman code is a prefix code, so the receiver can decode this bit stream without separators.