Past exam question: 2073 Shrawan, Q10(b)
Open in the Padhaiko appQuestion
Design a Binary Huffman code with a six symbol source with probability assignment as: .
Solution
Sorting and Huffman Tree Merging: Sorted symbol probabilities:
Sum .
Iterative merging:
- Merge lowest two: . Active list: .
- Merge lowest two: . Active list: .
- Merge lowest two: . Active list: .
- Merge lowest two: . Active list: .
- Merge final two: .
Assigning bits (0 to top, 1 to bottom branch):
-
1(length ) -
0-
00(length ) -
01-
010(length ) -
011-
0110(length ) -
0111-
01110(length ) -
01111(length )
-
-
-
-
Codeword Table and Performance:
| Symbol | Probability | Codeword | Length | |
|---|---|---|---|---|
1 | 1 | |||
00 | 2 | |||
010 | 3 | |||
0110 | 4 | |||
01110 | 5 | |||
01111 | 5 | |||
| Total | 1.00 | — | — |
- Average length:
- Entropy:
- Efficiency:
Answer:
The Binary Huffman code assignments are:
- ():
1 - ():
00 - ():
010 - ():
0110 - ():
01110 - ():
01111
Average codeword length is with coding efficiency .