Suppose the letters a, b, c, d, e, f have probabilities 1/2, 1/4, 1/8, 1/16,…
2007
Suppose the letters a, b, c, d, e, f have probabilities 1/2, 1/4, 1/8, 1/16, 1/32, 1/32 respectively. Which of the following is the Huffman code for the letter a, b, c, d, e, f?
- A.
0, 10, 110, 1110, 11110, 11111
- B.
11, 10, 011, 010, 001, 000
- C.
11, 10, 01, 001, 0001, 0000
- D.
110, 100, 010, 000, 001, 111
Attempted by 116 students.
Show answer & explanation
Correct answer: A
Huffman coding steps:
Combine e (1/32) and f (1/32) → EF with weight 1/16.
Combine d (1/16) and EF (1/16) → DEF with weight 1/8.
Combine c (1/8) and DEF (1/8) → CDEF with weight 1/4.
Combine b (1/4) and CDEF (1/4) → BCDEF with weight 1/2.
Combine a (1/2) and BCDEF (1/2) → root with weight 1.
Final codes:
a → 0
b → 10
c → 110
d → 1110
e → 11110
f → 11111
Average code length: 1/2*1 + 1/4*2 + 1/8*3 + 1/16*4 + 1/32*5 + 1/32*5 = 1.9375 bits.
A video solution is available for this question — log in and enroll to watch it.