- 2073 Chaitra · 8 marks
Shannon-Fano code for eight symbols
Short answer
Shannon-Fano encoding produces codes with average length equal to entropy (1.9844 bits/symbol), achieving 100% efficiency.
A message source generates 8 symbols with the following probabilities P(x1)=1/2, P(x2)=1/4, P(x3)=1/8, P(x4)=1/16, P(x5)=1/32, P(x6)=1/64, P(x7)=1/128, P(x8)=1/128. Encode the message with variable length binary codes using Shannon-Fano procedure. Find the transmission efficiency.
Shannon-Fano procedure: list symbols in decreasing probability, divide them into two groups of nearly equal total probability, assign 0 to one group and 1 to the other, and repeat for each group until each group has one symbol.
Partitioning
Probabilities are already in decreasing order, and each is half of what remains, so every split is exact:
| Step | Upper (0) | Lower (1) |
|---|---|---|
| 1 | x1 (1/2) | x2…x8 (1/2) |
| 2 | x2 (1/4) | x3…x8 (1/4) |
| 3 | x3 (1/8) | x4…x8 (1/8) |
| 4 | x4 (1/16) | x5…x8 (1/16) |
| 5 | x5 (1/32) | x6, x7, x8 (1/32) |
| 6 | x6 (1/64) | x7, x8 (1/64) |
| 7 | x7 (1/128) | x8 (1/128) |
Code table
| Symbol | p | Code | Length | p·l |
|---|---|---|---|---|
| x1 | 1/2 | 0 | 1 | 0.5 |
| x2 | 1/4 | 10 | 2 | 0.5 |
| x3 | 1/8 | 110 | 3 | 0.375 |
| x4 | 1/16 | 1110 | 4 | 0.25 |
| x5 | 1/32 | 11110 | 5 | 0.15625 |
| x6 | 1/64 | 111110 | 6 | 0.09375 |
| x7 | 1/128 | 1111110 | 7 | 0.0546875 |
| x8 | 1/128 | 1111111 | 7 | 0.0546875 |
Efficiency
- H = Σ p log₂(1/p) = 0.5·1 + 0.25·2 + 0.125·3 + 0.0625·4 + 0.03125·5 + 0.015625·6 + 2 × 0.0078125·7 = 1.9844 bits/symbol
- L = Σ p·l = 1.9844 bits/symbol
- η = H / L = 100 %
(A fixed-length code would need 3 bits/symbol.)
Answer: η = 100 %
✓ Answer checked by Claude Sonnet 5.5
Related questions
- Huffman code for eight symbols (1/2 ... 1/128) · Data Communication, chapter 8
- Shannon-Fano code for six symbols · Data Communication, chapter 8
- Huffman code for five symbols (0.2, 0.35, ...) · Data Communication, chapter 8
- 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
- Importance of source coding; fixed vs Shannon-Fano (five symbols) · Communication Systems, chapter 6
- Digital communication system; Shannon-Fano for six symbols · Communication Systems, chapter 6