- 2073 Shrawan · 6 marks
Huffman code for six symbols (0.04, 0.1, ...)
Short answer
Huffman coding yields average length 2.2000 bits/symbol and efficiency 97.43%.
Design a Binary Huffman code with a six symbol source with probability assignment as: P(s1)=0.04, P(s2)=0.1, P(s3)=0.1, P(s4)=0.4, P(s5)=0.06 and P(s6)=0.3.
Probabilities: s4 = 0.4, s6 = 0.3, s2 = 0.1, s3 = 0.1, s5 = 0.06, s1 = 0.04 (sum = 1).
Merging steps
At every step the two smallest probabilities are combined (N1, N2, ... are the new nodes):
1. s1(0.04) + s5(0.06) = 0.1
2. s2(0.1) + s3(0.1) = 0.2
3. N1(0.1) + N2(0.2) = 0.3
4. s6(0.3) + N3(0.3) = 0.6
5. s4(0.4) + N4(0.6) = 1
Code table
| Symbol | p | Code | Length l | p·l |
|---|---|---|---|---|
| s4 | 0.4 | 0 | 1 | 0.4000 |
| s6 | 0.3 | 10 | 2 | 0.6000 |
| s2 | 0.1 | 1110 | 4 | 0.4000 |
| s3 | 0.1 | 1111 | 4 | 0.4000 |
| s5 | 0.06 | 1101 | 4 | 0.2400 |
| s1 | 0.04 | 1100 | 4 | 0.1600 |
Entropy, average length, efficiency
- H = −Σ p log₂ p = 2.1435 bits/symbol
- L = Σ p·l = 2.2000 bits/symbol
- Efficiency η = H/L = 2.1435/2.2000 = 97.43 % (redundancy = 2.57 %)
Huffman codes are not unique when probabilities tie, but L and η are the same for every valid choice.
Answer: L = 2.2000 bits/symbol, η = 97.43 %
✓ Answer checked by Claude Sonnet 5.5
Related questions
- Shannon-Fano code for six symbols · Data Communication, chapter 8
- Huffman code for five symbols (0.2, 0.35, ...) · Data Communication, chapter 8
- Huffman code for symbols A to E (0.4, 0.3, ...) · Data Communication, chapter 8
- Huffman code for eight symbols (1/2 ... 1/128) · Data Communication, chapter 8
- Huffman code for symbols A0 to A4 · Data Communication, chapter 8
- Huffman code for seven-symbol source · Communication Systems, chapter 6
- Source vs channel coding; Huffman for five symbols · Communication Systems, chapter 6
- Source coding; Huffman for five symbols (0.3, 0.25, 0.2, 0.15, 0.1) · Communication Systems, chapter 6
- Huffman code for symbols A to E · Multimedia System, chapter 5