Kanalcodierung/Informationstheoretische Grenzen der Kanalcodierung

1. Kanalcodierung
2. Binäre Blockcodes zur Kanalcodierung
3. Informationstheoretische Grenzen der Kanalcodierung

• Vorherige Seite
• Nächste Seite

• Vorherige Seite
• Nächste Seite

Kanalcodierungstheorem und Kanalkapazität

Wir betrachten weiterhin einen binären Blockcode mit k Informationsbits pro Block und Codeworte der Länge n, woraus sich die Coderate R = k/n mit der Einheit Informationsbit/Codesymbol ergibt.

Der geniale Informationstheoretiker Claude E. Shannon hat sich schon 1948 sehr intensiv mit der Korrekturfähigkeit solcher Codes beschäftigt und hierfür für jeden Kanal eine Grenze angegeben, die sich allein aus informationstheoretischen Überlegungen ergibt. Bis heute wurde noch kein Code gefunden, der diese Grenze übersteigt, und dies wird auch so bleiben.

Shannons Kanalcodierungstheorem: Zu jedem Kanal mit der Kanalkapazität C > 0 existiert stets (mindestens) ein Code, dessen Fehlerwahrscheinlichkeit gegen Null geht, so lange die Coderate kleiner als die Kanalkapazität ist: R < C. Voraussetzung hierfür ist allerdings, dass für die Blocklänge dieses Codes gilt: n → ∞.

Die Umkehrung ist ebenfalls zutreffend und besagt:

Umkehrschluss: Ist die Coderate größer als die Kanalkapazität  ⇒  R > C, so kann eine beliebig kleine Fehlerwahrscheinlichkeit auf keinen Fall erreicht werden.

Zur Herleitung und Berechnung der Kanalkapazität gehen wir zunächst von einem digitalen Kanal mit M_x möglichen Eingangswerten x_i und M_y möglichen Ausgangswerten y_j aus. Dann gilt für den mittleren Transinformationsgehalt – kurz die Transinformation (englisch: Mutual Information) – zwischen der Zufallsgröße x am Kanaleingang und der Zufallsgröße y am Ausgang:

\[I(x; y) \hspace{-0.15cm} = \hspace{-0.15cm} \sum_{i= 1 }^{M_X} \hspace{0.15cm}\sum_{j= 1 }^{M_Y} \hspace{0.15cm}{\rm Pr}(x_i, y_j) \cdot {\rm log_2 } \hspace{0.15cm}\frac{{\rm Pr}(y_j \hspace{0.05cm}| \hspace{0.05cm}x_i)}{{\rm Pr}(y_j)} = \] \[\hspace{1.2cm} = \hspace{-0.15cm} \sum_{i= 1 }^{M_X} \hspace{0.15cm}\sum_{j= 1 }^{M_Y}\hspace{0.15cm}{\rm Pr}(y_j \hspace{0.05cm}| \hspace{0.05cm}x_i) \cdot {\rm Pr}(x_i) \cdot {\rm log_2 } \hspace{0.15cm}\frac{{\rm Pr}(y_j \hspace{0.05cm}| \hspace{0.05cm}x_i)}{\sum_{k= 1}^{M_X} {\rm Pr}(y_j \hspace{0.05cm}| \hspace{0.05cm}x_k) \cdot {\rm Pr}(x_k)} \hspace{0.05cm}.\]

Beim Übergang von der ersten zur zweiten Gleichung wurden dabei der Satz von Bayes sowie der Satz von der totalen Wahrscheinlichkeit berücksichtigt. Weiter ist anzumerken, dass hier der Logarithmus dualis mit „log₂” bezeichnet ist. Teilweise verwenden wir im LNTwww hierfür auch „ld”. Im Gegensatz zum Buch Einführung in die Informationstheorie unterscheiden wir im Folgenden auch nicht zwischen der Zufallsgröße (Großbuchstaben, X bzw. Y) und Realisierungen (Kleinbuchstaben, x bzw. y).

: Die von Shannon eingeführte Kanalkapazität gibt die maximale Transinformation I(x; y) zwischen der Eingangsgröße x und der Ausgangsgröße y an:

\[C = \max_{{{\rm Pr}(x_i)}} \hspace{0.1cm} I(X; Y) \hspace{0.05cm}.\]

Hinzugefügt werden muss die Pseudo–Einheit „bit/Kanalzugriff”.

Da die Maximierung der Transinformation über alle möglichen (diskreten) Eingangsverteilungen Pr(x_i) erfolgen muss, ist die Kanalkapazität unabhängig vom Eingang und damit eine reine Kanalkenngröße.

Kanalkapazität des BSC–Modells (1)

Wenden wir diese Definitionen auf das BSC–Modell an:

\[I(x; y) \hspace{-0.15cm} = \hspace{0.15cm} {\rm Pr}(y = 0 \hspace{0.05cm}| \hspace{0.05cm}x = 0) \cdot {\rm Pr}(x = 0) \cdot {\rm log_2 } \hspace{0.15cm}\frac{{\rm Pr}(y = 0 \hspace{0.05cm}| \hspace{0.05cm}x = 0)}{{\rm Pr}(y = 0)} + \] \[\hspace{1.2cm} + \hspace{0.15cm} {\rm Pr}(y = 1 \hspace{0.05cm}| \hspace{0.05cm}x = 0) \cdot {\rm Pr}(x = 0) \cdot {\rm log_2 } \hspace{0.15cm}\frac{{\rm Pr}(Y = 1 \hspace{0.05cm}| \hspace{0.05cm}x = 0)}{{\rm Pr}(y = 1)} + \] \[\hspace{1.2cm} + \hspace{0.15cm}{\rm Pr}(y = 0 \hspace{0.05cm}| \hspace{0.05cm}x = 1) \cdot {\rm Pr}(x = 1) \cdot {\rm log_2 } \hspace{0.15cm}\frac{{\rm Pr}(Y = 0 \hspace{0.05cm}| \hspace{0.05cm}x = 1)}{{\rm Pr}(y = 0)} + \] \[\hspace{1.2cm} + \hspace{0.15cm} {\rm Pr}(y = 1 \hspace{0.05cm}| \hspace{0.05cm}x = 1) \cdot {\rm Pr}(x = 1) \cdot {\rm log_2 } \hspace{0.15cm}\frac{{\rm Pr}(y = 1 \hspace{0.05cm}| \hspace{0.05cm}x = 1)}{{\rm Pr}(y = 1)} \hspace{0.05cm}.\]

Zur Kanalkapazität gelangt man durch folgende Überlegungen:

• Die Maximierung bezüglich der Eingangsverteilung führt auf gleichwahrscheinliche Symbole:

\[{\rm Pr}(x = 0) = {\rm Pr}(x = 1) = 1/2 \hspace{0.05cm}.\]

• Aufgrund der aus dem Modell erkennbaren Symmetrie gilt dann gleichzeitig:

\[{\rm Pr}(y = 0) = {\rm Pr}(y = 1) = 1/2 \hspace{0.05cm}.\]

• Berücksichtigt man weiter die BSC–Übergangswahrscheinlichkeiten

\[{\rm Pr}(y = 1 \hspace{0.05cm}| \hspace{0.05cm}x = 0) \hspace{-0.15cm} = \hspace{-0.15cm} {\rm Pr}(y = 0 \hspace{0.05cm}| \hspace{0.05cm}x = 1) = \varepsilon \hspace{0.05cm},\]

\[{\rm Pr}(y = 0 \hspace{0.05cm}| \hspace{0.05cm}x = 0) \hspace{-0.15cm} = \hspace{-0.15cm} {\rm Pr}(y = 1 \hspace{0.05cm}| \hspace{0.05cm}x = 1) = 1-\varepsilon \hspace{0.05cm},\]

so erhält man nach Zusammenfassen je zweier Terme:

\[C \hspace{0.15cm} = \hspace{0.15cm} 2 \cdot 1/2 \cdot \varepsilon \cdot {\rm log_2 } \hspace{0.15cm}\frac{\varepsilon}{1/2 }+ 2 \cdot 1/2 \cdot (1- \varepsilon) \cdot {\rm log_2 } \hspace{0.15cm}\frac{1- \varepsilon}{1/2 } =\]

\[\hspace{0.7cm} = \hspace{0.15cm} \varepsilon \cdot {\rm ld } \hspace{0.15cm}2 - \varepsilon \cdot {\rm log_2 } \hspace{0.15cm} \frac{1}{\varepsilon }+ (1- \varepsilon) \cdot {\rm ld } \hspace{0.15cm} 2 - (1- \varepsilon) \cdot {\rm log_2 } \hspace{0.15cm}\frac{1}{1- \varepsilon} = 1 - H_{\rm bin}(\varepsilon) \]

mit

\[H_{\rm bin}(\varepsilon) = \varepsilon \cdot {\rm log_2 } \hspace{0.15cm}\frac{1}{\varepsilon}+ (1- \varepsilon) \cdot {\rm log_2 } \hspace{0.15cm}\frac{1}{1- \varepsilon}\hspace{0.05cm}.\]

Das Ergebnis wird auf der nächsten Seite grafisch dargestellt.

Kanalkapazität des BSC–Modells (2)

Die rechte Grafik zeigt die BSC–Kanalkapazität abhängig von der Verfälschungswahrscheinlichkeit ε. Links ist zum Vergleich die binäre Entropiefunktion dargestellt, die bereits im Kapitel 1.1 des Buches „Einführung in die Informationstheorie” definiert wurde.

Man erkennt aus dieser Darstellung:

• Die Verfälschungswahrscheinlichkeit ε führt zur Kanalkapazität C(ε). Eine fehlerfreie Decodierung nach bestmöglicher Codierung ist nach dem Kanalcodierungstheorem nur dann möglich, wenn die Coderate R kleiner ist als C(ε).

• Mit ε = 10% ist wegen C(0.1) = 0.531 eine fehlerfreie Decodierung nicht möglich, wenn die Coderate R ≥ 0.531 beträgt. Bei 50–prozentiger Verfälschung ist eine fehlerfreie Decodierung auch bei beliebig kleiner Coderate unmöglich: C(0.5) = 0.
  

• Aus informationstheoretischer Sicht ist ε = 1 (Invertierung aller Bits) gleich gut wie ε = 0 (fehlerfreie Übertragung). Ebenso ist ε = 0.9 äquivalent zu ε = 0.1. Eine fehlerfreie Decodierung erzielt man hier durch Vertauschen der Nullen und Einsen, also durch ein Mapping.
  

Kanalkapazität des AWGN–Modells (1)

Wir betrachten den AWGN–Kanal (Additive White Gaussian Noise). Hier gilt für das Ausgangssignal y = x + n, wobei n eine gaußverteilte Zufallsgröße beschreibt, und es gilt E[n] = 0 und E[n²] = P_n.

Damit ergibt sich unabhängig vom Eingangssignal x ein kontinuierliches Ausgangssignal y, und in der Gleichung für die Transinformation ist M_y → ∞ einzusetzen.

Die Berechnung der Kanalkapazität für den AWGN–Kanal wird hier nur in Stichworten angegeben. Die genaue Herleitung finden Sie im Kapitel 4 des Buches „Einführung in die Informationstheorie”:

• Die im Hinblick auf maximale Transinformation optimierte Eingangsgröße x wird mit Sicherheit wertkontinuierlich sein, das heißt, beim AWGN–Kanal gilt außer M_y → ∞ auch M_x → ∞.

• Während bei wertdiskretem Eingang über alle Pr(x_i) zu optimieren ist, erfolgt nun die Optimierung anhand der WDF f_x(x) des Eingangssignals unter der Nebenbedingung Leistungsbegrenzung:

\[C = \max_{f_x(x)} \hspace{0.1cm} I(x; y)\hspace{0.05cm},\hspace{0.3cm}{\rm wobei \hspace{0.15cm} gelten \hspace{0.15cm} muss:}\hspace{0.15cm} {\rm E} \left [ x^2 \right ] \le P_x \hspace{0.05cm}.\]

• Die Optimierung liefert für die Eingangs–WDF ebenfalls eine Gaußverteilung ⇒ x, n und y sind gaußverteilt gemäß den Dichtefunktionen f_x(x), f_n(n), f_y(y) und den Leistungen P_x, P_n und P_y.
  

• Nach längerer Rechnung erhält man für die Kanalkapazität unter Verwendung des Logarithmus dualis log₂(.) – wiederum mit der Pseudo–Einheit „bit/Kanalzugriff”:

\[C = {\rm log_2 } \hspace{0.15cm} \sqrt{\frac{P_y}{P_n }} = {\rm log_2 } \hspace{0.15cm} \sqrt{\frac{P_x + P_n}{P_n }} = \frac{1}{2 } \cdot {\rm log_2 } \hspace{0.05cm}\left ( 1 + \frac{P_x}{P_n } \right )\hspace{0.05cm}.\]

• Beschreibt x ein zeitdiskretes Signal mit der Symbolrate 1/T_S, so muss dieses auf B = 1/(2T_S) bandbegrenzt sein, und die gleiche Bandbreite B muss man für das Rauschsignal n ansetzen:

\[P_X = \frac{E_{\rm S}}{T_{\rm S} } \hspace{0.05cm}, \hspace{0.4cm} P_N = \frac{N_0}{2T_{\rm S} }\hspace{0.05cm}. \]

• Somit lässt sich die AWGN–Kanalkapazität auch durch die Sendeenergie pro Symbol (E_S) und die Rauschleistungsdichte (N₀) ausdrücken:

\[C \hspace{-0.15cm} = \hspace{-0.15cm} \frac{1}{2 } \cdot {\rm log_2 } \hspace{0.05cm}\left ( 1 + \frac{2 E_{\rm S}}{N_0 } \right )\hspace{0.05cm}, \hspace{1.85cm} {\rm Einheit:} \hspace{0.3cm} \frac{\rm bit}{\rm Kanalzugriff}\hspace{0.05cm},\]

\[C^{\star} \hspace{-0.15cm} = \hspace{-0.15cm} \frac{C}{T_{\rm S} } = B \cdot {\rm log_2 } \hspace{0.05cm}\left ( 1 + \frac{2 E_{\rm S}}{N_0 } \right )\hspace{0.05cm}, \hspace{0.8cm} {\rm Einheit:} \hspace{0.3cm} \frac{\rm bit}{\rm Zeiteinheit}\hspace{0.05cm}.\]

: Für das Zahlenverhältnis E_S/N₀ = 7.5 ⇒ 10 · lg E_S/N₀ = 8.75 dB erhält man die Kanalkapazität C = 1/2 · log₂ (16) = 2 bit/Kanalzugriff. Bei einem Kanal mit der (physikalischen) Bandbreite B = 4 kHz, was der Abtastrate f_A = 8 kHz entspricht, gilt zudem C* = 16 kbit/s.

Kanalkapazität des AWGN–Modells (2)

Ein Vergleich verschiedener Codierverfahren bei konstantem E_S (Energie pro übertragenem Symbol) ist nicht fair. Vielmehr sollte man für diesen Vergleich die Energie E_B pro Nutzbit fest vorgeben. Dabei gilt:

\[E_{\rm S} = R \cdot E_{\rm B} \hspace{0.3cm} \Rightarrow \hspace{0.3cm} E_{\rm B} = E_{\rm S} / R \hspace{0.05cm}. \]

Damit lautet das Kanalcodierungstheorem: Eine fehlerfreie Decodierung (bei unendlich langen Blöcken) ist möglich, falls die Coderate R kleiner ist als die Kanalkapazität C:

\[R < C = {1}/{2 } \cdot {\rm log_2 } \hspace{0.05cm}\left ( 1 +2 \cdot R\cdot E_{\rm B}/{N_0 } \right )\hspace{0.05cm}.\]

Für jede Coderate R lässt sich damit das erforderliche E_B/N₀ des AWGN–Kanals ermitteln, damit eine fehlerfreie Decodierung möglich ist. Man erhält für den Grenzfall R = C:

\[{E_{\rm B}}/{N_0} > (2^{2R}-1)/(2R ) \hspace{0.05cm}.\]

Die Grafik fasst das Ergebnis zusammen, wobei die Ordinate R im linearen Maßstab und die Abszisse E_B/N₀ logarithmisch aufgetragen ist. Außerhalb der blauen Fläche ist eine fehlerfreie Codierung nicht möglich. Die blaue Grenzkurve gibt die Kanalkapazität C des AWGN–Kanals an.

Aus dieser Grafik und obiger Gleichung lässt sich Folgendes ableiten:

• Die Kanalkapazität C steigt etwas weniger als linear mit 10 · lg E_B/N₀ an. In der Grafik sind einige ausgewählte Funktionswerte angegeben (blaue Kreuze).
  

• Ist 10 · lg (E_B/N₀) kleiner als –1.59 dB, so ist eine fehlerfreie Decodierung prinzipiell unmöglich. Beträgt die Coderate R = 0.5, so muss 10 · lg (E_B/N₀) größer als 0 dB   ⇒   E_B > N₀ sein.
  

• Für alle binären Codes gilt per se 0 ≤ R ≤ 1. Coderaten R > 1 sind nur mit nichtbinären Codes möglich. Beispielsweise beträgt die maximal mögliche Coderate eines quaternären Codes R = 2.
  

• Alle eindimensionalen Modulationsarten – also solche Verfahren, die nur die Inphase– oder nur die Quadraturkomponente nutzen wie ASK, BPSK und FSK – müssen im blauen Bereich liegen.
  

AWGN–Kanalkapazität für binäre Eingangssignale

In diesem Buch beschränken wir uns meist auf binäre Codes, also auf das Galoisfeld GF(2ⁿ). Damit ist

• zum einen die Coderate auf den Bereich R ≤ 1 begrenzt,
  

• zum zweiten auch für R ≤ 1 nicht die gesamte blaue Region (siehe letzte Seite) verfügbar.
  
  

Die nun gültige Region ergibt sich aus der allgemeinen Gleichung der Transinformation durch

• die Parameter M_x = 2 und M_y → ∞,
  

• bipolare Signalisierung  ⇒  x = 0 → x̃ = +1,  x = 1 → x̃ = –1,
  

• den Übergang von bedingten Wahrscheinlichkeiten Pr(x̃_i) zu bedingten Wahrscheinlichkeitsdichtefunktionen,
  

• Ersetzen der Summe durch eine Integration.
  
  

Die Optimierung der Quelle führt auf gleichwahrscheinliche Symbole:

\[{\rm Pr}(\tilde{x} = +1) = {\rm Pr}(\tilde{x} = -1) = 1/2 \hspace{0.05cm}. \]

Damit erhält man bei binärem Eingang (±1) für die Kanalkapazität  ⇒  Maximum der Transinformation hinsichtlich Pr(x̃_i):

\[C \hspace{-0.15cm} = {1}/{2} \cdot \int_{-\infty }^{+ \infty} \left [ f_{y\hspace{0.05cm} |\hspace{0.05cm}\tilde{x} = +1}(y)\cdot {\rm log_2 } \hspace{0.15cm}\frac {f_{y\hspace{0.05cm} |\hspace{0.05cm}\tilde{x} = +1}(y)}{f_y(y)} + f_{y\hspace{0.05cm} |\hspace{0.05cm}\tilde{x} = -1}(y)\cdot {\rm log_2 } \hspace{0.15cm}\frac {f_{y\hspace{0.05cm} |\hspace{0.05cm}\tilde{x} = -1}(y)}{f_y(y)} \right ]\hspace{0.1cm}{\rm d}y \hspace{0.05cm}.\]

Das Integral lässt sich nicht in mathematisch–geschlossener Form lösen, sondern kann nur numerisch ausgewertet werden. Die grüne Kurve zeigt das Ergebnis. Die blaue Kurve gibt zum Vergleich die auf der letzten Seite hergeleitete Kanalkapazität für gaußverteilte Eingangssignale an. Man erkennt:

• Für 10 · lg E_B/N₀ < 0 unterscheiden sich die beiden Kapazitätskurven nur geringfügig. So muss man bei binärem bipolaren Eingang gegenüber dem Optimum (Gaußscher Eingang) die Kenngröße 10 · lg E_B/N₀ nur etwa um 0.1 dB erhöhen, um ebenfalls die Coderate R = 0.5 zu ermöglichen.
  

• Ab etwa 10 · lg E_B/N₀ = 6 dB ist die Kanalkapazität C = 1 bit/Kanalzugriff für binären Eingang (fast) erreicht. Dazwischen verläuft die grüne Grenzkurve annähernd exponentiell ansteigend.

Gebräuchliche Kanalcodes im Vergleich zur Kanalkapazität (1)

Nun soll gezeigt werden, in wie weit sich etablierte Kanalcodes der BPSK–Kanalkapazität (grüne Kurve) annähern. In der Grafik ist als Ordinate die Rate R = k/n dieser Codes bzw. die Kapazität C (mit der zusätzlichen Pseudo–Einheit „bit/Kanalzugriff”) aufgetragen. Weiter ist vorausgesetzt:

• der AWGN–Kanal, gekennzeichnet durch 10 · lg E_B/N₀ in dB, und
  

• für die durch Kreuze markierten Codes eine Bitfehlerrate (BER) von 10^–5.
  
  

Zu beachten ist, dass die Kanalkapazitätskurven stets für n → ∞ und BER = 0 gelten. Würde man diese strenge Forderung „feherfrei” auch an die betrachteten Kanalcodes endlicher Codelänge n anlegen, so wäre hierfür stets 10 · E_B/N₀ → ∞ erforderlich. Dies ist aber ein akademisches Problem, das für die Praxis wenig Bedeutung hat. Für BER = 10^–10 ergäbe sich eine qualitativ ähnliche Grafik.

Es folgen einige Erläuterungen zu den Daten, die der Vorlesung [Liv10] entnommen wurden:

• Die Punkte A, B und C markieren Hamming–Codes unterschiedlicher Rate, die im Kapitel 1.3 bereits ausführlich behandelt wurden. Sie alle benötigen 10 · lg E_B/N₀ > 8 dBfür BER = 10^–5.
  

• D kennzeichnet den binären Golay–Code mit der Rate 1/2 und E einen Reed–Muller–Code. Dieser sehr niederratige Code kam bereits 1971 bei der Raumsonde Mariner 9 zum Einsatz.
  

• Die Reed–Solomon–Codes (RS–Codes) werden im Kapitel 2 noch ausführlich behandelt. Mit F markiert ist der RS–Code der Rate 223/255 > 0.9 und einem erforderlichen E_B/N₀ < 6 dB.
  

• Die Markierungen G und H bezeichnen beispielhafte Faltungscodes (englisch: Convolutional Codes, CC) mittlerer Rate. Ersterer wurde schon 1972 bei der Pioneer10–Mission eingesetzt.
  

• Die Kanalcodierung der Voyager–Mission Ende der 1970er Jahre ist mit I markiert. Es handelt sich um die Verkettung eines (2, 1, 7)–Faltungscodes mit einem Reed–Solomon–Code.
  
  

Anzumerken ist, dass bei den Faltungscodes insbesondere der dritte Parameter der Kennung eine andere Bedeutung hat als bei den Blockcodes. (2, 1, 32) weist beispielsweise auf das Memory m = 32 hin.

Auf der nächsten Seite folgen noch Kenndaten von Systemen mit iterativer Decodierung.