Adaptive Huffman Decoding

Adaptive Huffman Decoding with Example. In case of Adaptive Huffman decoding scheme you need to have the information of two things:

• the binary tree
• string of binary numbers that you want to decode

Corresponding to the binary string, we traverse the same tree that we had during encoding time. As we arrive at a leaf, the symbol corresponding to the leaf is decoded. During the encoding time, we set the values of e and r such that:

m=2^e+r

If the leaf is NYT node, then we check the next e bits to see whether its corresponding decimal value is less than r or not.  If value is less than r, we read another bit to make a 5-bit code for the symbol. The index is found by adding 1 to the decimal equivalent of e or either e+1 bits.

Once we are done with decoding the symbol, we update the tree. Then we use the next bit for traversing down the tree. The decoding is shown in the following flowchart.

Adaptive Huffman Decoding Procedure

Suppose that the encoding procedure generates the following binary string:

0000010000100000011001

In the start, only NYT (not yet transmitted) node is present. Therefore the first symbol to decode will be obtained from NYT list. Since the value of e=4 (set during the encoding process) so we will read the next 4 bits which are 0000. The decimal value corresponding to them is 0. As this value is less than r which is 10, we will add 1 to this decimal value in order to find the index of the symbol. In this case, it corresponds to ‘a’ since 0+1=1 so first symbol in the alphabets. 

The tree will be updated now like the one shown below (2nd pic where only node a is inserted)

Now, read the next bit in the string which is 1 in this case. Since it is not the NYT, so if you traverse from the root to the node, you land at leaf ‘a’ again. Hence the next symbol is ‘a’.

Here the update procedure only involves in the increment of weight of node corresponding to a. It becomes 2 after decoding a.

The next bit, that you read is 0, which is the code for NYT node. Now you will read the next 4-bits which are 0001. The decimal equivalent of these bits is less than 10 (r) so we read in one more bit to get a 5-bit number 00010. The decimal equivalent of it is 2. This corresponds to the index value (2+1)=3 (C). Hence the next symbol is C.

As we read the next 2 bits for NYT (00 in this case), we will read 4 more bit for finding the value which is 0001 (1<10). Add one more bit to it so that you can find the 5-bit code (00011). Its decimal representation is 3 and the index is found by adding 1 in the decimal which results in 4. ‘D” will be the next symbol to be added in the tree.

So the next three bits are 001 which gives the symbol D again while going down from the root. Continuing in this manner we can decode the remaining string.

 

Also read here:

Adaptive Huffman Encoding 

Adaptive Huffman Encoding in Data Compression | Unique Example