<< Chapter < Page Chapter >> Page >
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 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.

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 .

Got questions? Get instant answers now!

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 aboveshortcomings is Lempel and Ziv.

Get Jobilize Job Search Mobile App in your pocket Now!

Get it on Google Play Download on the App Store Now




Source:  OpenStax, Digital communication systems. OpenStax CNX. Jan 22, 2004 Download for free at http://cnx.org/content/col10134/1.3
Google Play and the Google Play logo are trademarks of Google Inc.

Notification Switch

Would you like to follow the 'Digital communication systems' conversation and receive update notifications?

Ask