Das Quellcodierungstheorem von Shannon - Shannon's source coding theorem

In der Informationstheorie , Codierung Shannon-Theorems Quelle (oder geräuschlosen Kodierungs Theorem ) legt die Grenzen der möglichen Datenkompression , und die Betriebs Bedeutung der Shannon Entropie .

Genannt nach Claude Shannon , dem Source - Theorem Codierung zeigt , dass (in der Grenze, wenn die Länge eines Stroms von unabhängigem und Zufallsvariable gleich verteilt (iid) Daten gegen Unendlich) es unmöglich ist , die Daten , so dass die Code - Rate zu komprimieren , (durchschnittliche Anzahl von Bits pro Symbol) kleiner als die Shannon-Entropie der Quelle ist, ohne dass praktisch sicher ist, dass Informationen verloren gehen. Es ist jedoch möglich, die Coderate mit vernachlässigbarer Verlustwahrscheinlichkeit beliebig nahe an die Shannon-Entropie zu bringen.

Das Quellencodierungstheorem für Symbolcodes legt eine Ober- und eine Untergrenze für die minimal mögliche erwartete Länge von Codewörtern in Abhängigkeit von der Entropie des Eingangswortes (das als Zufallsvariable betrachtet wird ) und der Größe des Zielalphabets fest.

Aussagen

Quellencodierung ist eine Abbildung von (eine Abfolge von) Symbolen von einer Informationsquelle zu einer Sequenz von Alphabet - Symbolen ( in der Regel Bits) , so dass die Quellensymbole exakt aus den binären Bits (lossless Quellencodierung) oder in einem gewissen Verzerrung zurückgewonnen werden ( verlustbehaftete Quellcodierung). Dies ist das Konzept der Datenkomprimierung .

Quellcodierungstheorem

In der Informationstheorie besagt das Source Coding Theorem (Shannon 1948) informell (MacKay 2003, S. 81, Cover 2006, Kapitel 5):

$N$ i.id Zufallsvariablen mit jeweils der Entropie $H (X)$ können mit vernachlässigbarem Informationsverlustrisiko in mehr als $N H (X)$ Bits komprimiert werden , da $N \to \infty$ ; aber umgekehrt, wenn sie in weniger als $NH (X)$ Bits komprimiert werden , ist es praktisch sicher, dass Informationen verloren gehen.

Quellcodierungstheorem für Symbolcodes

Seien $Σ 1, Σ 2$ zwei endliche Alphabete und sei $Σ * 1$ und $Σ * 2$ die Menge aller endlichen Wörter aus diesen Alphabeten (jeweils) bezeichnen.

Angenommen, $X$ sei eine Zufallsvariable mit Werten in $Σ 1$ und sei $f$ ein eindeutig dekodierbarer Code aus $Σ$ $* 1$ zu $Σ * 2$ wobei $|Σ 2 | = ein$ . Sei $S$ die Zufallsvariable, die durch die Länge des Codeworts $f$ $($ $X$ $) gegeben ist$ .

Wenn $f$ in dem Sinne optimal ist, dass es die minimal erwartete Wortlänge für $X hat$ , dann (Shannon 1948):

{\frac {H(X)}{\log_{2}a}}\leq \mathbb {E} [S]<{\frac {H(X)}{\log_{2}a }}+1

Wo bezeichnet den Erwartungswertoperator . $\mathbb{E}$

Beweis: Quellcodierungstheorem

Gegeben $X$ ist eine iid- Quelle, ihre Zeitreihe $X 1, ..., X n$ ist iid mit Entropie $H (X)$ im diskretwertigen Fall und differentieller Entropie im stetigwertigen Fall. Das Quellencodierungstheorem besagt, dass für jedes $ε > 0$ , dh für jede Rate $H (X) + ε$ größer als die Entropie der Quelle, es groß genug $n$ und einen Codierer gibt, der $n$ iid Wiederholung der Quelle akzeptiert, $X 1: n$ , und ordnet sie $n (H (X) + ε)$ binäre Bits , so daß die Source - Symbole $X 1: n$ wiedergewinnbar sind aus den binären Bits mit einer Wahrscheinlichkeit von mindestens $1 - ε$ .

Nachweis der Erreichbarkeit. Fixiere einige $ε > 0$ und lass

p(x_{1},\ldots,x_{n})=\Pr\left[X_{1}=x_{1},\cdots,X_{n}=x_{n}\right].

Der typische Satz, $A ε nein$ , ist wie folgt definiert:

A_{n}^{\varepsilon}=\left\{(x_{1},\cdots ,x_{n})\ :\ \left|-{\frac {1}{n}}\log p(x_{1},\cdots,x_{n})-H_{n}(X)\right|<\varepsilon\right\}.

Die asymptotische Äquipartitionseigenschaft (AEP) zeigt, dass für groß genug $n$ die Wahrscheinlichkeit, dass eine von der Quelle erzeugte Folge in der typischen Menge liegt, $A ε nein$ , wie definiert nähert sich einem. Insbesondere für hinreichend große $n$ , kann beliebig nahe 1, und insbesondere größer als gemacht werden (siehe AEP für einen Nachweis). $P((X_{1},X_{2},\cdots,X_{n})\in A_{n}^{\varepsilon})$ $1-\varepsilon$

Die Definition typischer Mengen impliziert, dass die Folgen, die in der typischen Menge liegen, erfüllen:

2^{-n(H(X)+\varepsilon)}\leq p\left(x_{1},\cdots,x_{n}\right)\leq 2^{-n(H(X )-\varepsilon )}

Beachten Sie, dass:

Die Wahrscheinlichkeit, dass eine Folge aus $A . gezogen wird$ $(X_{1},X_{2},\cdots X_{n})$ $ε nein$ ist größer als $1 - ε$ .
$\left|A_{n}^{\varepsilon}\right|\leq 2^{n(H(X)+\varepsilon)}$ , die aus der linken Seite (untere Schranke) für folgt . $p(x_{1},x_{2},\cdots x_{n})$
$\left|A_{n}^{\varepsilon}\right|\geq (1-\varepsilon)2^{n(H(X)-\varepsilon)}$ , die sich aus der oberen Schranke für und der unteren Schranke für die Gesamtwahrscheinlichkeit der ganzen Menge $A .$ ergibt $p(x_{1},x_{2},\cdots x_{n})$ $ε nein$ .

Da Bits ausreichen, um auf einen beliebigen String in diesem Satz zu zeigen. $\left|A_{n}^{\varepsilon}\right|\leq 2^{n(H(X)+\varepsilon)},n(H(X)+\varepsilon)$

Der Kodierungsalgorithmus: Der Kodierer prüft, ob die Eingabesequenz innerhalb der typischen Menge liegt; wenn ja, gibt es den Index der Eingabesequenz innerhalb des typischen Satzes aus; Wenn nicht, gibt der Codierer eine beliebige $n (H (X) + ε)$ stellige Zahl. Solange die Eingabesequenz innerhalb der typischen Menge liegt (mit einer Wahrscheinlichkeit von mindestens $1 - ε$ ), macht der Encoder keinen Fehler. Die Fehlerwahrscheinlichkeit des Encoders ist also nach oben durch $ε begrenzt$ .

Beweis für Konversation. Die Umkehrung wird bewiesen, indem gezeigt wird, dass jede Menge kleiner als $A ε nein$ (im Sinne von Exponent) würde eine Menge von Wahrscheinlichkeiten abdecken, die von $1$ wegbegrenzt ist .

Beweis: Quellcodierungstheorem für Symbolcodes

Für $1 \leq i \leq n$ sei $s i$ die Wortlänge jedes möglichen $x i$ . Definiere , wobei $C$ so gewählt wird, dass $q$ $1$ $+ ... +$ $q$ $n$ $= 1 ist$ . Dann $q_{i}=a^{-s_{i}}/C$

{\begin{ausgerichtet}H(X)&=-\sum _{i=1}^{n}p_{i}\log _{2}p_{i}\\&\leq -\sum _{i=1}^{n}p_{i}\log _{2}q_{i}\\&=-\sum _{i=1}^{n}p_{i}\log _{2 }a^{-s_{i}}+\sum _{i=1}^{n}p_{i}\log _{2}C\\&=-\sum _{i=1}^{n }p_{i}\log_{2}a^{-s_{i}}+\log_{2}C\\&\leq -\sum_{i=1}^{n}-s_{i }p_{i}\log_{2}a\\&\leq\mathbb{E} S\log_{2}a\\\end{ausgerichtet}}

wobei die zweite Linie aus der Gibbs-Ungleichung und die fünfte Linie aus der Kraft-Ungleichung folgt :

C=\sum_{i=1}^{n}a^{-s_{i}}\leq 1

also $log C \leq 0$ .

Für die zweite Ungleichung können wir

s_{i}=\lceil -\log_{a}p_{i}\rceil

damit

-\log_{a}p_{i}\leq s_{i}<-\log_{a}p_{i}+1

und so

a^{-s_{i}}\leq p_{i}

und

\sum a^{-s_{i}}\leq \sum p_{i}=1

und so existiert nach der Kraft-Ungleichung ein präfixfreier Code mit diesen Wortlängen. Somit erfüllt das minimale $S$

{\begin{ausgerichtet}\mathbb {E} S&=\sum p_{i}s_{i}\\&<\sum p_{i}\left(-\log_{a}p_{i} +1\right)\\&=\sum -p_{i}{\frac {\log_{2}p_{i}}{\log_{2}a}}+1\\&={\frac {H(X)}{\log_{2}a}}+1\\\end{ausgerichtet}}

Erweiterung auf nicht stationäre unabhängige Quellen

Verlustfreie Quellencodierung mit fester Rate für zeitdiskrete, nicht stationäre unabhängige Quellen

Definiere typischen Satz $A ε nein$ wie:

A_{n}^{\varepsilon}=\left\{x_{1}^{n}\ :\ \left|-{\frac {1}{n}}\log p\left(X_{ 1},\cdots,X_{n}\right)-{\overline {H_{n}}}(X)\right|<\varepsilon\right\}.

Dann ist für gegebenes $δ > 0$ für $n$ groß genug $Pr(A ε nein) > 1 - δ$ . Jetzt codieren wir nur die Sequenzen in den typischen Satz, und übliche Methoden in der Quellcodierung zeigen, dass die Kardinalität dieses Satzes kleiner ist als . Somit wird auf einer mittleren, $H$ $n$ $($ $X$ $) +$ $ε$ Bits genügen zur Codierung mit einer Wahrscheinlichkeit von mehr als $1 -$ $δ$ , wobei $ε$ und $δ$ kann beliebig klein gemacht werden, indem man $n$ größer. $2^{n({\overline {H_{n}}}(X)+\varepsilon)}$

Siehe auch

Verweise

Languages

In other projects