Suppose the letters a, b, c, d, e, f have probabilities 1/2, 1/4, 1/8, 1/16,…

Solution: construct the Huffman tree by repeatedly combining the two least probable symbols.

1. Start with probabilities: a=1/2, b=1/4, c=1/8, d=1/16, e=1/32, f=1/32.

2. Combine e (1/32) + f (1/32) → ef (1/16).

3. Combine d (1/16) + ef (1/16) → def (1/8).

4. Combine c (1/8) + def (1/8) → cdef (1/4).

5. Combine b (1/4) + cdef (1/4) → bcdef (1/2).

6. Combine a (1/2) + bcdef (1/2) → root (1).

From this tree the codeword lengths are:

• a: length 1

• b: length 2

• c: length 3

• d: length 4

• e: length 5

• f: length 5

Compute the average code length L:

L = (1/2)*1 + (1/4)*2 + (1/8)*3 + (1/16)*4 + (1/32)*5 + (1/32)*5 = 31/16 = 1.9375

Therefore the average length of the Huffman codes is 1.9375.