--- title: "Huffman coding of \"Mississippi is missing\"" subject: "Communication Systems" chapter: 6 key: "semester_6/communication_systems:huffman-mississippi" source: https://www.bctengineer.com/q/semester_6/communication_systems/huffman-mississippi site: BCT Engineering --- # Huffman coding of "Mississippi is missing" Communication Systems · Chapter 6: Baseband Digital Data Transmission - Asked in: 2080 Chaitra, 8 marks - Video: [3.4 Huffman Coding - Greedy Method](https://www.youtube.com/watch?v=co4_ahEDCho) — Abdul Bari - Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14 - Page: https://www.bctengineer.com/q/semester_6/communication_systems/huffman-mississippi - Whole chapter: https://www.bctengineer.com/md/semester_6/communication_systems/chapter-6 ## Question Encode the message "Mississippi is missing" using weighted Huffman code and calculate transmission efficiency. ## Short answer For 'Mississippi is missing', counts: i=7, s=7, space=2, m=2, p=2, g=1, n=1. Huffman tree yields average length 2.455 bits/symbol, entropy 2.400 bits/symbol, efficiency 97.79%. Total message encoded in 54 bits vs 66 bits with fixed 3‑bit code. ## Answer **Weighted Huffman coding** builds the Huffman tree from the actual symbol counts (weights) in the message. **Assumptions:** case is ignored, and the space is counted as a symbol. The message "mississippi is missing" has **22 symbols** and **7 distinct symbols**: i = 7, s = 7, space = 2, m = 2, p = 2, g = 1, n = 1. #### Huffman tree construction **Huffman procedure:** list the symbols by probability. Repeatedly combine the two least probable entries into one node whose weight is their sum, until only one node is left. In each merge, the first group listed gets bit **0** and the second group gets bit **1**. Each symbol's code word is read from the root down to that symbol. 1. {n} (1) + {g} (1) → 2 2. {m} (2) + {space} (2) → 4 3. {n, g} (2) + {p} (2) → 4 4. {n, g, p} (4) + {m, space} (4) → 8 5. {s} (7) + {i} (7) → 14 6. {s, i} (14) + {n, g, p, m, space} (8) → 22 ```text (22) 0 / \ 1 (14) (8) 0/ \1 0/ \1 s:7 i:7 (4) (4) 0/ \1 0/ \1 (2) p:2 m:2 sp:2 0/ \1 n:1 g:1 ``` #### Code table | Symbol | Count | $p_i$ | Code | $l_i$ | $p_i l_i$ | |---|---|---|---|---|---| | i | 7 | 7/22 = 0.3182 | 01 | 2 | 0.6364 | | s | 7 | 7/22 = 0.3182 | 00 | 2 | 0.6364 | | space | 2 | 2/22 = 0.0909 | 111 | 3 | 0.2727 | | m | 2 | 2/22 = 0.0909 | 110 | 3 | 0.2727 | | p | 2 | 2/22 = 0.0909 | 101 | 3 | 0.2727 | | g | 1 | 1/22 = 0.0455 | 1001 | 4 | 0.1818 | | n | 1 | 1/22 = 0.0455 | 1000 | 4 | 0.1818 | #### Efficiency **Average code length:** $$ \bar L = \sum p_i l_i = \frac{54}{22} = 2.4545\ \text{bits/symbol} $$ Here the numerator is the total number of bits in the encoded message: $7(2) + 7(2) + 2(3) + 2(3) + 2(3) + 1(4) + 1(4) = 54$ bits. **Entropy:** $$ H = -\sum p_i \log_2 p_i = 2.4002\ \text{bits/symbol} $$ **Efficiency:** $$ \eta = \frac{H}{\bar L} = \frac{2.4002}{2.4545} = 0.9779 = 97.79\% $$ **Redundancy** $= 1 - \eta = 2.21\%$. A fixed-length code for 7 symbols needs $\lceil \log_2 7 \rceil = 3$ bits/symbol ($\eta = 80.01\%$). Huffman saves 18.18% of the bits. **Answer: $\bar L = 2.455$ bits/symbol, $H = 2.400$ bits/symbol, transmission efficiency η ≈ 97.79%. The whole message takes 54 bits, compared with 66 bits using a 3-bit fixed code.** ## Check yourself The answer's key points as multiple-choice questions, with the correct option and why. 1. In building a Huffman tree, which entries are combined at each step? A. Any two entries with equal counts only B. The two least probable entries C. The two most probable entries D. The most and least probable entries Answer: B. Huffman repeatedly merges the two least probable entries into a node whose weight is their sum, so rare symbols end up deepest with the longest codes. (Key point: Huffman merging rule) 2. How many symbols does 'mississippi is missing' contain (case ignored, space counted), and how many are distinct? A. 20 symbols, 6 distinct B. 22 symbols, 5 distinct C. 21 symbols, 7 distinct D. 22 symbols, 7 distinct Answer: D. The message has 22 symbols including 2 spaces, and the distinct symbols are i, s, space, m, p, g, n, which is 7. (Key point: Symbol counts) 3. Using code lengths i=2, s=2, space=3, m=3, p=3, g=4, n=4 with counts 7,7,2,2,2,1,1, what is the total number of bits for the message? A. 54 bits B. 48 bits C. 60 bits D. 66 bits Answer: A. 7(2)+7(2)+2(3)+2(3)+2(3)+1(4)+1(4) = 54 bits, so average length is 54/22 = 2.4545 bits/symbol. (Key point: Average length) 4. How is transmission efficiency computed here, and what is its value? A. 1 - L/H = 2.21% B. H/log2(7) = 85% C. L/H = 102% D. H/L = 97.79% Answer: D. Efficiency is entropy divided by average code length: 2.4002/2.4545 = 97.79%. Redundancy is the remaining 2.21%. (Key point: Efficiency) ## Related in Communication Systems - [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 - [Information rate and coding efficiency: BCD vs Huffman](https://www.bctengineer.com/question.md?key=semester_6%2Fcommunication_systems%3Abcd-source-info-rate-huffman) — Communication Systems, chapter 6 - [Huffman coding of "Engineer Ko Betha Arulai Ke Thaha"](https://www.bctengineer.com/question.md?key=semester_6%2Fcommunication_systems%3Ahuffman-engineer-ko-betha) — 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 - [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 - [Weighted Huffman encoding and decoding](https://www.bctengineer.com/question.md?key=semester_5%2Fdata_communication%3Ahuffman-jasta-lai) — Data Communication, chapter 8 - [Huffman code for eight symbols (1/2 ... 1/128)](https://www.bctengineer.com/question.md?key=semester_5%2Fdata_communication%3Ahuffman-eight-symbols) — Data Communication, chapter 8 - [Line coding: properties; encode 01001100011](https://www.bctengineer.com/question.md?key=semester_5%2Fdata_communication%3Aline-coding-01001100011) — Data Communication, chapter 5 - [Huffman coding of a sentence (Khoji Rahechha)](https://www.bctengineer.com/question.md?key=semester_5%2Fdata_communication%3Ahuffman-khoji-rahechha) — Data Communication, chapter 8