--- title: "Huffman coding of a sentence (Khoji Rahechha)" subject: "Data Communication" chapter: 8 key: "semester_5/data_communication:huffman-khoji-rahechha" source: https://www.bctengineer.com/q/semester_5/data_communication/huffman-khoji-rahechha site: BCT Engineering --- # Huffman coding of a sentence (Khoji Rahechha) Data Communication · Chapter 8: Information Theory and Coding - Asked in: 2079 Baisakh, 10 marks - Video: [Huffman Coding Technique for binary system.](https://www.youtube.com/watch?v=EPtWCVSZqi8) — WIT Solapur - Professional Learning Community - Answer checked by Claude Sonnet 5.5 on 2026-10-14 - Page: https://www.bctengineer.com/q/semester_5/data_communication/huffman-khoji-rahechha - Whole chapter: https://www.bctengineer.com/md/semester_5/data_communication/chapter-8 ## Question Calculate coding efficiency of "Khoji Rahechha Desh Le Yek Yug Nayak" using Huffman coding technique. ## Short answer Count letter frequencies, build Huffman tree, assign codes. Entropy H = 3.6696 bits/symbol, average length L = 3.7000 bits/symbol. Efficiency η = H/L ≈ 99.2%. ## Answer **Assumptions:** spaces are ignored, upper and lower case letters are treated as the same symbol, and each letter is a source symbol. The sentence has **30 letters** and **16 distinct symbols**. #### Step 1: frequencies h=5, a=4, e=4, k=3, y=3, c=1, d=1, g=1, i=1, j=1, l=1, n=1, o=1, r=1, s=1, u=1 #### Step 2: build the Huffman tree Repeatedly merge the two smallest weights (N1, N2, ... are the new nodes): ```text 1. c(1) + d(1) = 2 -> N1 2. g(1) + i(1) = 2 -> N2 3. j(1) + l(1) = 2 -> N3 4. n(1) + o(1) = 2 -> N4 5. r(1) + s(1) = 2 -> N5 6. u(1) + N1(2) = 3 -> N6 7. N2(2) + N3(2) = 4 -> N7 8. N4(2) + N5(2) = 4 -> N8 9. k(3) + y(3) = 6 -> N9 10. N6(3) + a(4) = 7 -> N10 11. e(4) + N7(4) = 8 -> N11 12. N8(4) + h(5) = 9 -> N12 13. N9(6) + N10(7) = 13 -> N13 14. N11(8) + N12(9) = 17 -> N14 15. N13(13) + N14(17) = 30 -> N15 ``` The branch to the smaller-weight node is labelled 0 and to the larger 1, and the codes are read from the root downwards. #### Step 3: code table | Symbol | Count | p | Code | Length | |---|---|---|---|---| | h | 5 | 5/30 | 111 | 3 | | a | 4 | 4/30 | 011 | 3 | | e | 4 | 4/30 | 100 | 3 | | k | 3 | 3/30 | 000 | 3 | | y | 3 | 3/30 | 001 | 3 | | c | 1 | 1/30 | 01010 | 5 | | d | 1 | 1/30 | 01011 | 5 | | g | 1 | 1/30 | 10100 | 5 | | i | 1 | 1/30 | 10101 | 5 | | j | 1 | 1/30 | 10110 | 5 | | l | 1 | 1/30 | 10111 | 5 | | n | 1 | 1/30 | 11000 | 5 | | o | 1 | 1/30 | 11001 | 5 | | r | 1 | 1/30 | 11010 | 5 | | s | 1 | 1/30 | 11011 | 5 | | u | 1 | 1/30 | 0100 | 4 | #### Step 4: entropy, average length and efficiency - Entropy H = −Σ p log₂ p = **3.6696 bits/symbol** - Average length L = Σ p·l = 111/30 = **3.7000 bits/symbol** - Efficiency η = H / L = 3.6696 / 3.7000 = **99.18 %** - Total bits with Huffman = 111; with fixed-length codes (4 bits/symbol) = 120, so saving = 9 bits. (Huffman codes are not unique when weights tie, but every choice gives the same average length and efficiency.) **Answer: η ≈ 99.2 %** ## Check yourself The answer's key points as multiple-choice questions, with the correct option and why. 1. How is the sentence treated before building the Huffman tree? A. Spaces are coded as symbols and case is distinguished B. Spaces are ignored, case is ignored, each letter is a symbol (30 letters, 16 distinct) C. Each word is a symbol D. Only vowels are counted Answer: B. The answer ignores spaces and case, giving 30 letters and 16 distinct symbols. (Key point: Assumptions and symbol count) 2. With the code lengths found (5 symbols of length 3, 1 of length 4, 10 of length 5), what is the average length L? A. 111/30 = 3.70 bits/symbol B. 4.00 bits/symbol C. 120/30 = 4.00 bits/symbol D. 3.67 bits/symbol Answer: A. Total bits = 111 over 30 letters, so L = 3.70 bits/symbol. (Key point: Average length) 3. How is coding efficiency computed? A. L / H B. H x L C. H / L, with H = 3.6696 and L = 3.70 giving about 99.2% D. 1 - L Answer: C. Efficiency is entropy divided by average length: 3.6696/3.7000 = 99.18%. (Key point: Efficiency formula) 4. Why is 4 bits per symbol the fixed-length alternative for 16 symbols? A. Because 16 = 2^4 B. Because there are 30 letters C. Because the longest Huffman code is 5 D. Because H is about 4 Answer: A. 16 distinct symbols need log2(16) = 4 bits, giving 120 bits versus 111 with Huffman. (Key point: Comparison with fixed length) ## Related in Data Communication - [Huffman code for a sentence (Kun Mandir)](https://www.bctengineer.com/question.md?key=semester_5%2Fdata_communication%3Ahuffman-kun-mandir) — Data Communication, chapter 8 - [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 - [Huffman coding principle](https://www.bctengineer.com/question.md?key=semester_5%2Fdata_communication%3Ahuffman-principle) — Data Communication, chapter 8, asked 3× - [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 - [Huffman code for symbols A0 to A4](https://www.bctengineer.com/question.md?key=semester_5%2Fdata_communication%3Ahuffman-a0-a4) — 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 ## Related in other subjects - [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 - [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