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 ⇒ $\mathbf{R = k/n > C}$, so kann niemals eine beliebig kleine Blockfehlerwahrscheinlichkeit erreicht werden.

Auch diesen Beweis finden Sie zum Beispiel wieder in , und .

Kanalkapazität eines Binärkanals

Die Transinformation des allgemeinen (unsymmetrischen) Binärkanals gemäß der nebenstehenden Grafik wurde auf der vorletzten Seite berechnet. Bei diesem Modell werden die Eingangssymbole „0” und „1” unterschiedlich stark verfälscht:

Die Transinformation lässt sich mit $P_X(X)$ = $(p_0, p_1)$ in folgender Form kompakt darstellen:

Im Folgenden setzen wir $ε_0$ = 0.01 und $ε_1$ = 0.2. In der vierten Spalte der nebenstehenden Tabelle (grün hinterlegt) ist die Transinformation $I(X; Y)$ dieses unsymmetrischen Binärkanals abhängig von der Quellensymbolwahrscheinlichkeit $p_0$ = Pr( $X$ = 0 ) angegeben. Man erkennt:

• Die Transinformation $I(X; Y)$ hängt von den Symbolwahrscheinlichkeiten $p_0$ und $p_1$ = 1 – $p_0$ ab.
• Der Maximalwert der Transinformation ergibt sich für $p_0$ ≈ 0.55 ⇒ $p_1$ ≈ 0.45.
• Das Optimierungsergebnis $p_0 > p_1$ folgt aus der Relation $ε_0 < ε_1$ (die „0” wird weniger verfälscht).
• Die Kanalkapazität ist somit für $ε_0$ = 0.01, $ε_1$ = 0.2 gleich $C$ = 0.5779 bit/Kanalzugriff.

In obiger Gleichung ist als Sonderfall auch der Binary Symmetric Channel (BSC) mit dem Parameter $ε$ = $ε_0$ = $ε_1$ mitenthalten. In Aufgabe A3.9 wird die Transinformation des BSC–Kanals für $ε$ = 0.1, $p_0$ = 0.2 berechnet und in Aufgabe Z3.9 seine Kanalkapazität wie folgt angegeben:

Eigenschaften symmetrischer Kanäle

Die Kapazitätsberechnung des (allgemeinen) diskreten gedächtnislosen Kanals ist oftmals aufwändig. Sie vereinfacht sich entscheidend, wenn Symmetrien des Kanals ausgenutzt werden. Die Grafik zeigt zwei Beispiele.

• Beim gleichmäßig dispersiven Kanal (englisch: Uniformly Dispersive Channel) ergibt sich für alle Quellensymbole $x ∈ X$ die genau gleiche Menge an Übergangswahrscheinlichkeiten ⇒ $\{P_Y|X(y_κ|x)\}$ mit 1 ≤ $κ$ ≤ $|Y|$. In der linken Grafik ist dies durch die Werte $q$, $r$ und $s$ mit $q + r + s$ = 1 angedeutet.
• Beim gleichmäßig fokussierenden Kanal (englisch: Uniformely Focusing Channel) ergibt sich für alle Sinkensymbole $y ∈ Y$ die gleiche Menge an Übergangswahrscheinlichkeiten ⇒ $\{P_Y|X(y|x_μ)\}$ mit 1 ≤ $μ$ ≤ $|X|$. Hier muss nicht notwendigerweise $t + u + v$ = 1 gelten (siehe rechte Grafik).

Ist ein diskreter gedächtnisloser Kanal sowohl gleichmäßig dispersiv als auch gleichmäßig fokussierend, so liegt ein streng symmetrischer Kanal (englisch: Strongly Symmetric Channel) vor. Bei gleichverteiltem Quellenalphabet besitzt dieser die Kapazität

Für diese Gleichung kann jedes beliebige $x ∈ X$ herangezogen werden.

Diese Definition soll durch ein Beispiel verdeutlicht werden.

Beim betrachteten Kanal bestehen Verbindungen zwischen allen $|X|$ = 3 Eingängen und allen $|Y|$ = 3 Ausgängen:

• Eine rote Verbindung steht für $P_Y|X(y_κ|x_μ)$ = 0.7.
• Eine blaue Verbindung steht für $P_Y|X(y_κ|x_μ)$ = 0.2.
• Eine grüne Verbindung steht für $P_Y|X(y_κ|x_μ)$ = 0.1.

Nach obiger Gleichung gilt dann für die Kanalkapazität:

Hinweis: Der Zusatz „die gleiche Menge an Übergangswahrscheinlichkeiten” bedeutet nicht, dass $P_Y|X(y_κ|x_1)$ = $P_Y|X(y_κ|x_2)$ = $P_Y|X(y_κ|x_3)$ gelten muss. Vielmehr geht in diesem Beispiel von jedem Eingang ein roter, ein blauer und ein grüner Pfeil ab und an jeden Ausgang kommt ein roter, ein blauer und ein grüner Pfeil an. Die jeweiligen Reihenfolgen permutieren. R – G – B, B – R – G, G – B – R.

Ein Beispiel für einen streng symmetrischen Kanal ist der Binary Symmetric Channel (BSC). Dagegen ist der Binary Erasure Channel (BEC) nicht streng symmetrisch, da er

• zwar gleichmäßig dispersiv ist,
• aber nicht gleichmäßig fokussierend.

Nachfolgende Definition ist weniger restriktiv als die vorherige des streng symmetrischen Kanals.

Ein symmetrischer Kanal (englisch: Symmetric Channel) liegt vor, wenn er in mehrere (allgemein $L$) streng symmetrische Teilkanäle aufgeteilt werden kann, indem das Ausgangsalphabet $Y$ in $L$ Teilmengen $Y_1$, ..., $Y_L$ aufgespalten wird. Ein solcher symmetrischer Kanal besitzt folgende Kapazität:

Hierbei sind folgende Bezeichnungen verwendet:

• $p_l$ gibt die Wahrscheinlichkeit an, dass der $l$–te Teilkanal ausgewählt wird,
• $C_l$ ist die Kanalkapazität dieses $l$–ten Teilkanals.

Die Grafik verdeutlicht diese Definition für $L$ = 2, wobei die Teilkanäle mit A und B bezeichnet sind. An den unterschiedlich gezeichneten Übergängen (gestrichelt oder gepunktet) erkennt man, dass die zwei Teilkanäle durchaus verschieden sind, so dass $C_A$ ≠ $C_B$ gelten wird.

Für die Kapazität des Gesamtkanals erhält man somit allgemein:

Über die Struktur der beiden Teilkanäle wird hier keine Aussage gemacht. Im Beispiel auf der nächsten Seite wird sich zeigen, dass auch der BEC durch diese Grafik grundsätzlich beschreibbar ist. Allerdings müssen dann die zwei Ausgangssysmbole $y_3$ und $y_4$ zu einem einzigen Symbol zusammengefasst werden.

Die linke Grafik zeigt den Binary Erasure Channel (BEC) mit Eingang $X$ = {0, 1} und Ausgang $Y$ = {0, 1, $E$}, wie er meistens gezeichnet wird. Teilt man diesen entsprechend der rechten Grafik auf in einen idealen Kanal $(y = x)$ mit $y ∈ Y_A$ = {0, 1} ⇒ $C_A$ = 1 bit, einen Auslöschungskanal mit $y ∈ Y_B$ = $\{E \}$ ⇒ $C_B$ = 0, so ergibt sich mit den Teilkanalgewichtungen $p_A$ = 1 – $λ$ und $p_B$ = $λ$ für die Kanalkapazität:

Beide Kanäle sind streng symmetrisch. Für den (idealen) Kanal A gilt gleichermaßen

• für $X = 0$ und $X = 1$: $\text{Pr}(Y = 0|X) = \text{Pr}(Y = 1|X) = 1 – λ$ ⇒ gleichmäßig dispersiv,
• für $Y = 0$ und $Y = 1$: $\text{Pr}(Y|X = 0) = Pr(Y|X = 1) = 1 – λ$ ⇒ gleichmäßig fokussierend.

Entsprechendes gilt für den Auslöschungskanal B.

In Aufgabe A3.11 wird sich zeigen, dass die Kapazität des Kanalmodells Binary Symmetric Error & Erasure Channel (BSEC) in gleicher Weise berechnet werden kann. Mit

• der Verfälschungswahrscheinlichkeit $ε$ und
• der Auslöschungswahrscheinlichkeit $λ$

erhält man in diesem Fall:

Einige Grundlagen der Kanalcodierung

Um das Kanalcodierungstheorem richtig interpretieren zu können, sind einige Grundlagen der Kanalcodierung (englisch: Channel Coding) erforderlich. Dieses äußerst wichtige Gebiet der Nachrichtentechnik wird in einem eigenen LNTwww–Buch behandelt. Die nachfolgende Beschreibung bezieht sich auf das stark vereinfachte Modell für binäre Blockcodes:

Zu diesem Blockschaltbild ist anzumerken:

• Die unendlich lange Quellensymbolfolge $\underline{u}$ (hier nicht dargestellt) wird in Blöcke zu jeweils $k$ bit unterteilt. Wir bezeichnen den Informationsblock mit der laufenden Nummerierung $j$ mit $\underline{u}_j^{(k)}$.
• Jeder Informationsblock j mit uj(k) wird durch den gelb hinterrlegten Kanalcoder in ein Codewort xj(n) umgesetzt, wobei n > k gelten soll. Das Verhältnis R = k/n bezeichnet man als die Coderate.
• Der Discrete Memoryless Channel (DMC) wird durch die Übergangswahrscheinlichkeit PY|X(⋅) berücksichtigt. Dieser grün hinterlegte Block bewirkt Fehler auf Bitebene ⇒ yj, i ≠ xj, i.
• Damit unterscheiden sich auch die aus n Bit bestehenden Empfangsblöcke yj(n) von den Codeworten xj(n). Ebenso gilt im allgemeinen für die Blöcke nach dem Deoder: υj(k) ≠ uj(k).

Die Grafik soll die hier verwendete Nomenklatur am Beispiel k = 3, n = 4 verdeutlichen. Dargestellt sind die jeweils ersten acht Blöcke der Informationssequenz und der Codesequenz.

Die Bildbeschreibung folgt auf der nächsten Seite.