--- title: "Huffman coding principle" subject: "Data Communication" chapter: 8 key: "semester_5/data_communication:huffman-principle" source: https://www.bctengineer.com/q/semester_5/data_communication/huffman-principle site: BCT Engineering --- # Huffman coding principle Data Communication · Chapter 8: Information Theory and Coding - Asked in: 2073 Shrawan, 4 marks; 2072 Kartik, 3 marks; 2071 Chaitra, 3 marks (asked 3 times) - Video: [3.4 Huffman Coding - Greedy Method](https://www.youtube.com/watch?v=co4_ahEDCho) — Abdul Bari - Answer checked by Claude Sonnet 5.5 on 2026-10-14 - Page: https://www.bctengineer.com/q/semester_5/data_communication/huffman-principle - Whole chapter: https://www.bctengineer.com/md/semester_5/data_communication/chapter-8 ## Question Explain the general working principle of the Huffman coding algorithm. ## Short answer Huffman coding assigns shorter variable-length prefix codes to more frequent symbols, minimizing average code length. The algorithm repeatedly merges the two least probable nodes, building a binary tree, then assigns 0/1 to branches. Example: probabilities 0.4,0.3,0.2,0.1 yield codes A=0, B=10, C=111, D=110 with average length 1.9 bits. ## Answer **Huffman coding** is a lossless source-coding method that assigns **variable-length prefix codes** to symbols, shorter codes to more probable symbols and longer codes to rare ones, so that the average code length is minimum and close to the entropy. #### Principle - A **prefix code** has no codeword that is a prefix of another, so decoding is instant and unambiguous. - Frequent symbols get short codes, so the average length L = Σ pᵢ lᵢ is minimised. Huffman's algorithm produces an optimal prefix code for given probabilities, with H ≤ L < H + 1. #### Algorithm 1. List the symbols with their probabilities (or frequencies). 2. Pick the two symbols with the smallest probabilities and merge them into a new node whose probability is the sum. 3. Repeat step 2 with the new node in the list until only one node (the root, probability 1) remains. 4. Label the two branches at each node 0 and 1. 5. Read the code for each symbol from the root down to its leaf. #### Small example A = 0.4, B = 0.3, C = 0.2, D = 0.1. ```text D(0.1)+C(0.2)=0.3 ; 0.3+B(0.3)=0.6 ; 0.6+A(0.4)=1 A=0 B=10 C=111 D=110 ``` L = 0.4(1) + 0.3(2) + 0.2(3) + 0.1(3) = 1.9 bits; H = 1.846 bits; efficiency = 97.2 %. #### Properties - Efficiency η = H / L. No other symbol-by-symbol code gives a smaller L. - Codes are not unique when ties occur, but L is the same. - The code table must be sent to the decoder (or both sides must know probabilities). - Used in JPEG, MP3, ZIP and fax. ## Check yourself The answer's key points as multiple-choice questions, with the correct option and why. 1. How does Huffman coding reduce the average code length? A. Gives all symbols equal-length codes B. Gives longer codes to more probable symbols C. Gives shorter codes to more probable symbols D. Adds parity bits to rare symbols Answer: C. Frequent symbols get short codes and rare ones get long codes, which minimises L = sum p_i l_i. (Key point: Variable-length prefix codes) 2. Why must a Huffman code be a prefix code? A. So that no codeword is a prefix of another and decoding is unambiguous B. So that all codewords have equal length C. So that the code table need not be sent D. So that the efficiency is exactly 100% Answer: A. With no codeword a prefix of another, the decoder can decide each symbol instantly without ambiguity. (Key point: Prefix property) 3. At each step of the algorithm, which nodes are merged? A. The two largest probabilities B. The largest and smallest probabilities C. Any two adjacent symbols in alphabetical order D. The two smallest probabilities Answer: D. Huffman repeatedly merges the two smallest probabilities into a node with their sum until one root of probability 1 remains. (Key point: Merging step) ## Related in Data Communication - [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 - [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 - [FHSS working principle](https://www.bctengineer.com/question.md?key=semester_5%2Fdata_communication%3Afhss-working) — Data Communication, chapter 6, asked 4× - [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 p = 0.6, 0.2, 0.1, 0.05, 0.05](https://www.bctengineer.com/question.md?key=semester_5%2Fdata_communication%3Ahuffman-p06-02-01) — Data Communication, chapter 8 - [Huffman code for five symbols (0.2, 0.35, ...)](https://www.bctengineer.com/question.md?key=semester_5%2Fdata_communication%3Ahuffman-five-symbols-02-035) — Data Communication, chapter 8 ## Related in other subjects - [Importance of source encoder; Huffman algorithm](https://www.bctengineer.com/question.md?key=semester_6%2Fcommunication_systems%3Asource-encoder-huffman-algorithm) — 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 - [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