Past exam question: 2075 Ashwin, Q9
Open in the Padhaiko appThe source of information symbols {A0, A1, A2, A3 and A4} have corresponding probabilities {0.4, 0.3, 0.15, 0.1 and 0.5}. Encode the source symbols using most efficient coding scheme and calculate the corresponding efficiency.
Solution
Selection of the Most Efficient Coding Scheme: According to Shannon's source coding theorem, the Huffman Coding Algorithm produces the mathematically optimal (most efficient) prefix-free variable-length binary code for a discrete memoryless source with known symbol probabilities. Given symbol alphabet with sorted probabilities:
- :
- :
- :
- :
- :
(Note: The exam printed as a typo for , but probabilities must sum to ; ).
Huffman Tree Construction:
- Stage 1: Merge lowest two symbols:
- Remaining set:
- Stage 2: Merge lowest two:
- Remaining set:
- Stage 3: Merge lowest two:
- Remaining set:
- Stage 4: Merge final two:
Assigning bits (0 to top/higher probability, 1 to bottom/lower probability):
- From Root:
- branch
0(length ) - branch
1- branch
10(length ) - branch
11- branch
110(length ) - branch
111- branch
1110(length ) - branch
1111(length )
- branch
- branch
- branch
- branch
Codeword Table and Performance Evaluation:
| Symbol | Probability | Codeword | Length | ||
|---|---|---|---|---|---|
0 | 1 | ||||
10 | 2 | ||||
110 | 3 | ||||
1110 | 4 | ||||
1111 | 4 | ||||
| Total | 1.00 | — | — |
- Average Codeword Length ():
- Entropy ():
- Coding Efficiency ():
The most efficient coding scheme is the Huffman Code:
- ():
0(length 1) - ():
10(length 2) - ():
110(length 3) - ():
1110(length 4) - ():
1111(length 4)
Performance:
- Average Length:
- Entropy:
- Efficiency: