--- title: "Digital communication system; Shannon-Fano for six symbols" subject: "Communication Systems" chapter: 6 key: "semester_6/communication_systems:dcs-block-shannon-fano-six" source: https://www.bctengineer.com/q/semester_6/communication_systems/dcs-block-shannon-fano-six site: BCT Engineering --- # Digital communication system; Shannon-Fano for six symbols Communication Systems · Chapter 6: Baseband Digital Data Transmission - Asked in: 2080 Baisakh (CS II), 5+5 marks - Video: [1 Shannon Fano Encoding (Algorithm, Procedure & Example) Explained in Digital Communication](https://www.youtube.com/watch?v=g2UlDNamG84) — Engineering Funda - Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14 - Page: https://www.bctengineer.com/q/semester_6/communication_systems/dcs-block-shannon-fano-six - Whole chapter: https://www.bctengineer.com/md/semester_6/communication_systems/chapter-6 ## Question Explain digital communication system with appropriate block diagram. A DMS has six symbols with probability of p(x₁) = 0.3, p(x₂) = 0.2, p(x₃) = 0.25, p(x₄) = 0.12 and p(x₅) = 0.08, p(x₆) = 0.05. Construct the Shannon-Fano code for X and calculate its efficiency and code Redundancy. ## Short answer A digital communication system comprises source, formatter, source encoder, channel encoder, modulator, channel, demodulator, channel decoder, source decoder, and formatter. For the given six symbols, Shannon-Fano coding yields codes: x1=00, x3=01, x2=10, x4=110, x5=1110, x6=1111. Average code length is 2.38 bits/symbol, entropy is 2.3601 bits/symbol, efficiency is 99.17%, redundancy is 0.83%. ## Answer #### Digital communication system A digital communication system sends information as a sequence of discrete symbols (usually bits) from a source to a user. ```text Source -> Formatter -> Source -> Channel -> Modulator (analog (sample, encoder encoder | /digital) quantize) v Channel (noise added) | User <- Formatter <- Source <- Channel <- Demodulator (D/A) decoder decoder /detector ``` - **Information source and formatter:** produces the message; an analog message is sampled, quantized and coded (A/D conversion) into bits. - **Source encoder:** removes redundancy so the average number of bits per symbol is close to the entropy (Huffman, Shannon–Fano). This reduces bit rate and bandwidth. - **Channel encoder:** adds controlled redundancy (parity bits) so that errors caused by the channel can be detected or corrected (Hamming, cyclic, convolutional codes). - **Modulator:** maps the bits onto waveforms suited to the channel: line codes for baseband, ASK/FSK/PSK/QAM for bandpass. - **Channel:** wire, cable, fibre or radio link; it attenuates, distorts (ISI) and adds noise. - **Demodulator/detector:** recovers the bit stream from the noisy waveform, usually with a matched filter and a decision device. - **Channel decoder, source decoder, formatter:** reverse the encoding steps and deliver the message to the user. Performance is measured by bit error probability and by bandwidth and power efficiency. #### Shannon–Fano code Probabilities add to 1. **Procedure:** list symbols in decreasing probability; split the list into two groups of nearly equal total probability; give 0 to the upper group and 1 to the lower group; repeat in each group until each has one symbol. First split: {0.3, 0.25} = 0.55 and {0.2, 0.12, 0.08, 0.05} = 0.45. | Symbol | $p_i$ | Step 1 | Step 2 | Step 3 | Step 4 | Code | $l_i$ | |---|---|---|---|---|---|---|---| | x1 | 0.3 | 0 | 0 | | | 00 | 2 | | x3 | 0.25 | 0 | 1 | | | 01 | 2 | | x2 | 0.2 | 1 | 0 | | | 10 | 2 | | x4 | 0.12 | 1 | 1 | 0 | | 110 | 3 | | x5 | 0.08 | 1 | 1 | 1 | 0 | 1110 | 4 | | x6 | 0.05 | 1 | 1 | 1 | 1 | 1111 | 4 | **Entropy:** | Symbol | $p_i$ | $\log_2(1/p_i)$ | $p_i\log_2(1/p_i)$ | |---|---|---|---| | x1 | 0.3 | 1.7370 | 0.5211 | | x2 | 0.2 | 2.3219 | 0.4644 | | x3 | 0.25 | 2.0000 | 0.5000 | | x4 | 0.12 | 3.0589 | 0.3671 | | x5 | 0.08 | 3.6439 | 0.2915 | | x6 | 0.05 | 4.3219 | 0.2161 | | **Total** | 1 | | **2.3601** | $$ H(X) = \sum p_i\log_2\frac{1}{p_i} = 2.3601\ \text{bits/symbol} $$ **Average code length:** $$ \begin{aligned} \bar L &= \sum p_i l_i = 0.3(2)+0.25(2)+0.2(2)+0.12(3)+0.08(4)+0.05(4) \\ &= 0.6+0.5+0.4+0.36+0.32+0.2 = 2.38\ \text{bits/symbol} \end{aligned} $$ **Efficiency and redundancy:** $$ \begin{aligned} \eta &= \frac{H}{\bar L} = \frac{2.3601}{2.38} = 0.9917 = 99.17\% \\ \gamma &= 1 - \eta = 0.0083 = 0.83\% \end{aligned} $$ **Answer:** codes $x_1 = 00$, $x_3 = 01$, $x_2 = 10$, $x_4 = 110$, $x_5 = 1110$, $x_6 = 1111$; $\bar L = 2.38$ bits/symbol, efficiency = 99.17 %, redundancy = 0.83 %. ## Check yourself The answer's key points as multiple-choice questions, with the correct option and why. 1. What does the source encoder do? A. Modulates the carrier B. Removes redundancy to reduce bits per symbol C. Corrects errors D. Adds parity bits Answer: B. The source encoder compresses; the channel encoder adds parity. (Key point: Source encoder role) 2. In Shannon-Fano coding, how are symbols grouped? A. Merge two smallest B. Split into two groups of nearly equal total probability C. Randomly D. Equal numbers of symbols Answer: B. Symbols sorted by probability are split into nearly equal probability groups, upper group gets 0, lower gets 1, and repeated. (Key point: Shannon-Fano split) 3. With lengths 2,2,2,3,4,4 for p = 0.3,0.25,0.2,0.12,0.08,0.05, L is: A. 2.36 B. 3.00 C. 2.38 D. 2.50 Answer: C. 0.6+0.5+0.4+0.36+0.32+0.2 = 2.38. (Key point: Average length) 4. With H = 2.3601, efficiency and redundancy are: A. 100%, 0% B. 95%, 5% C. 99.17%, 0.83% D. 92%, 8% Answer: C. 2.3601/2.38 = 0.9917; redundancy = 1 - eta = 0.83%. (Key point: Efficiency) ## Related in Communication Systems - [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 - [Digital communication system elements; Shannon-Fano coding](https://www.bctengineer.com/question.md?key=semester_6%2Fcommunication_systems%3Adcs-block-shannon-fano) — 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 - [Shannon-Fano and Huffman codes for six messages](https://www.bctengineer.com/question.md?key=semester_6%2Fcommunication_systems%3Asf-huffman-six-messages) — 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 - [Types of noise; Shannon-Fano and Huffman coding efficiency](https://www.bctengineer.com/question.md?key=semester_6%2Fcommunication_systems%3Anoise-types-shannon-fano-huffman) — Communication Systems, chapter 6 ## Related in other subjects - [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 - [Shannon-Fano code for eight symbols](https://www.bctengineer.com/question.md?key=semester_5%2Fdata_communication%3Ashannon-fano-eight-symbols) — Data Communication, chapter 8 - [Block diagram of digital communication system](https://www.bctengineer.com/question.md?key=semester_5%2Fdata_communication%3Ablock-diagram-digital-comm) — Data Communication, chapter 1, asked 8× - [Huffman code for six symbols (0.04, 0.1, ...)](https://www.bctengineer.com/question.md?key=semester_5%2Fdata_communication%3Ahuffman-six-symbols-004) — Data Communication, chapter 8