Question

Related to Optimal Huffman Codes

Construct a Huffman code for the symbols a through g, listed below together with their probabilities. Then determine the expected length of your resulting code!

            a 1/40    b 2/40    c 3/40    d 4/40    e 5/40    f 6/40    g 6/40    h 13/40

Answer 1

Here are the probabilities in increasing order

a = 1/40

b = 2/40

c = 3 /40

d = 4/40

e = 5/40

f = 6/40

g = 6/40

h = 13/40

The Huffman Tree is

Codes are

a = 1111110 ( 7 bits)

b = 1111111 ( 7 bits)

c = 111110 ( 6 bits)

d = 11110 ( 5 bits)

e = 1110 ( 4 bits)

f = 110 ( 3 bits)

g = 10 ( 2 bits)

h = 0 ( 1 bit)

Average number of bits = 7*1/40 + 7*2/40 + 6*3/40 + 5*4/40 + 4*5/40 + 3*6/40 + 2*6/40 + 1*13/40

= 7/40 + 14/40 + 18/40 + 20/40 + 20/40 + 18/40 + 12/40 + 13/40

= 3.05 bit/char

Please don't forget to give a positive rating to the answer. Your rating motivates experts to help other students also. Thank you :)