chapter  5
25 Pages

Variable-Length Coding: Information Theory Results (II)

ByYun Q. Shi, Huifang Sun

This chapter focuses on promising arithmetic coding algorithm, which is quite different from Huffman coding. While Huffman coding is a block-oriented coding technique, arithmetic coding is a stream-oriented coding technique. There are three stages that take place in an encoder: transformation, quantization, and code word assignment. A uniquely decodable code is said to be compact if its average length is the minimum among all other uniquely decodable codes based on the same source alphabet S and code alphabet A. A compact code is also referred to as a minimum redundancy code, or an optimum code. Instead of coding each source symbol in a discrete source alphabet, it is often useful to code blocks of symbols. It is, therefore, necessary to define the nth extension of a discrete memoryless source. The method of encoding source symbols according to their probabilities is not optimum.