A First Course in Information Theory (Information Technology: Transmission, Processing and Storage) by Raymond W. Yeung

Author:Raymond W. Yeung [Yeung, Raymond W.]
Language: eng
Format: epub
Published: 2007-08-28T05:02:00+00:00

Chapter 9

RATE-DISTORTION THEORY

Let H be the entropy rate of an information source. By the source coding theorem, it is possible to design a source code with rate R which reconstructs the source sequence X = (X1, X2. • • • , X,) with an arbitrarily small probability of error provided R > H and the block length n is sufficiently large. However, there are situations in which we want to convey an information source by a source code with rate less than H. Then we are motivated to ask: what is the best we can do when R < H?

A natural approach is to design a source code such that for part of the time the source sequence is reconstructed correctly, while for the other part of the time the source sequence is reconstructed incorrectly, i.e., an error occurs. In designing such a code, we try to minimize the probability of error. However, this approach is not viable asymptotically because the converse of the source coding theorem says that if R < H, then the probability of error inevitably tends to I as n -* oc.

Therefore, if R < H, no matter how the source code is designed, the source sequence is almost always reconstructed incorrectly when n is large. An alternative approach is to design a source code called a rate-distortion code which reproduces the source sequence with distortion. In order to formulate the problem properly, we need a distortion measure between each source sequence and each reproduction sequence. Then we try to design a rate-distortion code which with high probability reproduces the source sequence with a distortion within a tolerance level.

Clearly, a smaller distortion can potentially be achieved if we are allowed to use a higher coding rate. Rate-distortion theory, the subject matter of this chapter, gives a characterization of the asymptotic optimal tradeoff between the coding rate of a rate-distortion code for a given information source and the allowed distortion in the reproduction sequence with respect to a distortion measure.

Download

Copyright Disclaimer:
This site does not store any files on its server. We only index and link to content provided by other sites. Please contact the content providers to delete copyright contents if any and email us, we'll remove relevant links or contents immediately.