- 2076 Asoj · 7+3 marks
Shannon-Fano code for six symbols
Short answer
Sorted probabilities: s4=0.4, s6=0.3, s2=0.1, s3=0.1, s5=0.06, s1=0.04. Shannon-Fano codes: s4=0, s6=10, s2=110, s3=1110, s5=11110, s1=11111. Average length L=2.2 bits/symbol, entropy H=2.1435, efficiency 97.4%.
Design a Binary Shannon-Fano 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, P(s6)=0.3. Test its transmission efficiency.
Shannon-Fano procedure: arrange symbols in decreasing probability, split the list into two groups whose total probabilities are as nearly equal as possible, give 0 to the upper group and 1 to the lower, and repeat inside each group until every group has one symbol.
Sorted symbols
s4 = 0.4, s6 = 0.3, s2 = 0.1, s3 = 0.1, s5 = 0.06, s1 = 0.04
Partitioning
| Step | Group | Upper (0) | Lower (1) | Sums |
|---|---|---|---|---|
| 1 | all six | s4 | s6, s2, s3, s5, s1 | 0.4 / 0.6 |
| 2 | s6 s2 s3 s5 s1 | s6 | s2, s3, s5, s1 | 0.3 / 0.3 |
| 3 | s2 s3 s5 s1 | s2 | s3, s5, s1 | 0.1 / 0.2 |
| 4 | s3 s5 s1 | s3 | s5, s1 | 0.1 / 0.1 |
| 5 | s5 s1 | s5 | s1 | 0.06 / 0.04 |
(In step 3 the split 0.2 | 0.1 is equally good; either gives the same average length.)
Code table
| Symbol | p | Code | Length | p·l |
|---|---|---|---|---|
| s4 | 0.4 | 0 | 1 | 0.40 |
| s6 | 0.3 | 10 | 2 | 0.60 |
| s2 | 0.1 | 110 | 3 | 0.30 |
| s3 | 0.1 | 1110 | 4 | 0.40 |
| s5 | 0.06 | 11110 | 5 | 0.30 |
| s1 | 0.04 | 11111 | 5 | 0.20 |
Transmission efficiency
- H = −Σ p log₂ p = 2.1435 bits/symbol
- L = Σ p·l = 0.40 + 0.60 + 0.30 + 0.40 + 0.30 + 0.20 = 2.20 bits/symbol
- η = H / L = 2.1435 / 2.20 = 97.43 %
Answer: L = 2.2 bits/symbol, η ≈ 97.4 %
✓ Answer checked by Claude Sonnet 5.5
Related questions
- Huffman code for six symbols (0.04, 0.1, ...) · Data Communication, chapter 8
- Shannon-Fano code for eight symbols · Data Communication, chapter 8
- Huffman code for five symbols (0.2, 0.35, ...) · Data Communication, chapter 8
- Huffman code for seven-symbol source · Communication Systems, chapter 6
- Digital communication system; Shannon-Fano for six symbols · Communication Systems, chapter 6
- Importance of source coding; Shannon-Fano vs fixed length (seven symbols) · Communication Systems, chapter 6
- Importance of source coding; Shannon-Fano vs BCD (four symbols) · Communication Systems, chapter 6