Variable-Length Codes

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, s 1 , s 2 , s 3 , and s 4 , 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.