Huffman Coding 2.10 2001/07/10 2005/10/26 20:20:42.463 GMT-5 Behnaam Aazhang aaz@ece.rice.edu Dinesh Rajan dinesh@ece.rice.edu Mohammad Jaber Borran mohammad@ece.rice.edu Roy Ha rha@rice.edu Shawn Stewart mrshawn@alumni.rice.edu Behnaam Aazhang aaz@ece.rice.edu Huffman information theory source coding A description of the Huffman source encoding algorithm. One particular source coding algorithm is the Huffman encoding algorithm. It is a source coding algorithm which approaches, and sometimes achieves, Shannon's bound for source 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 to obtain the codeword the the preceding outputs and repeat step 5. If no output is preceded by another output in a preceding step, then stop. X A B C D with probabilities { 1 2 , 1 4 , 1 8 , 1 8 }

Average length 1 2 1 1 4 2 1 8 3 1 8 3 14 8 . As you may recall, the entropy of the source was also H X 14 8 . In this case, the Huffman code achieves the lower bound of 14 8 bits output . In general, we can define average code length as ℓ x x X ¯ p X x ℓ x where X ¯ is the set of possible values of x. It is not very hard to show that H X ℓ H X 1 For compressing single source output at a time, Huffman codes provide nearly optimum code lengths. The drawbacks of Huffman coding Codes are variable length. The algorithm requires the knowledge of the probabilities, p X x for all x X ¯ . Another powerful source coder that does not have the above shortcomings is Lempel and Ziv.