Kanalcodierung/Informationstheoretische Grenzen der Kanalcodierung: Unterschied zwischen den Versionen

Aus LNTwww
Wechseln zu:Navigation, Suche
 
(20 dazwischenliegende Versionen von 2 Benutzern werden nicht angezeigt)
Zeile 8: Zeile 8:
 
== Kanalcodierungstheorem und Kanalkapazität ==
 
== Kanalcodierungstheorem und Kanalkapazität ==
 
<br>
 
<br>
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 &bdquo;Informationsbit/Codesymbol&rdquo; ergibt.<br>
+
Wir betrachten weiterhin einen binären Blockcode mit&nbsp; $k$&nbsp; Informationsbits pro Block und Codeworte der Länge&nbsp; $n$, woraus sich die Coderate&nbsp; $R=k/n$&nbsp; mit der Einheit &bdquo;Informationsbit/Codesymbol&rdquo; ergibt.<br>
  
Der geniale Informationstheoretiker [https://de.wikipedia.org/wiki/Claude_Shannon 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.<br>
+
Der geniale Informationstheoretiker&nbsp; [https://de.wikipedia.org/wiki/Claude_Shannon Claude E. Shannon]&nbsp; 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.<br>
  
 
{{BlaueBox|TEXT=   
 
{{BlaueBox|TEXT=   
$\text{Shannons Kanalcodierungstheorem:}$&nbsp;  Zu jedem Kanal mit der Kanalkapazität $C > 0$ existiert stets (mindestens) ein Code, dessen Fehlerwahrscheinlichkeit gegen Null geht, so lange die Coderate $R$ kleiner als die Kanalkapazität $C$ ist. Voraussetzung hierfür ist allerdings, dass für die Blocklänge dieses Codes gilt: &nbsp; $n \to \infty$.}}<br>
+
$\text{Shannons Kanalcodierungstheorem:}$&nbsp;  Zu jedem Kanal mit der Kanalkapazität&nbsp; $C > 0$&nbsp; existiert stets (mindestens) ein Code, dessen Fehlerwahrscheinlichkeit gegen Null geht, so lange die Coderate&nbsp; $R$&nbsp; kleiner ist als die Kanalkapazität&nbsp; $C$. Voraussetzung hierfür ist, dass für die Blocklänge dieses Codes gilt: &nbsp; $n \to \infty$.}}<br>
  
Die Umkehrung ist ebenfalls zutreffend und besagt:<br>
+
''Anmerkungen:''&nbsp;
 +
*Die Aussage &bdquo;Die Fehlerwahrscheinlichkeit geht gegen Null&rdquo; ist nicht identisch mit der Aussage &bdquo;Die Übertragung ist fehlerfrei&rdquo;. Beispiel: &nbsp; Bei einer unendlich langen Folge werden endlich viele Symbole verfälscht.
 +
*Bei manchen Kanälen geht auch mit&nbsp; $R=C$&nbsp; die Fehlerwahrscheinlichkeit noch gegen Null (aber nicht bei allen).
 +
 
 +
 
 +
Die Umkehrung des Kanalcodierungstheorems ist ebenfalls zutreffend und besagt:<br>
  
 
{{BlaueBox|TEXT=   
 
{{BlaueBox|TEXT=   
$\text{Umkehrschluss:}$&nbsp;  <b>Umkehrschluss</b>: Ist die Coderate $R$ größer als die Kanalkapazität $C$, so kann eine beliebig kleine Fehlerwahrscheinlichkeit auf keinen Fall erreicht werden.}}<br>
+
$\text{Umkehrschluss:}$&nbsp;  Ist die Coderate&nbsp; $R$&nbsp; größer als die Kanalkapazität&nbsp; $C$, so kann eine beliebig kleine Fehlerwahrscheinlichkeit auf keinen Fall erreicht werden.}}<br>
  
Zur Herleitung und Berechnung der Kanalkapazität gehen wir zunächst von einem digitalen Kanal mit $M_x$ möglichen Eingangswerten $x$ und $M_y$ möglichen Ausgangswerten $y$ aus. Dann gilt für den mittleren Transinformationsgehalt  &ndash; kurz die [[Informationstheorie/Verschiedene_Entropien_zweidimensionaler_Zufallsgrößen#Transinformation_zwischen_zwei_Zufallsgr.C3.B6.C3.9Fen|Transinformation]] (englisch: <i>Mutual Information</i>)  &ndash; zwischen der Zufallsgröße $x$  am Kanaleingang und der Zufallsgröße $y$ am Ausgang:
+
Zur Herleitung und Berechnung der Kanalkapazität gehen wir zunächst von einem digitalen Kanal mit&nbsp; $M_x$&nbsp; möglichen Eingangswerten&nbsp; $x$&nbsp; und&nbsp; $M_y$&nbsp; möglichen Ausgangswerten&nbsp; $y$&nbsp; aus. Dann gilt für den mittleren Transinformationsgehalt  &ndash; kurz die&nbsp; [[Informationstheorie/Verschiedene_Entropien_zweidimensionaler_Zufallsgrößen#Transinformation_zwischen_zwei_Zufallsgr.C3.B6.C3.9Fen|Transinformation]]&nbsp; (englisch: &nbsp; <i>Mutual Information</i>)  &ndash; zwischen der Zufallsgröße&nbsp; $x$&nbsp; am Kanaleingang und der Zufallsgröße&nbsp; $y$&nbsp; an seinem Ausgang:
  
 
::<math>I(x; y) =\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)} =  \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)}
 
::<math>I(x; y) =\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)} =  \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}.</math>
 
  \hspace{0.05cm}.</math>
  
Beim Übergang von der ersten zur zweiten Gleichung wurden dabei der [[Stochastische_Signaltheorie/Statistische_Abh%C3%A4ngigkeit_und_Unabh%C3%A4ngigkeit#Bedingte_Wahrscheinlichkeit_.281.29| Satz von Bayes]] sowie der [[Stochastische_Signaltheorie/Statistische_Abh%C3%A4ngigkeit_und_Unabh%C3%A4ngigkeit#R.C3.BCckschlusswahrscheinlichkeit| Satz von der totalen Wahrscheinlichkeit]] berücksichtigt. Weiter ist anzumerken:  
+
Beim Übergang von der ersten zur zweiten Gleichung wurden dabei der&nbsp; [[Stochastische_Signaltheorie/Statistische_Abh%C3%A4ngigkeit_und_Unabh%C3%A4ngigkeit#Bedingte_Wahrscheinlichkeit_.281.29| Satz von Bayes]]&nbsp; sowie der&nbsp; [[Stochastische_Signaltheorie/Statistische_Abh%C3%A4ngigkeit_und_Unabh%C3%A4ngigkeit#R.C3.BCckschlusswahrscheinlichkeit| Satz von der totalen Wahrscheinlichkeit]]&nbsp; berücksichtigt.  
*Der <i>Logarithmus dualis</i> ist hier mit &bdquo;log<sub>2</sub>&rdquo; bezeichnet ist. Teilweise verwenden wir hierfür in unserem  Lerntutorial  auch &bdquo;ld&rdquo;.  
+
 
*Im Gegensatz zum Buch [[Informationstheorie]] unterscheiden wir im Folgenden auch nicht zwischen der Zufallsgröße  (Großbuchstaben, $X$ bzw. $Y$) und Realisierungen (Kleinbuchstaben, $x$ bzw. $y$).<br>
+
Weiter ist anzumerken:  
 +
*Der <i>Logarithmus dualis</i>&nbsp; ist hier mit &bdquo;log<sub>2</sub>&rdquo; bezeichnet ist. Teilweise verwenden wir in unserem  Lerntutorial hierfür auch &bdquo;ld&rdquo;.  
 +
*Im Gegensatz zum Buch&nbsp; [[Informationstheorie]]&nbsp; unterscheiden wir im Folgenden nicht zwischen der Zufallsgröße  $($Großbuchstaben&nbsp; $X$&nbsp; bzw.&nbsp; $Y)$&nbsp; und den Realisierungen $($Kleinbuchstaben&nbsp; $x$&nbsp; bzw.&nbsp; $y)$.<br>
 +
 
  
 
{{BlaueBox|TEXT=   
 
{{BlaueBox|TEXT=   
$\text{Definition:}$&nbsp;  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:
+
$\text{Definition:}$&nbsp;  Die von Shannon eingeführte&nbsp; '''Kanalkapazität'''&nbsp; gibt die maximale Transinformation&nbsp; $I(x; y)$&nbsp; zwischen der Eingangsgröße&nbsp; $x$&nbsp; und der Ausgangsgröße&nbsp; $y$&nbsp; an:
  
 
::<math>C = \max_{{{\rm Pr}(x_i)}} \hspace{0.1cm} I(X; Y) \hspace{0.05cm}.</math>
 
::<math>C = \max_{{{\rm Pr}(x_i)}} \hspace{0.1cm} I(X; Y) \hspace{0.05cm}.</math>
Zeile 36: Zeile 44:
 
Hinzugefügt werden muss die Pseudo&ndash;Einheit &bdquo;bit/Kanalzugriff&rdquo;.}}<br>
 
Hinzugefügt werden muss die Pseudo&ndash;Einheit &bdquo;bit/Kanalzugriff&rdquo;.}}<br>
  
Da die Maximierung der Transinformation über alle möglichen (diskreten) Eingangsverteilungen ${\rm Pr}(x_i)$ erfolgen muss, ist die Kanalkapazität unabhängig vom Eingang und damit eine reine Kanalkenngröße.<br>
+
Da die Maximierung der Transinformation über alle möglichen (diskreten) Eingangsverteilungen&nbsp; ${\rm Pr}(x_i)$&nbsp; erfolgen muss, ist die Kanalkapazität unabhängig vom Eingang und damit eine reine Kanalkenngröße.<br>
  
 
== Kanalkapazität des BSC–Modells ==
 
== Kanalkapazität des BSC–Modells ==
 
<br>
 
<br>
Wenden wir diese Definitionen auf das [http://www.lntwww.de/Kanalcodierung/Kanalmodelle_und_Entscheiderstrukturen#Binary_Symmetric_Channel_.E2.80.93_BSC BSC&ndash;Modell] an:
+
Wir wenden nun diese Definitionen auf das&nbsp; [[Kanalcodierung/Kanalmodelle_und_Entscheiderstrukturen#Binary_Symmetric_Channel_.E2.80.93_BSC|BSC&ndash;Modell]]&nbsp; (''Binary Symmetric Channel&nbsp;'') an:
  
:<math>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)  
+
::<math>I(x; y) = {\rm Pr}(y = 0 \hspace{0.03cm}| \hspace{0.03cm}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)}
+
\cdot {\rm log_2 } \hspace{0.15cm}\frac{{\rm Pr}(y = 0 \hspace{0.03cm}| \hspace{0.03cm}x = 0)}{{\rm Pr}(y = 0)}
 +
+ {\rm Pr}(y = 1 \hspace{0.03cm}| \hspace{0.03cm}x = 0) \cdot {\rm Pr}(x = 0)  
 +
\cdot {\rm log_2 } \hspace{0.15cm}\frac{{\rm Pr}(Y = 1 \hspace{0.03cm}| \hspace{0.03cm}x = 0)}{{\rm Pr}(y = 1)}
 
+ </math>
 
+ </math>
:<math>\hspace{1.2cm}  +  \hspace{0.15cm} {\rm Pr}(y = 1 \hspace{0.05cm}| \hspace{0.05cm}x = 0) \cdot {\rm Pr}(x = 0)
+
::<math>\hspace{1.45cm}  +  \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 = 1 \hspace{0.05cm}| \hspace{0.05cm}x = 0)}{{\rm Pr}(y = 1)}
 
+ </math>
 
:<math>\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)}
 
\cdot {\rm  log_2  } \hspace{0.15cm}\frac{{\rm Pr}(Y = 0 \hspace{0.05cm}| \hspace{0.05cm}x = 1)}{{\rm Pr}(y = 0)}
+ </math>
+
+ {\rm Pr}(y = 1 \hspace{0.05cm}| \hspace{0.05cm}x = 1) \cdot {\rm Pr}(x = 1)  
:<math>\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)}
 
\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}.</math>
 
  \hspace{0.05cm}.</math>
 +
 +
[[Datei:KC_T_1_7_Zusatz_version2.png|right|frame|BSC–Kanalmodell|class=fit]]
  
 
Zur Kanalkapazität gelangt man durch folgende Überlegungen:
 
Zur Kanalkapazität gelangt man durch folgende Überlegungen:
Zeile 66: Zeile 74:
 
  \hspace{0.05cm}.</math>
 
  \hspace{0.05cm}.</math>
  
*Berücksichtigt man weiter die BSC&ndash;Übergangswahrscheinlichkeiten
+
*Wir berücksichtigen zudem die BSC&ndash;Übergangswahrscheinlichkeiten:
  
::<math>{\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},</math>
+
::<math>{\rm Pr}(y = 1 \hspace{0.05cm}| \hspace{0.05cm}x = 0) = {\rm Pr}(y = 0 \hspace{0.05cm}| \hspace{0.05cm}x = 1) = \varepsilon \hspace{0.05cm},</math>
::<math>{\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},</math>
+
::<math>{\rm Pr}(y = 0 \hspace{0.05cm}| \hspace{0.05cm}x = 0) = {\rm Pr}(y = 1 \hspace{0.05cm}| \hspace{0.05cm}x = 1) = 1-\varepsilon  \hspace{0.05cm}.</math>
  
:so erhält man nach Zusammenfassen je zweier Terme:
+
*Nach Zusammenfassen je zweier Terme erhält man somit:
  
 
::<math>C \hspace{0.15cm}  =  \hspace{0.15cm} 2 \cdot 1/2 \cdot \varepsilon \cdot {\rm log_2 } \hspace{0.15cm}\frac{\varepsilon}{1/2 }+  
 
::<math>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 }
 
2 \cdot 1/2 \cdot (1- \varepsilon)  \cdot {\rm log_2 } \hspace{0.15cm}\frac{1- \varepsilon}{1/2 }
=</math>
+
\varepsilon \cdot {\rm ld } \hspace{0.15cm}2  - \varepsilon \cdot {\rm log_2 } \hspace{0.15cm} \frac{1}{\varepsilon }+  (1- \varepsilon) \cdot {\rm log_2 } \hspace{0.15cm} 2 - (1- \varepsilon) \cdot {\rm log_2 } \hspace{0.15cm}\frac{1}{1- \varepsilon}</math>
::<math>\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) </math>
+
::<math>\Rightarrow \hspace{0.3cm} C \hspace{0.15cm}  = \hspace{0.15cm}  1 - H_{\rm bin}(\varepsilon). </math>
  
:mit
+
*Verwendet ist hier die ''binäre Entropiefunktion'':
  
 
::<math>H_{\rm bin}(\varepsilon) =  \varepsilon \cdot {\rm log_2 } \hspace{0.15cm}\frac{1}{\varepsilon}+  
 
::<math>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}.</math>
 
(1- \varepsilon)  \cdot {\rm log_2 } \hspace{0.15cm}\frac{1}{1- \varepsilon}\hspace{0.05cm}.</math>
  
Das Ergebnis wird auf der nächsten Seite grafisch dargestellt.<br>
+
Die folgende rechte Grafik zeigt die BSC&ndash;Kanalkapazität abhängig von der Verfälschungswahrscheinlichkeit&nbsp; $\varepsilon$. Links ist zum Vergleich die binäre Entropiefunktion dargestellt, die bereits im Kapitel&nbsp; [[Informationstheorie/Ged%C3%A4chtnislose_Nachrichtenquellen#Bin.C3.A4re_Entropiefunktion|Gedächtnislose Nachrichtenquellen]]&nbsp; des Buches &bdquo;Informationstheorie&rdquo; definiert wurde.<br>
 
 
== Kanalkapazität des BSC–Modells (2) ==
 
<br>
 
Die rechte Grafik zeigt die BSC&ndash;Kanalkapazität abhängig von der Verfälschungswahrscheinlichkeit <i>&epsilon;</i>. Links ist zum Vergleich die binäre Entropiefunktion dargestellt, die bereits im [http://www.lntwww.de/Informationstheorie/Ged%C3%A4chtnislose_Nachrichtenquellen#Bin.C3.A4re_Entropiefunktion Kapitel 1.1] des Buches &bdquo;Einführung in die Informationstheorie&rdquo; definiert wurde.<br>
 
 
 
[[Datei:P ID2379 KC T 1 7 S2 v2.png|Kanalkapazität des BSC–Modells|class=fit]]<br>
 
  
 +
[[Datei:P ID2379 KC T 1 7 S2 v2.png|rght|frame|Kanalkapazität des BSC–Modells|class=fit]]
 
Man erkennt aus dieser Darstellung:
 
Man erkennt aus dieser Darstellung:
*Die Verfälschungswahrscheinlichkeit <i>&epsilon;</i> führt zur Kanalkapazität <i>C</i>(<i>&epsilon;</i>). Eine fehlerfreie Decodierung nach bestmöglicher Codierung ist nach dem [http://www.lntwww.de/Kanalcodierung/Informationstheoretische_Grenzen_der_Kanalcodierung#Kanalcodierungstheorem_und_Kanalkapazit.C3.A4t Kanalcodierungstheorem] nur dann möglich, wenn die Coderate <i>R</i> kleiner ist als <i>C</i>(<i>&epsilon;</i>).
+
*Die Verfälschungswahrscheinlichkeit&nbsp; $\varepsilon$&nbsp; führt zur Kanalkapazität $C(\varepsilon)$. Eine fehlerfreie Decodierung nach bestmöglicher Codierung ist nach dem&nbsp; [[Kanalcodierung/Informationstheoretische_Grenzen_der_Kanalcodierung#Kanalcodierungstheorem_und_Kanalkapazit.C3.A4t |Kanalcodierungstheorem]]&nbsp; nur dann möglich, wenn die Coderate $R$ nicht größer ist als&nbsp; $C(\varepsilon)$.
  
*Mit <i>&epsilon;</i> = 10% ist wegen <i>C</i>(0.1) = 0.531 eine fehlerfreie Decodierung nicht möglich, wenn die Coderate <i>R</i> &#8805; 0.531 beträgt. Bei 50&ndash;prozentiger Verfälschung ist eine fehlerfreie Decodierung auch bei beliebig kleiner Coderate unmöglich: <i>C</i>(0.5) = 0.<br>
+
*Mit&nbsp; $\varepsilon = 10\%$&nbsp; ist wegen&nbsp; $C(0.1) = 0.531$&nbsp; eine fehlerfreie Decodierung nicht möglich, wenn die Coderate&nbsp; $R > 0.531$&nbsp; beträgt. Bei 50&ndash;prozentiger Verfälschung ist eine fehlerfreie Decodierung auch bei beliebig kleiner Coderate unmöglich: &nbsp; $C(0.5) = 0$ .<br>
  
*Aus informationstheoretischer Sicht ist <i>&epsilon;</i> = 1 (Invertierung aller Bits) gleich gut wie <i>&epsilon;</i> = 0 (fehlerfreie Übertragung). Ebenso ist <i>&epsilon;</i> = 0.9 äquivalent zu <i>&epsilon;</i> = 0.1. Eine fehlerfreie Decodierung erzielt man hier durch Vertauschen der Nullen und Einsen, also durch ein  <i>Mapping</i>.<br>
+
*Aus informationstheoretischer Sicht ist&nbsp; $\varepsilon = 1$&nbsp; (Invertierung aller Bits) gleich gut wie&nbsp; $\varepsilon = 0$&nbsp; (fehlerfreie Übertragung). Ebenso ist&nbsp; $\varepsilon = 0.9$&nbsp; äquivalent zu&nbsp; $\varepsilon = 0.1$. Eine fehlerfreie Decodierung erzielt man hier durch Vertauschen der Nullen und Einsen, also durch ein  so genanntes <i>Mapping</i>.<br>
  
== Kanalkapazität des AWGN–Modells (1) ==
+
== Kanalkapazität des AWGN–Modells==
 
<br>
 
<br>
[[Datei:P ID2372 KC T 1 7 S3a.png|AWGN–Kanalmodell|rechts|rahmenlos]]<br>
+
[[Datei:P ID2372 KC T 1 7 S3a.png|right|frame|AWGN–Kanalmodell|class=fit]]
 +
Wir betrachten nun den&nbsp; [[Digitalsignalübertragung/Systemkomponenten_eines_Basisbandübertragungssystems#.C3.9Cbertragungskanal_und_St.C3.B6rungen|AWGN&ndash;Kanal]]&nbsp; (<i>Additive White Gaussian Noise</i>&nbsp;). Hier gilt für das Ausgangssignal&nbsp; $y = x + n$, wobei&nbsp; $n$&nbsp; eine&nbsp; [[Stochastische_Signaltheorie/Gaußverteilte_Zufallsgrößen|gaußverteilte Zufallsgröße]]&nbsp; beschreibt, und es gilt für deren Erwartungswerte (Momente):
 +
:$${\rm E}[n] = 0,\hspace{1cm} {\rm E}[n^2] = P_n.$$
  
Wir betrachten den AWGN&ndash;Kanal (<i>Additive White Gaussian Noise</i>). Hier gilt für das Ausgangssignal <i>y</i> = <i>x</i> + <i>n</i>, wobei <i>n</i> eine gaußverteilte Zufallsgröße beschreibt, und es gilt <i>E</i>[<i>n</i>] = 0 und <i>E</i>[<i>n</i><sup>2</sup>] = <i>P<sub>n</sub></i>.<br>
+
Damit ergibt sich unabhängig vom Eingangssignal&nbsp; $x$&nbsp; (analog oder digital) stets ein wertkontinuierliches Ausgangssignal&nbsp; $y$, und in der&nbsp; [[Kanalcodierung/Informationstheoretische_Grenzen_der_Kanalcodierung#Kanalcodierungstheorem_und_Kanalkapazit.C3.A4t|Gleichung für die Transinformation]]&nbsp; ist&nbsp; $M_y \to\infty$&nbsp; einzusetzen.<br>
  
Damit ergibt sich unabhängig vom Eingangssignal <i>x</i> ein kontinuierliches Ausgangssignal <i>y</i>, und in der [http://www.lntwww.de/Kanalcodierung/Informationstheoretische_Grenzen_der_Kanalcodierung#Kanalcodierungstheorem_und_Kanalkapazit.C3.A4t Gleichung] für die Transinformation ist <i>M<sub>y</sub></i> &#8594; &#8734; einzusetzen.<br>
+
Die Berechnung der Kanalkapazität für den AWGN&ndash;Kanal wird hier nur in Stichworten angegeben. Die genaue Herleitung finden Sie im vierten Hauptkapitel &bdquo;Wertdiskrete Informationstheorie&rdquo; des Buches&nbsp; [[Informationstheorie]].
 +
*Die im Hinblick auf maximale Transinformation optimierte Eingangsgröße&nbsp; $x$&nbsp; wird mit Sicherheit wertkontinuierlich sein, das heißt, beim AWGN&ndash;Kanal gilt außer&nbsp; $M_y \to\infty$&nbsp; auch&nbsp; $M_x \to\infty$.
  
Die Berechnung der Kanalkapazität für den AWGN&ndash;Kanal wird hier nur in Stichworten angegeben. Die genaue Herleitung finden Sie im Kapitel 4 des Buches &bdquo;Einführung in die Informationstheorie&rdquo;:
+
*Während bei wertdiskretem Eingang über alle&nbsp; ${\rm Pr}(x_i)$&nbsp; zu optimieren ist, erfolgt nun die Optimierung anhand der&nbsp; [[Stochastische_Signaltheorie/Gau%C3%9Fverteilte_Zufallsgr%C3%B6%C3%9Fe#Wahrscheinlichkeitsdichte-_und_Verteilungsfunktion| WDF]]&nbsp; $f_x(x)$  des Eingangssignals unter der Nebenbedingung&nbsp; [[Digitalsignal%C3%BCbertragung/Optimierung_der_Basisband%C3%BCbertragungssysteme#Leistungs.E2.80.93_und_Spitzenwertbegrenzung| Leistungsbegrenzung]]:
*Die im Hinblick auf maximale Transinformation optimierte Eingangsgröße <i>x</i> wird mit Sicherheit wertkontinuierlich sein, das heißt, beim AWGN&ndash;Kanal gilt außer <i>M<sub>y</sub></i> &#8594; &#8734; auch <i>M<sub>x</sub></i> &#8594; &#8734;.
 
  
*Während bei wertdiskretem Eingang über alle Pr(<i>x<sub>i</sub></i>) zu optimieren ist, erfolgt nun die Optimierung anhand der [http://www.lntwww.de/Stochastische_Signaltheorie/Gau%C3%9Fverteilte_Zufallsgr%C3%B6%C3%9Fe#Wahrscheinlichkeitsdichte-_und_Verteilungsfunktion WDF] <i>f<sub>x</sub></i>(<i>x</i>) des Eingangssignals unter der Nebenbedingung [http://www.lntwww.de/Digitalsignal%C3%BCbertragung/Optimierung_der_Basisband%C3%BCbertragungssysteme#Leistungs.E2.80.93_und_Spitzenwertbegrenzung_.281.29 Leistungsbegrenzung:]
+
::<math>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} \text{:}\hspace{0.15cm} {\rm E} \left [ x^2 \right ] \le P_x  \hspace{0.05cm}.</math>
  
::<math>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}.</math>
+
*Die Optimierung liefert für die Eingangs&ndash;WDF ebenfalls eine Gaußverteilung &nbsp; &#8658; &nbsp;  $x$,&nbsp; $n$&nbsp; und&nbsp; $y$&nbsp; sind gaußverteilt gemäß den Dichtefunktionen&nbsp; $f_x(x)$,&nbsp; $f_n(n)$&nbsp; und&nbsp; $f_y(y)$. Die entsprechenden Leistungen benennen wir&nbsp; $P_x$,&nbsp; $P_n$&nbsp; und&nbsp; $P_y$.<br>
  
*Die Optimierung liefert für die Eingangs&ndash;WDF ebenfalls eine Gaußverteilung &#8658; <i>x</i>, <i>n</i> und <i>y</i> sind gaußverteilt gemäß den Dichtefunktionen <i>f<sub>x</sub></i>(<i>x</i>), <i>f<sub>n</sub></i>(<i>n</i>), <i>f<sub>y</sub></i>(<i>y</i>) und den Leistungen <i>P<sub>x</sub></i>, <i>P<sub>n</sub></i> und <i>P<sub>y</sub></i>.<br>
+
*Nach längerer Rechnung erhält man für die Kanalkapazität unter Verwendung des <i>Logarithmus dualis</i>&nbsp;  $\log_2(\cdot)$ &ndash; wiederum mit der Pseudo&ndash;Einheit &bdquo;bit/Kanalzugriff&rdquo;:
  
*Nach längerer Rechnung erhält man für die Kanalkapazität unter Verwendung des <i>Logarithmus dualis</i>  log<sub>2</sub>(.) &ndash; wiederum mit der Pseudo&ndash;Einheit &bdquo;bit/Kanalzugriff&rdquo;:
+
::<math>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 }} =  {1}/{2 } \cdot {\rm log_2 } \hspace{0.05cm}\left ( 1 + \frac{P_x}{P_n } \right )\hspace{0.05cm}.</math>
  
::<math>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}.</math>
+
*Beschreibt&nbsp; $x$ ein&nbsp; zeitdiskretes Signal mit der Symbolrate&nbsp; $1/T_{\rm S}$, so muss dieses auf&nbsp; $B = 1/(2T_{\rm S})$&nbsp; bandbegrenzt sein, und die gleiche Bandbreite&nbsp; $B$&nbsp; muss man auch für das Rauschsignal&nbsp; $n$&nbsp;  ansetzen &nbsp; &#8658; &nbsp; &bdquo;Rauschbandbreite&rdquo;:
 
 
*Beschreibt <i>x</i> ein zeitdiskretes Signal mit der Symbolrate 1/<i>T</i><sub>S</sub>, so muss dieses auf <i>B</i>&nbsp;=&nbsp;1/(2<i>T</i><sub>S</sub>) bandbegrenzt sein, und die gleiche Bandbreite <i>B</i> muss man für das Rauschsignal <i>n</i> ansetzen:
 
  
 
::<math>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}. </math>
 
::<math>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}. </math>
  
*Somit lässt sich die AWGN&ndash;Kanalkapazität auch durch die Sendeenergie pro Symbol (<i>E</i><sub>S</sub>) und die Rauschleistungsdichte (<i>N</i><sub>0</sub>) ausdrücken:
+
*Somit lässt sich die AWGN&ndash;Kanalkapazität auch durch die&nbsp; '''Sendeenergie pro Symbol''' $(E_{\rm S})$&nbsp; und die&nbsp; '''Rauschleistungsdichte'''&nbsp; $(N_0)$ ausdrücken:
  
::<math>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}
+
::<math>C =  {1}/{2 } \cdot {\rm log_2 } \hspace{0.05cm}\left ( 1 + {2 E_{\rm S}}/{N_0 } \right )\hspace{0.05cm}, \hspace{1.9cm}
{\rm Einheit:} \hspace{0.3cm} \frac{\rm bit}{\rm Kanalzugriff}\hspace{0.05cm},</math>  
+
\text {Einheit:}\hspace{0.3cm} \frac{\rm bit}{\rm Kanalzugriff}\hspace{0.05cm}.</math>
::<math>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}
+
*Mit der folgenden Gleichung erhält man die Kanalkapazität pro Zeiteinheit (Kennzeichnung durch $^{\star})$:
{\rm Einheit:} \hspace{0.3cm} \frac{\rm bit}{\rm Zeiteinheit}\hspace{0.05cm}.</math><br>
+
::<math>C^{\star} = \frac{C}{T_{\rm S} } =    B \cdot {\rm log_2 } \hspace{0.05cm}\left ( 1 + {2  E_{\rm S}}/{N_0 } \right )\hspace{0.05cm}, \hspace{0.8cm}
 +
\text {Einheit:} \hspace{0.3cm} \frac{\rm bit}{\rm Zeiteinheit}\hspace{0.05cm}.</math><br>
  
{{Beispiel}}''':''' Für das Zahlenverhältnis <i>E</i><sub>S</sub>/<i>N</i><sub>0</sub> = 7.5 &#8658; 10 &middot; lg <i>E</i><sub>S</sub>/<i>N</i><sub>0</sub> = 8.75 dB erhält man die Kanalkapazität <b><i>C</i> = 1/2 &middot; log<sub>2</sub> (16) = 2 bit/Kanalzugriff</b>. Bei einem Kanal mit der (physikalischen) Bandbreite <i>B</i> = 4 kHz, was der Abtastrate <i>f</i><sub>A</sub> = 8 kHz entspricht, gilt zudem <b><i>C</i>* = 16 kbit/s</b>.{{end}}<br>
+
{{GraueBox|TEXT= 
 +
$\text{Beispiel 1:}$&nbsp; 
 +
*Für&nbsp; $E_{\rm S}/N_0  = 7.5$ &nbsp; &#8658; &nbsp; $10 \cdot \lg \, E_{\rm S}/N_0 = 8.75 \, \rm dB$&nbsp; erhält man die Kanalkapazität&nbsp; $C = {1}/{2 } \cdot {\rm log_2 } \hspace{0.05cm} (16) = 2 \, \rm  bit/Kanalzugriff$.  
 +
*Bei einem Kanal mit der (physikalischen) Bandbreite&nbsp; $B = 4 \, \rm  kHz$, was der Abtastrate&nbsp; $f_{\rm A} = 8\, \rm  kHz$&nbsp; entspricht, gilt zudem&nbsp; $C^\star = 16 \, \rm  kbit/s$.}}<br>
  
== Kanalkapazität des AWGN–Modells (2) ==
+
Ein Vergleich verschiedener Codierverfahren bei konstantem&nbsp; $E_{\rm S}$&nbsp; (Energie ''pro übertragenem Symbol''&nbsp;) ist allerdings nicht fair. Vielmehr sollte man für diesen Vergleich die Energie&nbsp; $E_{\rm B}$&nbsp; ''pro Nutzbit''&nbsp; fest vorgeben. Dabei gelten folgende Zusammenhänge:
<br>
 
Ein Vergleich verschiedener Codierverfahren bei konstantem <i>E</i><sub>S</sub> (Energie pro übertragenem Symbol) ist nicht fair. Vielmehr sollte man für diesen Vergleich die Energie <i>E</i><sub>B</sub> pro Nutzbit fest vorgeben. Dabei gilt:
 
  
:<math>E_{\rm S} = R \cdot E_{\rm B}  \hspace{0.3cm} \Rightarrow \hspace{0.3cm}
+
::<math>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}. </math>
 
E_{\rm B} = E_{\rm S} / R \hspace{0.05cm}. </math>
  
Damit lautet das <i>Kanalcodierungstheorem</i>: Eine fehlerfreie Decodierung (bei unendlich langen Blöcken) ist möglich, falls die Coderate <i>R</i> kleiner ist als die Kanalkapazität <i>C</i>:
+
{{BlaueBox|TEXT= 
 +
$\text{Kanalcodierungstheorem für den AWGN&ndash;Kanal:}$&nbsp;
  
:<math>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}.</math>
+
Eine fehlerfreie Decodierung $($bei unendlich langen Blöcken &nbsp; &#8658; &nbsp; $n \to \infty)$&nbsp; ist immer dann möglich, falls die Coderate&nbsp; $R$&nbsp; kleiner ist als die Kanalkapazität&nbsp; $C$:
  
Für jede Coderate <i>R</i> lässt sich damit das erforderliche <i>E</i><sub>B</sub>/<i>N</i><sub>0</sub> des AWGN&ndash;Kanals ermitteln, damit eine fehlerfreie Decodierung möglich ist. Man erhält für den Grenzfall <i>R</i> = <i>C</i>:
+
::<math>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}.</math>
  
:<math>{E_{\rm B}}/{N_0} >  (2^{2R}-1)/(2R ) \hspace{0.05cm}.</math>
+
Für jede Coderate&nbsp $R$&nbsp; lässt sich damit  das erforderliche&nbsp; $E_{\rm B}/N_0$&nbsp; des AWGN&ndash;Kanals ermitteln, damit eine fehlerfreie Decodierung gerade noch möglich ist. Man erhält für den Grenzfall&nbsp; $R = C$:
  
Die Grafik fasst das Ergebnis zusammen, wobei die Ordinate <i>R</i> im linearen Maßstab und die Abszisse <i>E</i><sub>B</sub>/<i>N</i><sub>0</sub> logarithmisch aufgetragen ist. Außerhalb der blauen Fläche ist eine fehlerfreie Codierung nicht möglich. Die blaue Grenzkurve gibt die Kanalkapazität <i>C</i> des AWGN&ndash;Kanals an.<br>
+
::<math>{E_{\rm B} }/{N_0} > \frac{2^{2R}-1}{2R } \hspace{0.05cm}.</math>}}
  
[[Datei:P ID2373 KC T 1 7 S3b v3.png|Kanalkapazität des AWGN–Kanals|class=fit]]<br>
 
  
 +
Die Grafik fasst das Ergebnis zusammen, wobei die Ordinate&nbsp; $R$&nbsp; im linearen Maßstab und die Abszisse&nbsp; $E_{\rm B}/{N_0 }$&nbsp; logarithmisch aufgetragen ist.
 +
[[Datei:P ID2373 KC T 1 7 S3b v3.png|right|frame|Kanalkapazität des AWGN–Kanals|class=fit]]
 +
*Außerhalb der blauen Fläche ist eine fehlerfreie Codierung nicht möglich.
 +
*Die blaue Grenzkurve gibt die Kanalkapazität&nbsp; $C$&nbsp; des AWGN&ndash;Kanals an.<br>
 +
<br clear=all>
 
Aus dieser Grafik und obiger Gleichung lässt sich Folgendes ableiten:
 
Aus dieser Grafik und obiger Gleichung lässt sich Folgendes ableiten:
*Die Kanalkapazität <i>C</i> steigt etwas weniger als linear mit 10 &middot; lg <i>E</i><sub>B</sub>/<i>N</i><sub>0</sub> an. In der Grafik sind einige ausgewählte Funktionswerte angegeben (blaue Kreuze).<br>
+
*Die Kanalkapazität&nbsp; $C$&nbsp; steigt etwas weniger als linear mit&nbsp; $10 \cdot \lg \, E_{\rm B}/N_0 $&nbsp; an. In der Grafik sind einige ausgewählte Funktionswerte als blaue Kreuze angegeben.<br>
  
*Ist 10 &middot; lg (<i>E</i><sub>B</sub>/<i>N</i><sub>0</sub>) kleiner als &ndash;1.59 dB, so ist eine fehlerfreie Decodierung prinzipiell unmöglich. Beträgt die Coderate <i>R</i> = 0.5, so muss 10 &middot; lg (<i>E</i><sub>B</sub>/<i>N</i><sub>0</sub>) größer als 0 dB &nbsp;&nbsp;&#8658;&nbsp;&nbsp; <i>E</i><sub>B</sub> > <i>N</i><sub>0</sub> sein.<br>
+
*Ist&nbsp; $10 \cdot \lg \, E_{\rm B}/N_0  < -1.59 \, \rm dB$, so ist eine fehlerfreie Decodierung prinzipiell unmöglich. Beträgt die Coderate&nbsp; $R = 0.5$, so muss&nbsp; $10 \cdot \lg \, E_{\rm B}/N_0  > 0 \, \rm dB$&nbsp; sein &nbsp;&nbsp;&#8658;&nbsp;&nbsp; $E_{\rm B} > N_0$.<br>
  
*Für alle binären Codes gilt per se 0 &#8804; <i>R</i> &#8804; 1. Coderaten <i>R</i> >  1 sind nur mit <i>nichtbinären</i> Codes möglich. Beispielsweise beträgt die maximal mögliche Coderate eines quaternären Codes <i>R</i> = 2.<br>
+
*Für alle binären Codes gilt per se&nbsp; $0 < R &#8804; 1$. Nur mit <i>nichtbinären</i> Codes sind Coderaten&nbsp; $R >  1$&nbsp; möglich. Beispielsweise beträgt die maximal mögliche Coderate eines quaternären Codes&nbsp; $R = \log_2 \, M_y = \log_2 \, 4 = 2$.<br>
  
*Alle eindimensionalen Modulationsarten &ndash; also solche Verfahren, die nur die Inphase&ndash; oder nur die Quadraturkomponente nutzen wie ASK, BPSK und FSK &ndash; müssen im blauen Bereich liegen.<br>
+
*Alle eindimensionalen Modulationsarten &ndash; also solche Verfahren, die nur die Inphase&ndash; oder nur die Quadraturkomponente nutzen wie&nbsp; [[Digitalsignalübertragung/Trägerfrequenzsysteme_mit_kohärenter_Demodulation#On.E2.80.93Off.E2.80.93Keying_.282.E2.80.93ASK.29|2&ndash;ASK]],&nbsp; [[Digitalsignalübertragung/Trägerfrequenzsysteme_mit_kohärenter_Demodulation#Binary_Phase_Shift_Keying_.28BPSK.29|BPSK]]&nbsp; und&nbsp; [[Digitalsignalübertragung/Trägerfrequenzsysteme_mit_nichtkohärenter_Demodulation#Nichtkoh.C3.A4rente_Demodulation_von_bin.C3.A4rer_FSK_.282.E2.80.93FSK.29|2&ndash;FSK]]&nbsp; &ndash; müssen im blauen Bereich der vorliegenden Grafik liegen.<br>
 +
*Wie im Kapitel&nbsp; [[Informationstheorie/AWGN–Kanalkapazität_bei_wertdiskretem_Eingang#Maximale_Coderate_f.C3.BCr_QAM.E2.80.93Strukturen|Maximale Coderate für QAM&ndash;Strukturen]]&nbsp; des Buches &bdquo;Informationstheorie&rdquo; gezeigt wird, gibt es für zweidimensionale Modulationsarten wie zum Beispiel die&nbsp; [[Modulationsverfahren/Quadratur–Amplitudenmodulation|Quadratur&ndash;Amplitudenmodulation]]&nbsp; eine &bdquo;freundlichere&rdquo; Grenzkurve. 
  
 
== AWGN–Kanalkapazität für binäre Eingangssignale ==
 
== AWGN–Kanalkapazität für binäre Eingangssignale ==
 
<br>
 
<br>
In diesem Buch beschränken wir uns meist auf binäre Codes, also auf das Galoisfeld GF(2<sup><i>n</i></sup>). Damit ist
+
In diesem Buch beschränken wir uns vorwiegend auf binäre Codes, also auf das Galoisfeld&nbsp; ${\rm GF}(2^n)$. Damit ist
*zum einen die Coderate auf den Bereich <i>R</i> &#8804; 1 begrenzt,<br>
+
[[Datei:P ID2374 KC T 1 7 S4a.png|right|frame|Bedingte Dichtefunktionen bei AWGN–Kanal und binärem Eingang]]
 
+
*zum einen die Coderate auf den Bereich&nbsp; $R &#8804; 1$&nbsp; begrenzt,<br>
*zum zweiten auch für <i>R</i> &#8804; 1 nicht die gesamte blaue Region (siehe letzte Seite) verfügbar.<br><br>
+
*zum zweiten auch für&nbsp; $R &#8804; 1$&nbsp; nicht die gesamte blaue Region verfügbar  (siehe vorherige Seite).
 
 
[[Datei:P ID2374 KC T 1 7 S4a.png|Bedingte Wahrscheinlichkeitsdichten des binären AWGN–Kanals|rechts|rahmenlos]]
 
 
 
Die nun gültige Region ergibt sich aus der [http://www.lntwww.de/Kanalcodierung/Informationstheoretische_Grenzen_der_Kanalcodierung#Kanalcodierungstheorem_und_Kanalkapazit.C3.A4t allgemeinen Gleichung] der Transinformation durch
 
*die Parameter <i>M<sub>x</sub></i> = 2 und <i>M<sub>y</sub></i> &#8594; &#8734;,<br>
 
  
*bipolare Signalisierung &nbsp;&#8658;&nbsp; <i>x</i> = 0 &#8594; <i>x</i>&#x0303; = +1,&nbsp; <i>x</i> = 1 &#8594; <i>x</i>&#x0303; = &ndash;1,<br>
 
 
*den Übergang von bedingten Wahrscheinlichkeiten Pr(<i>x&#x0303;</i><sub><i>i</i></sub>) zu bedingten Wahrscheinlichkeitsdichtefunktionen,<br>
 
  
 +
Die nun gültige Region ergibt sich aus der&nbsp; [[Kanalcodierung/Informationstheoretische_Grenzen_der_Kanalcodierung#Kanalcodierungstheorem_und_Kanalkapazit.C3.A4t|allgemeinen Gleichung]]&nbsp; der Transinformation durch
 +
*die Parameter&nbsp; $M_x = 2$&nbsp; und&nbsp; $M_y \to \infty$,<br>
 +
*bipolare Signalisierung &nbsp; &#8658; &nbsp; $x=0$ &nbsp; &#8594; &nbsp; $\tilde{x} = +1$&nbsp; und&nbsp; $x=1$ &nbsp; &#8594; &nbsp; $\tilde{x} = -1$,<br>
 +
*den Übergang von bedingten Wahrscheinlichkeiten&nbsp; ${\rm Pr}(\tilde{x}_i)$&nbsp; zu bedingten Wahrscheinlichkeitsdichtefunktionen,<br>
 
*Ersetzen der Summe durch eine Integration.<br><br>
 
*Ersetzen der Summe durch eine Integration.<br><br>
  
 
Die Optimierung der Quelle führt auf gleichwahrscheinliche Symbole:
 
Die Optimierung der Quelle führt auf gleichwahrscheinliche Symbole:
  
:<math>{\rm Pr}(\tilde{x} = +1) = {\rm Pr}(\tilde{x} = -1) = 1/2  \hspace{0.05cm}. </math>
+
::<math>{\rm Pr}(\tilde{x} = +1) = {\rm Pr}(\tilde{x} = -1) = 1/2  \hspace{0.05cm}. </math>
  
Damit erhält man  bei binärem Eingang (&plusmn;1) für die Kanalkapazität &nbsp;&#8658;&nbsp; Maximum der Transinformation hinsichtlich Pr(<i>x&#x0303;</i><sub><i>i</i></sub>):
+
Damit erhält man  für das Maximum der Transinformation, also für die Kanalkapazität:  
  
:<math>C \hspace{-0.15cm} = {1}/{2} \cdot \int_{-\infty }^{+ \infty}
+
::<math>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)} +  
 
\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)}
 
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)}
Zeile 190: Zeile 197:
 
\hspace{0.05cm}.</math>
 
\hspace{0.05cm}.</math>
  
Das Integral lässt sich nicht in mathematisch&ndash;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:
+
Das Integral lässt sich nicht in mathematisch&ndash;geschlossener Form lösen, sondern kann nur numerisch ausgewertet werden.  
*Für 10 &middot; lg <i>E</i><sub>B</sub>/<i>N</i><sub>0</sub> < 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 &middot; lg <i>E</i><sub>B</sub>/<i>N</i><sub>0</sub> nur etwa um 0.1 dB erhöhen, um ebenfalls die Coderate <i>R</i> = 0.5 zu ermöglichen.<br>
+
*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.
 +
   
 +
[[Datei:P ID2375 KC T 1 7 S4b v3.png|right|frame|AWGN–Kanalkapazität für binäre Eingangssignale|class=fit]]
  
*Ab etwa 10 &middot; lg <i>E</i><sub>B</sub>/<i>N</i><sub>0</sub> = 6 dB ist die Kanalkapazität <i>C</i> = 1 bit/Kanalzugriff für binären Eingang (fast) erreicht. Dazwischen verläuft die grüne Grenzkurve annähernd  exponentiell ansteigend.
 
  
:[[Datei:P ID2375 KC T 1 7 S4b v3.png|AWGN–Kanalkapazität für binäre Eingangssignale|class=fit]]<br>
+
Man erkennt:
 +
*Für&nbsp; $10 \cdot \lg \, E_{\rm B}/N_0  < 0  \, \rm dB$&nbsp; 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&nbsp;  $10 \cdot \lg \, E_{\rm B}/N_0$&nbsp; nur etwa um&nbsp; $0.1 \, \rm dB$&nbsp; erhöhen, um ebenfalls die Coderate&nbsp; $R = 0.5$&nbsp; zu ermöglichen.<br>
  
== Gebräuchliche Kanalcodes im Vergleich zur Kanalkapazität (1) ==
+
*Ab&nbsp; $10 \cdot \lg \, E_{\rm B}/N_0 \approx6  \, \rm dB$&nbsp; ist die Kapazität&nbsp; $C = 1 \, \rm bit/Kanalzugriff$&nbsp; des AWGN&ndash;Kanals für binären Eingang (fast) erreicht.
 +
*Dazwischen verläuft die Grenzkurve annähernd  exponentiell ansteigend.
 +
<br clear=all>
 +
== Gebräuchliche Kanalcodes im Vergleich zur Kanalkapazität ==
 
<br>
 
<br>
Nun soll gezeigt werden, in wie weit sich etablierte Kanalcodes der BPSK&ndash;Kanalkapazität (grüne Kurve) annähern. In der Grafik ist als Ordinate die Rate <i>R</i> = <i>k</i>/<i>n</i> dieser Codes bzw. die Kapazität <i>C</i> (mit der zusätzlichen Pseudo&ndash;Einheit &bdquo;bit/Kanalzugriff&rdquo;) aufgetragen. Weiter ist vorausgesetzt:
+
Nun soll gezeigt werden, in wie weit sich etablierte Kanalcodes der BPSK&ndash;Kanalkapazität (grüne Kurve) annähern. In der folgenden Grafik ist als Ordinate die Rate&nbsp; $R=k/n$&nbsp; dieser Codes bzw. die Kapazität&nbsp; $C$&nbsp; (mit der zusätzlichen Pseudo&ndash;Einheit &bdquo;bit/Kanalzugriff&rdquo;) aufgetragen. Weiter ist vorausgesetzt:
*der AWGN&ndash;Kanal, gekennzeichnet durch 10 &middot; lg <i>E</i><sub>B</sub>/<i>N</i><sub>0</sub> in dB, und<br>
+
*der AWGN&ndash;Kanal, gekennzeichnet durch&nbsp; $10 \cdot \lg \, E_{\rm B}/N_0$&nbsp; in dB, und<br>
  
*für die durch Kreuze markierten Codes eine Bitfehlerrate (BER) von 10<sup>&ndash;5</sup>.<br><br>
+
*für die durch Kreuze markierten Codes eine Bitfehlerrate (BER) von&nbsp; $10^{-5}$.<br>
  
Zu beachten ist, dass die Kanalkapazitätskurven stets für <i>n</i> &#8594; &#8734;  und BER = 0 gelten. Würde man diese strenge Forderung &bdquo;feherfrei&rdquo; auch an die betrachteten Kanalcodes endlicher Codelänge <i>n</i> anlegen, so wäre hierfür stets 10 &middot; <i>E</i><sub>B</sub>/<i>N</i><sub>0</sub> &#8594; &#8734; erforderlich. Dies ist aber ein akademisches Problem, das für die Praxis wenig Bedeutung hat. Für BER = 10<sup>&ndash;10</sup> ergäbe sich eine qualitativ ähnliche Grafik.<br>
 
  
[[Datei:P ID2968 KC T 1 7 S5a v3.png|Raten und erforderliches <i>E</i><sub>B</sub>/<i>N</i><sub>0</sub> verschiedener Kanalcodes|class=fit]]<br>
+
[[Datei:P ID2968 KC T 1 7 S5a v3.png|right|frame|Raten und erforderliches&nbsp; $E_{\rm B}/N_0$&nbsp; verschiedener Kanalcodes|class=fit]]
  
Es folgen einige Erläuterungen zu den Daten, die der Vorlesung [Liv10]<ref>Liva, G.: Channel Coding. Vorlesungsmanuskript, Lehrstuhl für Nachrichtentechnik, TU München und DLR Oberpfaffenhofen, 2010.</ref> entnommen wurden:
 
*Die Punkte <b>A</b>, <b>B</b> und <b>C</b> markieren Hamming&ndash;Codes unterschiedlicher Rate, die im [http://www.lntwww.de/Kanalcodierung/Beispiele_bin%C3%A4rer_Blockcodes#Single_Parity.E2.80.93check_Codes_.281.29 Kapitel 1.3] bereits ausführlich behandelt wurden. Sie alle benötigen 10 &middot; lg <i>E</i><sub>B</sub>/<i>N</i><sub>0</sub> > 8 dBfür BER = 10<sup>&ndash;5</sup>.<br>
 
  
*<b>D</b> kennzeichnet den binären Golay&ndash;Code mit der Rate 1/2 und <b>E</b> einen Reed&ndash;Muller&ndash;Code. Dieser sehr niederratige Code kam  bereits 1971 bei der Raumsonde Mariner 9 zum Einsatz.<br>
+
 +
$\text{Bitte beachten Sie:}$&nbsp;
 +
*Die Kanalkapazitätskurven gelten stets für&nbsp; $n \to \infty$&nbsp;  und&nbsp; $\rm BER \to 0$&nbsp; gelten.
 +
*Würde man diese strenge Forderung &bdquo;fehlerfrei&rdquo; auch an die betrachteten Kanalcodes endlicher Codelänge&nbsp; $n$&nbsp; anlegen, so wäre hierfür stets&nbsp; $10 \cdot \lg \, E_{\rm B}/N_0 \to \infty$&nbsp;  erforderlich.
 +
*Dies ist aber ein akademisches Problem, das für die Praxis wenig Bedeutung hat. Für&nbsp; $\rm BER = 10^{-10}$&nbsp; ergäbe sich eine qualitativ und auch quantitativ ähnliche Grafik.<br>
 +
<br clear=all>
 +
Es folgen einige Erläuterungen zu den Daten, die der Vorlesung [Liv10]<ref name='Liv10'>Liva, G.: Channel Coding. Vorlesungsmanuskript, Lehrstuhl für Nachrichtentechnik, TU München und DLR Oberpfaffenhofen, 2010.</ref> entnommen wurden:
 +
*Die Punkte&nbsp; $\rm A$,&nbsp; $\rm B$&nbsp; und&nbsp; $\rm C$&nbsp; markieren&nbsp; [[Kanalcodierung/Beispiele_binärer_Blockcodes#Hamming.E2.80.93Codes|Hamming&ndash;Codes]]&nbsp; unterschiedlicher Rate. Sie alle benötigen für&nbsp; $\rm BER = 10^{-5}$&nbsp; mehr alss&nbsp; $10 \cdot \lg \, E_{\rm B}/N_0  = 8  \, \rm dB$.
 +
*Die Markierung&nbsp; $\rm D$&nbsp; kennzeichnet den binären&nbsp; [https://de.wikipedia.org/wiki/Golay-Code Golay&ndash;Code]&nbsp; mit der Rate&nbsp; $1/2$&nbsp; und die Markierung&nbsp; $\rm E$&nbsp; einen&nbsp; [https://de.wikipedia.org/wiki/Reed-Muller-Code Reed&ndash;Muller&ndash;Code]. Dieser sehr niederratige Code kam  bereits 1971 bei der Raumsonde Mariner 9 zum Einsatz.
 +
*Die&nbsp; [[Kanalcodierung/Definition_und_Eigenschaften_von_Reed–Solomon–Codes|Reed&ndash;Solomon&ndash;Codes]]&nbsp; (RS&ndash;Codes) werden im zweiten Hauptkapitel ausführlich behandelt. Mit&nbsp; $\rm F$&nbsp; markiert ist ein hochratiger RS&ndash;Code&nbsp; $(R = 223/255 > 0.9)$&nbsp; und einem erforderlichen&nbsp; $10 \cdot \lg \, E_{\rm B}/N_0  < 6  \, \rm dB$.
 +
*Die Markierungen&nbsp; $\rm G$&nbsp; und&nbsp; $\rm H$&nbsp; bezeichnen beispielhafte&nbsp; [[Kanalcodierung/Grundlagen_der_Faltungscodierung|Faltungscodes]]&nbsp; (englisch: &nbsp; <i>Convolutional Codes</i>, CC) mittlerer Rate. Der Code&nbsp; $\rm G$&nbsp; wurde schon 1972 bei der Pioneer10&ndash;Mission eingesetzt.
 +
*Die Kanalcodierung der Voyager&ndash;Mission Ende der 1970er Jahre ist mit&nbsp; $\rm I$&nbsp; markiert. Es handelt sich um die Verkettung eines&nbsp; $\text{(2, 1, 7)}$&ndash;Faltungscodes mit einem Reed&ndash;Solomon&ndash;Code, wie im vierten Hauptkapitel beschrieben.<br><br>
  
*Die [http://www.lntwww.de/Kanalcodierung/Definition_und_Eigenschaften_von_Reed%E2%80%93Solomon%E2%80%93Codes#Konstruktion_von_Reed.E2.80.93Solomon.E2.80.93Codes_.281.29 Reed&ndash;Solomon&ndash;Codes] (RS&ndash;Codes) werden im Kapitel 2 noch ausführlich behandelt. Mit <b>F</b> markiert ist der RS&ndash;Code der Rate 223/255 > 0.9 und einem erforderlichen <i>E</i><sub>B</sub>/<i>N</i><sub>0</sub> < 6 dB. <br>
+
''Anmerkung'': &nbsp; Bei den Faltungscodes hat insbesondere der dritte Kennungsparameter eine andere Bedeutung als bei den Blockcodes. $\text{CC (2, 1, 32)}$&nbsp; weist beispielsweise auf das Memory&nbsp; $m = 32$&nbsp; hin.<br>
 +
[[Datei:P ID2377 KC T 1 7 S5b v4.png|right|frame|Raten und erforderliches&nbsp; $E_{\rm B}/N_0$&nbsp;  für iterative Codierverfahren |class=fit]]
  
*Die Markierungen <b>G</b> und <b>H</b> bezeichnen beispielhafte Faltungscodes (englisch: <i>Convolutional Codes</i>, CC) mittlerer Rate. Ersterer wurde schon 1972 bei der Pioneer10&ndash;Mission eingesetzt.<br>
 
  
*Die Kanalcodierung der Voyager&ndash;Mission Ende der 1970er Jahre ist mit <b>I</b> markiert. Es handelt sich um die Verkettung eines (2, 1, 7)&ndash;Faltungscodes mit einem Reed&ndash;Solomon&ndash;Code.<br><br>
 
  
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 <i>m</i> = 32 hin.<br>
 
  
Auf der nächsten Seite folgen noch Kenndaten von Systemen mit iterativer Decodierung.<br>
+
Mit iterativer Decodierung lassen sich deutlich bessere Ergebnisse erzielen, wie die zweite Grafik zeigt.
 +
*Das heißt: &nbsp;Die einzelnen Markierungspunkte liegen sehr viel näher an der Kapazitätskurve.<br>
 +
*Die bisher mit &bdquo;Gauß&ndash;Kapazität&rdquo; beschriftete durchgezogene blaue Kurve wird hier &bdquo;Gauß (reell)&rdquo; genannt.
 +
<br clear=all>
 +
Hier noch einige weitere Erläuterungen zu dieser Grafik:
 +
* Rote Kreuze markieren sogenannte&nbsp; [[Kanalcodierung/Grundlegendes_zu_den_Turbocodes|Turbocodes]]&nbsp; nach&nbsp; [https://en.wikipedia.org/wiki/Consultative_Committee_for_Space_Data_Systems CCSDS]&nbsp; (<i>Consultative Committee for Space Data Systems</i>&nbsp;) mit jeweils&nbsp; $k = 6920$&nbsp; Informationsbits und unterschiedlichen Codelängen&nbsp; $n$. Diese von&nbsp; [http://perso.telecom-bretagne.eu/claudeberrou/ Claude Berrou]&nbsp; um 1990 erfundenen Codes können iterativ decodiert werden. Die (roten) Markierungen liegen jeweils weniger als&nbsp; $1 \, \rm dB$&nbsp; von der Shannon&ndash;Grenze entfernt.<br>
  
== Gebräuchliche Kanalcodes im Vergleich zur Kanalkapazität (2) ==
+
*Ähnliches Verhalten zeigen die durch weiße Rechtecke gekennzeichneten&nbsp; [[Kanalcodierung/Grundlegendes_zu_den_Low–density_Parity–check_Codes|LDPC&ndash;Codes]]&nbsp; (<i>Low Density Parity&ndash;check Codes</i>&nbsp;), die seit 2006 bei&nbsp; [https://praxistipps.chip.de/dvb-s-und-dvb-s2-was-ist-der-unterschied_12879 DVB&ndash;S(2)]&nbsp; (<i>Digital Video Broadcast over Satellite</i>&nbsp;) eingesetzt werden. Diese eignen sich aufgrund der spärlichen Belegung der Prüfmatrix&nbsp; $\boldsymbol {\rm H}$&nbsp; (mit Einsen) sehr gut für die iterative Decodierung mittels ''Faktor&ndash;Graphen'' &nbsp; und &nbsp;  ''Exit Charts''. Siehe  [Hag02]<ref name='Hag02'>Hagenauer, J.: ''The Turbo Principle in Mobile Communications''. In: Int. Symp. on Information Theory and Its Applications, Oct.2010,  [http://wwwmayr.in.tum.de/konferenzen/Jass05/courses/4/papers/prof_hagenauer.pdf PDF&ndash;Dokument.]</ref><br>
<br>
 
Mit iterativer Decodierung lassen sich deutlich bessere Ergebnisse erzielen, wie die folgende Grafik zeigt. Das heißt: Die einzelnen Markierungspunkte liegen sehr viel näher an der Kapazitätskurve.<br>
 
  
[[Datei:P ID2377 KC T 1 7 S5b v4.png|Raten und erforderliches <i>E</i><sub>B</sub>/<i>N</i><sub>0</sub>  für iterative Codierverfahren |class=fit]]<br>
+
*Die schwarzen Punkte markieren die von CCSDS spezifizierten&nbsp; [[Kanalcodierung/Grundlegendes_zu_den_Low–density_Parity–check_Codes|LDPC&ndash;Codes]], die alle von einer konstanten Anzahl von Informationsbits ausgehen&nbsp; $(k = 16384)$. Dagegen ist bei allen weißen Rechtecken die Codelänge&nbsp; $n = 64800$&nbsp; konstant, während sich die Anzahl&nbsp; $k$&nbsp; der Informationsbits entsprechend der Rate&nbsp; $R = k/n$&nbsp; ändert.<br>
  
Die bisher mit &bdquo;Gauß&ndash;Kapazität&rdquo; beschriftete durchgezogene blaue Kurve wird hier &bdquo;Gauß (reell)&rdquo; genannt. Hier noch einige weitere Erläuterungen zu dieser Grafik:
+
*Um das Jahr 2000 hatten viele Forscher den Ehrgeiz, sich der Shannon&ndash;Grenze bis auf Bruchteile von einem &nbsp;$\rm dB$&nbsp; anzunähern. Das gelbe Kreuz markiert ein solches Ergebnis aus [CFRU01]<ref name='CFRU01'>Chung S.Y; Forney Jr., G.D.; Richardson, T.J.; Urbanke, R.: ''On the Design of Low-Density Parity- Check Codes within 0.0045 dB of the Shannon Limit''. – In: IEEE Communications Letters, vol. 5, no. 2 (2001), pp. 58–60.''</ref>. Verwendet wurde ein irregulärer Rate&ndash;1/2&ndash;LDPC&ndash;Code der Codelänge&nbsp; $n = 2 \cdot10^6$.<br><br>
* Rote Kreuze markieren sogenannte Turbocodes nach CCSDS (<i>Consultative Committee for Space Data Systems</i>) mit jeweils <i>k</i> = 6920 Informationsbits und unterschiedlichen Codelängen <i>n</i>. Diese von [http://perso.telecom-bretagne.eu/claudeberrou/ Claude Berrou] um 1990 erfundenen Codes können iterativ decodiert werden. Die (roten) Markierungen liegen jeweils weniger als 1 dB von der Shannon&ndash;Grenze entfernt.<br>
 
  
*Ähnliches Verhalten zeigen die durch weiße Rechtecke gekennzeichneten LDPC&ndash;Codes (<i>Low Density Parity&ndash;check Codes</i>), die seit 2006 bei DVB&ndash;S2 (<i>Digital Video Broadcast over Satellite</i>) eingesetzt werden. Diese eignen sich aufgrund der spärlichen Belegung der Prüfmatrix <b>H</b> (mit Einsen) sehr gut für die iterative Decodierung mittels Faktor&ndash;Graphen und [http://wwwmayr.in.tum.de/konferenzen/Jass05/courses/4/papers/prof_hagenauer.pdf Exit Charts.]<br>
+
{{BlaueBox|TEXT=
 
+
$\text{Fazit:}$&nbsp; Festzuhalten ist, dass Shannon bereits 1948 erkannt und nachgewiesen hat, dass kein eindimensionales Modulationsverfahren links von der durchgehend eingezeichneten AWGN&ndash;Grenzkurve &bdquo;Gauß (reell)&rdquo; liegen kann.   
*Die schwarzen Punkte markieren die von CCSDS spezifizierten LDPC&ndash;Codes, die alle von einer konstanten Anzahl von Informationsbits ausgehen (<i>k</i> = 16384). Dagegen ist bei allen weißen Rechtecken die Codelänge <i>n</i> = 64800 konstant, während sich die Anzahl <i>k</i> der Informationsbits entsprechend der Rate <i>R</i> = <i>k</i>/<i>n</i> ändert.<br>
+
*Für zweidimensionale Verfahren wie QAM und mehrstufige PSK gilt dagegen die Grenzkurve &bdquo;Gauß (komplex)&rdquo;, die hier gestrichelt gezeichnet ist und stets links von der durchgezogenen Kurve liegt.  
 
+
*Näheres hierzu finden Sie im Abschnitt&nbsp; [[Informationstheorie/AWGN%E2%80%93Kanalkapazit%C3%A4t_bei_wertdiskretem_Eingang#Maximale_Coderate_f.C3.BCr_QAM.E2.80.93Strukturen|Maximale Coderate für QAM&ndash;Strukturen]]&nbsp; des Buches &bdquo;Informationstheorie&rdquo;.<br>
*Um das Jahr 2000 hatten viele Forscher den Ehrgeiz, sich der Shannon&ndash;Grenze bis auf Bruchteile von einem dB anzunähern. Das gelbe Kreuz markiert ein solches Ergebnis aus [CFRU01] von 2001. Verwendet wurde ein irregulärer Rate&ndash;1/2&ndash;LDPC&ndash;Code der Codelänge <i>n</i> = 2 &middot; 10<sup>6</sup>.<br><br>
+
*Auch diese Grenzkurve wurde mit QAM&ndash;Verfahren und sehr langen Kanalcodes inzwischen nahezu erreicht, ohne dass sie jemals überschritten werden wird.}}<br>
 
 
Festzuhalten ist, dass Shannon bereits 1948 erkannt und nachgewiesen hat, dass kein eindimensionales Modulationsverfahren links von der durchgehend eingezeichneten AWGN&ndash;Grenzkurve &bdquo;Gauß (reell)&rdquo; liegen kann.  Für zweidimensionale Verfahren wie QAM und mehrstufige PSK gilt dagegen die Grenzkurve &bdquo;Gauß (komplex)&rdquo;, die hier gestrichelt gezeichnet ist und stets links von der durchgezogenen Kurve liegt. Näheres hierzu im [http://www.lntwww.de/Informationstheorie/AWGN%E2%80%93Kanalkapazit%C3%A4t_bei_wertdiskretem_Eingang#Maximale_Coderate_f.C3.BCr_QAM.E2.80.93Strukturen Kapitel 4.3] des Buches &bdquo;Einführung in die Informationstheorie&rdquo;.<br>
 
 
 
Auch diese Grenzkurve wurde mit QAM und sehr langen Kanalcodes inzwischen nahezu erreicht, ohne dass sie jemals überschritten werden wird.<br>
 
  
== Aufgaben ==
+
== Aufgaben zum Kapitel ==
 
<br>
 
<br>
[[Aufgaben:1.17 Coderate vs. EB/N0|A1.17 Coderate vs. EB/N0]]
+
[[Aufgaben:Aufgabe_1.17:_Zum_Kanalcodierungstheorem|Aufgabe 1.17: Zum Kanalcodierungstheorem]]
  
[[Zusatzaufgaben:1.17 BPSK–Kanalkapazität]]
+
[[Aufgaben:Aufgabe_1.17Z:_BPSK–Kanalkapazität|Aufgabe 1.17Z: BPSK–Kanalkapazität]]
  
 
==Quellenverzeichnis==
 
==Quellenverzeichnis==

Aktuelle Version vom 18. August 2022, 15:17 Uhr

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.

$\text{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  $R$  kleiner ist als die Kanalkapazität  $C$. Voraussetzung hierfür ist, dass für die Blocklänge dieses Codes gilt:   $n \to \infty$.


Anmerkungen: 

  • Die Aussage „Die Fehlerwahrscheinlichkeit geht gegen Null” ist nicht identisch mit der Aussage „Die Übertragung ist fehlerfrei”. Beispiel:   Bei einer unendlich langen Folge werden endlich viele Symbole verfälscht.
  • Bei manchen Kanälen geht auch mit  $R=C$  die Fehlerwahrscheinlichkeit noch gegen Null (aber nicht bei allen).


Die Umkehrung des Kanalcodierungstheorems ist ebenfalls zutreffend und besagt:

$\text{Umkehrschluss:}$  Ist die Coderate  $R$  größer als die Kanalkapazität  $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$  und  $M_y$  möglichen Ausgangswerten  $y$  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$  an seinem Ausgang:

\[I(x; y) =\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)} = \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:

  • Der Logarithmus dualis  ist hier mit „log2” bezeichnet ist. Teilweise verwenden wir in unserem Lerntutorial hierfür auch „ld”.
  • Im Gegensatz zum Buch  Informationstheorie  unterscheiden wir im Folgenden nicht zwischen der Zufallsgröße $($Großbuchstaben  $X$  bzw.  $Y)$  und den Realisierungen $($Kleinbuchstaben  $x$  bzw.  $y)$.


$\text{Definition:}$  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  ${\rm Pr}(x_i)$  erfolgen muss, ist die Kanalkapazität unabhängig vom Eingang und damit eine reine Kanalkenngröße.

Kanalkapazität des BSC–Modells


Wir wenden nun diese Definitionen auf das  BSC–Modell  (Binary Symmetric Channel ) an:

\[I(x; y) = {\rm Pr}(y = 0 \hspace{0.03cm}| \hspace{0.03cm}x = 0) \cdot {\rm Pr}(x = 0) \cdot {\rm log_2 } \hspace{0.15cm}\frac{{\rm Pr}(y = 0 \hspace{0.03cm}| \hspace{0.03cm}x = 0)}{{\rm Pr}(y = 0)} + {\rm Pr}(y = 1 \hspace{0.03cm}| \hspace{0.03cm}x = 0) \cdot {\rm Pr}(x = 0) \cdot {\rm log_2 } \hspace{0.15cm}\frac{{\rm Pr}(Y = 1 \hspace{0.03cm}| \hspace{0.03cm}x = 0)}{{\rm Pr}(y = 1)} + \]
\[\hspace{1.45cm} + \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)} + {\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}.\]
BSC–Kanalmodell

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}.\]
  • Wir berücksichtigen zudem die BSC–Übergangswahrscheinlichkeiten:
\[{\rm Pr}(y = 1 \hspace{0.05cm}| \hspace{0.05cm}x = 0) = {\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) = {\rm Pr}(y = 1 \hspace{0.05cm}| \hspace{0.05cm}x = 1) = 1-\varepsilon \hspace{0.05cm}.\]
  • Nach Zusammenfassen je zweier Terme erhält man somit:
\[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 } \varepsilon \cdot {\rm ld } \hspace{0.15cm}2 - \varepsilon \cdot {\rm log_2 } \hspace{0.15cm} \frac{1}{\varepsilon }+ (1- \varepsilon) \cdot {\rm log_2 } \hspace{0.15cm} 2 - (1- \varepsilon) \cdot {\rm log_2 } \hspace{0.15cm}\frac{1}{1- \varepsilon}\]
\[\Rightarrow \hspace{0.3cm} C \hspace{0.15cm} = \hspace{0.15cm} 1 - H_{\rm bin}(\varepsilon). \]
  • Verwendet ist hier die binäre Entropiefunktion:
\[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}.\]

Die folgende rechte Grafik zeigt die BSC–Kanalkapazität abhängig von der Verfälschungswahrscheinlichkeit  $\varepsilon$. Links ist zum Vergleich die binäre Entropiefunktion dargestellt, die bereits im Kapitel  Gedächtnislose Nachrichtenquellen  des Buches „Informationstheorie” definiert wurde.

Kanalkapazität des BSC–Modells

Man erkennt aus dieser Darstellung:

  • Die Verfälschungswahrscheinlichkeit  $\varepsilon$  führt zur Kanalkapazität $C(\varepsilon)$. Eine fehlerfreie Decodierung nach bestmöglicher Codierung ist nach dem  Kanalcodierungstheorem  nur dann möglich, wenn die Coderate $R$ nicht größer ist als  $C(\varepsilon)$.
  • Mit  $\varepsilon = 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  $\varepsilon = 1$  (Invertierung aller Bits) gleich gut wie  $\varepsilon = 0$  (fehlerfreie Übertragung). Ebenso ist  $\varepsilon = 0.9$  äquivalent zu  $\varepsilon = 0.1$. Eine fehlerfreie Decodierung erzielt man hier durch Vertauschen der Nullen und Einsen, also durch ein so genanntes Mapping.

Kanalkapazität des AWGN–Modells


AWGN–Kanalmodell

Wir betrachten nun 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 für deren Erwartungswerte (Momente):

$${\rm E}[n] = 0,\hspace{1cm} {\rm E}[n^2] = P_n.$$

Damit ergibt sich unabhängig vom Eingangssignal  $x$  (analog oder digital) stets ein wertkontinuierliches Ausgangssignal  $y$, und in der  Gleichung für die Transinformation  ist  $M_y \to\infty$  einzusetzen.

Die Berechnung der Kanalkapazität für den AWGN–Kanal wird hier nur in Stichworten angegeben. Die genaue Herleitung finden Sie im vierten Hauptkapitel „Wertdiskrete Informationstheorie” des Buches  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 \to\infty$  auch  $M_x \to\infty$.
  • Während bei wertdiskretem Eingang über alle  ${\rm 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} \text{:}\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)$  und  $f_y(y)$. Die entsprechenden Leistungen benennen wir  $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_2(\cdot)$ – 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 }} = {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_{\rm S}$, so muss dieses auf  $B = 1/(2T_{\rm S})$  bandbegrenzt sein, und die gleiche Bandbreite  $B$  muss man auch für das Rauschsignal  $n$  ansetzen   ⇒   „Rauschbandbreite”:
\[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_{\rm S})$  und die  Rauschleistungsdichte  $(N_0)$ ausdrücken:
\[C = {1}/{2 } \cdot {\rm log_2 } \hspace{0.05cm}\left ( 1 + {2 E_{\rm S}}/{N_0 } \right )\hspace{0.05cm}, \hspace{1.9cm} \text {Einheit:}\hspace{0.3cm} \frac{\rm bit}{\rm Kanalzugriff}\hspace{0.05cm}.\]
  • Mit der folgenden Gleichung erhält man die Kanalkapazität pro Zeiteinheit (Kennzeichnung durch $^{\star})$:
\[C^{\star} = \frac{C}{T_{\rm S} } = B \cdot {\rm log_2 } \hspace{0.05cm}\left ( 1 + {2 E_{\rm S}}/{N_0 } \right )\hspace{0.05cm}, \hspace{0.8cm} \text {Einheit:} \hspace{0.3cm} \frac{\rm bit}{\rm Zeiteinheit}\hspace{0.05cm}.\]

$\text{Beispiel 1:}$ 

  • Für  $E_{\rm S}/N_0 = 7.5$   ⇒   $10 \cdot \lg \, E_{\rm S}/N_0 = 8.75 \, \rm dB$  erhält man die Kanalkapazität  $C = {1}/{2 } \cdot {\rm log_2 } \hspace{0.05cm} (16) = 2 \, \rm bit/Kanalzugriff$.
  • Bei einem Kanal mit der (physikalischen) Bandbreite  $B = 4 \, \rm kHz$, was der Abtastrate  $f_{\rm A} = 8\, \rm kHz$  entspricht, gilt zudem  $C^\star = 16 \, \rm kbit/s$.


Ein Vergleich verschiedener Codierverfahren bei konstantem  $E_{\rm S}$  (Energie pro übertragenem Symbol ) ist allerdings nicht fair. Vielmehr sollte man für diesen Vergleich die Energie  $E_{\rm B}$  pro Nutzbit  fest vorgeben. Dabei gelten folgende Zusammenhänge:

\[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}. \]

$\text{Kanalcodierungstheorem für den AWGN–Kanal:}$ 

Eine fehlerfreie Decodierung $($bei unendlich langen Blöcken   ⇒   $n \to \infty)$  ist immer dann 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&nbsp $R$  lässt sich damit das erforderliche  $E_{\rm B}/N_0$  des AWGN–Kanals ermitteln, damit eine fehlerfreie Decodierung gerade noch möglich ist. Man erhält für den Grenzfall  $R = C$:

\[{E_{\rm B} }/{N_0} > \frac{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_{\rm B}/{N_0 }$  logarithmisch aufgetragen ist.

Kanalkapazität des AWGN–Kanals
  • 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 \cdot \lg \, E_{\rm B}/N_0 $  an. In der Grafik sind einige ausgewählte Funktionswerte als blaue Kreuze angegeben.
  • Ist  $10 \cdot \lg \, E_{\rm B}/N_0 < -1.59 \, \rm dB$, so ist eine fehlerfreie Decodierung prinzipiell unmöglich. Beträgt die Coderate  $R = 0.5$, so muss  $10 \cdot \lg \, E_{\rm B}/N_0 > 0 \, \rm dB$  sein   ⇒   $E_{\rm B} > N_0$.
  • Für alle binären Codes gilt per se  $0 < R ≤ 1$. Nur mit nichtbinären Codes sind Coderaten  $R > 1$  möglich. Beispielsweise beträgt die maximal mögliche Coderate eines quaternären Codes  $R = \log_2 \, M_y = \log_2 \, 4 = 2$.
  • Alle eindimensionalen Modulationsarten – also solche Verfahren, die nur die Inphase– oder nur die Quadraturkomponente nutzen wie  2–ASKBPSK  und  2–FSK  – müssen im blauen Bereich der vorliegenden Grafik liegen.
  • Wie im Kapitel  Maximale Coderate für QAM–Strukturen  des Buches „Informationstheorie” gezeigt wird, gibt es für zweidimensionale Modulationsarten wie zum Beispiel die  Quadratur–Amplitudenmodulation  eine „freundlichere” Grenzkurve.

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


In diesem Buch beschränken wir uns vorwiegend auf binäre Codes, also auf das Galoisfeld  ${\rm GF}(2^n)$. Damit ist

Bedingte Dichtefunktionen bei AWGN–Kanal und binärem Eingang
  • zum einen die Coderate auf den Bereich  $R ≤ 1$  begrenzt,
  • zum zweiten auch für  $R ≤ 1$  nicht die gesamte blaue Region verfügbar (siehe vorherige Seite).


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

  • die Parameter  $M_x = 2$  und  $M_y \to \infty$,
  • bipolare Signalisierung   ⇒   $x=0$   →   $\tilde{x} = +1$  und  $x=1$   →   $\tilde{x} = -1$,
  • den Übergang von bedingten Wahrscheinlichkeiten  ${\rm Pr}(\tilde{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 für das Maximum der Transinformation, also für die Kanalkapazität:

\[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.
AWGN–Kanalkapazität für binäre Eingangssignale


Man erkennt:

  • Für  $10 \cdot \lg \, E_{\rm B}/N_0 < 0 \, \rm dB$  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 \cdot \lg \, E_{\rm B}/N_0$  nur etwa um  $0.1 \, \rm dB$  erhöhen, um ebenfalls die Coderate  $R = 0.5$  zu ermöglichen.
  • Ab  $10 \cdot \lg \, E_{\rm B}/N_0 \approx6 \, \rm dB$  ist die Kapazität  $C = 1 \, \rm bit/Kanalzugriff$  des AWGN–Kanals für binären Eingang (fast) erreicht.
  • Dazwischen verläuft die Grenzkurve annähernd exponentiell ansteigend.


Gebräuchliche Kanalcodes im Vergleich zur Kanalkapazität


Nun soll gezeigt werden, in wie weit sich etablierte Kanalcodes der BPSK–Kanalkapazität (grüne Kurve) annähern. In der folgenden 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 \cdot \lg \, E_{\rm B}/N_0$  in dB, und
  • für die durch Kreuze markierten Codes eine Bitfehlerrate (BER) von  $10^{-5}$.


Raten und erforderliches  $E_{\rm B}/N_0$  verschiedener Kanalcodes


$\text{Bitte beachten Sie:}$ 

  • Die Kanalkapazitätskurven gelten stets für  $n \to \infty$  und  $\rm BER \to 0$  gelten.
  • Würde man diese strenge Forderung „fehlerfrei” auch an die betrachteten Kanalcodes endlicher Codelänge  $n$  anlegen, so wäre hierfür stets  $10 \cdot \lg \, E_{\rm B}/N_0 \to \infty$  erforderlich.
  • Dies ist aber ein akademisches Problem, das für die Praxis wenig Bedeutung hat. Für  $\rm BER = 10^{-10}$  ergäbe sich eine qualitativ und auch quantitativ ähnliche Grafik.


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

  • Die Punkte  $\rm A$,  $\rm B$  und  $\rm C$  markieren  Hamming–Codes  unterschiedlicher Rate. Sie alle benötigen für  $\rm BER = 10^{-5}$  mehr alss  $10 \cdot \lg \, E_{\rm B}/N_0 = 8 \, \rm dB$.
  • Die Markierung  $\rm D$  kennzeichnet den binären  Golay–Code  mit der Rate  $1/2$  und die Markierung  $\rm 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 zweiten Hauptkapitel ausführlich behandelt. Mit  $\rm F$  markiert ist ein hochratiger RS–Code  $(R = 223/255 > 0.9)$  und einem erforderlichen  $10 \cdot \lg \, E_{\rm B}/N_0 < 6 \, \rm dB$.
  • Die Markierungen  $\rm G$  und  $\rm H$  bezeichnen beispielhafte  Faltungscodes  (englisch:   Convolutional Codes, CC) mittlerer Rate. Der Code  $\rm G$  wurde schon 1972 bei der Pioneer10–Mission eingesetzt.
  • Die Kanalcodierung der Voyager–Mission Ende der 1970er Jahre ist mit  $\rm I$  markiert. Es handelt sich um die Verkettung eines  $\text{(2, 1, 7)}$–Faltungscodes mit einem Reed–Solomon–Code, wie im vierten Hauptkapitel beschrieben.

Anmerkung:   Bei den Faltungscodes hat insbesondere der dritte Kennungsparameter eine andere Bedeutung als bei den Blockcodes. $\text{CC (2, 1, 32)}$  weist beispielsweise auf das Memory  $m = 32$  hin.

Raten und erforderliches  $E_{\rm B}/N_0$  für iterative Codierverfahren



Mit iterativer Decodierung lassen sich deutlich bessere Ergebnisse erzielen, wie die zweite Grafik zeigt.

  • Das heißt:  Die einzelnen Markierungspunkte liegen sehr viel näher an der Kapazitätskurve.
  • Die bisher mit „Gauß–Kapazität” beschriftete durchgezogene blaue Kurve wird hier „Gauß (reell)” genannt.


Hier noch einige weitere Erläuterungen zu dieser Grafik:

  • Rote Kreuze markieren sogenannte  Turbocodes  nach  CCSDS  (Consultative Committee for Space Data Systems ) mit jeweils  $k = 6920$  Informationsbits und unterschiedlichen Codelängen  $n$. Diese von  Claude Berrou  um 1990 erfundenen Codes können iterativ decodiert werden. Die (roten) Markierungen liegen jeweils weniger als  $1 \, \rm dB$  von der Shannon–Grenze entfernt.
  • Ähnliches Verhalten zeigen die durch weiße Rechtecke gekennzeichneten  LDPC–Codes  (Low Density Parity–check Codes ), die seit 2006 bei  DVB–S(2)  (Digital Video Broadcast over Satellite ) eingesetzt werden. Diese eignen sich aufgrund der spärlichen Belegung der Prüfmatrix  $\boldsymbol {\rm H}$  (mit Einsen) sehr gut für die iterative Decodierung mittels Faktor–Graphen   und   Exit Charts. Siehe [Hag02][2]
  • Die schwarzen Punkte markieren die von CCSDS spezifizierten  LDPC–Codes, die alle von einer konstanten Anzahl von Informationsbits ausgehen  $(k = 16384)$. Dagegen ist bei allen weißen Rechtecken die Codelänge  $n = 64800$  konstant, während sich die Anzahl  $k$  der Informationsbits entsprechend der Rate  $R = k/n$  ändert.
  • Um das Jahr 2000 hatten viele Forscher den Ehrgeiz, sich der Shannon–Grenze bis auf Bruchteile von einem  $\rm dB$  anzunähern. Das gelbe Kreuz markiert ein solches Ergebnis aus [CFRU01][3]. Verwendet wurde ein irregulärer Rate–1/2–LDPC–Code der Codelänge  $n = 2 \cdot10^6$.

$\text{Fazit:}$  Festzuhalten ist, dass Shannon bereits 1948 erkannt und nachgewiesen hat, dass kein eindimensionales Modulationsverfahren links von der durchgehend eingezeichneten AWGN–Grenzkurve „Gauß (reell)” liegen kann.

  • Für zweidimensionale Verfahren wie QAM und mehrstufige PSK gilt dagegen die Grenzkurve „Gauß (komplex)”, die hier gestrichelt gezeichnet ist und stets links von der durchgezogenen Kurve liegt.
  • Näheres hierzu finden Sie im Abschnitt  Maximale Coderate für QAM–Strukturen  des Buches „Informationstheorie”.
  • Auch diese Grenzkurve wurde mit QAM–Verfahren und sehr langen Kanalcodes inzwischen nahezu erreicht, ohne dass sie jemals überschritten werden wird.


Aufgaben zum Kapitel


Aufgabe 1.17: Zum Kanalcodierungstheorem

Aufgabe 1.17Z: BPSK–Kanalkapazität

Quellenverzeichnis

  1. Liva, G.: Channel Coding. Vorlesungsmanuskript, Lehrstuhl für Nachrichtentechnik, TU München und DLR Oberpfaffenhofen, 2010.
  2. Hagenauer, J.: The Turbo Principle in Mobile Communications. In: Int. Symp. on Information Theory and Its Applications, Oct.2010, PDF–Dokument.
  3. Chung S.Y; Forney Jr., G.D.; Richardson, T.J.; Urbanke, R.: On the Design of Low-Density Parity- Check Codes within 0.0045 dB of the Shannon Limit. – In: IEEE Communications Letters, vol. 5, no. 2 (2001), pp. 58–60.