[go: up one dir, main page]
Scribd
Upload
16 views4 pages

Huffman Code

The document outlines the process of constructing a Huffman tree using given symbols and their frequencies. It details the steps of arranging nodes, combining them to form a tree, and assigning binary codes to each symbol. Additionally, it demonstrates encoding the text 'DAD' into a bit string and decoding the bit string '10011011011101' back into the text 'BAD_AD'.

Uploaded by

retick72
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
16 views4 pages

Huffman Code

The document outlines the process of constructing a Huffman tree using given symbols and their frequencies. It details the steps of arranging nodes, combining them to form a tree, and assigning binary codes to each symbol. Additionally, it demonstrates encoding the text 'DAD' into a bit string and decoding the bit string '10011011011101' back into the text 'BAD_AD'.

Uploaded by

retick72
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Construct the Huffman Code for the following data:

Encode the text DAD and decode the text 10011011011101

Solution:

First, we need to Construct Huffman tree by following below steps of Huffman


algorithm:

Step1: Create 5- one node trees with symbol and its frequency as weight

0.35 0.1 0.2 0.2 0.15


A B C D _

Step 2: Arrange the above nodes in ascending order of their weights

0.1 0.15 0.2 0.2 0.35


B _ C D A

Step 3: Construct the Huffman tree by repeating the following operation until a
single tree is obtained.

 Find two trees with the smallest weight.


 Make them the left and right subtree of a new tree and record the sum of
their weights in the root of the new tree as its weight.
 Rearrange the nodes again in ascending order of weights
0.1 0.15 0.2 0.2 0.35
B _ C D A

0.2 0.2 0.35


C D A
0.1 0.15
B _

0.35
A
0.1 0.15 0.2 0.2
B _ C D

0.2 0.2 0.35


C D A
0.1 0.15
B _
1.0

0.2 0.2 0.35


C D A
0.1 0.15
B _

Now, Assign the label 0 to left edges and label 1 to right edges to the above
Huffman tree to generate codeword.

1.0
0 1

0 0 1
1

0.2 0.2 0.35


0 1
C D A
0.1 0.15
B _

 The codeword for the given symbol is as follows

Symbol A B C D _

Codeword 11 100 00 01 101

 Encode the text DAD, the bit string is 011101


 Decode the string 10011011011101

100 11 01 101 11 01
B A D _ A D
The text for the above string BAD_AD

You might also like