--- title: "Digital communication system elements; Shannon-Fano coding" subject: "Communication Systems" chapter: 6 key: "semester_6/communication_systems:dcs-block-shannon-fano" source: https://www.bctengineer.com/q/semester_6/communication_systems/dcs-block-shannon-fano site: BCT Engineering --- # Digital communication system elements; Shannon-Fano coding Communication Systems · Chapter 6: Baseband Digital Data Transmission - Asked in: 2073 Shrawan (CS II), 5+3 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 - Whole chapter: https://www.bctengineer.com/md/semester_6/communication_systems/chapter-6 ## Question Explain in brief the functional block diagram and the basic elements of a digital communication system. Explain Shannon-Fano coding. ## Short answer A digital communication system consists of source, source encoder, channel encoder, modulator, channel, demodulator, channel decoder, source decoder, and destination. Shannon-Fano coding assigns variable-length prefix codes by recursively splitting symbols into two nearly equiprobable groups, assigning 0 and 1, achieving code length close to entropy. ## Answer #### Digital communication system A digital communication system transmits information as discrete symbols (bits) over a channel. Its functional blocks: ```text Info -> Formatter -> Source -> Channel -> Modulator source (A/D) encoder encoder | v Channel noise -> (+) | User <- Formatter <- Source <- Channel <- Demodulator (D/A) decoder decoder /detector ``` **Basic elements:** 1. **Information source:** produces the message (voice, video, text, data). Analog messages are first converted to digital by the **formatter** (sampling, quantizing, PCM encoding). 2. **Source encoder:** removes redundancy and represents the symbols with the fewest bits on average (Huffman, Shannon–Fano). It lowers the bit rate. 3. **Channel encoder:** adds controlled redundancy (parity bits) so the receiver can detect and correct errors (Hamming, cyclic, convolutional codes). 4. **Digital modulator:** converts the bits into waveforms suitable for the channel: line coding for baseband, ASK, FSK, PSK or QAM for bandpass. 5. **Channel:** the physical medium (wire, coaxial cable, optical fibre, radio). It adds noise, attenuation, distortion and interference. 6. **Demodulator/detector:** recovers the bit sequence from the received waveform, using matched filtering, sampling and decisions. 7. **Channel decoder:** uses the redundancy to correct errors. 8. **Source decoder and formatter:** rebuild the original message (D/A conversion) for the user. Other blocks often included: encryption/decryption, multiplexing, synchronization. Performance is judged by the probability of bit error $P_e$, bandwidth efficiency (bits/s/Hz) and power efficiency ($E_b/N_0$ needed). #### Shannon–Fano coding Shannon–Fano coding is a variable-length source coding method that gives short code words to likely symbols and long ones to unlikely symbols. **Algorithm:** 1. List the symbols in decreasing order of probability. 2. Split the list into two groups whose total probabilities are as nearly equal as possible. 3. Assign bit 0 to every symbol of the upper group and 1 to the lower group. 4. Repeat steps 2–3 inside each group until every group has one symbol. 5. The code word of a symbol is the sequence of bits assigned to it. **Example:** $P = \{0.4, 0.2, 0.2, 0.1, 0.1\}$ for A–E. First split {A} = 0.4 vs {B, C, D, E} = 0.6. | Symbol | $p_i$ | Step 1 | Step 2 | Step 3 | Step 4 | Code | $l_i$ | |---|---|---|---|---|---|---|---| | A | 0.4 | 0 | | | | 0 | 1 | | B | 0.2 | 1 | 0 | | | 10 | 2 | | C | 0.2 | 1 | 1 | 0 | | 110 | 3 | | D | 0.1 | 1 | 1 | 1 | 0 | 1110 | 4 | | E | 0.1 | 1 | 1 | 1 | 1 | 1111 | 4 | $$ \begin{aligned} \bar L &= 0.4(1)+0.2(2)+0.2(3)+0.1(4)+0.1(4) = 2.2\ \text{bits/symbol} \\ H &= 2.1219\ \text{bits/symbol}, \qquad \eta = \frac{2.1219}{2.2} = 96.45\% \end{aligned} $$ The code is a prefix code (uniquely decodable), but Shannon–Fano is not always optimal; Huffman coding is. ## Check yourself The answer's key points as multiple-choice questions, with the correct option and why. 1. What is the main job of the source encoder in a digital communication system? A. Remove redundancy so each symbol uses the fewest bits on average B. Add parity bits for error correction C. Convert bits into ASK/FSK/PSK waveforms D. Sample and quantize the analog message Answer: A. The source encoder compresses the data by removing redundancy (Huffman, Shannon-Fano), lowering the bit rate. (Key point: Source encoder role) 2. Why does the channel encoder add controlled redundancy? A. To reduce the bit rate B. To let the receiver detect and correct errors C. To convert the signal to bandpass D. To make the code uniquely decodable Answer: B. Parity bits added by the channel encoder (Hamming, cyclic, convolutional) let the channel decoder fix errors caused by noise. (Key point: Channel encoder role) 3. In Shannon-Fano coding, how is the sorted symbol list split at each step? A. Into two groups with equal numbers of symbols B. Into two groups whose total probabilities are as nearly equal as possible C. Into the most probable symbol and all the others, always D. Into groups chosen at random Answer: B. Each group is divided so that the two sub-totals of probability are as close as possible, then 0 and 1 are assigned. (Key point: Shannon-Fano splitting) 4. For P = {0.4, 0.2, 0.2, 0.1, 0.1} with Shannon-Fano coding, what are the average length and efficiency? A. L = 2.0 bits, efficiency 100% B. L = 2.2 bits, efficiency about 96.45% C. L = 2.2 bits, efficiency about 100% D. L = 3 bits, efficiency about 70.7% Answer: B. L = 0.4(1)+0.2(2)+0.2(3)+0.1(4)+0.1(4) = 2.2; H = 2.1219, so efficiency = 2.1219/2.2 = 96.45%. (Key point: Shannon-Fano example result) ## Related in Communication Systems - [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 - [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; 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 - [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 - [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 - [Coding efficiency: binary, Shannon-Fano and Huffman](https://www.bctengineer.com/question.md?key=semester_6%2Fcommunication_systems%3Acoding-efficiency-binary-sf-huffman) — Communication Systems, chapter 6 ## Related in other subjects - [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× - [Communication system and block diagram](https://www.bctengineer.com/question.md?key=semester_2%2Fbasic_electronics_engineering%3Acomm-system-block-diagram) — Basic Electronics Engineering, chapter 5, asked 7× - [Communication system and AM block diagram](https://www.bctengineer.com/question.md?key=semester_2%2Fbasic_electronics_engineering%3Adefine-comm-am) — Basic Electronics Engineering, chapter 5 - [Digital control system block diagram and advantages](https://www.bctengineer.com/question.md?key=semester_6%2Fdigital_control_system%3Adcs-block-diagram-advantages) — Digital Control System, chapter 1, asked 3×