--- title: "Importance of source coding; fixed vs Shannon-Fano (five symbols)" subject: "Communication Systems" chapter: 6 key: "semester_6/communication_systems:source-coding-fixed-sf-five" source: https://www.bctengineer.com/q/semester_6/communication_systems/source-coding-fixed-sf-five site: BCT Engineering --- # Importance of source coding; fixed vs Shannon-Fano (five symbols) Communication Systems · Chapter 6: Baseband Digital Data Transmission - Asked in: 2073 Chaitra (CS II), 6+4 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 Opus 5.5 (high effort) on 2026-10-14 - Page: https://www.bctengineer.com/q/semester_6/communication_systems/source-coding-fixed-sf-five - Whole chapter: https://www.bctengineer.com/md/semester_6/communication_systems/chapter-6 ## Question Discuss the importance of source coding in Digital Communication System. A discrete memory less source emits five symbols with probabilities P = {0.3, 0.25, 0.2, 0.15, 0.1}, find coding efficiency for both fixed and Shannon-Fano coding and compare results. ## Short answer Source coding removes redundancy, lowering bit rate, bandwidth, and power. For P={0.3,0.25,0.2,0.15,0.1}, entropy H=2.2282 bits/symbol. Fixed-length (3-bit) efficiency 74.27%; Shannon-Fano coding gives average length 2.25 bits/symbol, efficiency 99.03% and saves 0.75 bits per symbol. ## Answer #### Importance of source coding **Source coding** converts the source output into a binary sequence using as few bits per symbol as possible, by removing redundancy. Its importance: 1. **Lower bit rate:** the average code length $\bar L$ approaches the entropy $H$, so fewer bits are sent for the same information. 2. **Bandwidth saving:** a lower bit rate needs less channel bandwidth, so more users or services fit in the same band. 3. **Power and energy saving:** fewer bits means less transmitted energy, important in mobile and satellite links. 4. **Storage saving:** compressed files (ZIP, JPEG, MP3) need less memory. 5. **Exploits statistics:** variable-length codes give short words to frequent symbols and long words to rare ones. 6. **Theoretical guarantee:** Shannon's source coding theorem, $H \le \bar L < H + 1$, shows how close a code can come to the limit; efficiency $\eta = H/\bar L$ measures the code. 7. **Uniquely decodable prefix codes** allow decoding without separators. 8. **Supports channel coding:** removing useless redundancy leaves room to add useful redundancy for error control. #### Numerical: $P = \{0.3, 0.25, 0.2, 0.15, 0.1\}$ **Entropy:** | Symbol | $p_i$ | $\log_2(1/p_i)$ | $p_i\log_2(1/p_i)$ | |---|---|---|---| | S0 | 0.3 | 1.7370 | 0.5211 | | S1 | 0.25 | 2.0000 | 0.5000 | | S2 | 0.2 | 2.3219 | 0.4644 | | S3 | 0.15 | 2.7370 | 0.4105 | | S4 | 0.1 | 3.3219 | 0.3322 | | **Total** | 1 | | **2.2282** | $$ H = 2.2282\ \text{bits/symbol} $$ **(a) Fixed-length coding:** 5 symbols need $\lceil\log_2 5\rceil = 3$ bits each (000 to 100). $$ \eta_{FL} = \frac{H}{\bar L} = \frac{2.2282}{3} = 74.27\% $$ **(b) Shannon–Fano coding:** first split {0.3, 0.25} = 0.55 vs {0.2, 0.15, 0.1} = 0.45; then {0.2} vs {0.15, 0.1}. | Symbol | $p_i$ | Step 1 | Step 2 | Step 3 | Code | $l_i$ | |---|---|---|---|---|---|---| | S0 | 0.3 | 0 | 0 | | 00 | 2 | | S1 | 0.25 | 0 | 1 | | 01 | 2 | | S2 | 0.2 | 1 | 0 | | 10 | 2 | | S3 | 0.15 | 1 | 1 | 0 | 110 | 3 | | S4 | 0.1 | 1 | 1 | 1 | 111 | 3 | $$ \begin{aligned} \bar L_{SF} &= 0.3(2)+0.25(2)+0.2(2)+0.15(3)+0.1(3) = 2.25\ \text{bits/symbol} \\ \eta_{SF} &= \frac{2.2282}{2.25} = 99.03\% \end{aligned} $$ #### Comparison | Method | $\bar L$ | Efficiency | Redundancy | |---|---|---|---| | Fixed length | 3 | 74.27 % | 25.73 % | | Shannon–Fano | 2.25 | 99.03 % | 0.97 % | Shannon–Fano uses 0.75 bit/symbol less (25 % fewer bits) and is almost at the entropy limit, while fixed-length coding wastes about a quarter of the bits. ## Check yourself The answer's key points as multiple-choice questions, with the correct option and why. 1. How many bits per symbol does a fixed-length code need for 5 symbols? A. 2 B. 3 C. 4 D. 5 Answer: B. ceil(log2 5) = 3 bits. (Key point: Fixed-length bits) 2. For P = {0.3, 0.25, 0.2, 0.15, 0.1}, Shannon-Fano gives code lengths 2,2,2,3,3. What is the average length? A. 2.00 bits B. 2.25 bits C. 2.50 bits D. 3.00 bits Answer: B. 0.3(2)+0.25(2)+0.2(2)+0.15(3)+0.1(3) = 2.25 bits/symbol. (Key point: Shannon-Fano average length) 3. With H = 2.2282 bits, how do the efficiencies of fixed-length and Shannon-Fano coding compare? A. Fixed 74.27%, Shannon-Fano 99.03% B. Fixed 99.03%, Shannon-Fano 74.27% C. Both about 88% D. Fixed 74.27%, Shannon-Fano 85% Answer: A. eta = H/L: 2.2282/3 = 74.27% and 2.2282/2.25 = 99.03%. (Key point: Efficiency comparison) ## 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 - [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 - [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 - [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 - [Source coding; Huffman for five symbols (0.3, 0.25, 0.2, 0.15, 0.1)](https://www.bctengineer.com/question.md?key=semester_6%2Fcommunication_systems%3Asource-coding-huffman-five-s0) — Communication Systems, chapter 6 - [Source vs channel coding; Huffman for five symbols](https://www.bctengineer.com/question.md?key=semester_6%2Fcommunication_systems%3Asource-channel-huffman-five) — Communication Systems, chapter 6 ## Related in other subjects - [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 - [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 - [Source coding; fixed vs variable length codes](https://www.bctengineer.com/question.md?key=semester_5%2Fdata_communication%3Asource-coding-fixed-variable) — Data Communication, chapter 8