huffman coding

Question

Assume that letters p, q, r, s, t and q have probabilities 1/2, 1/4, 1/8, 1/16, 1/32 and 1/32 respectively. The difference in the average length of the message without and with using Huffman’s coding is ______ . (upto 2 decimal places)

Comments

Using huffman tree, avg length = (1/2)*1 + (1/4)*2 + (1/8)*3 + (1/16)*4 + (1/32 )*5 + (1/32)*5 = 1.9375

here 6 letters are use hence without huffman we can represent each letter using 3 bits.

(1/2 + 1/4 + 1/8 + 1/16 + 1/32 + 1/32)*3 = 1*3 = 3

 

Hence difference = 3-1.93 = 1.07