Shannon-Untergrenze und Rate-Distortion-Funktion: Tutorial für Studenten

Einführung in die Rate-Distortion-Theorie

In der Informationstheorie geht es oft um die Frage: Wie stark kann man eine Datenquelle komprimieren, ohne die Qualität zu sehr zu beeinträchtigen? Die Rate-Distortion-Funktion R(D) gibt die minimale Bitrate an, die benötigt wird, um eine durchschnittliche Verzerrung D nicht zu überschreiten. Dieses Konzept ist fundamental für moderne Anwendungen wie Video-Streaming (Netflix, YouTube), Sprachassistenten (Siri, Alexa) oder die Kompression von KI-Modellen.

Stell dir vor, du streamst ein Fußballspiel in 4K – die Übertragung muss komprimiert werden, um mit der Internetgeschwindigkeit Schritt zu halten. Die Rate-Distortion-Funktion hilft dabei, den optimalen Kompromiss zwischen Bitrate und Bildqualität zu finden. Ähnlich wie bei einem Gaming-Stream auf Twitch: Je niedriger die Bitrate, desto mehr Pixel-Fehler (Verzerrung) treten auf.

Shannon-Untergrenze für mittlere quadratische Verzerrung

Betrachten wir eine kontinuierliche Zufallsvariable X mit Mittelwert Null und Varianz σ². Die Shannon-Untergrenze besagt:

R(D) ≥ (1/2) log(σ²/D)  für D ≤ σ²

Diese untere Schranke gilt für jede Verteilung von X mit derselben Varianz. Sie zeigt, dass die Rate mindestens so groß sein muss wie bei einer Gaußverteilung. Warum? Weil die Gaußverteilung die maximale differentielle Entropie bei gegebener Varianz hat – sie ist am „schwersten zu beschreiben“. Das bedeutet: Gaußsche Zufallsvariablen benötigen mehr Bits, um eine bestimmte Verzerrung zu erreichen, als andere Verteilungen mit gleicher Varianz.

Beispiel aus der Praxis: KI-Bildkompression

Moderne KI-Modelle wie Stable Diffusion oder DALL·E erzeugen Bilder, die oft als latente Darstellungen (Gaußsche Rauschvektoren) gespeichert werden. Die Shannon-Untergrenze erklärt, warum diese Darstellungen eine hohe Bitrate benötigen – sie sind eben „Gauß-artig“ und damit schwer zu komprimieren. Im Gegensatz dazu lassen sich Bilder mit vielen gleichfarbigen Flächen (z.B. Cartoons) leichter komprimieren, da ihre Verteilung weniger Entropie hat.

Obere Schranke durch gemeinsame Verteilung

Die obere Schranke in der Aufgabenstellung wird mit einer speziellen gemeinsamen Verteilung gezeigt (siehe Abbildung 1). Dabei wird X als Summe von Z und einer unabhängigen Störgröße modelliert. Die resultierende obere Schranke lautet:

R(D) ≤ (1/2) log(σ²/D)  für D ≤ σ²

Zusammen mit der unteren Schranke ergibt sich für die Gaußverteilung eine exakte Formel: R(D) = (1/2) log(σ²/D). Dies ist die Rate-Distortion-Funktion einer Gaußquelle mit mittlerer quadratischer Verzerrung.

Rate-Distortion für gleichverteilte Quelle mit Hamming-Verzerrung

Betrachten wir eine diskrete Quelle X, die gleichverteilt auf {1,2,…,m} ist. Die Hamming-Verzerrung zählt, ob X und Xˆ übereinstimmen: d(x,xˆ)=0 falls x=xˆ, sonst 1. Die Rate-Distortion-Funktion hierfür ist:

Für D=0: R(0) = log m (keine Verzerrung erlaubt).
Für D ≥ (m-1)/m: R(D)=0 (man kann immer den häufigsten Wert raten).
Für 0 < D < (m-1)/m: R(D) = log m - H(D) - D log(m-1).

Fano-Ungleichung liefert die untere Schranke: Sie besagt, dass die Fehlerwahrscheinlichkeit bei der Schätzung von X aus Xˆ mindestens so groß ist wie (H(X|Xˆ)-1)/log m. Dies wird genutzt, um R(D) ≥ log m - H(D) - D log(m-1) zu zeigen.

Anwendung: Fehlerkorrektur in der DNA-Sequenzierung

In der Bioinformatik werden DNA-Basen (A, C, G, T) sequenziert – das ist eine gleichverteilte Quelle mit m=4. Die Hamming-Verzerrung ist hier die Anzahl der falsch gelesenen Basen. Die Rate-Distortion-Funktion hilft, die minimale Anzahl an Bits zu bestimmen, um die Sequenz mit einer bestimmten Fehlerrate zu speichern. Ähnlich wie bei QR-Codes, die Fehlerkorrektur verwenden, um auch bei Verschmutzung lesbar zu bleiben.

Rate-Distortion für zwei unabhängige Quellen

Die Frage: Kann man zwei unabhängige Quellen gemeinsam besser komprimieren als getrennt? Die Antwort lautet: Nein, im Allgemeinen nicht. Es gilt:

R_{X,Y}(D1,D2) ≥ R_X(D1) + R_Y(D2)

Gleichheit gilt, wenn die Quellen unabhängig sind und die Verzerrungsmaße getrennt betrachtet werden. Das bedeutet, dass die gemeinsame Kompression keinen Vorteil bringt – die Summe der Einzelraten ist optimal.

Beispiel aus der Praxis: Video-Codecs

Bei der Videokompression werden oft Farb- und Helligkeitskanäle getrennt kodiert (z.B. YUV). Da die Kanäle statistisch abhängig sind, kann man durch gemeinsame Kodierung tatsächlich Bits sparen. In diesem Fall sind die Quellen aber nicht unabhängig, sodass die Ungleichung nicht als Gleichheit gilt. Moderne Codecs wie H.265/HEVC oder AV1 nutzen solche Abhängigkeiten aus.

Distortion-Rate-Funktion D(R)

Die Distortion-Rate-Funktion D(R) ist die Umkehrfunktion von R(D). Sie gibt die minimal mögliche Verzerrung bei gegebener Rate an. Wichtige Eigenschaften:

Monoton fallend: Je höher die Rate, desto geringer die Verzerrung.
Konvex: Die Funktion ist konvex in R (abnehmende Grenzerträge).

Diese Eigenschaften sind intuitiv: Mit mehr Bits kann man die Qualität verbessern, aber der zusätzliche Nutzen jedes Bits wird immer geringer. Das erinnert an das Gesetz des abnehmenden Grenznutzens in der Wirtschaft.

Beweisschritte für die Datenverarbeitungsungleichung

In der Aufgabenstellung wird gezeigt, dass für i.i.d. Quellen und einen optimalen Code mit Rate R gilt: D(R) ≥ E[d(X, Xˆ)] mit I(X; Xˆ) ≤ R. Die Beweisschritte nutzen die Datenverarbeitungsungleichung und die Tatsache, dass die gegenseitige Information durch die Rate begrenzt ist. Konkret:

Für einen Code mit Rate R gilt I(X^n; f(X^n)) ≤ nR.
Da der Dekodierer nur f(X^n) sieht, gilt I(X^n; Xˆ^n) ≤ nR.
Mit der Kette von Ungleichungen und der i.i.d.-Eigenschaft folgt die Behauptung.

Zusammenfassung und Ausblick

Die Rate-Distortion-Theorie ist ein mächtiges Werkzeug, um die Grenzen der Kompression zu verstehen. Von der Shannon-Untergrenze für Gaußquellen bis zur optimalen Kodierung unabhängiger Quellen – die Konzepte sind in vielen Bereichen anwendbar: Streaming-Dienste optimieren ihre Bitrate, KI-Modelle werden komprimiert, und Datenwissenschaftler minimieren Speicherplatz. Mit den heutigen Trends wie Generative AI und Metaverse wird die Nachfrage nach effizienter Kompression nur noch steigen.

Wenn du mehr über Informationstheorie lernen möchtest, vertiefe dich in die Quellencodierung oder Kanalcodierung – beides Schlüsselgebiete für die moderne Kommunikation.