Extended Huffman Coding:

In applications where the alphabet size is large, pmax is generally quite small, and the amount of deviation from the entropy, especially in terms of a percentage of the rate, is quite small.

However, in cases where the alphabet is small and the probability of occurrence of the different letters is skewed, the value of pmax can be quite large and the Huffman code can become rather inefficient when compared to the entropy.

To overcome this inefficiency we use adaptive Huffman coding, the same can be illustrated with the help of following example:

Consider a source that puts out iid letters from the alphabet A = {a1, a2, a3} with the probability model P(a1) = 0.8, P(a2) = 0.02, and P(a3) = 0.18. The entropy for this source is 0.816 bits/symbol. A Huffman code for this source is shown in Table below

TABLE 1: The Huffman code.

The average length for this code is 1.2 bits/symbol. The difference between the average code length and the entropy, or the redundancy, for this code is 0.384 bits/symbol, which is 47% of the entropy. This means that to code this sequence we would need 47% more bits than the minimum required.

Now for the source described in the above example, instead of generating a codeword for every symbol, we will generate a codeword for every two symbols. If we look at the source sequence two at a time, the number of possible symbol pairs, or size of the extended alphabet, is 32 = 9. The extended alphabet, probability model, and Huffman code for this example are shown in Table below

TABLE 2: The extended alphabet and corresponding Huffman code.

The average codeword length for this extended code is 1.7228 bits/symbol. However, each symbol in the extended alphabet corresponds to two symbols from the original alphabet.

Therefore, in terms of the original alphabet, the average codeword length is 1.7228/2 = 0.8614 bits/symbol.

This redundancy is about 0.045 bits/symbol, which is only about 5.5% of the entropy.

Advantage of extended Huffman coding

We see that by coding blocks of symbols together we can reduce the redundancy of Huffman codes.