Question

Suppose you want to encode messages containing only the following characters with their given respective frequencies: B: 55 D: 15 E: 80 G: 5 U: 45

(a) What is the minimum length bit string required to encode each character with a distinct, fixed-length code?

(b) Construct the Huffman Tree for the characters with the given frequencies. (Use the convention that when merging two vertices, the vertex with the largest count goes on the left.)

(c) Use your Huffman Tree to decode the message M = 00101010000011

(d) How many bits are required to encode the characters with the given frequencies using the Huffman Encoding and the fixed-length encoding you found in part (a)? How much storage savings does this represent?

Answer 1

(a) Using two bits for each letter, we can represent different letters.

$\text{Letter 1 $\rightarrow$ 00}\\ \text{Letter 2 $\rightarrow$ 01}\\ \text{Letter 3 $\rightarrow$ 10}\\ \text{Letter 4 $\rightarrow$ 11}$

But here are 5 letters (B, D, E, G, U). So we will need three bits for each letter. Because maximum $2^3=8$ letters can be represented using 3 bits.

Now total frequency = 55+15+80+5+45=200

Hence total bits required $=200\times3=600$ bits.

b)

Therefore

$E=1\\ B=0~1\\U=0~0~0\\ D=0~0~1~0\\G=0~0~1~1$

c)

$\therefore M = 00101010000011=\\\underline{0010}~\underline{1}~\underline{01}~\underline{000}~\underline{0011}=DEBUG$

d)

Total bits by Huffman

$=80\times 1+55\times 2+45\times 3+15\times 4+5\times 4\\=405 \text{ bits}$