ITPEC FE Morning October 2023 Question 6
There is communication data that consists of five characters “A”, “B”, “C”, “D”, and “E” that have different appearance frequencies, and in order to compress the data by using Huffman coding, the code table shown below is created. Which of the following is an appropriate code that should be inserted in the blank?
Explanation
110 — a Huffman code is prefix-free, and 110 is the only candidate that no existing code begins, and that begins no existing code.
The codes already assigned are A = 00, B = 01, C = 10 and E = 111. A 3-bit code for D must not start with 00, 01 or 10, or the decoder could not tell D from A, B or C after two bits. So D starts with 11, and since 111 is taken by E, D = 110.
This matches the Huffman tree: the two rarest characters, D (13%) and E (12%), are merged first and become siblings with the longest codes, 110 and 111.
Answer (d)
Why not others:
- •(a) 001 — begins with A's code 00, so the prefix property fails
- •(b) 010 — begins with B's code 01
- •(c) 101 — begins with C's code 10
Key rule: In a prefix-free code no codeword is the start of another; the two least frequent symbols end up as siblings that differ only in their last bit.
Basic Theory · AI-written, may contain errors
This question comes from an official ITPEC past paper. ITPEC Practice is an independent study tool and is not affiliated with ITPEC. See the official FE past-paper collection or Report an issue.