Question

Suppose the alphabet is S = {A B C D} and the known probability distribution is P_A = 0.3, P_B = 0.1, P_C = 0.5, and P_D = 0.1. Decode the Huffman coding result {11000010101110100} to the original string based on the probability distribution mentioned above. The codeword for symbol “D” is {111}. Please writing down all the details of calculation.

Answer 1

Given Information

P_A = 0.3, P_B = 0.1, P_C = 0.5, and P_D = 0.1

First, let us create a Huffman tree

Since D's codeword is 111, it has to be at the extreme right of the root node.

In Huffman tree

Left child is assigned with value 0

The right child is assigned with value 1

Here is the Huffman tree

While constructing a Huffman tree, we always start from the lowest values of probability or frequency. First B, D are merged based on their probabilities. BD's result is merged with the next smallest probability, that is A. At last we merge with C to get the root node.

From the above Huffman Tree

A = 10

B = 110

C = 0

And it is proved that D = 111

Let us decode 11000010101110100

110 00010101110100

B 0 0 0 10101110100 //We have three zeros//

BCCC 10 10 1110100 // We have two 10//

BCCCAA 111 0100

BCCCAAD 0 100

BCCCAADC 10 0

BCCCAADCA 0

BCCCAADCAC is the original string.

If you liked the solution, please give a positive rating to the answer. Your rating motivates experts to help other students also. Thank you :)