Past exam question: 2076 Chaitra, Q8
Open in the Padhaiko appQuestion
Encode "Phool ko aankhama phoolai sansara" using Huffman encoder and find the transmission efficiency.
Solution
Frequency Analysis of the Message: Given string: "Phool ko aankhama phoolai sansara" (case-sensitive, including spaces). Total length: characters across 13 unique symbols:
'a': 8 ()'o': 5 ()' '(space): 4 ()'h': 3 ()'k': 2 ()'l': 2 ()'n': 2 ()'s': 2 ()'P': 1 ()'i': 1 ()'m': 1 ()'p': 1 ()'r': 1 ()
Check total: .
Huffman Tree Construction and Codeword Table: Iteratively merging the two lowest-frequency nodes (0 to left child, 1 to right child):
| Symbol | Frequency | Probability | Codeword | Length | |
|---|---|---|---|---|---|
'a' | 8 | 01 | 2 | 16 | |
'o' | 5 | 110 | 3 | 15 | |
' ' | 4 | 001 | 3 | 12 | |
'h' | 3 | 1111 | 4 | 12 | |
'k' | 2 | 0001 | 4 | 8 | |
'l' | 2 | 1000 | 4 | 8 | |
'n' | 2 | 1001 | 4 | 8 | |
's' | 2 | 1010 | 4 | 8 | |
'r' | 1 | 0000 | 4 | 4 | |
'P' | 1 | 10110 | 5 | 5 | |
'i' | 1 | 10111 | 5 | 5 | |
'm' | 1 | 11100 | 5 | 5 | |
'p' | 1 | 11101 | 5 | 5 | |
| Total | 33 | 1 | — | — | 111 |
Average Length, Entropy, and Transmission Efficiency:
- Average Codeword Length ():
- Source Entropy ():
- Transmission Efficiency ():
Answer:
For "Phool ko aankhama phoolai sansara" ( characters, 13 unique symbols):
- Huffman codewords assign 2 bits to
'a'(01), 3 bits to'o'(110) and' '(001), 4 bits to'h','k','l','n','s','r', and 5 bits to'P','i','m','p'(total encoded length ). - Average codeword length: .
- Source entropy: .
- Transmission efficiency: .