A binary source emits 0 with probability 0.8 and 1 with probability 0.2, independently. Symbols are taken two at a time, each of the four pairs 00, 01, 10 and 11 is treated as one symbol, and they are encoded with a Huffman code. Which of the following is the average code length per original symbol?

Answer: B. 0.78 bits

The four pairs have probabilities 0.64 for 00, 0.16 for 01 and 10, and 0.04 for 11. 0.04 and 0.16 are merged into 0.2, 0.2 and 0.16 into 0.36, and finally that with 0.64, so the code lengths are 1, 2, 3 and 3 bits and the average per pair is 0.64 × 1 + 0.16 × 2 + 0.16 × 3 + 0.04 × 3 = 1.56 bits. Per original symbol this is 1.56 ÷ 2 = 0.78 bits. Coding one symbol at a time can only give 0 and 1 one bit each, but coding symbols together brings the length closer to the entropy of about 0.72 bits.

• A. About 0.72 bits is the entropy of this source, the lower bound of the average code length. Grouping only two symbols does not yet reach it.
• B. Correct. 1.56 ÷ 2 = 0.78 bits.
• C. 1 bit is the value when the symbols are coded one at a time. Coding binary symbols one at a time needs one bit for each.