Question

4. a) Distinguish between adaptive Huffman coding and Adaptive Arithmetic coding in terms of adaptation rate.

b) Describe how quick changes are adapted and prevented in each method for source statistics? Explain in elaborate?

Answer 1

Huffman Coding:

Huffman coding is the best known form of entropy coding. The premise behind Huffman coding is that more frequently occurring symbols are coded using longer code words. To accomplish this, variable length code words are assigned to symbols based on their frequency of occurrence.

* Huffman code satisfies two conditions:

1. All code words are uniquely decodable

2. No delimiters or extra information is inserted in the code words to facilitate decidability The first condition is accomplished by the use of prefix code. This leads to the second condition. No markers are needed to separate the code words because of the use of prefix code.

* Huffman coding have fastest adaptive version has speeds on larger alphabets with easier implementation advantage and much more versatile.

* The main advantage of arithmetic coding is it make relatively easy to adaptive. In contracts, adaptive Huffman codes can be much more complex.

Adaptive Huffman Coding:

* Scanning of all the data is needed to provide accurate probabilities In order to perform Huffman coding. In some instances this may be an immense amount of data or the data may not be available at all.

* Adaptive Huffman coding schemes were created to deal with this problem,. In these schemes, the probabilities are updated as more inputs are processed. Instead of two passes through the data, only one pass is needed. One of the most famous types of adaptive Huffman algorithms is the FGK algorithm developed by Faller and Gallager. The algorithm was later improved by Cormack and Horspool with a final improvement by Knuth.

* The sibling property is used in the FGK algorithm,. A tree follows the sibling property if every internal node besides the root has a sibling and all nodes can be numbered and arranged in nondecreasing probability order. The numbering corresponds to the order in which the nodes are combined in the algorithm. This tree has a total of 2n-1 nodes. Another property is lexicographical ordering.

* A tree is lexicographically ordered if the probabilities of the nodes at depth d are smaller than the probabilities of the nodes at depth d-1. If these two properties are employed, it will ensure that a binary prefix code tree is a Huffman tree. In order for the adaptive Huffman algorithm to work, two trees must be maintained.

* One tree is in the encoder and the other is in the decoder. Both encoder and decoder start with the same tree. When a new symbol is observed, the old symbol code is send to the decoder and its frequency in the tree is incremented.

* If the new incremented value causes the tree to violate the sibling property, exchange the node with the rightmost node with frequency country lower than the incremented node.

Adaptive Arithmetic Coding

* As with Adaptive Huffman, Adaptive Arithmetic coding also reduces the number of passes through the data from two to one. The difference between the two is that there is no need to keep a tree for the codewords. The only information that needs to be synchronized is the frequency of occurrence of the symbols.

* The decoder takes compressed sequence as input and a sequence of probability distributions of predicted and then outputs the original characters sequence.

* The sequence of probability distributions of predicted must be same for the encoder and the decoder in order for the decoder to regenerate the original sequence of character.

*  As it is using the sequence of predicted probability distributions it help to quick and easily encode and decode the sequence of character.