Solution to Suppose you want to encode messages containing only the following characters with their given respective … - Sikademy
Author Image

Archangel Macsika

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?

The Answer to the Question
is below this banner.

Can't find a solution anywhere?

NEED A FAST ANSWER TO ANY QUESTION OR ASSIGNMENT?

Get the Answers Now!

You will get a detailed answer to your question or assignment in the shortest time possible.

Here's the Solution to this Question

(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}

Related Answers

Was this answer helpful?

Join our Community to stay in the know

Get updates for similar and other helpful Answers

Question ID: mtid-5-stid-8-sqid-643-qpid-528