Past exam question: 2072 Chaitra, Q10
Open in the Padhaiko appA message source generates 8 symbols with the following probabilities:
Encode the message using Huffman code.
Solution
Initial Probabilities and Dyadic Property: Notice that all probabilities are powers of two ( for , and ). Check the sum of probabilities:
Huffman Tree Construction: Following Huffman's algorithm, repeatedly combine the two lowest probability nodes:
- Iteration 1: Combine and to form node with probability:
- Iteration 2: Combine and to form node with probability:
- Iteration 3: Combine and to form node with probability:
- Iteration 4: Combine and to form node with probability:
- Iteration 5: Combine and to form node with probability:
- Iteration 6: Combine and to form node with probability:
- Iteration 7: Combine and to form root node with probability .
Assign 0 to the upper branch and 1 to the lower branch at each internal node.
Codeword Assignment Table:
| Symbol | Probability | Assigned Binary Codeword | Code Length |
|---|---|---|---|
0 | 1 | ||
10 | 2 | ||
110 | 3 | ||
1110 | 4 | ||
11110 | 5 | ||
111110 | 6 | ||
1111110 | 7 | ||
1111111 | 7 |
Performance and Efficiency Evaluation: Calculate source entropy :
Calculate average codeword length :
Coding efficiency :
Because the symbol probabilities are exact negative powers of 2, the Huffman code achieves theoretical 100% efficiency.
Huffman codewords for the 8 dyadic symbols: : 0, : 10, : 110, : 1110, : 11110, : 111110, : 1111110, : 1111111. Average length , giving 100% coding efficiency.