Rate Distortion Theory and Data Compression
In this introductory lecture we present the rudiments of rate distortion theory, the branch of information theory that treats data compression problems. The rate distortion function is defined and a powerful iterative algorithm for calculating it is descr
- PDF / 2,403,917 Bytes
- 35 Pages / 481.89 x 691.654 pts Page_size
- 5 Downloads / 150 Views
TOBYBERGER School of Electrical Engineering Cornell University, Ithaca, New York
T. Berger et al., Advances in Source Coding © Springer-Verlag Wien 1975
PREFACE I am grateful to CISM and to Prof. Giuseppe Longo for the opportunity to lecture about rate distortion theory research during the 1973 CISM summer school session. Rate distortion theory is currently the most vital area of probabilistic information · theory, affording significantly increased insight and understanding about data compression mechanisms in both man-mcde and natural information processing systems. The lectures that follow are intended to convey an appreciation for the important results that have been obtained to date and the challenging problems that remain to be resolved in this rapidly evolving branch of information theory. The international composition of the CISM summer school attendees affords a unique opportunity to attempt to stimulate subsequent contributions to the theory from many nations. It is my hope that the lectures which follow capitalize successfully on this promising opportunity.
T. Berger
LECTURE 1 Rate Distortion Theory: An Introduction In this introductory lecture we present the rudiments of rate distortion theory, the brauch of information theory that treats data compression problems. The rate distortion function is defined and a powerful iterative algorithm for calculating it is described. Shannon's source ~oding theorems are stated and heuristically discussed. Shannon's celebrated coding theorem states that a source of entropy rate H can be transmitted reliably over any channel of capacity C > H. This theorem also has a converse devoted to the frequently encountered situation in which the entropy rate of the source exceeds the capacity of the channel.'Said converse states that not all the source data can be recovered reliably when H > C [ 1 ]. Since it is always desirable to recover all the data correctly, one can reduce H either by (a) slowing down the rate of production of source letters, or (b) encoding the letters more slowly than they are being produced. However, (a) often is impossible because the source rate is not under the communication system designer's control, and (b) often is impossible both because the data becomes stale, or perhaps even useless, because of lang coding delays and because extensive buffering memory is needed. If H cannot be lowered, then the only other remedy is to increase C. This, however, is usually very expensive in practice. We shall assume in all that follows that H already has been lowered and that C already has been raised as much as is practically possible but the situation H >C nonetheless continues to prevail. (This is always true in the important case of analog sources because their absolute entropy H is infinite whereas the C of any physical channel is finite). In such a situation it is reasonable to attempt to preserve those aspects of the source data that are the most crucial to the application at hand. That is, the communication system should be configured to reconstruct
Data Loading...
