Rate-Distortion-Theorie

Die Rate-Distortion-Theorie (deutsch: Rate-Verzerrungs-Theorie) ist eine theoretische Grundlage für Berechnungen in der Informationstheorie. Mit ihrer Hilfe kann rechnerisch eine untere Grenze der Datenübertragungsrate für eine Nachrichtenquelle bestimmt werden, bei der eine Rekonstruktion der Nachricht am Empfänger unter Einhaltung eines vorgegebenen Gütekriteriums, der sogenannten Verzerrung, noch gewährleistet werden kann. Entwickelt wurde sie von Claude E. Shannon, der als Begründer der Informationstheorie gilt.

Nutzung

Durch die Rate-Distortion-Theorie ist es möglich, bei der Nutzung von Irrelevanzreduzierender Codierung theoretische Grenzen für die maximale Kompression zu finden. In vielen Verfahren der Audio-, Sprach-, Bild- und Videocodierung wird die Theorie daher angewendet.

Sie ermöglicht zudem die Bewertung der Effektivität verschiedener Quellencodierungsverfahren, indem die jeweilige Datenrate der verlustbehafteten Kompressionsverfahren mit der unteren Grenze verglichen wird.

Berechnung

Rate-Distortion-Funktion einer diskreten, gedächtnislosen Quelle

Zur Berechnung der Rate-Distortion-Funktion wird jeder möglichen Darstellung eines gesendeten Symbols k durch ein empfangenes Symbol j ein numerischer Wert als Maß für die Verfälschung zugeordnet. Dieser ist das sogenannte Verzerrungsmaß D(k;j). Ein großes D(k;j) bedeutet somit eine große Verfälschung des Signals. Als Verzerrungsmaß wird häufig der einfache Fall des mittleren quadratischen Fehlers genutzt. Die maximal zulässige Verzerrung wird als D* bezeichnet. Die Rate-Distortion-Funktion R(D*) kann nun als Minimum der mittleren Transinformation berechnet werden.

Der Verlauf der Rate-Distortion-Funktion entspricht einer konvexen U-Funktion, die mit wachsendem D* fällt. Das Maximum von R(D*) ist gleich der Entropie H(U) und tritt auf bei D* = 0, also bei keiner erlaubten Verzerrung.

Literatur

• C. E. Shannon: A Mathematical Theory of Communication, The Bell System Technical Journal, Juli/Oktober, 1948
• W. Weaver, C. E. 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
• H. G. Musmann: Informationstheorie, Vorlesungsskript der Leibniz Universität Hannover, 2000
• H. G. Musmann: Quellencodierung, Vorlesungsskript der Leibniz Universität Hannover, 2002

Weblinks

• A Mathematical Theory of Communication (engl.; PDF; 366 kB)
• Rate Distortion Theory (PDF; 130 kB) Vortrag an der National Sun Yat-Sen University (engl.)
• Rate-Distortion Optimization of Hybrid Video Coding Fraunhofer Heinrich Hertz Institute (engl.)