Informationstheoretische Grenzen der Kanalcodierung

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.