Question

Consider a DMS where output is generated from an alphabet {a,b,c,d,e,f,g,h} with respective with probabilities {0.25, 0.1, 0.02, 0.05, 0.25, 0.03, 0.25, 0.05}.

a) Design a Huffman code and sketch the corresponding coding tree. Explain the codewords for each

Answer 1

To design a Huffman code for the given DMS, order the probabilities in descending order and combine the two lowest probabilities to form a new node until all nodes are combined into a single tree. The codewords for each symbol are: a: 00, b: 01, c: 100, d: 101, e: 10, f: 1100, g: 11, h: 111.

Step-by-step explanation:

To design a Huffman code for the given DMS, we start by ordering the probabilities in descending order. The two lowest probabilities are then combined to form a new node with a probability equal to the sum of the two original probabilities. This process continues until all the nodes are combined into a single tree.

In this case, the codewords for each symbol are:

• a: 00
• b: 01
• c: 100
• d: 101
• e: 10
• f: 1100
• g: 11
• h: 111

The corresponding coding tree can be sketched as follows:

-----------
/ \
/ \
0.35 0.65
/ \ / \
0.15 0.20 0.25 0.40
/ \ / \ / \ / \
0.05 0.10 0.05 0.05 0.02 0.25
a b d e c PT