--- title: "Huffman coding of \"Engineer Ko Betha Arulai Ke Thaha\"" subject: "Communication Systems" chapter: 6 key: "semester_6/communication_systems:huffman-engineer-ko-betha" source: https://www.bctengineer.com/q/semester_6/communication_systems/huffman-engineer-ko-betha site: BCT Engineering --- # Huffman coding of "Engineer Ko Betha Arulai Ke Thaha" Communication Systems · Chapter 6: Baseband Digital Data Transmission - Asked in: 2081 Chaitra, 7+2+3 marks - Video: [L-4.4: Huffman Coding Question in Greedy Technique | Imp Question for all competitive exams](https://www.youtube.com/watch?v=ocFO1rmh4Zc) — Gate Smashers - Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14 - Page: https://www.bctengineer.com/q/semester_6/communication_systems/huffman-engineer-ko-betha - Whole chapter: https://www.bctengineer.com/md/semester_6/communication_systems/chapter-6 ## Question Encode "Engineer Ko Betha Arulai Ke Thaha" using Huffman Encoder and calculate the transmission efficiency. Find the codeword if the message is received as "Engineer Ko Betha Ke Ke". ## Short answer Huffman coding on 33 symbols gives entropy 3.542 bits/symbol, average length 3.576 bits/symbol, efficiency 99.05%. For 'Engineer Ko Betha Ke Ke', substitute symbols from code table: e=000, n=1010, g=01110, i=1100, etc., producing a 83‑bit codeword. ## Answer **Assumptions:** upper and lower case are treated as the same letter, and the space is counted as a symbol because it must also be sent. The message "engineer ko betha arulai ke thaha" has **33 symbols**, with **14 distinct symbols**. #### Huffman encoding **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. Merge steps (weights are counts out of 33): 1. {g} (1) + {b} (1) → 2 2. {o} (1) + {l} (1) → 2 3. {i} (2) + {u} (1) → 3 4. {n} (2) + {k} (2) → 4 5. {t} (2) + {r} (2) → 4 6. {o, l} (2) + {g, b} (2) → 4 7. {i, u} (3) + {h} (3) → 6 8. {t, r} (4) + {n, k} (4) → 8 9. {space} (5) + {o, l, g, b} (4) → 9 10. {e} (5) + {a} (5) → 10 11. {t, r, n, k} (8) + {i, u, h} (6) → 14 12. {e, a} (10) + {space, o, l, g, b} (9) → 19 13. {e, a, space, o, l, g, b} (19) + {t, r, n, k, i, u, h} (14) → 33 | Symbol | Count | $p_i$ | Code | $l_i$ | $p_i l_i$ | |---|---|---|---|---|---| | space | 5 | 5/33 = 0.1515 | 010 | 3 | 0.4545 | | a | 5 | 5/33 = 0.1515 | 001 | 3 | 0.4545 | | e | 5 | 5/33 = 0.1515 | 000 | 3 | 0.4545 | | h | 3 | 3/33 = 0.0909 | 111 | 3 | 0.2727 | | i | 2 | 2/33 = 0.0606 | 1100 | 4 | 0.2424 | | k | 2 | 2/33 = 0.0606 | 1011 | 4 | 0.2424 | | n | 2 | 2/33 = 0.0606 | 1010 | 4 | 0.2424 | | r | 2 | 2/33 = 0.0606 | 1001 | 4 | 0.2424 | | t | 2 | 2/33 = 0.0606 | 1000 | 4 | 0.2424 | | b | 1 | 1/33 = 0.0303 | 01111 | 5 | 0.1515 | | g | 1 | 1/33 = 0.0303 | 01110 | 5 | 0.1515 | | l | 1 | 1/33 = 0.0303 | 01101 | 5 | 0.1515 | | o | 1 | 1/33 = 0.0303 | 01100 | 5 | 0.1515 | | u | 1 | 1/33 = 0.0303 | 1101 | 4 | 0.1212 | **Average code length:** $$ \bar L = \sum p_i l_i = \frac{118}{33} = 3.5758\ \text{bits/symbol} $$ Here the numerator is the total number of bits in the encoded message: $5(3) + 5(3) + 5(3) + 3(3) + 2(4) + 2(4) + 2(4) + 2(4) + 2(4) + 1(5) + 1(5) + 1(5) + 1(5) + 1(4) = 118$ bits. **Entropy:** $$ H = -\sum p_i \log_2 p_i = 3.5419\ \text{bits/symbol} $$ **Efficiency:** $$ \eta = \frac{H}{\bar L} = \frac{3.5419}{3.5758} = 0.9905 = 99.05\% $$ **Redundancy** $= 1 - \eta = 0.95\%$. A fixed-length code for 14 symbols needs $\lceil \log_2 14 \rceil = 4$ bits/symbol ($\eta = 88.55\%$). Huffman saves 10.61% of the bits. **Answer: average length = 3.576 bits/symbol, entropy = 3.542 bits/symbol, transmission efficiency η ≈ 99.05%.** #### Codeword for the received message "Engineer Ko Betha Ke Ke" Each character (including the 4 spaces) is replaced by its code from the table above: | Part | Code | |---|---| | engineer | 000 1010 01110 1100 1010 000 000 1001 | | space | 010 | | ko | 1011 01100 | | space | 010 | | betha | 01111 000 1000 111 001 | | space | 010 | | ke | 1011 000 | | space | 010 | | ke | 1011 000 | Full codeword (83 bits for 23 characters): ```text 000 1010 01110 1100 1010 000 000 1001 010 1011 01100 010 01111 000 1000 111 001 010 1011 000 010 1011 000 ``` The Huffman code is a prefix code, so the receiver can decode this bit stream without separators. ## Check yourself The answer's key points as multiple-choice questions, with the correct option and why. 1. How is a Huffman code built? A. Repeatedly combine the two least probable entries into one node, until one node remains B. Repeatedly combine the two most probable entries C. Assign equal-length codes to all symbols D. Sort symbols alphabetically and assign binary counts Answer: A. Merging the two least probable entries gives the shortest codes to the most frequent symbols. (Key point: Huffman procedure) 2. The encoded 33-symbol message uses 118 bits in total. What is the average code length? A. 4 bits/symbol B. 3.576 bits/symbol C. 3.542 bits/symbol D. 118 bits/symbol Answer: B. L = 118/33 = 3.5758 bits/symbol. (Key point: Average length) 3. Given H = 3.5419 and average length 3.5758 bits/symbol, what is the efficiency? A. About 88.55% B. About 100% C. About 99.05% D. About 95% Answer: C. Efficiency = H/L = 3.5419/3.5758 = 0.9905. A fixed 4-bit code would give only 88.55%. (Key point: Efficiency) 4. Why can the received Huffman bit stream be decoded without separators? A. Spaces mark each symbol B. Huffman is a prefix code, so no codeword begins another C. All codes have the same length D. Each codeword ends with 0 Answer: B. No codeword is a prefix of another, so the decoder can read symbols one by one from the stream. (Key point: Prefix property) ## 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 - [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 - [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 - [Huffman coding of "Mississippi is missing"](https://www.bctengineer.com/question.md?key=semester_6%2Fcommunication_systems%3Ahuffman-mississippi) — Communication Systems, chapter 6 - [Huffman and Shannon-Fano coding of A0–A4](https://www.bctengineer.com/question.md?key=semester_6%2Fcommunication_systems%3Ahuffman-sf-a0-a4-compare) — Communication Systems, chapter 6 - [Source coding aim; Huffman "Kun Mandir Ma Janchhau Yatri"](https://www.bctengineer.com/question.md?key=semester_6%2Fcommunication_systems%3Ahuffman-kun-mandir) — Communication Systems, chapter 6 ## Related in other subjects - [Huffman code for a sentence (Phool ko)](https://www.bctengineer.com/question.md?key=semester_5%2Fdata_communication%3Ahuffman-phool-ko) — Data Communication, chapter 8 - [Dataword vs codeword; error coding techniques](https://www.bctengineer.com/question.md?key=semester_5%2Fdata_communication%3Adataword-codeword-error-coding) — Data Communication, chapter 8 - [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 - [Line coding: properties; encode 01001100011](https://www.bctengineer.com/question.md?key=semester_5%2Fdata_communication%3Aline-coding-01001100011) — Data Communication, chapter 5