--- title: "Huffman code for seven-symbol source" subject: "Communication Systems" chapter: 6 key: "semester_6/communication_systems:huffman-seven-symbols" source: https://www.bctengineer.com/q/semester_6/communication_systems/huffman-seven-symbols site: BCT Engineering --- # Huffman code for seven-symbol source Communication Systems · Chapter 6: Baseband Digital Data Transmission - Asked in: 2079 Bhadra (CS II), 5 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-seven-symbols - Whole chapter: https://www.bctengineer.com/md/semester_6/communication_systems/chapter-6 ## Question A discrete memoryless source has an alphabet of seven symbols whose probabilities occurrence are as under. | Symbol | S0 | S1 | S2 | S3 | S4 | S5 | S6 | |---|---|---|---|---|---|---|---| | Probability | 0.25 | 0.25 | 0.125 | 0.125 | 0.125 | 0.0625 | 0.0625 | Determine the Huffman code for above source. ## Short answer Huffman codes are S0=10, S1=11, S2=001, S3=010, S4=011, S5=0000, S6=0001. Average code length equals entropy at 2.625 bits/symbol, giving 100% efficiency since all probabilities are negative powers of two. ## Answer **Huffman procedure:** arrange symbols in decreasing probability; combine the two lowest probabilities into one; place the sum in the list as high as possible; repeat until one probability (1.0) is left. Then trace back, giving 0 to the upper branch and 1 to the lower branch at each combination. **Reduction (sum of two lowest moved up as high as possible):** | Stage | Probabilities (descending) | Combined | |---|---|---| | 1 | 0.25, 0.25, 0.125, 0.125, 0.125, 0.0625, 0.0625 | 0.0625 + 0.0625 = 0.125 | | 2 | 0.25, 0.25, 0.125, 0.125, 0.125, 0.125 | 0.125 + 0.125 = 0.25 | | 3 | 0.25, 0.25, 0.25, 0.125, 0.125 | 0.125 + 0.125 = 0.25 | | 4 | 0.25, 0.25, 0.25, 0.25 | 0.25 + 0.25 = 0.5 | | 5 | 0.5, 0.25, 0.25 | 0.25 + 0.25 = 0.5 | | 6 | 0.5, 0.5 | 0.5 + 0.5 = 1 | | Symbol | $p_i$ | Huffman code | $l_i$ | |---|---|---|---| | S0 | 0.25 | 10 | 2 | | S1 | 0.25 | 11 | 2 | | S2 | 0.125 | 001 | 3 | | S3 | 0.125 | 010 | 3 | | S4 | 0.125 | 011 | 3 | | S5 | 0.0625 | 0000 | 4 | | S6 | 0.0625 | 0001 | 4 | **Entropy:** $$ \begin{aligned} H &= \sum p_i\log_2\frac{1}{p_i} = 2(0.25)(2) + 3(0.125)(3) + 2(0.0625)(4) \\ &= 1.0 + 1.125 + 0.5 = 2.625\ \text{bits/symbol} \end{aligned} $$ **Average code length:** $$ \bar L = 2(0.25)(2) + 3(0.125)(3) + 2(0.0625)(4) = 2.625\ \text{bits/symbol} $$ **Efficiency:** $$ \eta = \frac{H}{\bar L} = \frac{2.625}{2.625} = 100\% $$ The efficiency is 100 % because every probability is a negative power of 2 ($2^{-2}, 2^{-3}, 2^{-4}$), so each code length equals $\log_2(1/p_i)$ exactly. A fixed-length code would need 3 bits/symbol (efficiency $2.625/3 = 87.5\%$). **Answer:** S0, S1 get 2-bit codes, S2, S3, S4 get 3-bit codes and S5, S6 get 4-bit codes (as in the table); $\bar L = H = 2.625$ bits/symbol, efficiency 100 %. ## Check yourself The answer's key points as multiple-choice questions, with the correct option and why. 1. In the Huffman procedure, what is done at each reduction stage? A. Split the list into two groups of nearly equal total probability B. Combine the two lowest probabilities into one and reinsert the sum into the list C. Combine the two highest probabilities into one D. Assign a fixed 3-bit code to every symbol Answer: B. Huffman coding is bottom-up: the two smallest probabilities are merged and the sum is placed back in the sorted list until 1.0 remains. (Key point: Huffman procedure) 2. Why do S5 and S6 (p = 0.0625) get the longest codes of 4 bits? A. They are the most probable symbols B. They are the least probable, so they are merged first and sit deepest in the tree C. Because 0.0625 is not a power of 2 D. Because they come last alphabetically Answer: B. Rare symbols get long codes; here l = log2(1/0.0625) = 4 bits. (Key point: Code lengths) 3. What are the average code length and entropy for this source? A. L = 2.625 and H = 2.625 bits/symbol B. L = 3 and H = 2.625 bits/symbol C. L = 2.625 and H = 3 bits/symbol D. L = 2.5 and H = 2.625 bits/symbol Answer: A. L = 2(0.25)(2) + 3(0.125)(3) + 2(0.0625)(4) = 2.625, which equals H. (Key point: Average length and entropy) 4. Why is the Huffman efficiency exactly 100% here? A. Huffman coding is always 100% efficient B. All probabilities are negative powers of 2, so each length equals log2(1/p) C. There are exactly seven symbols D. The codes are fixed length Answer: B. When every p is 2^-k, the length l = log2(1/p) is an integer, so L = H. (Key point: 100% efficiency) ## 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 - [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; 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 - [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 - [Huffman code for five-symbol DMS vs fixed length](https://www.bctengineer.com/question.md?key=semester_6%2Fcommunication_systems%3Ahuffman-dms-five-symbols) — Communication Systems, chapter 6 - [Symbol rate, entropy and information rate (6 symbols per 10 μs)](https://www.bctengineer.com/question.md?key=semester_6%2Fcommunication_systems%3Asymbol-rate-six-symbols-10us) — Communication Systems, chapter 6 ## Related in other subjects - [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 - [Huffman code for p = 0.5, 0.25, 0.125, 0.125](https://www.bctengineer.com/question.md?key=semester_5%2Fdata_communication%3Ahuffman-p05-025-0125) — 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 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