--- title: "Shannon-Fano code for eight symbols" subject: "Data Communication" chapter: 8 key: "semester_5/data_communication:shannon-fano-eight-symbols" source: https://www.bctengineer.com/q/semester_5/data_communication/shannon-fano-eight-symbols site: BCT Engineering --- # Shannon-Fano code for eight symbols Data Communication · Chapter 8: Information Theory and Coding - Asked in: 2073 Chaitra, 8 marks - Video: [SHANNON FANO CODING SOLVED EXAMPLE - with table and calculations - Hindi](https://www.youtube.com/watch?v=U-SpTfzZwFY) — Electronics Subjectified - Answer checked by Claude Sonnet 5.5 on 2026-10-14 - Page: https://www.bctengineer.com/q/semester_5/data_communication/shannon-fano-eight-symbols - Whole chapter: https://www.bctengineer.com/md/semester_5/data_communication/chapter-8 ## Question 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. ## Short answer Shannon-Fano encoding produces codes with average length equal to entropy (1.9844 bits/symbol), achieving 100% efficiency. ## Answer **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 %** ## Check yourself The answer's key points as multiple-choice questions, with the correct option and why. 1. What is the basic step of the Shannon-Fano procedure? A. Repeatedly merge the two least probable symbols B. Sort by decreasing probability, split into two groups of nearly equal total probability, assign 0 and 1, and repeat C. Give every symbol the same number of bits D. Assign codes in alphabetical order of the symbols Answer: B. Shannon-Fano works top-down by splitting the sorted list into two groups of nearly equal probability; merging the two least probable symbols is Huffman. (Key point: Shannon-Fano procedure) 2. Why is every split in this problem exact (equal group totals)? A. All eight symbols have equal probability B. Each symbol's probability equals the total of all the symbols below it, except the last two C. The probabilities sum to more than 1 D. Shannon-Fano always gives exact splits Answer: B. Each probability is half of what remains (1/2 vs 1/2, 1/4 vs 1/4, ...), so the upper and lower groups always have equal totals. (Key point: Why splits are exact) 3. Which code lengths result for x1 to x8? A. 1,2,3,4,5,6,7,7 B. 3,3,3,3,3,3,3,3 C. 1,2,3,4,5,6,7,8 D. 2,2,3,3,4,4,5,5 Answer: A. x1 gets 0, x2 gets 10, and so on, with the last two symbols x7 and x8 both getting 7 bits (1111110 and 1111111). (Key point: Resulting code) 4. Why is the efficiency 100 %? A. Because L is 3 bits, equal to log2 8 B. Because H = L = 1.9844 bits/symbol, since each length equals log2(1/p) C. Because the code is fixed length D. Because H is greater than L Answer: B. Every code length equals log2(1/p), so average length L equals entropy H and eta = H/L = 100 %. (Key point: Transmission efficiency) ## Related in Data Communication - [Huffman code for eight symbols (1/2 ... 1/128)](https://www.bctengineer.com/question.md?key=semester_5%2Fdata_communication%3Ahuffman-eight-symbols) — Data Communication, chapter 8 - [Shannon-Fano code for six symbols](https://www.bctengineer.com/question.md?key=semester_5%2Fdata_communication%3Ashannon-fano-six-symbols) — Data Communication, chapter 8 - [Huffman code for five symbols (0.2, 0.35, ...)](https://www.bctengineer.com/question.md?key=semester_5%2Fdata_communication%3Ahuffman-five-symbols-02-035) — Data Communication, chapter 8 ## Related in other subjects - [Importance of source coding; Shannon-Fano vs fixed length (seven symbols)](https://www.bctengineer.com/question.md?key=semester_6%2Fcommunication_systems%3Asource-coding-sf-fixed-seven) — Communication Systems, chapter 6 - [Importance of source coding; Shannon-Fano vs BCD (four symbols)](https://www.bctengineer.com/question.md?key=semester_6%2Fcommunication_systems%3Asource-coding-sf-bcd-four) — Communication Systems, chapter 6 - [Importance of source coding; fixed vs Shannon-Fano (five symbols)](https://www.bctengineer.com/question.md?key=semester_6%2Fcommunication_systems%3Asource-coding-fixed-sf-five) — Communication Systems, chapter 6 - [Digital communication system; Shannon-Fano for six symbols](https://www.bctengineer.com/question.md?key=semester_6%2Fcommunication_systems%3Adcs-block-shannon-fano-six) — Communication Systems, chapter 6