A source emits the symbols A to E independently with probabilities 0.3, 0.25, 0.2, 0.15 and 0.1, and it is encoded with a Huffman code. The codewords may change depending on which of two equal probabilities is chosen first, but the average code length does not. Which of the following is the average code length per symbol?

Answer: A. 2.25 bits

First 0.1 and 0.15 are merged into 0.25, then 0.2 and 0.25 into 0.45, the remaining 0.25 and 0.3 into 0.55, and finally 0.45 and 0.55. The code lengths are 2 bits for A, B and C and 3 bits for D and E, and the average code length is (0.3 + 0.25 + 0.2) × 2 + (0.15 + 0.1) × 3 = 1.5 + 0.75 = 2.25 bits. For a source whose probabilities are not strongly skewed, a code with nearly equal lengths is shorter than one with stepped lengths such as 1, 2, 3, 4, 4.

• A. Correct. With code lengths 2, 2, 2, 3, 3 the average is 2.25 bits.
• B. 2.4 bits is the value when the code lengths are assigned in steps as 1, 2, 3, 4, 4. A prefix code can be built with them, but it is not optimal for these probabilities.
• C. 3 bits is the code length of a fixed-length code that represents the five symbols with equal lengths.