Application to Digital Signal Transmission

1. Information Theory
2. Information zwischen zwei wertdiskreten Zufallsgrößen
3. Application to Digital Signal Transmission

• Previous page
• Next page

• Previous page
• Next page

Informationstheoretisches Modell der Digitalsignalübertragung

Die bisher allgemein definierten Entropien werden nun auf die Digitalsignalübertragung angewendet, wobei wir von einem digitalen Kanalmodell ohne Gedächtnis (englisch: Discrete Memoryless Channel, DMC) entsprechend der nachfolgenden Grafik ausgehen:

• Die Menge der möglichen Quellensymbole wird durch die diskrete Zufallsgröße $X$ charakterisiert, wobei $|X|$ den Quellensymbolumfang angibt:

• Entsprechend kennzeichnet $Y$ die Menge der Sinkensymbole mit dem Symbolvorrat $|Y|$:

• Meist gilt $|Y|$ = $|X|$. Möglich ist aber auch $|Y|$ > $|X|$, zum Beispiel beim Binary Erasure Channel (BEC) mit $X$ = {0, 1} und $Y$ = {0, 1, E} ⇒ $|X|$ = 2, $|Y|$ = 3.
• Das Sinkensymbol $E$ kennzeichnet eine Auslöschung (englisch: Erasure). Das Ereignis $Y$ = $E$ gibt an, dass eine Entscheidung für 0 oder für 1 zu unsicher wäre.
• Die Symbolwahrscheinlichkeiten der Quelle und der Sinke sind in der oberen Grafik durch die Wahrscheinlichkeitsfunktionen $P_X(X)$ und $P_Y(Y)$ berücksichtigt, wobei gilt:

• Es gelte: $P_X(X)$ und $P_Y(Y)$ enthalten keine Nullen ⇒ $\text{supp}(P_X)$ = $P_X$, $\text{supp}(P_Y)$ = $P_Y$. Diese Voraussetzung erleichtert die Modellbeschreibung, ohne Verlust an Allgemeingültigkeit.
• Alle Übergangswahrscheinlichkeiten des digitalen gedächtnislosen Kanals (DMC) werden durch die bedingte Wahrscheinlichkeitsfunktion $P_{Y|X}(Y|X)$ erfasst. Mit $x_μ ∈ X$ und $y_κ ∈ Y$ gelte hierfür folgende Definition:

In obiger Grafik ist $P_{Y|X}(⋅)$ als ein Block mit $|X|$ Eingängen und $|Y|$ Ausgängen dargestellt. Die blauen Verbindungen markieren die Übergangswahrscheinlichkeiten $\text{Pr}(y_i | x_μ)$ ausgehend von $x_μ$ mit 1 ≤ $i$ ≤ $|Y|$, während alle roten Verbindungen bei $y_κ$ enden: $\text{Pr}(y_κ | x_i)$ mit 1 ≤ $i$ ≤ $|X|$.

Bevor wir die Entropien für die einzelnen Wahrscheinlichkeitsfunktionen angeben, nämlich $P_X(X) ⇒ H(X)$, $P_Y(Y) ⇒ H(Y)$, $P_{XY}(X) ⇒ H(XY)$, $P_Y|X(Y|X) ⇒ H(Y|X)$, $P_{X|Y}(X|Y) ⇒ H(X|Y)$, sollen die Aussagen der letzten Seite an einem Beispiel verdeutlicht werden.

Im Buch „Einführung in die Kanalcodierung” behandeln wir den Binary Erasure Channel (BEC), der rechts in etwas modifizierter Form skizziert ist.

Dabei gelten folgende Voraussetzungen:

• Das Eingangsalphabet ist binär: $X$ = (0, 1) ⇒ $|X|$ = 2, während am Ausgang drei Werte möglich sind: $Y$ = (0, 1, $E$) ⇒ $|Y|$ = 3.
• „E” kennzeichnet den Fall, dass sich der Empfänger aufgrund von zu großen Kanalstörungen nicht für eines der Binärsymbole 0 oder 1 entscheiden kann. „E” steht hierbei für Erasure (Auslöschung).
• Beim BEC gemäß obiger Skizze werden sowohl eine gesendete „0” als auch eine „1” mit der Wahrscheinlichkeit $λ$ ausgelöscht, während die Wahrscheinlichkeit einer richtigen Übertragung jeweils 1 – $λ$ beträgt.
• Dagegen werden Übertragungsfehler durch das BEC–Modell ausgeschlossen ⇒ die bedingten Wahrscheinlichkeiten Pr( $Y$ = 1 | $X$ = 0 ) sowie Pr( $Y$ = 0 | $X$ = 1) sind jeweils 0.

Beim Sender seien die Nullen und Einsen nicht unbedingt gleichwahrscheinlich. Vielmehr verwenden wir die beiden Wahrscheinlichkeitsfunktionen

Aus obigem Modell erhalten wir dann:

Fassen wir nun $P_X(X)$ und $P_Y(Y)$ als Vektoren auf, so lässt sich das Ergebnis wie folgt darstellen:

wobei die Übergangswahrscheinlichkeiten $\text{Pr}(y_κ | x_μ)$ durch folgende Matrix berücksichtigt sind:

Beachten Sie: Wir haben diese Darstellung nur gewählt, um die Beschreibung zu vereinfachen. $P_X(X)$ und $P_Y(Y)$ sind keine Vektoren im eigentlichen Sinne und $P_{Y|X}(Y|X)$ ist keine Matrix.

Alle in Kapitel 3.2 definierten Entropien gelten auch für die Digitalsignalübertragung. Es ist aber zweckmäßig, anstelle des bisher verwendeten Schaubildes (linke Grafik) die rechte Darstellung zu wählen, bei der die Richtung von der Quelle $X$ zur Sinke $Y$ erkennbar ist.

Interpretieren wir nun ausgehend vom allgemeinen DMC–Kanalmodell die rechte Grafik:

• Die Quellenentropie (englisch: Source Entropy) $H(X)$ bezeichnet den mittleren Informationsgehalt der Quellensymbolfolge. Mit dem Symbolumfang $|X|$ gilt:

• Die Äquivokation (auch Rückschlussentropie genannt, englisch: Equivocation) $H(X|Y)$ gibt den mittleren Informationsgehalt an, den ein Betrachter, der über die Sinke $Y$ genau Bescheid weiß, durch Beobachtung der Quelle $X$ gewinnt:

• Die Äquivokation ist der Anteil der Quellenentropie $H(X)$, der durch Kanalstörungen (bei digitalem Kanal: Übertragungsfehler) verloren geht. Es verbleibt die Transinformation (englisch: Mutual Information) $I(X; Y)$, die zur Sinke gelangt:

• Die Irrelevanz (manchmal auch Streuentropie genannt, englisch: Irrelevance) $H(Y|X)$ gibt den mittleren Informationsgehalt an, den ein Betrachter, der über die Quelle $X$ genau Bescheid weiß, durch Beobachtung der Sinke $Y$ gewinnt:

• Die Sinkenentropie $H(Y)$, der mittlere Informationsgehalt der Sinke, ist die Summe aus der nützlichen Transinformation $I(X; Y)$ und der Irrelevanz $H(Y|X)$, die ausschließlich von Kanalfehlern herrührt:

Transinformationsberechnung für den Binärkanal

Die Definitionen der letzten Seite sollen nun an einem Beispiel verdeutlicht werden, wobei wir bewusst vermeiden, die Berechnungen durch die Ausnutzung von Symmetrien zu vereinfachen.

Wir betrachten den allgemeinen Binärkanal (englisch: Binary Channel) ohne Gedächtnis gemäß der Skizze mit den Verfälschungswahrscheinlichkeiten.

Außerdem gehen wir von nicht gleichwahrscheinlichen Quellensymbolen aus:

Mit der binären Entropiefunktion erhält man so für die Quellenentropie:

Für die Wahrscheinlichkeitsfunktion der Sinke sowie für die Sinkenentropie ergibt sich somit:

Auf der nächsten Seite werden noch berechnet:

• die Verbundentropie $H(XY)$,
• die Transinformation $I(X; Y)$,
• die Rückschlussentropie $H(X|Y)$ ⇒ Äquivokation,
• die Streuentropie $H(Y|X)$ ⇒ Irrelevanz.

Diese Ergebnisse sind in der folgenden zusammenfassenden Grafik bereits mit aufgenommen.

Wir betrachten weiter den allgemeinen Binärkanal (englisch: Binary Channel) ohne Gedächtnis gemäß der Skizze, und es gelte weiterhin:

Die Verbundwahrscheinlichkeiten $p_{\{μκ\}}$ = $\text{Pr}[(X = μ) ∩ (Y = κ)]$ zwischen Quelle und Sinke sind:

Daraus erhält man für

• die Verbundentropie (englisch Joint Entropy):

• die Transinformation (englisch Mutual Information):

• die Äquivokation (oder Rückschlussentropie):

• die Irrelevanz (oder Streuentropie):

Die Ergebnisse sind in der folgenden Grafik nochmals zusammengefasst.

Anmerkung: Äquivokation und Irrelevanz hätte man auch direkt (aber mit Mehraufwand) aus den entsprechenden Wahrscheinlichkeitsfunktionen berechnen können. Zum Beispiel die Irrelevanz:

Definition und Bedeutung der Kanalkapazität

Wir betrachten weiter einen diskreten gedächtnislosen Kanal (englisch: Discrete Memoryless Channel, kurz DMC) mit einer endlichen Anzahl an Quellensymbolen ⇒ $|X|$ und ebenfalls nur endlich vielen Sinkensymbolen ⇒ $|Y|$, wie auf der ersten Seite dieses Kapitels dargestellt. Berechnet man die Transinformation $I(X, Y)$ wie zuletzt an einem Beispiel ausgeführt, so hängt diese auch von der Quellenstatistik ⇒ $P_X(X)$ ab. Ergo: $I(X, Y)$ ist keine reine Kanalkenngröße.

Die von Claude E. Shannon eingeführte Kanalkapazität (englisch: Channel Capacity) lautet entsprechend seinem Standardwerk :

Da nach dieser Definition stets die bestmögliche Quellenstatistik zugrunde liegt, hängt $C$ nur von den Kanaleigenschaften ⇒ $P_{Y|X}(Y|X)$ ab, nicht jedoch von $P_X(X)$. Oft wird die Zusatzeinheit „bit/Kanalzugriff” hinzugefügt, bei englischen Texten „bit/use”.

C. E. Shannon benötigte diese Kanalbeschreibungsgröße $C$, um das Kanalcodierungstheorem formulieren zu können – eines der Highlights der von ihm begründeten Informationstheorie.

Shannons Kanalcodierungstheorem: Zu jedem Übertragungskanal mit der Kanalkapazität $C$ > 0 existiert (mindestens) ein $(k, n)$–Blockcode, dessen (Block–)Fehlerwahrscheinlichkeit gegen Null geht, so lange die Coderate $R = $k/n$ kleiner oder gleich der Kanalkapazität ist: $R ≤ C$. Voraussetzung hierfür ist allerdings, dass für die Blocklänge dieses Codes gilt: $n → ∞$.

Den Beweis dieses Theorems finden Sie zum Beispiel in , und . Der Beweis würde den Rahmen unseres Lerntutorials sprengen.

Im Kapitel 4.3 wird im Zusammenhang mit dem wertkontinuierlichen AWGN–Kanalmodell ausgeführt, welche phänomenal große Bedeutung Shannons informationstheoretisches Theorem für die gesamte Informationstechnik besitzt, nicht nur für ausschließlich theoretisch Interessierte, sondern ebenso auch für Praktiker. Wie in Aufgabe A3.12 gezeigt werden soll, gilt auch der Umkehrschluss: Ist die Rate des verwendeten (n, k)–Blockcodes größer als die Kanalkapazität ⇒ R = k/n > C, so kann niemals eine beliebig kleine Blockfehlerwahrscheinlichkeit erreicht werden. Auch diesen Beweis finden Sie zum Beispiel wieder in [CT06], [Kra13] und [Meck09].