Given the symbols A, B, C, D, E, F, G and H with the probabilities…
2015
Given the symbols A, B, C, D, E, F, G and H with the probabilities
\(\frac{1}{30}, \frac{1}{30}, \frac{1}{30}, \frac{2}{30}, \frac{3}{30}, \frac{5}{30}, \frac{5}{30} and \frac{12}{30}\) respectively. The average Huffman code size in bits per symbol is :
- A.
\(\frac{67}{30}\) - B.
\(\frac{70}{34}\) - C.
\(\frac{76}{30}\) - D.
\(\frac{78}{30}\)
Attempted by 129 students.
Show answer & explanation
Correct answer: C
Solution: Build the Huffman tree using integer weights obtained by multiplying probabilities by 30.
Weights (out of 30): [1, 1, 1, 2, 3, 5, 5, 12]
Combine 1 + 1 = 2 (two symbols of weight 1)
Combine remaining 1 + 2 = 3
Combine 2 + 3 = 5
Combine 3 + 5 = 8
Combine 5 + 5 = 10
Combine 8 + 10 = 18
Combine 12 + 18 = 30 (root)
From these merges the final code lengths (depths) are:
Symbols with weight 1: length 6
Symbol with weight 1 (third one): length 5
Weight 2: length 4
Weight 3: length 3
Weights 5 and 5: length 3 each
Weight 12: length 1
Compute the total weight × length:
1×6 + 1×6 + 1×5 + 2×4 + 3×3 + 5×3 + 5×3 + 12×1 = 76
Average code length = 76/30 ≈ 2.533 bits per symbol.
Answer: 76/30 bits per symbol.