Source Coding Algorithms

In this chapter, we have presented some of the key source coding algorithms widely used in data and image compression. First we have described the run-length coding scheme with an example. We have described the popular Huffman coding scheme which is used in various image and data compression techniques. We have discussed the Modified Huffman coding scheme to enhance its efficiency. Arithmetic coding is an alternative approach for efficient entropy encoding and it achieves compression efficiency very close to the entropy limit. We have described the basic principles of arithmetic coding with an example and the implementation issues. We have described the Binary arithmetic coding with an example. Binary arithmetic coding is a key algorithm for bi-level image compression. Variations of adaptive implementation of binary arithmetic coding algorithm have been adopted in different image compression standards - JBIG, JBIG2, JPEG, JPEG2000. We have discussed the QM-coder algorithm for implementation of an adaptive binary arithmetic coding which has been adopted in the JBIG standard for bi-level image compression and also in a mode of JPEG standard. A variation of QM-coder called the MQ-coder is the basis of the entropy encoding of the new JPEG2000 standard for still picture compression. We also described the dictionary based coding, especially the key algorithms in the popular Ziv-Lempel family of algorithms mainly used in text compression.