5.5 Huffman coding

One particular source coding algorithm is the Huffman encoding algorithm. It is a source coding algorithm which approaches, and sometimes achieves, Shannon's bound forsource compression. A brief discussion of the algorithm is also given in another module .

Huffman encoding algorithm

• Sort source outputs in decreasing order of their probabilities
• Merge the two least-probable outputs into a single output whose probability is the sum of the corresponding probabilities.
• If the number of remaining outputs is more than 2, then go to step 1.
• Arbitrarily assign 0 and 1 as codewords for the two remaining outputs.
• If an output is the result of the merger of two outputs in a preceding step, append the current codeword with a 0 and a 1 toobtain the codeword the the preceding outputs and repeat step 5. If no output is preceded by another output in a preceding step, thenstop.

In general, we can define average code length as

It is not very hard to show that

The drawbacks of Huffman coding

• Codes are variable length.
• The algorithm requires the knowledge of the probabilities, $p(X, x)$ for all $x\in \stackrel{}{X}$ .