Question

Use Huffman coding to encode these symbols with givenfrequencies: 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?

Short answer

a: 11; b: 101; c: 100; d: 01; e: 00;

The average number of bits required is2.25 bits.

Step-by-step solution

Firstly, draw a forest of 5 trees containing one vertex while each are labelled as follows:

First draw a forest of 5 trees,

\(\begin{array}{l}\,\,\,\,\,{\bf{a}}\,\,\,\,\,\,\,\,\,\,\,\,{\bf{b}}\,\,\,\,\,\,\,\,\,\,\,\,{\bf{c}}\,\,\,\,\,\,\,\,\,\,\,\,\,{\bf{d}}\,\,\,\,\,\,\,\,\,\,\,{\bf{e}}\\{\bf{0}}{\bf{.20}}\,\,\,\,\,{\bf{0}}{\bf{.10}}\,\,\,\,\,{\bf{0}}{\bf{.15}}\,\,\,\,\,{\bf{0}}{\bf{.25}}\,\,\,\,\,{\bf{0}}{\bf{.25}}\end{array}\)

Combine two trees having the least weight into a single tree. note that b and c have the smallest labels. replace their trees with a new tree that has a root with an edge to the left child is labelled as 0 and an edge to the right child labelled as 1.

As c has highest label value than 1), so the left child is named as c and the right child is named as b.

The sum of the labels of the trees that were replaced is:

The smallest labels are a, b+c, and d.

Now choose a and d, replace a and d trees with a new tree that has a root with a left child labeled as 0 and right child labeled as 1.

As d has highest label value than a. so the left child is named as d and the right child is named as a.

Now the smallest labels are b+c and e.

Replace b+ c and e trees with a new tree that has a root with an edge to the left child is labeled as 0 and an edge to the right child labeled as 1.

As e has highest label value than b + c, so the left child is named as e and the right child is named as b + c.

Now the smallest labels are b+ c+ e and a + d.

Replace these trees with a new tree that has a root with an edge to the left child is labeled as 0 and an edge to the right child labeled as 1.

As b+ c +e has highest label value than a +d, so the left child is named as ab+ c+ e and the right child is named as a +d.

Find the sequence of labels and the weight.

The sequence of labels of the edges in the path from the root to the letter is:

\({\bf{a:00, b:100, c:101, d:01, e:11}}\)

The weight of the letter is the number of bits in the code of the letter:

\({{\bf{w}}_{\bf{a}}}{\bf{ = 2,}}\,{{\bf{w}}_{\bf{b}}}{\bf{ = 3,}}\,{{\bf{w}}_{\bf{c}}}{\bf{ = 2,}}\,{{\bf{w}}_{\bf{d}}}{\bf{ = 2,}}\,{{\bf{w}}_{\bf{e}}}{\bf{ = 2}}\)

Now, find the average number of bits.

The average number of bits required is then the sum of the products of the weights and their frequencies:

Average number of bits

\(\begin{array}{c}\sum {{\bf{w}}_{\bf{i}}}{{\bf{f}}_{\bf{i}}}{\bf{ = 2}}\left( {{\bf{0}}{\bf{.20}}} \right){\bf{ + 3}}\left( {{\bf{0}}{\bf{.10}}} \right){\bf{ + 3}}\left( {{\bf{0}}{\bf{.15}}} \right){\bf{ + 2}}\left( {{\bf{0}}{\bf{.25}}} \right){\bf{ + 2}}\left( {{\bf{0}}{\bf{.30}}} \right)\\{\bf{ = 0}}{\bf{.40 + 0}}{\bf{.30 + 0}}{\bf{.45 + 0}}{\bf{.50 + 0}}{\bf{.60}}\\{\bf{ = 2}}{\bf{.25}}\end{array}\)

Therefore, the average number of bits required is 2.25.