Consider a source with symbols A, B, C, D with probabilities 1/2, 1/4, 1/8,…
2016
Consider a source with symbols A, B, C, D with probabilities 1/2, 1/4, 1/8, 1/8 respectively. What is the average number of bits per symbol for the Huffman code generated from above information ?
- A.
2 bits per symbol
- B.
1.75 bits per symbol
- C.
1.50 bits per symbol
- D.
1.25 bits per symbol
Attempted by 256 students.
Show answer & explanation
Correct answer: B
Answer: 1.75 bits per symbol.
Huffman tree construction:
Combine symbols C and D (each with probability 1/8) to form a node with probability 1/4.
Combine symbol B (probability 1/4) with the CD node (probability 1/4) to form a node with probability 1/2.
Combine symbol A (probability 1/2) with the BCD node (probability 1/2) to form the root.
From this tree the codeword lengths are: A = 1, B = 2, C = 3, D = 3.
Compute the average code length L = sum(p_i * l_i):
0.5 * 1 = 0.5
0.25 * 2 = 0.5
0.125 * 3 = 0.375
0.125 * 3 = 0.375
Total L = 0.5 + 0.5 + 0.375 + 0.375 = 1.75 bits per symbol.
Huffman coding is optimal for these symbol probabilities, so 1.75 is the minimum average number of bits per symbol achievable with a prefix code.