Past exam question: 2074 Ashwin, Q8
Open in the Padhaiko appQuestion
Consider a five symbol source with probability assignment as . By using Huffman algorithm, find the source code for these symbols and determine efficiency of the code.
Solution
Source Sorting and Huffman Tree Construction: Given alphabet symbols sorted in descending probability order:
Sum .
Iterative reduction:
- Stage 1: Merge lowest two:
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, 1 to bottom/lower):
- From Root:
- branch
0- branch
00(length ) - branch
01- branch
010(length ) - branch
011(length )
- branch
- branch
- branch
1- branch
10(length ) - branch
11(length )
- branch
- branch
Codeword Table and Performance Analysis:
| Symbol | Probability | Codeword | Length | ||
|---|---|---|---|---|---|
00 | 2 | ||||
10 | 2 | ||||
11 | 2 | ||||
010 | 3 | ||||
011 | 3 | ||||
| Total | 1.00 | — | — |
- Average Codeword Length ():
- Entropy ():
- Coding Efficiency ():
Answer:
The Huffman codewords are:
- ():
00 - ():
10 - ():
11 - ():
010 - ():
011
Performance:
- Average Codeword Length:
- Source Entropy:
- Coding Efficiency: