| Home | Sign up! | Projects | Seminars | Research Notes | Today's Lecture | About |

Update Research Note Form
 Course: Research Note Topic: Research Note Description: When a file or data is tranmitted over a medium or better known as channel, it needs to be compressed. This is required to save the transmission time.For this various compression methods are available, like Huffman Encoding.
The Huffman encoding method uses tree (data structure) to do the actual encoding and hence compression.
HUFFMAN CODING
To start the procedure or coding, first a tree structure is formed.This is done by first finding the frequency of each alphabet existing in the text or data.These frequencies are plcaed in a line at the bottom of the tree.Then the least two values are added to form a new level or node which is known as the parent node of the two numbers (least) added which are known as the children nodes.Following the procedure, a tree structure is formed and at the top of the tree ie the root holds the value which represents the size of the data or the alphabet occurence frequencies total.
Then the children nodes of the root node are assigned 0 and 1 respectively ie left child is assigned 0 and right child is assigned 1.Moving downwards to each child node is assigned value in correspondence to its parent node ie the value of parent node is considered for children nodes by adding 0 and 1 at the end of the parent node value ie suffix 0 and 1 to parent node value respectively for left child and right child.
Example-Suppose parent node value is 100, then the left child value will be 1000 and right child value is 1001.
After the values are asigned to each node, the are assigned to the alphabets in the frequency table.The value is associated by tracking down the intial frequency tree to the exact node holding the value.The value or the codeword or huffman code is the value of the leaves ie. the nodes which donot have any children.
Example:-
the data to be transmitted is-ENQUIRE

Steps-
1.Make frequency table.
Frequency-table
Alaphabet Frequency
E  2  00
N   1   01
Q  1   100
U   1   101
I  1   110
R   1   111
2.Make binary tree and try maintaining levels.

4.Label the nodes using combinations of 0s and 1s as per huffman coding rule (mentioned earlier).
5.Assign each alphabet the corresponding binary numbers.
6.Transmit the message-
ENQUIRE as
000110010111011100
For decoding
7.When the message is received by the receiver, it is decoded.Each binary number is picked and compared with the codeords assigned to each alphabet.Next binary digit is suffixed in case the previous one doesn't match any in the table.