Answer to Question #322795 in Discrete Mathematics for Alamanda

Question

Use Huffman coding to encode these symbols with given frequencies:

a: 0.20, b: 0.10, c: 0.15, d: 0.25, e: 0.30.

What is the average number of bits required to encode a character?

(12 Marks)

Answer 1

1. Sort symbols in order of descending frequencies
2. Unite symbols with lowest frequencies
3. Repeat steps 1,2 until all symbols are united in one

1. Go from right to left of the table.
2. Separate the groups of symbols, and place the group with higher frequency to the left (0), group with lower frequency to the right (1)

Write the code of each symbol beginning from the root of the tree. Then average length is

$\sum l_i w_i =2.25$ , where $l_i$ is length of code, $w_i$ is frequency.