Past exam question: 2074 Chaitra, Q9(b)
Open in the Padhaiko appQuestion
Find an efficient code word and calculate efficiency that can be assign to the symbols using Huffman Algorithm using probabilities .
Solution
Huffman Tree Construction: Given sorted probabilities:
Total probability .
- Iteration 1: Merge lowest two:
Active nodes: .
- Iteration 2: Merge lowest two:
Active nodes: .
- Iteration 3: Merge final two:
Assign binary 0 to top branch and 1 to bottom branch:
-
0(length ) -
1-
10(length ) -
11-
110(length ) -
111(length )
-
-
Performance Evaluation:
- Average Codeword Length ():
- Source Entropy ():
- Coding Efficiency ():
Since each symbol probability is an exact negative power of 2 (), the code achieves 100% theoretical efficiency.
Answer:
The Huffman codewords are:
- ():
0 - ():
10 - ():
110 - ():
111
Performance:
- Average Codeword Length:
- Source Entropy:
- Coding Efficiency: