Theorie der Rate-Verzerrung ist ein Hauptzweig der Informationstheorie, die die theoretischen Fundamente für die lossy Datenkompression zur Verfügung stellt; es richtet das Problem, die minimale Zahl von Bit pro Symbol, wie gemessen, durch die Rate R zu bestimmen, der über einen Kanal mitgeteilt werden sollte, so dass die Quelle (eingegebenes Signal) am Empfänger (Produktionssignal) ungefähr wieder aufgebaut werden kann, ohne eine gegebene Verzerrung D. zu überschreiten

Einführung

Theorie der Rate-Verzerrung gibt einen analytischen Ausdruck dafür, wie viel Kompression mit lossy Kompressionsmethoden erreicht werden kann. Viele vom vorhandenen Audio, der Rede, dem Image und den Videokompressionstechniken haben verwandelt sich, quantization, und Zuteilungsverfahren der Bit-Rate, die auf der allgemeinen Gestalt von Funktionen der Rate-Verzerrung Kapital anhäufen.

Theorie der Rate-Verzerrung wurde von Claude Shannon in seiner Foundational-Arbeit an der Informationstheorie geschaffen.

In der Theorie der Rate-Verzerrung, wie man gewöhnlich versteht, wird die Rate als die Zahl von Bit pro Datenprobe versorgt oder übersandt. Der Begriff der Verzerrung ist ein Thema der andauernden Diskussion. Im einfachsten Fall (der wirklich in den meisten Fällen verwendet wird) wird die Verzerrung als der erwartete Wert des Quadrats des Unterschieds zwischen Eingang und Produktionssignal (d. h., der karierte Mittelfehler) definiert. Jedoch, da wir wissen, dass die meisten lossy Kompressionstechniken auf Daten funktionieren, die von menschlichen Verbrauchern wahrgenommen werden (Musik zuhörend, Bilder und Video beobachtend), sollte das Verzerrungsmaß vorzugsweise auf der menschlichen Wahrnehmung und vielleicht Ästhetik modelliert werden: Viel wie der Gebrauch der Wahrscheinlichkeit in der lossless Kompression können Verzerrungsmaßnahmen mit Verlust-Funktionen, wie verwendet, nach der Bewertung von Bayesian und Entscheidungstheorie schließlich identifiziert werden. In der Audiokompression, perceptual Modelle (und deshalb perceptual Verzerrungsmaßnahmen) werden relativ gut entwickelt und alltäglich in Kompressionstechniken wie MP3 oder Vorbis verwendet, aber sind häufig nicht leicht, in die Theorie der Rate-Verzerrung einzuschließen. Im Image und der Videokompression werden die menschlichen Wahrnehmungsmodelle weniger gut entwickelt, und Einschließung wird größtenteils auf den JPEG und MPEG beschränkt, der (quantization, Normalisierung) Matrix beschwert.

Funktionen der Rate-Verzerrung

Die Funktionen, die die Rate und Verzerrung verbinden, werden als die Lösung des folgenden Minimierungsproblems gefunden:

:

Hier Q (y | x), manchmal genannt einen Testkanal, ist die bedingte Wahrscheinlichkeitsdichte-Funktion (PDF) der Nachrichtenkanalproduktion (zusammengepresstes Signal) Y für einen gegebenen Eingang (ursprüngliches Signal) X, und ich (Y; X) ist die gegenseitige Information zwischen Y und X definiert als

:

wo H (Y) und H (Y | X) das Wärmegewicht des Produktionssignals Y sind und das bedingte Wärmegewicht der Produktion gegeben das Eingangssignal beziehungsweise signalisieren:

::

- \int_ {-\infty} ^ {\\infty} \int_ {-\infty} ^\\infty Q_ {Y|X} (y|x) P_X (x) \log_ {2} (Q_ {Y|X} (y|x)) \, dx \, dy. </Mathematik>

Das Problem kann auch als eine Verzerrungsrate-Funktion formuliert werden, wo wir den infimum über erreichbare Verzerrungen für die gegebene Rate-Einschränkung finden. Der relevante Ausdruck ist:

:

Die zwei Formulierungen führen zu Funktionen, die Gegenteile von einander sind.

Die gegenseitige Information kann als ein Maß für die vorherige Unklarheit verstanden werden, die der Empfänger über das Signal des Absenders (H (Y)), verringert durch die Unklarheit hat, die nach dem Empfang der Information über das Signal des Absenders (H (Y | X)) verlassen wird. Natürlich ist die Abnahme in der Unklarheit wegen des mitgeteilten Betrags der Information, die ich ist (Y; X).

Als ein Beispiel, im Falle dass es keine Kommunikation überhaupt, dann H (Y |X) = H (Y) und ich gibt (Y; X) = 0. Wechselweise, wenn der Nachrichtenkanal vollkommen ist und das empfangene Signal Y zum Signal X am Absender, dann H (Y | X) = 0 und ich identisch ist (Y; X) = H (Y) = H (X).

In der Definition der Funktion der Rate-Verzerrung sind D und D die Verzerrung zwischen X und Y für einen gegebenen Q (y | x) und die vorgeschriebene maximale Verzerrung beziehungsweise. Wenn wir den karierten Mittelfehler als Verzerrungsmaß verwenden, haben wir (für mit dem Umfang dauernde Signale):

:

P_ {X, Y} (x, y) (x-y) ^2 \, dx \, dy = \int_ {-\infty} ^\\infty \int_ {-\infty} ^\\infty

Q_ {Y|X} (y|x) P_ {X} (x) (x-y) ^2 \, dx \, dy </Mathematik>

Da sich die obengenannten Gleichungen zeigen, verlangt das Berechnen einer Funktion der Rate-Verzerrung die stochastische Beschreibung des Eingangs X in Bezug auf den PDF P (x), und zielt dann darauf, den bedingten PDF Q zu finden (y | x), die Quote für eine gegebene Verzerrung D minimieren. Diese Definitionen können Maß theoretisch formuliert werden, um getrennt dafür verantwortlich zu sein, und haben zufällige Variablen ebenso gemischt.

Eine analytische Lösung dieses Minimierungsproblems ist häufig schwierig, außer in einigen Beispielen vorzuherrschen, für die wir als nächstes zwei der am besten bekannten Beispiele anbieten. Wie man bekannt, folgt die Funktion der Rate-Verzerrung jeder Quelle mehreren grundsätzlichen Eigenschaften, die wichtigsten, die das sind, es ist ein dauernder, monotonically das Verringern konvex (U) Funktion, und so ist die Gestalt für die Funktion in den Beispielen typisch (sogar gemessene Funktionen der Rate-Verzerrung im echten Leben neigen dazu, sehr ähnliche Formen zu haben).

Obwohl analytische Lösungen dieses Problems knapp sind, gibt es obere und niedrigere Grenzen zu diesen Funktionen einschließlich des berühmten Shannons Hat Tiefer Gebunden (SLB), der im Fall vom karierten Fehler und den memoryless Quellen, das für willkürliche Quellen mit dem begrenzten Differenzialwärmegewicht, feststellt

:

wo h (D) das Differenzialwärmegewicht von Gaussian zufällige Variable mit der Abweichung D ist. Das tiefer gebunden ist zu Quellen mit dem Gedächtnis und den anderen Verzerrungsmaßnahmen ausziehbar. Eine wichtige Eigenschaft des SLB ist, dass es im niedrigen Verzerrungsregime für eine breite Klasse von Quellen und in einigen Gelegenheiten asymptotisch dicht ist, fällt es wirklich mit der Funktion der Rate-Verzerrung zusammen. Shannon Lower Bounds kann allgemein gefunden werden, ob die Verzerrung zwischen irgendwelchen zwei Zahlen als eine Funktion des Unterschieds zwischen dem Wert dieser zwei Zahlen ausgedrückt werden kann.

Der Blahut-Arimoto Algorithmus, co-invented durch Richard Blahut, ist eine elegante wiederholende Technik, um Funktionen der Rate-Verzerrung von willkürlichen begrenzten Alphabet-Quellen des Eingangs/Produktion numerisch zu erhalten, und viel Arbeit ist getan worden, um ihn zu allgemeineren Problem-Beispielen zu erweitern.

Wenn

man mit stationären Quellen mit dem Gedächtnis arbeitet, ist es notwendig, die Definition der Rate-Verzerrungsfunktion zu modifizieren, und es muss im Sinne einer Grenze übernommen Folgen von zunehmenden Längen verstanden werden.

:

R (D) = \lim_ {n \rightarrow \infty} R_n (D)

</Mathematik>

wo

:

R_n (D) = \frac {1} {n} \inf_ {Q_ {Y^n|X^n} \in \mathcal {Q}} ich (Y^n, X^n)

</Mathematik>

und

:

\mathcal {Q} = \{Q_ {Y^n|X^n} (Y^n|X^n, X_0): E [d (X^n, Y^n)] \leq D \}\

</Mathematik>

wo Exponenten eine ganze Folge bis zu dieser Zeit anzeigen und die Subschrift 0 anfänglichen Staat anzeigt.

Memoryless (unabhängige) Quelle von Gaussian

Wenn wir annehmen, dass P (x) Gaussian mit der Abweichung σ ist, und wenn wir annehmen, dass aufeinander folgende Proben des Signals X stochastisch unabhängig sind (oder, wenn Sie mögen, ist die Quelle memoryless, oder das Signal ist unkorreliert), wir finden den folgenden analytischen Ausdruck für die Funktion der Rate-Verzerrung:

:

\frac {1} {2 }\\log_2 (\sigma_x^2/D), & \mbox {wenn} D \le \sigma_x^2 \\\\

0, & \mbox {wenn} D> \sigma_x^2

\end {Matrix} \right.

</Mathematik>

Die folgende Zahl zeigt, wie was diese Funktion aussieht:

Theorie der Rate-Verzerrung sagt uns, dass kein Kompressionssystem besteht, der außerhalb der Grauzone leistet. Je näher ein praktisches Kompressionssystem zum (tiefer) gebundenen Rot ist, desto besser es leistet. Als eine allgemeine Regel hat das gebunden kann nur durch die Erhöhung des Codierblock-Länge-Parameters erreicht werden. Dennoch sogar an der Einheit blocklengths kann man häufig guter (Skalar) quantizers finden, die in Entfernungen von der Funktion der Rate-Verzerrung funktionieren, die praktisch wichtig sind.

Diese Funktion der Rate-Verzerrung hält nur für Quellen von Gaussian memoryless. Es ist bekannt, dass die Quelle von Gaussian die "schwierigste" Quelle ist, um zu verschlüsseln: Für einen gegebenen Mittelquadratfehler verlangt es die größte Zahl von Bit. Die Leistung eines praktischen Kompressionssystems, das "daran arbeitet, sagt Images", kann unter dem R (D) gut sein tiefer hat gezeigt gebunden.

Das Anschließen der Theorie der Rate-Verzerrung, Kapazität zu leiten

Nehmen Sie an, dass wir Information über eine Quelle dem Benutzer mit einer Verzerrung übersenden wollen, die nicht D zu weit geht. Theorie der Rate-Verzerrung sagt uns, die mindestens R (D) Bit/Symbol der Information von der Quelle den Benutzer erreichen müssen. Wir wissen auch vom Kanalcodierlehrsatz von Shannon, dass, wenn das Quellwärmegewicht H Bit/Symbol ist, und die Kanalkapazität C ist (wo C