--- title: "Source coding aim; Huffman \"Kun Mandir Ma Janchhau Yatri\"" subject: "Communication Systems" chapter: 6 key: "semester_6/communication_systems:huffman-kun-mandir" source: https://www.bctengineer.com/q/semester_6/communication_systems/huffman-kun-mandir site: BCT Engineering --- # Source coding aim; Huffman "Kun Mandir Ma Janchhau Yatri" Communication Systems · Chapter 6: Baseband Digital Data Transmission - Asked in: 2079 Chaitra, 10 marks - Video: [Huffman Coding | Lecture 6| Information Theory & Coding Technique| ITCCN](https://www.youtube.com/watch?v=yVG4FnH3Rc8) — Dr. Sarika Panwar - Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14 - Page: https://www.bctengineer.com/q/semester_6/communication_systems/huffman-kun-mandir - Whole chapter: https://www.bctengineer.com/md/semester_6/communication_systems/chapter-6 ## Question What is the aim of source coding? Encode "Kun Mandir Ma Janchhau Yatri" using Huffman codes and find its efficiency. ## Short answer Source coding aims to compress data by removing redundancy, using short codes for frequent symbols to reduce average bit rate while allowing exact recovery. Huffman coding of the phrase yields average length 3.607 bits/symbol, entropy 3.580 bits/symbol, and efficiency 99.25%. ## Answer #### Aim of source coding **Source coding** represents the output of an information source with as few bits as possible, while still allowing the receiver to recover it exactly (lossless coding) or acceptably (lossy coding). Its aims are: - **Remove redundancy:** give short code words to frequent symbols and long ones to rare symbols, so the average code length $\bar L$ approaches the entropy $H$ (Shannon's source coding theorem: $\bar L \ge H$). - **Raise efficiency** $\eta = H/\bar L$ towards 100%. - **Lower the bit rate**, which saves bandwidth, storage and transmission power. - Produce a **uniquely decodable** (prefix) code so the receiver can decode it without separators. Examples are Huffman, Shannon–Fano and LZW coding, as well as speech and image compression. #### Huffman coding of "Kun Mandir Ma Janchhau Yatri" **Assumptions:** case is ignored, and the space is counted as a symbol. The message has **28 symbols** and **14 distinct symbols**. **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: 1. {d} (1) + {c} (1) → 2 2. {k} (1) + {j} (1) → 2 3. {y} (1) + {t} (1) → 2 4. {i} (2) + {h} (2) → 4 5. {r} (2) + {m} (2) → 4 6. {d, c} (2) + {u} (2) → 4 7. {y, t} (2) + {k, j} (2) → 4 8. {space} (4) + {n} (3) → 7 9. {r, m} (4) + {i, h} (4) → 8 10. {y, t, k, j} (4) + {d, c, u} (4) → 8 11. {space, n} (7) + {a} (5) → 12 12. {y, t, k, j, d, c, u} (8) + {r, m, i, h} (8) → 16 13. {y, t, k, j, d, c, u, r, m, i, h} (16) + {space, n, a} (12) → 28 | Symbol | Count | $p_i$ | Code | $l_i$ | $p_i l_i$ | |---|---|---|---|---|---| | a | 5 | 5/28 = 0.1786 | 11 | 2 | 0.3571 | | space | 4 | 4/28 = 0.1429 | 100 | 3 | 0.4286 | | n | 3 | 3/28 = 0.1071 | 101 | 3 | 0.3214 | | h | 2 | 2/28 = 0.0714 | 0111 | 4 | 0.2857 | | i | 2 | 2/28 = 0.0714 | 0110 | 4 | 0.2857 | | m | 2 | 2/28 = 0.0714 | 0101 | 4 | 0.2857 | | r | 2 | 2/28 = 0.0714 | 0100 | 4 | 0.2857 | | u | 2 | 2/28 = 0.0714 | 0011 | 4 | 0.2857 | | c | 1 | 1/28 = 0.0357 | 00101 | 5 | 0.1786 | | d | 1 | 1/28 = 0.0357 | 00100 | 5 | 0.1786 | | j | 1 | 1/28 = 0.0357 | 00011 | 5 | 0.1786 | | k | 1 | 1/28 = 0.0357 | 00010 | 5 | 0.1786 | | t | 1 | 1/28 = 0.0357 | 00001 | 5 | 0.1786 | | y | 1 | 1/28 = 0.0357 | 00000 | 5 | 0.1786 | **Average code length:** $$ \bar L = \sum p_i l_i = \frac{101}{28} = 3.6071\ \text{bits/symbol} $$ Here the numerator is the total number of bits in the encoded message: $5(2) + 4(3) + 3(3) + 2(4) + 2(4) + 2(4) + 2(4) + 2(4) + 1(5) + 1(5) + 1(5) + 1(5) + 1(5) + 1(5) = 101$ bits. **Entropy:** $$ H = -\sum p_i \log_2 p_i = 3.5801\ \text{bits/symbol} $$ **Efficiency:** $$ \eta = \frac{H}{\bar L} = \frac{3.5801}{3.6071} = 0.9925 = 99.25\% $$ **Redundancy** $= 1 - \eta = 0.75\%$. A fixed-length code for 14 symbols needs $\lceil \log_2 14 \rceil = 4$ bits/symbol ($\eta = 89.50\%$). Huffman saves 9.82% of the bits. **Answer: $\bar L = 3.607$ bits/symbol, $H = 3.580$ bits/symbol, efficiency η ≈ 99.25%. The message needs 101 bits instead of 112 bits with a 4-bit fixed code.** ## Check yourself The answer's key points as multiple-choice questions, with the correct option and why. 1. What is the main aim of source coding? A. Represent the source output with as few bits as possible while allowing recovery B. Increase the bandwidth of the signal C. Add parity bits to correct errors D. Make the signal immune to noise Answer: A. Source coding removes redundancy so the average code length approaches the entropy, lowering the bit rate. (Key point: Aim of source coding) 2. What does Shannon's source coding theorem say about average code length? A. L is at least H B. L is independent of H C. L equals 2H D. L is less than or equal to H Answer: A. No uniquely decodable code can have average length below the entropy: L >= H. Huffman gets close to H. (Key point: Source coding theorem) 3. The 28-symbol message with 14 distinct symbols has a Huffman code totalling how many bits? A. 108 bits B. 112 bits C. 101 bits D. 98 bits Answer: C. Summing count x length gives 101 bits, so average length = 101/28 = 3.607 bits/symbol. A 4-bit fixed code would need 112 bits. (Key point: Total bits) 4. Given H = 3.5801 and average length 3.6071 bits/symbol, what is the efficiency? A. 96.5% B. 89.50% C. 100.75% D. 99.25% Answer: D. Efficiency = H/L = 3.5801/3.6071 = 0.9925, i.e. 99.25%, with 0.75% redundancy. (Key point: 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 - [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 - [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 - [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 ## Related in other subjects - [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 - [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 - [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