Jump to Content
chapter 3, Variable-Length Codes
Table of Contents
- I Background
- 1. Digital Images and Image Compression
- II Information Theory Concepts
- 2. Source Models and Entropy
- III Lossless Compression Techniques
- 6. Bit Plane Encoding
- IV Lossy Compression Techniques
- 9. Lossy Predictive Coding
- 10. Transform Coding
- 13. Subband Coding
Chapter Contents
- 3.1 Code Efficiency and Source Extensions
- 3.2 Huffman Codes
- 3.3 Modified Huffman Codes
- 3.4 Limitations of Huffman Coding
- 3.5 Arithmetic Coding
- 3.5.1 The IBM Q-coder
Excerpt
While the noiseless coding theorem provides for the existence of a code that can achieve a rate equal to or approaching the entropy of a source, it unfortunately does not provide a means for constructing an actual code. Generally, variable-length codes are used together with source extensions to achieve the desired performance. In this chapter, we discuss the use and construction of variable-length codes for source encoding.
Consider an example in which a DMS S has four symbols, s1, s2, s3, and s4, with probabilities given in Table 3.1. We wish to construct an efficient code using a binary alphabet to encode this source. Our code should have some desired characteristics. For instance, each codeword in the sequence should be instantaneously decodable, i.e., decodable without reference to the succeeding codewords. A necessary and sufficient condition for constructing such codes is that no codeword be a prefix of some other codeword. Any code satisfying this condition is called a prefix condition code. Code I in Table 3.1, which is a fixed-length code, has an average length of 2 bits/symbol and is clearly a prefix condition code.
©1991 Society of Photo-Optical Instrumentation Engineers
