Gray R.M. Source Coding Theory

Kluwer, 1990. — 611 p.Source coding theory has as its goal the characterization of the optimal performance achievable in idealized communication systems which must code an information source for transmission over a digital communication or storage channel for transmission to a user. The user must decode the information into a form that is a good approximation to the original. A code is optimal within some class if it achieves the best possible fidelity given whatever constraints are imposed on the code by the available channel. In theory, the primary constraint imposed on a code by the channel is its rate or resolution, the number of bits per second or per input symbol that it can transmit from sender to receiver. In the real world, complexity may be as important as rate.
The origins and the basic form of much of the theory date from Shannon's classical development of noiseless source coding and source coding subject to a fidelity criterion (also called rate-distortion theory). Shannon combined a probabilistic notion of information with limit theorems from ergodic theory and a random coding technique to describe the optimal performance of systems with a constrained rate but with unconstrained complexity and delay. An alternative approach called asymptotic or high rate quantization theory based on different techniques and approximations was introduced by Bennett at approximately the same time. This approach constrained the delay but allowed the rate to grow large.
The goal of both approaches was to provide unbeatable bounds to the achievable performance using realistic code structures on reasonable mathematical models of real-world source coding systems such as analog-to-digital conversion, data compression, and entropy coding. The original theory dealt almost exclusively with a particular form of code-a block code or, as it is sometimes called in current applications, a vector quantizer. Such codes operate on nonoverlapping blocks or vectors of input symbols in a memoryless fashion, that is, in a way that does not depend on previous blocks. Much of the theory also concentrated on memoryless sources or sources with very simple memory structure. These results have since been extended to a variety of coding structures and to far more general sources. Unfortunately, however, most of the results for nonblock codes have not appeared in book form and their proofs have involved a heavy dose of measure theory and ergodic theory. The results for nonmemoryless sources have also usually been either difficult to prove or confined to Gaussian sources.
This monograph is intended to provide a survey of the Shannon coding theorems for general sources and coding structures along with a treatment of high rate vector quantization theory. The two theories are compared and contrasted. As perhaps the most important special case of the theory, the uniform quantizer is analyzed in some detail and the behavior of quantization noise is compared and contrasted with that predicted by the theory and approximations. The treatment includes examples of uniform quantizers used inside feedback loops. In particular, the validity of the common white noise approximation is examined for both Sigma-Delta and Delta modulation. Lattice vector quantizers are also considered briefly.
Much of this manuscript was originally intended to be part of a book by Allen Gersho and myself titled Vector Quantization and Signal Compression which was originally intended to treat in detail both the design algorithms and performance theory of source coding. The project grew too large, however, and the design and applications-oriented material eventually crowded out the theory. This volume can be considered as a theoretical companion to Vector Quantization and Signal Compression, which will also be published by Kluwer Academic Press.Information Sources.
Codes, Distortion, and Information.
Distortion-Rate Theory.
Rate-Distortion Functions.
High Rate Quantization.
Uniform Quantization Noise.