Rate distortion theory

from Wikipedia, the free encyclopedia

The rate distortion theory (German: rate distortion theory ) is a theoretical basis for calculations in information theory . With their help, a lower limit of the data transmission rate for a message source can be determined computationally , at which a reconstruction of the message at the recipient can still be guaranteed in compliance with a predetermined quality criterion, the so-called distortion. It was developed by Claude E. Shannon , who is considered the founder of information theory.

use

The rate distortion theory makes it possible to find theoretical limits for the maximum compression when using irrelevance-reducing coding . The theory is therefore applied in many methods of audio, speech, image and video coding.

It also enables the effectiveness of different source coding methods to be assessed by comparing the respective data rate of the lossy compression method with the lower limit.

calculation

Rate distortion function of a discrete, memoryless source

To calculate the rate distortion function , each possible representation of a transmitted symbol k by a received symbol j is assigned a numerical value as a measure of the corruption. This is the so-called distortion measure D (k; j) . A capital D (k; j) thus means that the signal is seriously corrupted. The simple case of the mean square error is often used as a measure of distortion . The maximum allowable distortion is referred to as D * . The rate distortion function R (D *) can now be calculated as the minimum of the mean transinformation .

The course of the rate-distortion function corresponds to a convex U-function, which falls with increasing D * . The maximum of R (D *) is equal to the entropy H (U) and occurs at D * = 0 , i.e. with no permitted distortion.

literature

  • CE Shannon: A Mathematical Theory of Communication , The Bell System Technical Journal, July / October, 1948
  • W. Weaver, CE Shannon: The Mathematical Theory of Communication , University of Illinois Press, 1949
  • T. Berger: Rate Distortion Theory: Mathematical Basis for Data Compression , Prentice Hall, 1971. ISBN 978-0137531035
  • J. Gibson, W. Tranter: Information Theory and Rate Distortion Theory , Morgan & Claypool Publishers, 2010. ISBN 978-1598298079
  • HG Musmann: Information theory , lecture notes from Leibniz University Hannover, 2000
  • HG Musmann: Source coding , lecture script from Leibniz University Hannover, 2002

Web links