--- title: "Huffman code for five-symbol DMS vs fixed length" subject: "Communication Systems" chapter: 6 key: "semester_6/communication_systems:huffman-dms-five-symbols" source: https://www.bctengineer.com/q/semester_6/communication_systems/huffman-dms-five-symbols site: BCT Engineering --- # Huffman code for five-symbol DMS vs fixed length Communication Systems · Chapter 6: Baseband Digital Data Transmission - Asked in: 2081 Baisakh (CS II), 4 marks - Video: [Huffman Coding Technique for binary system.](https://www.youtube.com/watch?v=EPtWCVSZqi8) — WIT Solapur - Professional Learning Community - Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14 - Page: https://www.bctengineer.com/q/semester_6/communication_systems/huffman-dms-five-symbols - Whole chapter: https://www.bctengineer.com/md/semester_6/communication_systems/chapter-6 ## Question A DMS has five symbols with probability of p(x₁) = 0.4, p(x₂) = 0.19, p(x₃) = 0.16, p(x₄) = 0.15 and p(x₅) = 0.1. Construct the Huffman code for X and calculate its efficiency and compare with fixed length coding. ## Short answer Huffman codes: x1: 1, x2: 000, x3: 001, x4: 010, x5: 011. Average length L = 2.20 bits/symbol, entropy H = 2.1498 bits/symbol. Efficiency η = H/L = 97.72%. Fixed-length (3 bits) efficiency is 71.66%; Huffman saves 0.8 bits/symbol. ## Answer #### Huffman code construction Arrange the symbols by probability and repeatedly combine the two smallest. In each merge, the first group gets bit 0 and the second gets bit 1. 1. $x_4$ (0.15) + $x_5$ (0.10) → 0.25 2. $x_2$ (0.19) + $x_3$ (0.16) → 0.35 3. {x2,x3} (0.35) + {x4,x5} (0.25) → 0.60 4. {x2..x5} (0.60) + $x_1$ (0.40) → 1.00 ```text (1.00) 0 / \ 1 (0.60) x1 (0.40) 0/ \1 (0.35) (0.25) 0/ \1 0/ \1 x2 x3 x4 x5 ``` | Symbol | $p_i$ | Code | $l_i$ | $p_i l_i$ | |---|---|---|---|---| | $x_1$ | 0.40 | 1 | 1 | 0.40 | | $x_2$ | 0.19 | 000 | 3 | 0.57 | | $x_3$ | 0.16 | 001 | 3 | 0.48 | | $x_4$ | 0.15 | 010 | 3 | 0.45 | | $x_5$ | 0.10 | 011 | 3 | 0.30 | #### Efficiency $$ \begin{aligned} \bar L &= \sum p_i l_i = 0.40 + 0.57 + 0.48 + 0.45 + 0.30 = 2.20\ \text{bits/symbol} \\ H &= -\sum p_i \log_2 p_i \\ &= 0.4(1.3219) + 0.19(2.3959) + 0.16(2.6439) \\ &\quad + 0.15(2.7370) + 0.1(3.3219) \\ &= 2.1498\ \text{bits/symbol} \\ \eta &= \frac{H}{\bar L} = \frac{2.1498}{2.20} = 0.9772 = 97.72\% \end{aligned} $$ #### Comparison with fixed-length coding Five symbols need $\lceil \log_2 5 \rceil = 3$ bits each: $$ \eta_{fixed} = \frac{H}{3} = \frac{2.1498}{3} = 0.7166 = 71.66\% $$ | Code | Avg. length | Efficiency | |---|---|---| | Fixed length | 3 bits | 71.66% | | Huffman | 2.20 bits | 97.72% | Huffman coding saves $3 - 2.2 = 0.8$ bits/symbol (about 26.7%). Its efficiency is close to the entropy limit. ## Check yourself The answer's key points as multiple-choice questions, with the correct option and why. 1. Which two symbols are merged first for probabilities 0.4,0.19,0.16,0.15,0.1? A. x1 and x2 B. x2 and x3 C. x3 and x5 D. x4 and x5 Answer: D. The two smallest, 0.15 and 0.10, merge to give 0.25. (Key point: First merge) 2. With code lengths 1,3,3,3,3 what is L? A. 1.80 B. 3.00 C. 2.50 D. 2.20 bits/symbol Answer: D. L = 0.4(1)+0.19(3)+0.16(3)+0.15(3)+0.1(3) = 2.20. (Key point: Average length) 3. With H = 2.1498 and L = 2.20, efficiency is: A. 97.72% B. 71.66% C. 89% D. 102.3% Answer: A. 2.1498/2.20 = 0.9772. (Key point: Efficiency) 4. Fixed-length coding of 5 symbols needs how many bits and gives what efficiency? A. 5 bits, 43% B. 3 bits, 71.66% C. 3 bits, 97.7% D. 2 bits, 100% Answer: B. ceil(log2 5) = 3, so efficiency = 2.1498/3 = 71.66%; Huffman saves 0.8 bits/symbol. (Key point: Fixed-length comparison) ## Related in Communication Systems - [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 - [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 - [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 - [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 - [Variable length coding; entropy and fixed code efficiency](https://www.bctengineer.com/question.md?key=semester_6%2Fcommunication_systems%3Avariable-length-coding-entropy-six) — Communication Systems, chapter 6 - [Importance of source coding; Huffman for eight symbols at 1000 symbols/s](https://www.bctengineer.com/question.md?key=semester_6%2Fcommunication_systems%3Asource-coding-huffman-eight-1000) — Communication Systems, chapter 6 ## Related in other subjects - [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 - [Huffman code for symbols A to E (0.4, 0.3, ...)](https://www.bctengineer.com/question.md?key=semester_5%2Fdata_communication%3Ahuffman-table-abcde) — 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 - [Huffman code for symbols A to E](https://www.bctengineer.com/question.md?key=semester_8%2Fmultimedia_system%3Ahuffman-numerical-abcde) — Multimedia System, chapter 5