Kanalcodierung/Grundlegendes zu den Turbocodes: Unterschied zwischen den Versionen

Aus LNTwww
Wechseln zu:Navigation, Suche
 
(29 dazwischenliegende Versionen von 2 Benutzern werden nicht angezeigt)
Zeile 6: Zeile 6:
 
}}
 
}}
  
== Grundstruktur eines Turbocodes (1) ==
+
== Grundstruktur eines Turbocodes ==
 
<br>
 
<br>
Alle heute (2016) aktuellen Kommunikationssysteme wie UMTS (3. Mobilfunkgeneration) und LTE (4. Mobilfunkgeneration) verwenden das in [[Kanalcodierung/Soft%E2%80%93in_Soft%E2%80%93out_Decoder#Hard_Decision_vs._Soft_Decision_.281.29| Kapitel 4.1]] dargelegte Konzept der symbolweisen iterativen Decodierung. Dass dies so ist, steht unmittelbar mit der Erfindung der Turbocodes im Jahre 1993 durch C. Berrou, A. Glavieux und P. Thitimajshima in Zusammenhang, denn erst mit diesen Codes konnte man sich der Shannon&ndash;Grenze mit vertretbarem Decodieraufwand annähern.<br>
+
Alle heute (2017) aktuellen Kommunikationssysteme wie&nbsp; [[Beispiele_von_Nachrichtensystemen/Allgemeine_Beschreibung_von_UMTS#.23_.C3.9CBERBLICK_ZUM_VIERTEN_HAUPTKAPITEL_.23|UMTS]]&nbsp; (<i>Universal Mobile Telecommunications System</i> &nbsp; &rArr; &nbsp;  3. Mobilfunkgeneration) und&nbsp; [[Mobile_Kommunikation/Allgemeines_zum_Mobilfunkstandard_LTE#.23_.C3.9CBERSICHT_ZUM_VIERTEN_HAUPTKAPITEL_.23|LTE]]&nbsp; (<i>Long Term Evolution</i>&nbsp; &rArr; &nbsp; 4. Mobilfunkgeneration) verwenden das Konzept der&nbsp;  [[Kanalcodierung/Soft–in_Soft–out_Decoder#Symbolweise_Soft.E2.80.93in_Soft.E2.80.93out_Decodierung| symbolweisen iterativen Decodierung]]. Dass dies so ist, steht unmittelbar mit der Erfindung der&nbsp; ''Turbocodes''&nbsp; im Jahre 1993 durch&nbsp; [https://de.wikipedia.org/wiki/Claude_Berrou Claude Berrou],&nbsp; [https://de.wikipedia.org/wiki/Alain_Glavieux Alain Glavieux]&nbsp; und&nbsp; [https://scholar.google.com/citations?user=-UZolIAAAAAJ Punya Thitimajshima]&nbsp; in Zusammenhang, denn erst mit diesen Codes konnte man sich der Shannon&ndash;Grenze mit vertretbarem Decodieraufwand annähern.<br>
  
Turbocodes ergeben sich durch die parallele oder serielle Verkettung von Faltungscodes. Die Grafik zeigt die parallele Verkettung zweier Codes mit den Parametern $k = 1, \ n = 2$ &nbsp;&#8658;&nbsp; Rate $R = 1/2$.<br>
+
Turbocodes ergeben sich durch die parallele oder serielle Verkettung von Faltungscodes. Die Grafik zeigt die parallele Verkettung zweier Codes, jeweils mit den Parametern&nbsp; $k = 1, \ n = 2$ &nbsp; &#8658; &nbsp; Rate $R = 1/2$.<br>
  
[[Datei:P ID3034 KC T 4 3 S1a v1.png|center|frame|Parallele Verkettung zweier Rate–$1/2$–Codes|class=fit]]<br>
+
[[Datei:P ID3034 KC T 4 3 S1a v1.png|center|frame|Parallele Verkettung zweier Rate–$1/2$–Codes|class=fit]]
  
 
In dieser Darstellung bezeichnet:
 
In dieser Darstellung bezeichnet:
* $u$ das aktuell betrachtete Bit der Informationssequenz $\underline{u}$,<br>
+
* $u$&nbsp; das aktuell betrachtete Bit der Informationssequenz&nbsp; $\underline{u}$,<br>
  
* $x_{i,j}$ das aktuell betrachtete Bit am Ausgang $j$ von Coder $i$ (mit $1 &#8804; i &#8804; 2, \ 1 &#8804; j &#8804; 2)$,<br>
+
* $x_{i,\hspace{0.03cm}j}$&nbsp; das aktuell betrachtete Bit am Ausgang&nbsp; $j$&nbsp; von Coder&nbsp; $i$&nbsp; $($mit&nbsp; $1 &#8804; i &#8804; 2, \ 1 &#8804; j &#8804; 2)$,<br>
  
* $\underline{X} = (x_{1,1}, \ x_{1,2}, \ x_{2,1}, \ x_{2,2})$ das Codewort für das aktuelle Informationsbit $u$.<br><br>
+
* $\underline{X} = (x_{1,\hspace{0.03cm}1}, \ x_{1,\hspace{0.03cm}2}, \ x_{2,\hspace{0.03cm}1}, \ x_{2,\hspace{0.03cm}2})$&nbsp; das Codewort für das aktuelle Informationsbit&nbsp; $u$.<br><br>
  
Die resultierende Rate des verketteten Codiersystems ist somit $R = 1/4$.<br>
+
Die resultierende Rate des verketteten Codiersystems ist somit&nbsp; $R = 1/4$.<br>
  
 
Verwendet man systematische Komponentencodes, so ergibt sich das folgende Modell:<br>
 
Verwendet man systematische Komponentencodes, so ergibt sich das folgende Modell:<br>
  
[[Datei:P ID3035 KC T 4 3 S1b v1.png|center|frame|Rate–1/3–Turbocodierer (parallele Verkettung zweier Rate–1/2–Faltungscodes) |class=fit]]<br>
+
[[Datei:P ID3035 KC T 4 3 S1b v1.png|center|frame|Rate–1/3–Turbocodierer (parallele Verkettung zweier Rate–$1/2$–Faltungscodes) |class=fit]]
  
 
Die Modifikationen gegenüber der oberen Grafik lassen sich wie folgt begründen:
 
Die Modifikationen gegenüber der oberen Grafik lassen sich wie folgt begründen:
*Bei systematischen Codes $C_1$ und $C_2$ ist sowohl $x_{1,1} = u$ als auch $x_{2,1} = u$. Deshalb kann man auf die Übertragung eines redundanten Bits (zum Beispiel $x_{2,2}$) verzichten.
+
*Bei systematischen Codes&nbsp; $C_1$&nbsp; und&nbsp; $C_2$&nbsp; ist sowohl&nbsp; $x_{1,\hspace{0.03cm}1} = u$&nbsp; als auch&nbsp; $x_{2,\hspace{0.03cm}1} = u$. Deshalb kann man auf die Übertragung eines redundanten Bits&nbsp; $($zum Beispiel $x_{2,\hspace{0.03cm}2})$&nbsp; verzichten.
  
*Mit dieser Reduktion ergibt sich ein Rate&ndash;1/3&ndash;Turbocode mit den Parametern $k = 1$ und $n = 3$. Das Codewort lautet mit den Paritybits $p_1$ und $p_2$ von Coder 1 bzw. Coder 2:
+
*Mit dieser Reduktion ergibt sich ein Rate&ndash;$1/3$&ndash;Turbocode mit&nbsp; $k = 1$&nbsp; und&nbsp; $n = 3$. Das Codewort lautet mit den Paritybits&nbsp; $p_1$&nbsp; (Coder 1) und&nbsp; $p_2$&nbsp;  (Coder 2):
 +
:$$\underline{X} = \left (u, \ p_1, \ p_2 \right )\hspace{0.05cm}.$$
  
::<math>\underline{X} = \left (u, p_1, p_2 \right )\hspace{0.05cm}.</math>
 
  
Auf der nächsten Seite wird unser Turbocode&ndash;Modell nochmals geringfügig modifiziert.<br>
+
== Weitere Modifizierung der Turbocode&ndash;Grundstruktur ==
 
 
== Grundstruktur eines Turbocodes (2) ==
 
 
<br>
 
<br>
Im Folgenden gehen wir stets von einem noch weiter modifizierten Turbocoder&ndash;Modell aus:
+
Im Folgenden gehen wir stets von einem noch etwas weiter modifizierten Turbocoder&ndash;Modell aus:
*Wie es für die Beschreibung von Faltungscodes erforderlich ist,  liegt nun am Eingang anstelle des isolierten Informationsbits $u$ die Informationssequenz $\underline{u} = (u_1, \ u_2, \ ... , \ u_i , \ ...)$ an.<br>
+
*Wie es für die Beschreibung von Faltungscodes erforderlich ist,  liegt nun am Eingang anstelle des isolierten Informationsbits&nbsp; $u$&nbsp; die Informationssequenz&nbsp; $\underline{u} = (u_1, \ u_2, \ \text{...}\hspace{0.05cm} , \ u_i , \ \text{...}\hspace{0.05cm} )$&nbsp; an.<br>
  
*Die Codewortsequenz wird mit $\underline{x} = (\underline{X}_1, \underline{X}_2, \ ... , \ \underline{X}_i, \ ...)$ bezeichnet. Um Verwechslungen zu vermeiden, wurden vorne die Codeworte $\underline{X}_i = (u, \ p_1, \ p_2)$ mit Großbuchstaben eingeführt.<br>
+
*Die Codewortsequenz wird mit&nbsp; $\underline{x} = (\underline{X}_1, \underline{X}_2, \ \text{...}\hspace{0.05cm}  , \ \underline{X}_i, \ \text{...}\hspace{0.05cm} )$&nbsp; bezeichnet. Um Verwechslungen zu vermeiden, wurden vorne die Codeworte&nbsp; $\underline{X}_i = (u, \ p_1, \ p_2)$&nbsp; mit Großbuchstaben eingeführt.<br>
  
[[Datei:P ID3036 KC T 4 3 S1c v1.png|center|frame|Rate–1/3–Turbocodierer mit Interleaver|class=fit]]<br>
+
[[Datei:P ID3036 KC T 4 3 S1c v1.png|center|frame|Rate–$1/3$–Turbocodierer mit Interleaver|class=fit]]
  
*Die Coder $C_1$ und $C_2$ werden (gedanklich) als [[Stochastische_Signaltheorie/Digitale_Filter| Digitale Filter]] konzipiert und sind somit durch die [[Kanalcodierung/Algebraische_und_polynomische_Beschreibung#Anwendung_der_D.E2.80.93Transformation_auf_Rate.E2.80.931.2Fn.E2.80.93Faltungscoder_.282.29| Übertragungsfunktionen]] $G_1(D)$ und $G_2(D)$ darstellbar.<br>
+
*Die Coder&nbsp; $\mathcal{C}_1$&nbsp; und&nbsp; $\mathcal{C}_2$&nbsp; werden (zumindest gedanklich) als&nbsp; [[Stochastische_Signaltheorie/Digitale_Filter| Digitale Filter]]&nbsp; konzipiert und sind somit durch die&nbsp; [[Kanalcodierung/Algebraische_und_polynomische_Beschreibung#Anwendung_der_D.E2.80.93Transformation_auf_Rate.E2.80.931.2Fn.E2.80.93Faltungscoder| Übertragungsfunktionen]]&nbsp; $G_1(D)$&nbsp; und&nbsp; $G_2(D)$&nbsp; darstellbar.<br>
  
*Aus verschiedenen Gründen &nbsp;&#8658;&nbsp; siehe [[Kanalcodierung/Grundlegendes_zu_den_Turbocodes#Zweite_Voraussetzung_f.C3.BCr_Turbocodes:_Interleaving| übernächste Seite]] sollte die Eingangssequenz des zweiten Coders &nbsp;&#8658;&nbsp; $\underline{u}_{\pi}$ gegenüber der Sequenz $\underline{u}$ durch einen Interleaver $(\Pi)$ verwürfelt sein.<br>
+
*Aus verschiedenen Gründen &nbsp; &#8658; &nbsp; siehe&nbsp; [[Kanalcodierung/Grundlegendes_zu_den_Turbocodes#Zweite_Voraussetzung_f.C3.BCr_Turbocodes:_Interleaving| übernächste Seite]]&nbsp; sollte die Eingangssequenz des zweiten Coders &nbsp; &#8658; &nbsp; $\underline{u}_{\pi}$&nbsp; gegenüber der Sequenz&nbsp; $\underline{u}$&nbsp; durch einen Interleaver&nbsp; $(\Pi)$&nbsp; verwürfelt sein.<br>
  
*Somit spricht nichts dagegen, die beiden Coder gleich zu wählen: $G_1(D) = G_2(D) = G_3(D)$. Ohne Interleaver würde dies die Korrekturfähigkeit extrem einschränken.<br><br>
+
*Somit spricht nichts dagegen, beide Coder gleich zu wählen: &nbsp; $G_1(D) = G_2(D) = G(D)$. Ohne Interleaver würde die Korrekturfähigkeit extrem eingeschränkt sein.<br><br>
  
{{Beispiel}}''':''' Die Grafik zeigt die verschiedenen Sequenzen in angepassten Farben. Anzumerken ist:
+
{{GraueBox|TEXT= 
#&nbsp;&nbsp; Für $\underline{u}_{\pi}$  ist eine $3×4$&ndash;Interleaver&ndash;Matrix entsprechend Aufgabe Z4.8 berücksichtigt.
+
$\text{Beispiel 1:}$&nbsp; Die Grafik zeigt die verschiedenen Sequenzen in angepassten Farben. Anzumerken ist:
# &nbsp;&nbsp;<sub>&nbsp;</sub>Die Paritysequenzen ergeben sich gemäß $G_1(D) = G_2(D) = 1 + D^2$ &nbsp;&#8658;&nbsp; siehe Aufgabe A4.8.<br>
+
#&nbsp;&nbsp; Für&nbsp; $\underline{u}_{\pi}$&nbsp; ist eine&nbsp; $3×4$&ndash;Interleaver&ndash;Matrix entsprechend&nbsp; [[Aufgaben:Aufgabe_4.08Z:_Grundlegendes_zum_Interleaving|Aufgabe 4.8Z]]&nbsp; berücksichtigt.
 +
# &nbsp;&nbsp;<sub>&nbsp;</sub>Die Paritysequenzen ergeben sich gemäß&nbsp; $G_1(D) = G_2(D) = 1 + D^2$ &nbsp; &#8658; &nbsp; siehe&nbsp; [[Aufgaben:Aufgabe_4.08:_Wiederholung_zu_den_Faltungscodes|Aufgabe 4.8]].<br>
  
[[Datei:P ID3037 KC T 4 3 S1d v2.png|center|frame|Beispielhafte Sequenzen beim Rate–1/3–Turbocodierer|class=fit]]{{end}}<br>
+
[[Datei:P ID3037 KC T 4 3 S1d v2.png|center|frame|Beispielhafte Sequenzen beim Rate–$1/3$–Turbocodierer|class=fit]]}}
  
 
== Erste Voraussetzung für Turbocodes: Rekursive Komponentencodes ==
 
== Erste Voraussetzung für Turbocodes: Rekursive Komponentencodes ==
 
<br>
 
<br>
Nichtrekursive Übertragungsfunktionen zur Erzeugung der Paritysequenzen bewirken einen Turbocode mit unzureichend kleiner Minimaldistanz. Grund für diese Unzulänglichkeit ist die endliche Impulsantwort $\underline{g} = (1, \ g_2, \ ... , \ g_m, \ 0, \ 0, \ ...)$ mit $g_2, \ ... , \ g_m &#8712; \{0, 1\}$. Hierbei  bezeichnet $m$ das Codegedächtnis.<br>
+
Nichtrekursive Übertragungsfunktionen zur Erzeugung der Paritysequenzen bewirken einen Turbocode mit unzureichend kleiner Minimaldistanz. Grund für diese Unzulänglichkeit ist die endliche Impulsantwort&nbsp; $\underline{g} = (1, \ g_2, \ \text{...}\hspace{0.05cm}  , \ g_m, \ 0, \ 0, \ \text{...}\hspace{0.05cm} )$&nbsp; mit&nbsp; $g_2, \ \text{...}\hspace{0.05cm}  , \ g_m &#8712; \{0, 1\}$. Hierbei  bezeichnet&nbsp; $m$&nbsp; das Codegedächtnis.<br>
 +
 
 +
Die Grafik zeigt das Zustandsübergangsdiagramm für das Beispiel&nbsp; $\mathbf{G}(D) = \big [1, \ 1 + D^2 \big ]$. Die Übergänge sind mit &bdquo;$u_i\hspace{0.05cm}|\hspace{0.05cm}u_i p_i$&rdquo; beschriftet.
 +
*Die Abfolge&nbsp; $S_0 &#8594; S_1 &#8594; S_2 &#8594; S_0 &#8594; S_0 &#8594; S_0 &#8594; \ \text{...}\hspace{0.05cm} \ $&nbsp; führt bezüglich des Eingangs zur Informationssequenz&nbsp; $\underline{u} = (1, 0, 0, 0, 0, \ \text{...}\hspace{0.05cm})$&nbsp;
 +
*und bezüglich des jeweils zweiten Codesymbols zur Paritysequenz &nbsp; $\underline{p} = (1, 0, 1, 0, 0, \ \text{...}\hspace{0.05cm})$&nbsp; &nbsp; &#8658; &nbsp;  identisch mit der Impulsantwort&nbsp; $\underline{g}$ &nbsp; &#8658; &nbsp; Gedächtnis $m = 2$.<br>
 +
 
  
Die Grafik zeigt das Zustandsübergangsdiagramm für das Beispiel $\mathbf{G}(D) = [1, \ 1 + D^2]$. Die Übergänge sind mit &bdquo;$u_i|u_i p_i$&rdquo; beschriftet. Die Abfolge $S_0 &#8594; S_1 &#8594; S_2 &#8594; S_0 &#8594; S_0 &#8594; S_0 &#8594; \ ... \ $ führt bezüglich des Eingangs zur Informationssequenz $\underline{u} = (1, 0, 0, 0, 0, \ ...)$ und bezüglich des jeweils zweiten Codesymbols zur Paritysequenz &nbsp; $\underline{p} = (1, 0, 1, 0, 0, \ ...)$ &nbsp;&#8658;&nbsp;  identisch mit der Impulsantwort $\underline{g}$ &nbsp;&#8658;&nbsp; Gedächtnis $m = 2$.<br>
+
[[Datei:P ID3044 KC T 4 3 S2a v2.png|center|frame|Nichtrekursiver systematischer Turbocode und Zustandsübergangsdiagramm|class=fit]]
  
[[Datei:P ID3044 KC T 4 3 S2a v2.png|center|frame|Nichtrekursiver Turbocode und Zustandsübergangsdiagramm|class=fit]]<br>
+
Die untere Grafik gilt für einen so genannten&nbsp; '''RSC&ndash;Code'''&nbsp;  (<i>Recursive Systematic Convolutional</i>) entsprechend&nbsp; $\mathbf{G}(D) = \big [1, \ (1+ D^2)/(1 + D + D^2)\big ]$.
 +
*Hier führt die Folge&nbsp; $S_0 &#8594; S_1 &#8594; S_3 &#8594; S_2 &#8594; S_1 &#8594; S_3 &#8594; S_2 &#8594; \ \text{...}\hspace{0.05cm} \ $&nbsp; zur Impulsantwort&nbsp; $\underline{g} = (1, 1, 1, 0, 1, 1, 0, 1, 1, \ \text{...}\hspace{0.05cm})$.
 +
*Diese Impulsantwort setzt sich aufgrund der Schleife&nbsp; $S_1 &#8594; S_3 &#8594; S_2 &#8594; S_1$ bis ins Unendliche fort. Dies ermöglicht bzw. erleichtert die iterative Decodierung.<br>
  
Die untere Grafik gilt für einen sog. RSC&ndash;Code (<i>Recursive Systematic Convolutional</i>) entsprechend $\mathbf{G}(D) = [1, \ (1+ D^2)/(1 + D + D^2)]$. Hier führt die Folge $S_0 &#8594; S_1 &#8594; S_3 &#8594; S_2 &#8594; S_1 &#8594; S_3 &#8594; S_2 &#8594; \ ... \ $ zur Impulsantwort $\underline{g} = (1, 1, 1, 0, 1, 1, 0, 1, 1, \ ...)$. Diese Impulsantwort setzt sich aufgrund der Schleife $S_1 &#8594; S_3 &#8594; S_2 &#8594; S_1$ bis ins Unendliche fort. Dies ermöglicht bzw. erleichtert die iterative Decodierung.<br>
 
  
[[Datei:P ID3045 KC T 4 3 S2b v2.png|center|frame|RSC-Turbocode und Zustandsübergangsdiagramm|class=fit]]<br>
+
[[Datei:P ID3045 KC T 4 3 S2b v2.png|center|frame|Nichtrekursiver systematischer Turbocode und Zustandsübergangsdiagramm|class=fit]]
  
Mehr Details zu den Beispielen auf dieser Seite finden Sie in Aufgabe A4.8 und Aufgabe A4.9.<br>
+
Mehr Details zu den Beispielen auf dieser Seite finden Sie in der&nbsp; [[Aufgaben:Aufgabe_4.08Z:_Grundlegendes_zum_Interleaving|Aufgabe 4.8]]&nbsp; und der&nbsp; [[Aufgaben:Aufgabe_4.09:_Recursive_Systematic_Convolutional_Codes|Aufgabe 4.9]].<br>
  
 
== Zweite Voraussetzung für Turbocodes: Interleaving ==
 
== Zweite Voraussetzung für Turbocodes: Interleaving ==
 
<br>
 
<br>
Es ist offensichtlich, dass bei $G_1(D) = G_2(D)$ ein Interleaver $(\Pi)$ unerlässlich ist. Ein weiterer Grund ist, dass die Apriori&ndash;Information als unabhängig vorausgesetzt wird. Somit sollten benachbarte (und somit möglicherweise stark abhängige) Bits für den jeweils anderen Teilcode weit auseinander liegen.<br>
+
Es ist offensichtlich, dass bei&nbsp; $G_1(D) = G_2(D)$&nbsp; ein Interleaver&nbsp; $(\Pi)$&nbsp; unerlässlich ist. Ein weiterer Grund ist, dass die Apriori&ndash;Information als unabhängig vorausgesetzt wird. Somit sollten benachbarte (und somit möglicherweise stark abhängige) Bits für den jeweils anderen Teilcode weit auseinander liegen.<br>
  
Für jeden RSC&ndash;Code &nbsp;&#8658;&nbsp; unendliche Impulsantwort $\underline{g}$ &nbsp;&#8658;&nbsp; gebrochen&ndash;rationale Übertragungsfunktion $G(D)$ gibt es nämlich gewisse Eingangssequenzen $\underline{u}$, die zu sehr kurzen Paritysequenzen $\underline{p} = \underline{u} &#8727; \underline{g}$ mit geringem Hamming&ndash;Gewicht $w_{\rm H}(\underline{p})$ führen.  Eine solche Sequenz ist beispielsweise in der unteren Grafik auf der [[Kanalcodierung/Grundlegendes_zu_den_Turbocodes#Erste_Voraussetzung_f.C3.BCr_Turbocodes:_Rekursive_Komponentencodes| letzten Seite]] angegeben: &nbsp; $\underline{u} = (1, 1, 1, 0, 0, \ ...)$. Dann gilt für die Ausgangssequenz:
+
Für jeden RSC&ndash;Code &nbsp; &#8658; &nbsp; unendliche Impulsantwort&nbsp; $\underline{g}$ &nbsp; &#8658; &nbsp; gebrochen&ndash;rationale Übertragungsfunktion&nbsp; $G(D)$&nbsp; gibt es nämlich gewisse Eingangssequenzen&nbsp; $\underline{u}$, die zu sehr kurzen Paritysequenzen&nbsp; $\underline{p} = \underline{u} &#8727; \underline{g}$&nbsp; mit geringem Hamming&ndash;Gewicht&nbsp; $w_{\rm H}(\underline{p})$&nbsp; führen.
  
:<math>P(D) = U(D) \cdot G(D) = (1+D+D^2) \cdot \frac{1+D^2}{1+D+D^2}= 1+D^2</math>
+
Eine solche Sequenz ist beispielsweise in der unteren Grafik auf der&nbsp; [[Kanalcodierung/Grundlegendes_zu_den_Turbocodes#Erste_Voraussetzung_f.C3.BCr_Turbocodes:_Rekursive_Komponentencodes| letzten Seite]]&nbsp; angegeben: &nbsp; $\underline{u} = (1, 1, 1, 0, 0, \ \text{...}\hspace{0.05cm})$. Dann gilt für die Ausgangssequenz:
  
:<math>\Rightarrow\hspace{0.3cm}  \underline{p}= (\hspace{0.05cm}1\hspace{0.05cm},\hspace{0.05cm} 0\hspace{0.05cm},\hspace{0.05cm} 1\hspace{0.05cm},\hspace{0.05cm} 0\hspace{0.05cm},\hspace{0.05cm} 0\hspace{0.05cm},\hspace{0.05cm} ...\hspace{0.05cm})\hspace{0.05cm}. </math>
+
::<math>P(D) = U(D) \cdot G(D) = (1+D+D^2) \cdot \frac{1+D^2}{1+D+D^2}= 1+D^2\hspace{0.3cm}\Rightarrow\hspace{0.3cm}  \underline{p}= (\hspace{0.05cm}1\hspace{0.05cm},\hspace{0.05cm} 0\hspace{0.05cm},\hspace{0.05cm} 1\hspace{0.05cm},\hspace{0.05cm} 0\hspace{0.05cm},\hspace{0.05cm} 0\hspace{0.05cm},\hspace{0.05cm} \text{...}\hspace{0.05cm}\hspace{0.05cm})\hspace{0.05cm}. </math>
  
Durch Interleaving (deutsch: <i>Verwürfelung</i>) wird nun mit großer Wahrscheinlichkeit sichergestellt, dass diese Sequenz $\underline{u} = (1, 1, 1, 0, 0, \ ...)$ in eine Sequenz $\underline{u}_{\pi}$ gewandelt wird,
+
{{BlaueBox|TEXT= 
 +
$\text{Sinn und Zweck:}$&nbsp;
 +
Durch&nbsp; $\rm Interleaving$&nbsp; (deutsch: &nbsp; <i>Verwürfelung</i>) wird nun mit großer Wahrscheinlichkeit sichergestellt, dass diese Sequenz&nbsp; $\underline{u} = (1, 1, 1, 0, 0, \ \text{...}\hspace{0.05cm})$&nbsp; in eine Sequenz&nbsp; $\underline{u}_{\pi}$&nbsp; gewandelt wird,
 
*die zwar ebenfalls nur drei Einsen beinhaltet,<br>
 
*die zwar ebenfalls nur drei Einsen beinhaltet,<br>
  
*deren Ausgangssequenz aber durch ein großes Hamming&ndash;Gewicht $w_{\rm H}(\underline{p})$ gekennzeichnet ist.<br><br>
+
*deren Ausgangssequenz aber durch ein großes Hamming&ndash;Gewicht&nbsp; $w_{\rm H}(\underline{p})$&nbsp; gekennzeichnet ist.<br>
  
Somit gelingt es dem Decoder, solche &bdquo;Problemsequenzen&rdquo; iterativ aufzulösen.<br>
+
Somit gelingt es dem Decoder, solche &bdquo;Problemsequenzen&rdquo; iterativ aufzulösen.}}<br>
  
Zur Beschreibung der Interleaver verwendet man die Zuordnung $I_{\rm In} &#8594; I_{\rm Out}$. Diese Bezeichnungen stehen für die Indizes von Ausgangs&ndash; bzw. Eingangsfolge. Die Interleavergröße wird mit $I_{\rm max}$ benannt.<br>
+
[[Datei:P ID3048 KC T 4 3 S3a v5.png|right|frame|Zur Verdeutlichung von Block–Interleaving]]
  
[[Datei:P ID3048 KC T 4 3 S3a v5.png|right|frame|Zur Verdeutlichung von Block–Interleaving]]<br>
+
Zur folgenden Beschreibung der Interleaver verwendet wir die Zuordnung&nbsp; $I_{\rm In} &#8594; I_{\rm Out}$. Diese Bezeichnungen stehen für die Indizes von Ausgangs&ndash; bzw. Eingangsfolge. Die Interleavergröße wird mit&nbsp; $I_{\rm max}$&nbsp; benannt.<br>
  
 
Es gibt mehrere, grundsätzlich verschiedene Interleaver&ndash;Konzepte:<br>
 
Es gibt mehrere, grundsätzlich verschiedene Interleaver&ndash;Konzepte:<br>
  
[[Datei:P ID3050 KC T 4 3 S3b v5.png|left|frame|Zur Verdeutlichung von $S$–Random–Interleaving]]
+
Bei einem&nbsp; <b>Block&ndash;Interleaver</b>&nbsp; füllt man eine Matrix mit&nbsp; $S$&nbsp; Spalten und&nbsp; $Z$&nbsp; Zeilen spaltenweise und liest die Matrix zeilenweise aus. Damit wird ein Informationsblock mit&nbsp; $I_{\rm max} = S \cdot Z$&nbsp; Bit deterministisch verwürfelt.<br>
 
 
Bei einem <b>Block&ndash;Interleaver</b> füllt man eine Matrix mit $S$ Spalten und $Z$ Zeilen spaltenweise und liest die Matrix zeilenweise aus. Damit wird ein Informationsblock mit $I_{\rm max} = S \cdot Z \ \rm Bit$ deterministisch verwürfelt.<br>
 
 
 
Die Grafik verdeutlicht das Prinzip für $I_{\rm max} = 64$ &nbsp;&#8658;&nbsp; $1 &#8804; I_{\rm In} < 65$ und $1 &#8804; I_{\rm Out} < 65$. Die Reihenfolge der Ausgangsbits lautet dann:<br>
 
  
:$$1, 9, 17, 25, 33, 41, 49, 57, 2, 10, 18, \ ... , 48, 56, 64.$$
+
Die rechte Grafik verdeutlicht das Prinzip für&nbsp; $I_{\rm max} = 64$ &nbsp; &#8658; &nbsp; $1 &#8804; I_{\rm In} \le 64$&nbsp; und&nbsp; $1 &#8804; I_{\rm Out} \le 64$. Die Reihenfolge der Ausgangsbits lautet dann: &nbsp; $1, 9, 17, 25, 33, 41, 49, 57, 2, 10, 18, \ \text{...}\hspace{0.05cm} , 48, 56, 64.$
  
Mehr Informationen zum Block&ndash;Interleaving gibt es in Aufgabe Z4.8.<br>
+
Mehr Informationen zum Block&ndash;Interleaving gibt es in der&nbsp; [[Aufgaben:Aufgabe_4.08Z:_Grundlegendes_zum_Interleaving| Aufgabe 4.8Z]].<br>
  
Turbocodes verwenden oft den <span style="font-weight: bold;">$S$&ndash;Random&ndash;Interleaver</span>.  Dieser pseudozufällige Algorithmus mit dem Parameter &bdquo;$S$&rdquo; garantiert, dass zwei am Eingang weniger als $S$ auseinander liegende Indizes am Ausgang mindestens im Abstand $S + 1$ auftreten. Die linke Grafik zeigt die $S$&ndash;Random&ndash;Kennlinie $I_{\rm Out}(I_{\rm In})$ für $I_{\rm max} = 640$.<br>
+
[[Datei:P ID3050 KC T 4 3 S3b v5.png|left|frame|Zur Verdeutlichung von&nbsp; $S$–Random–Interleaving]]
 +
<br><br><br><br>Turbocodes verwenden oft den&nbsp; '''$S$&ndash;Random&ndash;Interleaver'''.  Dieser pseudozufällige Algorithmus mit dem Parameter &bdquo;$S$&rdquo; garantiert, dass zwei am Eingang weniger als&nbsp; $S$&nbsp; auseinander liegende Indizes am Ausgang mindestens im Abstand&nbsp; $S + 1$&nbsp; auftreten. Die linke Grafik zeigt die&nbsp; $S$&ndash;Random&ndash;Kennlinie&nbsp; $I_{\rm Out}(I_{\rm In})$&nbsp; für&nbsp; $I_{\rm max} = 640$.<br>
  
Auch dieser Algorithmus ist deterministisch, und man kann die Verwürfelung im Decoder rückgängig machen &#8658; <i>De&ndash;Interleaving</i>. Die Verteilung wirkt trotzdem &bdquo;zufälliger&rdquo; als bei Block&ndash;Interleaving.<br>
+
*Auch dieser Algorithmus ist deterministisch, und man kann die Verwürfelung im Decoder rückgängig machen &#8658; <i>De&ndash;Interleaving</i>.  
 +
*Die Verteilung wirkt trotzdem &bdquo;zufälliger&rdquo; als bei Block&ndash;Interleaving.
 +
<br clear=all>
  
 
== Symbolweise iterative Decodierung eines Turbocodes ==
 
== Symbolweise iterative Decodierung eines Turbocodes ==
 
<br>
 
<br>
Die Decodierung eines Turbocodes geschieht grundsätzlich wie in [[Kanalcodierung/Soft%E2%80%93in_Soft%E2%80%93out_Decoder#Grundstruktur_von_verketteten_Codiersystemen| Kapitel 4.1]] beschrieben. Aus der folgenden Grafik erkennt man aber einige nur für den Turbodecoder zutreffende Besonderheiten.<br>
+
Die Decodierung eines Turbocodes geschieht grundsätzlich wie im Abschnitt&nbsp; [[Kanalcodierung/Soft–in_Soft–out_Decoder#Symbolweise_Soft.E2.80.93in_Soft.E2.80.93out_Decodierung|Symbolweise Soft&ndash;in Soft&ndash;out_Decodierung]]&nbsp; beschrieben. Aus der folgenden Grafik erkennt man aber auch einige nur für den Turbodecoder zutreffende Besonderheiten.<br>
 
 
[[Datei:P ID3049 KC T 4 3 S4a v2.png|center|frame|Iterativer Turbodecoder für die Rate $R = 1/3$|class=fit]]<br>
 
  
Vorausgesetzt ist ein Rate&ndash;1/3&ndash;Turbocode entsprechend der Beschreibung auf der [[Kanalcodierung/Grundlegendes_zu_den_Turbocodes#Grundstruktur_eines_Turbocodes_.282.29| ersten Seite]] dieses Abschnitts. Auch die Farbgebung für die Informationssequenz $\underline{u}$ und die beiden Paritysequenzen $\underline{p}_1$ und $\underline{p}_2$ sind an die früheren Grafiken angepasst. Weiter ist zu bemerken:
+
[[Datei:P ID3049 KC T 4 3 S4a v2.png|center|frame|Iterativer Turbodecoder für die Rate&nbsp; $R = 1/3$|class=fit]]
*Die Empfangsvektoren $\underline{y}_0, \underline{y}_1$ und $\underline{y}_2$ sind reellwertig und liefern die jeweilige Soft&ndash;Information bezüglich der Sequenzen $\underline{u}$ (Information), $\underline{p}_1$ (Parity für Coder 1) und $\underline{p}_2$ (Parity für Coder 2).<br>
 
  
*Der Decoder 1 erhält die erforderliche intrinsische Information in Form der $L$&ndash;Werte $L_{\rm K, 0}$ (aus $\underline{y}_0$) und $L_{\rm K,1}$ (aus $\underline{y}_1$) über jedes einzelne Bit der Sequenzen $\underline{u}$ und $\underline{p}_1$.<br>
+
Vorausgesetzt ist ein Rate&ndash;$1/3$&ndash;Turbocode entsprechend der Beschreibung auf der&nbsp; [[Kanalcodierung/Grundlegendes_zu_den_Turbocodes#Grundstruktur_eines_Turbocodes| ersten Seite  dieses Abschnitts]]. Auch die Farbgebung für die Informationssequenz&nbsp; $\underline{u}$&nbsp; und die beiden Paritysequenzen&nbsp; $\underline{p}_1$&nbsp; und&nbsp; $\underline{p}_2$&nbsp; sind an die früheren Grafiken angepasst. Weiter ist zu bemerken:
 +
*Die Empfangsvektoren&nbsp; $\underline{y}_0, \underline{y}_1$&nbsp; und&nbsp; $\underline{y}_2$&nbsp; sind reellwertig und liefern die jeweilige Soft&ndash;Information bezüglich der Informationssequenz&nbsp; $\underline{u}$&nbsp; sowie der Sequenzen&nbsp; $\underline{p}_1$&nbsp; (Parity für Coder 1) und&nbsp; $\underline{p}_2$&nbsp; (Parity für Coder 2).<br>
  
*Beim zweiten Decoder ist auch die Verwürfelung der Informationssequenz $\underline{u}$ durch den Interleaver zu berücksichtigen. Die zu verarbeitenden $L$&ndash;Werte sind somit $\pi(L_{\rm K, 0}$ und $L_{\rm K, 2}$.<br>
+
*Der Decoder 1 erhält die erforderliche intrinsische Information in Form der&nbsp; $L$&ndash;Werte $L_{\rm K,\hspace{0.03cm} 0}$&nbsp; $($aus&nbsp; $\underline{y}_0)$&nbsp; und&nbsp; $L_{\rm K,\hspace{0.03cm}1}$ $($aus&nbsp; $\underline{y}_1)$&nbsp; über jedes einzelne Bit der Sequenzen&nbsp; $\underline{u}$&nbsp; und&nbsp; $\underline{p}_1$. Beim zweiten Decoder ist die Verwürfelung der Informationssequenz&nbsp; $\underline{u}$&nbsp; zu berücksichtigen. Die zu verarbeitenden&nbsp; $L$&ndash;Werte sind somit&nbsp; $\pi(L_{\rm K, \hspace{0.03cm}0})$&nbsp; und&nbsp; $L_{\rm K, \hspace{0.03cm}2}$.<br>
  
*Beim allgemeinen [[Kanalcodierung/Soft%E2%80%93in_Soft%E2%80%93out_Decoder#Grundstruktur_von_verketteten_Codiersystemen| SISO&ndash;Decoder]] am Ende von Kapitel 4.1 wurde der Informationsaustausch zwischen den beiden Komponentendecodern mit $\underline{L}_{\rm A, 2} = \underline{L}_{\rm E, 1}$ sowie $\underline{L}_{\rm A, 1} = \underline{L}_{\rm E, 2}$ angegeben. Ausgeschrieben auf Bitebene bedeuten diese Gleichungen mit $1 &#8804; i &#8804; n$:
+
*Beim allgemeinen&nbsp; [[Kanalcodierung/Soft–in_Soft–out_Decoder#Grundstruktur_von_verketteten_Codiersystemen| SISO&ndash;Decoder]]&nbsp; wurde der Informationsaustausch zwischen den beiden Komponentendecodern mit&nbsp; $\underline{L}_{\rm A, \hspace{0.03cm}2} = \underline{L}_{\rm E, \hspace{0.03cm}1}$&nbsp; sowie&nbsp; $\underline{L}_{\rm A, \hspace{0.03cm}1} = \underline{L}_{\rm E, \hspace{0.03cm}2}$&nbsp; angegeben. Ausgeschrieben auf Bitebene bedeuten diese Gleichungen mit&nbsp; $1 &#8804; i &#8804; n$:
  
::<math>L_{\rm A, \hspace{0.01cm}2}(i) = L_{\rm E, \hspace{0.01cm}1}(i)  
+
::<math>L_{\rm A, \hspace{0.03cm}2}(i) = L_{\rm E, \hspace{0.03cm}1}(i)  
 
\hspace{0.5cm}{\rm bzw.}\hspace{0.5cm}
 
\hspace{0.5cm}{\rm bzw.}\hspace{0.5cm}
L_{\rm A, \hspace{0.01cm}1}(i) = L_{\rm E, \hspace{0.01cm}2}(i) \hspace{0.03cm}.</math>
+
L_{\rm A, \hspace{0.03cm}1}(i) = L_{\rm E, \hspace{0.03cm}2}(i) \hspace{0.03cm}.</math>
  
*Beim Turbodecoder muss bei diesem Informationsaustausch auch der Interleaver berücksichtigt werden. Dann gilt wieder für $i = 1, \ ... , \ \pi$:
+
*Beim Turbodecoder muss bei diesem Informationsaustausch auch der Interleaver berücksichtigt werden. Dann gilt für&nbsp; $i = 1, \ \text{...}\hspace{0.05cm} , \ n$:
  
::<math>L_{\rm A, \hspace{0.01cm}2}\left ({\rm \pi}(i) \right ) = L_{\rm E, \hspace{0.01cm}1}(i)  
+
::<math>L_{\rm A, \hspace{0.03cm}2}\left ({\rm \pi}(i) \right ) = L_{\rm E, \hspace{0.03cm}1}(i)  
 
\hspace{0.5cm}{\rm bzw.}\hspace{0.5cm}
 
\hspace{0.5cm}{\rm bzw.}\hspace{0.5cm}
L_{\rm A, \hspace{0.01cm}1}(i) = L_{\rm E, \hspace{0.01cm}2}\left ({\rm \pi}(i) \right ) \hspace{0.05cm}.</math>
+
L_{\rm A, \hspace{0.03cm}1}(i) = L_{\rm E, \hspace{0.03cm}2}\left ({\rm \pi}(i) \right ) \hspace{0.05cm}.</math>
  
 
*Der Aposteriori&ndash;$L$&ndash;Wert wird in obigem Modell (willkürlich) vom Decoder 1 abgegeben. Dies lässt sich damit begründen, dass eine Iteration für einen zweifachen Informationsaustausch steht.<br>
 
*Der Aposteriori&ndash;$L$&ndash;Wert wird in obigem Modell (willkürlich) vom Decoder 1 abgegeben. Dies lässt sich damit begründen, dass eine Iteration für einen zweifachen Informationsaustausch steht.<br>
  
== Leistungsfähigkeit der Turbocodes (1) ==
+
== Leistungsfähigkeit der Turbocodes ==
 
<br>
 
<br>
Wir betrachten wieder wie auf den letzten Seiten den Rate&ndash;1/3&ndash;Turbocode
+
[[Datei:P ID3053 KC T 4 3 S5a v7.png|right|frame|Bit– und Blockfehlerwahrscheinlichkeit von Turbocodes beim AWGN&ndash;Kanal]]
*mit gleichen Filterfunktionen $G_1(D) = G_2(D) = (1 + D^2)/(1 + D + D^2)$ &nbsp;&#8658;&nbsp; Gedächtnis $m = 2$,<br>
+
Wir betrachten wie auf den letzten Seiten den Rate&ndash;$1/$3&ndash;Turbocode
 +
 
 +
*mit gleichen Filterfunktionen&nbsp; $G_1(D) = G_2(D) = (1 + D^2)/(1 + D + D^2)$ &nbsp; &#8658; &nbsp; Gedächtnis&nbsp; $m = 2$,<br>
 +
 
 +
*mit der Interleavergröße&nbsp; $K$; zunächst gelte&nbsp; $K = 10000,$<br>
 +
 
 +
*eine ausreichende Anzahl an Iterationen&nbsp; $(I = 20)$, vom Ergebnis her nahezu gleichzusetzen mit &bdquo;$I &#8594; &#8734;$&rdquo;.<br><br>
  
*mit der Interleavergröße $K$; zunächst gelte $K = 10000,$<br>
+
Die beiden RSC&ndash;Komponentencodes sind jeweils auf&nbsp; $K$&nbsp; Bit terminiert. Deshalb gruppieren wir
  
*eine ausreichende Anzahl an Iterationen $(I = 20)$, hier nahezu gleichzusetzen mit &bdquo;$I &#8594; &#8734;$&rdquo;.<br><br>
+
* die Informationssequenz&nbsp; $\underline{u}$&nbsp; zu Blöcken mit je&nbsp; $K$&nbsp; Informationsbits, und<br>
  
Die beiden RSC&ndash;Komponentencodes sind jeweils auf $K \ \rm Bit$ terminiert. Deshalb gruppieren wir
+
*die Codesequenz $\underline{x}$ zu Blöcken mit je&nbsp; $N = 3 \cdot K$&nbsp; Codebits.<br><br>
* die Informationssequenz $\underline{u}$ zu Blöcken mit je $K$ Informationsbits, und<br>
 
  
*die Codesequenz $\underline{x}$ zu Blöcken mit je $N = 3 \cdot K$ Codebits.<br><br>
+
Alle Ergebnisse gelten für den&nbsp; [[Kanalcodierung/Klassifizierung_von_Signalen#AWGN.E2.80.93Kanal_bei_bin.C3.A4rem_Eingang| AWGN&ndash;Kanal]]. Die Daten entstammen dem Vorlesungsskript&nbsp; [Liv15]<ref>Liva, G.: ''Channels Codes for Iterative Decoding.'' Vorlesungsmanuskript, Lehrstuhl für Nachrichtentechnik, TU München und DLR Oberpfaffenhofen, 2015.</ref>
  
Die Grafik zeigt als grüne Kurve in doppelt&ndash;logarithmischer Darstellung die Blockfehlerwahrscheinlichkeit &#8658; &nbsp; ${\rm Pr(Blockfehler)}$ beim [[Kanalcodierung/Klassifizierung_von_Signalen#AWGN.E2.80.93Kanal_bei_bin.C3.A4rem_Eingang| AWGN&ndash;Kanal]] in Abhängigkeit der Kenngröße $10 \cdot {\rm lg} \, (E_{\rm B}/N_0)$. Man erkennt:
+
Die Grafik zeigt als grüne Kurve die&nbsp; '''Blockfehlerwahrscheinlichkeit''' &nbsp; &#8658; &nbsp; ${\rm Pr(Blockfehler)}$&nbsp; in doppelt&ndash;logarithmischer Darstellung  in Abhängigkeit der AWGN&ndash;Kenngröße&nbsp; $10 \cdot {\rm lg} \, (E_{\rm B}/N_0)$. Man erkennt:
[[Datei:P ID3053 KC T 4 3 S5a v7.png|right|frame|Bit– und Blockfehlerwahrscheinlichkeit von Turbodecodes]]
 
*Die Daten entstammen dem Vorlesungsskript [Liv15]<ref>Liva, G.: ''Channels Codes for Iterative Decoding.'' Vorlesungsmanuskript, Lehrstuhl für Nachrichtentechnik, TU München und DLR Oberpfaffenhofen, 2015.</ref>. Die mit Kreuzen markierten Punkte ergaben sich aus den Gewichtsfunktionen des Turbocodes mit Hilfe der [[Kanalcodierung/Schranken_f%C3%BCr_die_Blockfehlerwahrscheinlichkeit#Union_Bound_der_Blockfehlerwahrscheinlichkeit| Union Bound]]. <br>
 
  
*Simulationsergebnisse aus [Liv15] sind in der Grafik durch Kreise markiert. Sie sind nahezu deckungsgleich mit den berechneten Werten.<br>
+
*Die mit Kreuzen markierten Punkte ergaben sich aus den Gewichtsfunktionen des Turbocodes mit Hilfe der&nbsp; [[Kanalcodierung/Schranken_f%C3%BCr_die_Blockfehlerwahrscheinlichkeit#Union_Bound_der_Blockfehlerwahrscheinlichkeit| &bdquo;Union Bound&rdquo;]]. Die Simulationsergebnisse &ndash; in der Grafik durch Kreise markiert &ndash;  sind nahezu deckungsgleich mit den analytisch berechneten Werten.<br>
  
*Die Union Bound ist nur eine obere Schranke, basierend auf ML&ndash;Decodierung. Der iterative Decoder ist suboptimal (also schlecher als ML). Diese beiden Effekte heben sich scheinbar auf.<br>
+
*Die &bdquo;Union Bound&rdquo; ist nur eine obere Schranke, basierend auf Maximum&ndash;Likelihood&ndash;Decodierung (&bdquo;ML&rdquo;). Der iterative Decoder ist suboptimal (also schlecher als &bdquo;ML&rdquo;). Diese beiden Effekte heben sich scheinbar nahezu auf.<br>
  
*Etwa bei $10 \cdot {\rm lg} \, (E_{\rm B}/N_0) = 1 \ \rm dB$ ist ein Knick im (grünen) Kurvenverlauf festzustellen, der mit der Steigungsänderung von ${\rm Pr(Bitfehler)}$ &nbsp;&#8658;&nbsp; blaue Kurve korrespondiert. Die Erklärung folgt unten.<br><br>
+
*Etwa bei&nbsp; $10 \cdot {\rm lg} \, (E_{\rm B}/N_0) = 1 \ \rm dB$&nbsp; ist ein Knick im (grünen) Kurvenverlauf festzustellen, der mit der Steigungsänderung von&nbsp; ${\rm Pr(Bitfehler)}$ &nbsp; &#8658; &nbsp; blaue Kurve korrespondiert. <br><br>
  
Die blauen Kreuze (Berechnung) und die blauen Kreise (Simulation) bezeichnen die Bitfehlerwahrscheinlichkeit. Als Vergleichskurve ist die (strichpunktierte) Kurve für uncodierte Übertragung eingezeichnet. Anzumerken ist:
+
Die blauen Kreuze (Berechnung) und die blauen Kreise (Simulation) bezeichnen die&nbsp; '''Bitfehlerwahrscheinlichkeit'''&nbsp; für die Interleavergröße&nbsp; $K = 10000$ . Als Vergleichskurve eingezeichnet ist die (strichpunktierte) Kurve für uncodierte Übertragung. Zu diesen blauen Kurven ist anzumerken:
*Bei kleinen Abszissenwerten ist der Kurvenabfall in der gewählten Darstellung nahezu linear und ausreichend steil. Für ${\rm Pr(Bitfehler)} = 10^{&ndash;5}$ benötigt man $10 \cdot {\rm lg} \, (E_{\rm B}/N_0) \approx \, &ndash;0.55 \ \rm dB$ ergibt, liegt unser Standard&ndash;Turbocode (mit Gedächtnis $m = 2$) nur etwa $1.35 \ \rm dB$ entfernt.<br>
+
*Bei kleinen Abszissenwerten ist der Kurvenabfall in der gewählten Darstellung nahezu linear und ausreichend steil. Zum Beispiel benötigt man für&nbsp; ${\rm Pr(Bitfehler)} = 10^{-5}$&nbsp; mindestens&nbsp; $10 \cdot {\rm lg} \, (E_{\rm B}/N_0) \approx \, 0.8 \ \rm dB$.<br>
  
*Im Vergleich zur [[Kanalcodierung/Informationstheoretische_Grenzen_der_Kanalcodierung#Kanalkapazit.C3.A4t_des_AWGN.E2.80.93Modells_.282.29| Shannon&ndash;Grenze]], die sich für die Coderate $R = 1/3$ zu $10 \cdot {\rm lg} \, (E_{\rm B}/N_0) \approx &ndash;0.55 \ \rm dB$ ergibt, liegt unser Standard&ndash;Turbocode (mit Gedächtnis $m = 2$) nur etwa $1.35 \ \rm dB$ entfernt.<br>
+
*Im Vergleich zur&nbsp; [[Kanalcodierung/Informationstheoretische_Grenzen_der_Kanalcodierung#Kanalkapazit.C3.A4t_des_AWGN.E2.80.93Modells_.282.29| Shannon&ndash;Grenze]], die sich für die Coderate&nbsp; $R = 1/3$&nbsp; zu&nbsp; $10 \cdot {\rm lg} \, (E_{\rm B}/N_0) \approx \, &ndash;0.55 \ \rm dB$&nbsp; ergibt, liegt unser Standard&ndash;Turbocode&nbsp; $($mit Gedächtnis&nbsp; $m = 2)$&nbsp; nur etwa&nbsp; $1.35 \ \rm dB$&nbsp; entfernt.<br>
  
*Ab $10 \cdot {\rm lg} \, (E_{\rm B}/N_0) \approx 0.5 \ \rm dB$ verläuft die Kurve flacher. Ab ca. $1.5 \ \rm dB$ ist der Verlauf wieder (fast) linear mit geringerer Steigung. Für ${\rm Pr(Bitfehler)} = 10^{&ndash;7}$ benötigt man etwa $10 \cdot {\rm lg} \, (E_{\rm B}/N_0) = 3 \ \rm dB$.<br><br>
+
*Ab&nbsp; $10 \cdot {\rm lg} \, (E_{\rm B}/N_0) \approx 0.5 \ \rm dB$&nbsp; verläuft die Kurve flacher. Ab ca.&nbsp; $1.5 \ \rm dB$&nbsp; ist der Verlauf wieder (nahezu) linear mit geringerer Steigung. Für&nbsp; ${\rm Pr(Bitfehler)} = 10^{-7}$&nbsp; benötigt man etwa&nbsp; $10 \cdot {\rm lg} \, (E_{\rm B}/N_0) = 3 \ \rm dB$.<br><br>
  
Die Bildbeschreibung wird auf der nächsten Seite fortgesetzt.<br>
+
Wir versuchen nun, den flacheren Abfall der Bitfehlerwahrscheinlichkeit bei größerem&nbsp; $E_{\rm B}/N_0$&nbsp; zu erklären. Man spricht von einem&nbsp; $\text{Error Floor}$:
  
== Leistungsfähigkeit der Turbocodes (2) ==
+
*Der Grund für dieses asymptotisch schlechtere Verhalten bei besserem Kanal&nbsp; $($im Beispiel: &nbsp; ab&nbsp; $10 \cdot {\rm lg} \, E_{\rm B}/N_0 \approx 2 \ \rm dB)$&nbsp; ist die Periode&nbsp; $P$&nbsp; der Coderimpulsantwort&nbsp; $\underline{g}$, wie auf der Seite&nbsp; [[Kanalcodierung/Grundlegendes_zu_den_Turbocodes#Zweite_Voraussetzung_f.C3.BCr_Turbocodes:_Interleaving|Interleaving]]&nbsp; nachgewiesen und in der&nbsp; [[Aufgaben:Aufgabe_4.10:_Turbocoder_für_UMTS_und_LTE|Aufgabe 4.10]]&nbsp; an Beispielen erläutert. <br>
<br>
 
Wir betrachten weiter die (blaue) Bitfehlerwahrscheinlichkeit für die Interleavergröße <i>K</i>&nbsp;=&nbsp;10000 und versuchen, den flacheren Abfall bei größerem <i>E</i><sub>B</sub>/<i>N</i><sub>0</sub> zu erklären. Man spricht von einem <i>Error Floor</i>.
 
[[Datei:P ID3056 KC T 4 3 S5b v4.png|rahmenlos|rechts|Bit– und Blockfehlerwahrscheinlichkeit von Turbodecodes]]
 
*Der Grund für dieses asymptotisch schlechtere Verhalten bei besserem Kanal (im Beispiel: ab ca. 10 &middot; lg <i>E</i><sub>B</sub>/<i>N</i><sub>0</sub> > 2 dB) ist die Periode <i>P</i> der Coderimpulsantwort <u><i>g</i></u>, wie auf der Seite [http://www.lntwww.de/Kanalcodierung/Grundlegendes_zu_den_Turbocodes#Zweite_Voraussetzung_f.C3.BCr_Turbocodes:_Interleaving Zweite Voraussetzung: Interleaving] nachgewiesen.<br>
 
  
*Im  Beispiel (<i>m</i> &#61; 2) ist die Periode <i>P</i> = 2<sup><i>m</i></sup> = 3. Dadurch ist für <u><i>u</i></u> = (1, 1, 1) &nbsp;&#8658;&nbsp; <i>w</i><sub>H</sub>(<u><i>u</i></u>) = 3 trotz unbegrenzter Impulsantwort <u><i>g</i></u> die Paritysequenz begrenzt: &nbsp; <u><i>p</i></u> = (1, 0, 1) &nbsp;&#8658;&nbsp; <i>w</i><sub>H</sub>(<u><i>p</i></u>) = 2.<br>
+
*Für&nbsp; $m = 2$&nbsp; ist die Periode $P = 2^m -1 = 3$. Dadurch ist für $\underline{u} = (1, 1, 1) &#8658; w_{\rm H}(\underline{u}) = 3$&nbsp; trotz unbegrenzter Impulsantwort&nbsp; $\underline{g}$&nbsp; die Paritysequenz begrenzt: &nbsp; $\underline{p} = (1, 0, 1)$ &nbsp; &#8658; &nbsp; $w_{\rm H}(\underline{p}) = 2$.<br>
  
*Die Sequenz <u><i>u</i></u> = (0, ..., 0, 1, 0, 0, 1, 0, ...) &nbsp;&#8658;&nbsp; <i>U</i>(<i>D</i>) = <i>D</i><sup><i>x</i></sup> &middot; (1 + <i>D</i><sup><i>P</i></sup>) führt ebenfalls zu einem kleinen Hamming&ndash;Gewicht <i>w</i><sub>H</sub>(<u><i>p</i></u>) am Ausgang, was den iterativen Decodierprozess erschwert.<br>
+
*Die Sequenz&nbsp; $\underline{u} = (0, \ \text{...}\hspace{0.05cm} , \ 0, \ 1, \ 0, \ 0, \ 1, \ 0, \ \text{...}\hspace{0.05cm})$ &nbsp; &#8658; &nbsp; $U(D) = D^x \cdot (1 + D^P)$&nbsp; führt ebenfalls zu einem kleinen Hamming&ndash;Gewicht&nbsp; $w_{\rm H}(\underline{p})$&nbsp; am Ausgang, was den iterativen Decodierprozess erschwert.<br>
  
*Eine gewisse Abhilfe schafft der Interleaver, der dafür sorgt, dass nicht die beiden Sequenzen <u><i>p</i></u><sub>1</sub> und <u><i>p</i></u><sub>2</sub> gleichzeitig durch sehr kleine Hamming&ndash;Gewichte <i>w</i><sub>H</sub>(<u><i>p</i></u><sub>1</sub>) und <i>w</i><sub>H</sub>(<u><i>p</i></u><sub>2</sub>) belastet sind.<br>
+
*Eine gewisse Abhilfe schafft der Interleaver, der dafür sorgt, dass nicht die beiden Sequenzen&nbsp; $\underline{p}_1$&nbsp; und&nbsp; $\underline{p}_2$&nbsp; gleichzeitig durch sehr kleine Hamming&ndash;Gewichte&nbsp; $w_{\rm H}(\underline{p}_1)$&nbsp; und&nbsp; $w_{\rm H}(\underline{p}_2)$&nbsp; belastet sind.<br>
  
*Aus der Grafik erkennt man, dass Pr(Bitfehler) umgekehrt proportional zur Interleavergröße <i>K</i> ist. Das heißt: Bei großem <i>K</i> funktioniert die Entspreizung ungünstiger Eingangssequenzen besser.<br>
+
*Aus der Grafik erkennt man auch, dass die Bitfehlerwahrscheinlichkeit umgekehrt proportional zur Interleavergröße&nbsp; $K$&nbsp; ist. Das heißt: &nbsp; Bei großem&nbsp; $K$&nbsp; funktioniert die Entspreizung ungünstiger Eingangssequenzen besser.<br>
  
*Allerdings gilt die Näherung <i>K</i> &middot; Pr(Bitfehler) = const. nur für größere <i>E</i><sub>B</sub>/<i>N</i><sub>0</sub>&ndash;Werte&nbsp;&#8658;&nbsp;kleinere Bitfehlerwahrscheinlichkeiten. Der oben beschriebene Effekt tritt zwar auch bei kleinerem <i>E</i><sub>B</sub>/<i>N</i><sub>0</sub> auf, doch sind dann die Auswirkungen auf die Bitfehlerwahrscheinlichkeit geringer.<br><br>
+
*Allerdings gilt die Näherung&nbsp; $K \cdot {\rm Pr(Bitfehler) = const.}$&nbsp; nur für größere&nbsp; $E_{\rm B}/N_0$&ndash;Werte &nbsp; &#8658; &nbsp; kleine Bitfehlerwahrscheinlichkeiten. Der beschriebene Effekt tritt zwar auch bei kleinerem&nbsp; $E_{\rm B}/N_0$&nbsp; auf, doch sind dann die Auswirkungen auf die Bitfehlerwahrscheinlichkeit geringer.<br><br>
  
Dagegen gilt der flachere Verlauf der Blockfehlerwahrscheinlichkeit (grüne Kurve weitgehend unabhängig von der Interleavergröße <i>K</i>, also sowohl für <i>K</i> = 1000 als auch für <i>K</i> = 10000. Im Bereich ab 10 &middot; lg <i>E</i><sub>B</sub>/<i>N</i><sub>0</sub> > 2 dB dominieren aufgrund der kleinen Bitfehlerwahrscheinlichkeiten (< 10<sup>&ndash;5</sup>) nämlich Einzelfehler, so dass hier die Näherung Pr(Blockfehler) &asymp; Pr(Bitfehler) &middot; <i>K</i> gültig ist.<br>
+
Dagegen gilt der flachere Verlauf der Blockfehlerwahrscheinlichkeit (grüne Kurve) weitgehend unabhängig von der Interleavergröße&nbsp; $K$, also sowohl für&nbsp; $K = 1000$&nbsp; als auch für&nbsp; $K = 10000$. Im Bereich ab&nbsp; $10 \cdot {\rm lg} \, E_{\rm B}/N_0 > 2 \ \rm dB$&nbsp; dominieren nämlich Einzelfehler, so dass hier die Näherung&nbsp; ${\rm Pr(Blockfehler)} \approx {\rm Pr(Bitfehler)} \cdot K$&nbsp; gültig ist.<br>
  
Die hier beispielhaft gezeigten Kurven für Bit&ndash; und Blockfehlerwahrscheinlichkeit gelten qualitativ auch für <i>m</i> > 2, zum Beispiel für den Turbocode von UMTS und LTE (jeweils <i>m</i> = 3), der in Aufgabe A4.10 analysiert wird. Es ergeben sich aber einige quantitative Unterschiede:
+
{{BlaueBox|TEXT= 
*Die Kurve verläuft bei  kleinem <i>E</i><sub>B</sub>/<i>N</i><sub>0</sub>  steiler und der Abstand von der Shannongrenze ist etwas geringer als im hier gezeigten Beispiel für <i>m</i> = 2.<br>
+
$\text{Fazit:}$&nbsp; Die beispielhaft gezeigten Kurven für Bitfehlerwahrscheinlichkeit und Blockfehlerwahrscheinlichkeit gelten qualitativ auch für&nbsp; $m > 2$, zum Beispiel für den Turbocode von UMTS und LTE&nbsp; $($jeweils mit&nbsp; $m = 3)$, der in der&nbsp; [[Aufgaben:Aufgabe_4.10:_Turbocoder_für_UMTS_und_LTE|Aufgabe 4.10]]&nbsp; analysiert wird. Es ergeben sich aber einige quantitative Unterschiede:
 +
*Die Kurve verläuft bei  kleinem&nbsp; $E_{\rm B}/N_0$&nbsp; steiler und der Abstand von der Shannongrenze ist etwas geringer als im hier gezeigten Beispiel für&nbsp; $m = 2$.<br>
  
*Auch für größeres <i>m</i> gibt es einen <i>Error Floor</i>. Der Knick in den dargestellten Kurven erfolgt aber später, also bei kleineren Fehlerwahrscheinlichkeiten.<br>
+
*Auch für größeres&nbsp; $m$&nbsp; gibt es einen <i>Error Floor</i>. Der Knick in den dargestellten Kurven erfolgt dann aber später, also bei kleineren Fehlerwahrscheinlichkeiten.}}<br>
  
 
== Seriell verkettete Turbocodes – SCCC ==
 
== Seriell verkettete Turbocodes – SCCC ==
 
<br>
 
<br>
Die bisher betrachteten Turbocodes werden manchmal auch als <i>Parallel Concatenated Convolutional Codes</i> (PCCC) bezeichnet. Einige Jahre nach Berrou's Erfindung wurden von anderen Autoren auch <i>Serial Concatenated Convolutional Codes</i> (SCCC)  entsprechend folgender Grafik vorgeschlagen.
+
Die bisher betrachteten Turbocodes werden manchmal auch als&nbsp; <i>Parallel Concatenated Convolutional Codes</i>&nbsp; (PCCC) bezeichnet.  
*Die Informationssequenz <u><i>u</i></u> liegt am äußeren Faltungscoder <i>C</i><sub>1</sub> an. Dessen Ausgangssequenz sei <u><i>c</i></u>.<br>
+
 
 +
Einige Jahre nach Berrou's Erfindung wurden von anderen Autoren auch&nbsp; <i>Serial Concatenated Convolutional Codes</i>&nbsp; (SCCC)  entsprechend der folgenden Grafik vorgeschlagen.
 +
*Die Informationssequenz&nbsp; $\underline{u}$&nbsp; liegt am äußeren Faltungscoder&nbsp; $\mathcal{C}_1$&nbsp; an. Dessen Ausgangssequenz sei&nbsp; $\underline{c}$.<br>
 +
 
 +
*Nach dem Interleaver&nbsp; $(\Pi)$&nbsp; folgt der innere Faltungscoder&nbsp; $\mathcal{C}_2$. Die Codesequenz wird hier&nbsp; $\underline{x}$&nbsp; genannt.<br>
  
*Nach dem Interleaver (&Pi;) folgt der innere Faltungscoder <i>C</i><sub>2</sub>. Die Codesequenz wird  <u><i>x</i></u> genannt.<br>
+
*Die resultierende Coderate ist&nbsp; $R = R_1 \cdot R_2$. Bei Rate&ndash;$1/2$&ndash;Komponentencodes ist&nbsp; $R = 1/4$.<br><br>
  
*Die resultierende Coderate ist <i>R</i> = <i>R</i><sub>1</sub> &middot; <i>R</i><sub>2</sub>. Bei Rate&ndash;1/2&ndash;Komponentencodes ist <i>R</i> = 1/4.<br><br>
+
[[Datei:P ID3058 KC T 4 3 S7a v1.png|center|frame|<i>Serial Concatenated Convolutional Codes</i> (SCCC): Coder und Decoder |class=fit]]
  
[[Datei:P ID3058 KC T 4 3 S7a v1.png|SCCC–Coder und –Decoder|class=fit]]<br>
+
Die untere Grafik zeigt den SCCC&ndash;Decoder und verdeutlicht die Verarbeitung der&nbsp; $L$&ndash;Werte und den Austausch der extrinsischen Information zwischen den beiden Komponentencoder:
 +
*Der innere Decoder&nbsp; (für den Code&nbsp; $\mathcal{C}_2)$&nbsp; erhält vom Kanal die intrinsische Information&nbsp; $\underline{L}_{\rm K}(\underline{x})$&nbsp; und vom äußeren Decoder (nach Interleaving) die Apriori&ndash;Information&nbsp; $\underline{L}_{\rm A}(\underline{w})$&nbsp; mit&nbsp; $\underline{w} = \pi(\underline{c})$. An den äußeren Decoder wird die extrinsische Information&nbsp; $\underline{L}_{\rm E}(\underline{w})$&nbsp; abgegeben.<br>
  
Die untere Grafik zeigt den SCCC&ndash;Decoder und verdeutlicht die Verarbeitung der <i>L</i>&ndash;Werte und den Austausch der extrinsischen Information zwischen den beiden Komponentencoder:
+
*Der äußere Decoder $($für&nbsp; $\mathcal{C}_1)$&nbsp; verarbeitet die Apriori&ndash;Information&nbsp; $\underline{L}_{\rm A}(\underline{c})$, also die extrinsische Information&nbsp; $\underline{L}_{\rm E}(\underline{w})$&nbsp; nach dem De&ndash;Interleaving. Er liefert die extrinsische Information&nbsp; $\underline{L}_{\rm E}(\underline{c})$.<br>
*Der innere Decoder (für den Code <i>C</i><sub>2</sub>) erhält vom Kanal die intrinsische Information <u><i>L</i></u><sub>K</sub>(<u><i>x</i></u>) und vom äußeren Decoder (nach Interleaving) die Apriori&ndash;Information <u><i>L</i></u><sub>A</sub>(<u><i>w</i></u>) mit <u><i>w</i></u> = &pi;(<u><i>c</i></u>). An den äußeren Decoder wird die extrinsische Information <u><i>L</i></u><sub>E</sub>(<u><i>w</i></u>) abgegeben.<br>
 
  
*Der äußere Decoder (für <i>C</i><sub>1</sub>) verarbeitet die Apriori&ndash;Information <u><i>L</i></u><sub>A</sub>(<u><i>c</i></u>), also die extrinsische  Information <u><i>L</i></u><sub>E</sub>(<u><i>w</i></u>) nach dem De&ndash;Interleaving. Er liefert die extrinsische Information <u><i>L</i></u><sub>E</sub>(<u><i>c</i></u>).<br>
+
*Nach hinreichend vielen Iterationen ergibt sich das  das gewünschte Decodierergebnis in Form der Aposteriori&ndash;$L$&ndash;Werte&nbsp; $\underline{L}_{\rm APP}(\underline{u})$&nbsp; der Informationssequenz&nbsp; $\underline{u}$.<br><br>
  
*Nach hinreichend vielen Iterationen ergibt sich das das gewünschte Decodierergebnis in Form der Aposteriori&ndash;<i>L</i>&ndash;Werte <u><i>L</i></u><sub>APP</sub>(<u><i>u</i></u>) der Informationssequenz <u><i>u</i></u>.<br><br>
+
{{BlaueBox|TEXT=  
 +
$\text{Fazit:}$&nbsp; Wichtig für <i>Serial Concatenated Convolutional Codes</i> (SCCC) ist, dass der innere Code&nbsp; $\mathcal{C}_2$&nbsp; rekursiv ist (also ein RSC&ndash;Code). Der äußere Code&nbsp; $\mathcal{C}_1$&nbsp; kann auch nichtrekursiv sein.
  
Wichtig für seriell verkettete Faltungscodes ist, dass der innere Code rekursiv ist (also ein RSC&ndash;Code). Der äußere Code <i>C</i><sub>1</sub> kann auch nichtrekursiv sein. Zur Leistungsfähigkeit solcher Codes ist anzumerken:
+
Zur Leistungsfähigkeit solcher Codes ist anzumerken:
*SCCCs sind bei großem <i>E</i><sub>B</sub>/<i>N</i><sub>0</sub> besser als PCCCs &nbsp;&#8658;&nbsp; niedrigerer <i>Error Floor</i>. Die Aussage gilt schon für SCCC&ndash;Komponentencodes mit Gedächtnis <i>m</i> = 2 (nur vier Trelliszustände), während bei PCCC das Gedächtnis <i>m</i> = 3 bzw. <i>m</i> = 4 (acht bzw. sechzehn Trelliszustände) sein sollte.<br>
+
*Ein SCCC ist bei großem&nbsp; $E_{\rm B}/N_0$&nbsp; oft besser als ein PCCC &nbsp;&#8658;&nbsp; niedrigerer <i>Error Floor</i>. Die Aussage gilt schon für SCCC&ndash;Komponentencodes mit Gedächtnis&nbsp; $m = 2$&nbsp; (nur vier Trelliszustände), während bei PCCC das Gedächtnis&nbsp; $m = 3$&nbsp; bzw.&nbsp; $m = 4$&nbsp; (acht bzw. sechzehn Trelliszustände) sein sollte.<br>
  
*Im unteren Bereich (kleines <i>E</i><sub>B</sub>/<i>N</i><sub>0</sub>) ist dagegen der beste seriell verkettete Faltungscode (SCCC) um einige Zehntel Dezibel schlechter als der vergleichbare Turbocode gemäß Berrou (PCCC). Entsprechend größer ist auch der Abstand von der Shannongrenze.<br><br>
+
*Im unteren Bereich $($kleines &nbsp;$E_{\rm B}/N_0)$&nbsp; ist dagegen der beste seriell verkettete Faltungscode (SCCC) um einige Zehntel Dezibel schlechter als der vergleichbare Turbocode gemäß Berrou (PCCC). Entsprechend größer ist auch der Abstand von der Shannongrenze.}}<br><br>
  
 
== Einige Anwendungsgebiete für Turbocodes ==
 
== Einige Anwendungsgebiete für Turbocodes ==
 
<br>
 
<br>
[[Datei:P ID3059 KC T 4 3 S7b v2.png|rahmenlos|rechts|Einige standardisierte Turbocodes im Vergleich zur Shannon–Grenze]]
+
[[Datei:P ID3059 KC T 4 3 S7b v2.png|right|frame|Einige standardisierte Turbocodes im Vergleich zur Shannon–Grenze]]
In fast allen neueren Kommunikationssystemen (nach 1993 standardisiert) werden Turbocodes eingesetzt. Die Grafik zeigt deren Leistungsfähigkeit beim AWGN&ndash;Kanal im Vergleich zur [http://www.lntwww.de/Kanalcodierung/Informationstheoretische_Grenzen_der_Kanalcodierung#Kanalkapazit.C3.A4t_des_AWGN.E2.80.93Modells_.282.29 Shannonschen Kanalkapazität] (blaue Kurve).<br>
+
In fast allen neueren Kommunikationssystemen werden Turbocodes eingesetzt. Die Grafik zeigt deren Leistungsfähigkeit beim AWGN&ndash;Kanal im Vergleich zur&nbsp; [[Kanalcodierung/Informationstheoretische_Grenzen_der_Kanalcodierung#Kanalkapazit.C3.A4t_des_AWGN.E2.80.93Modells| Shannonschen Kanalkapazität]]&nbsp; (blaue Kurve).<br>
 +
 
 +
Der  grün hinterlegte Bereich &bdquo;BPSK&rdquo; gibt die Shannongrenze für Nachrichtensysteme mit binärem Eingang an, mit der nach dem&nbsp; [[Kanalcodierung/Informationstheoretische_Grenzen_der_Kanalcodierung#Kanalcodierungstheorem_und_Kanalkapazit.C3.A4t| Kanalcodierungstheorem]]&nbsp; eine fehlerfreie Übertragung gerade noch möglich ist.<br>
 +
 
 +
Anzumerken ist, dass hier für die eingezeichneten Kanalcodes von standardisierten Systemen die Fehlerrate&nbsp; $10^{-5}$&nbsp; zugrunde liegt, während die informationstheoretischen Kapazitätskurven (Shannon, BPSK) für die Fehlerwahrscheinlichkeit&nbsp; $0$&nbsp; gelten.
 +
*Die blauen Rechtecke markieren die Turbocodes für UMTS. Diese sind Rate&ndash;$1/3$&ndash;Codes mit Gedächtnis&nbsp; $m = 3$. Die Leistungsfähigkeit hängt stark von der Interleavergröße ab. Mit&nbsp; $K = 6144$&nbsp; liegt dieser Code nur etwa&nbsp; $1 \ \rm dB$&nbsp; rechts von der Shannon&ndash;Grenze. LTE verwendet die gleichen Turbocodes. Geringfügige Unterschiede ergeben sich aufgrund des unterschiedlichen Interleavers.<br>
 +
 
 +
*Die roten Kreuze markieren die Turbocodes nach CCSDS (<i>Consultative Comittee for Space Data Systems</i>), entwickelt für den Einsatz bei Weltraummissionen. Diese Klasse geht von der festen Interleavergröße&nbsp; $K = 6920$&nbsp; aus und stellt Codes der Rate&nbsp; $1/6$,&nbsp; $1/4$,&nbsp; $1/3$&nbsp; und&nbsp; $1/2$&nbsp; bereit. Die niedrigsten Coderaten erlauben einen Betrieb mit&nbsp; $10 \cdot {\rm lg} \, (E_{\rm B}/N_0) \approx 0 \ \rm dB$.<br>
 +
 
 +
*Der grüne Kreis steht für einen sehr einfachen&nbsp; <i>Repeat&ndash;Accumulate</i>&nbsp; (RA) Code, einem seriell&ndash;verketteten Turbocode. Nachfolgend ist dessen Struktur skizziert: &nbsp; Der äußere Decoder verwendet einen&nbsp; [[Kanalcodierung/Beispiele_bin%C3%A4rer_Blockcodes#Wiederholungscodes_.281.29| Wiederholungscode]]&nbsp; (englisch:&nbsp;  <i>Repetition Code</i>), im gezeichneten Beispiel mit der Rate&nbsp; $R = 1/3$. Nach dem Interleaver folgt ein RSC&ndash;Code mit&nbsp; $G(D) = 1/(1 + D)$ &nbsp; &#8658; &nbsp; Gedächtnis&nbsp; $m = 1$. Bei systematischer Ausführung ist die Gesamtcoderate&nbsp; $R = 1/4$&nbsp; (zu jedem Informationsbit werden noch drei Paritybit hinzugefügt).
  
Der  grün hinterlegte Bereich &bdquo;BPSK&rdquo; gibt die Shannongrenze für Nachrichtensystemee mit binärem Eingang an, mit der nach dem [http://www.lntwww.de/Kanalcodierung/Informationstheoretische_Grenzen_der_Kanalcodierung#Kanalcodierungstheorem_und_Kanalkapazit.C3.A4t Kanalcodierungstheorem] eine fehlerfreie Übertragung gerade noch möglich ist.<br>
+
[[Datei:P ID3064 KC T 4 3 S7c v1.png|center|frame|<i>Repeat Accumulate</i> (RA) Code der Rate $1/4$|class=fit]]
  
Anzumerken ist, dass hier für die eingezeichneten Kanalcodes von standardisierten Systemen die Fehlerrate 10<sup>&ndash;5</sup> zugrunde liegt, während die informationstheoretischen Kapazitätskurven (Shannon, BPSK) für die Fehlerwahrscheinlichkeit 0 gelten.
+
Aus der Grafik rechts oben erkennt man, dass dieser einfache RA&ndash;Code überraschend gut ist. Mit der Interleavergröße&nbsp; $K = 300000$&nbsp; beträgt der Abstand von der Shannon&ndash;Grenze lediglich etwa &nbsp;$1.5 \ \rm dB$&nbsp; (grüner Punkt).
*Die blauen Rechtecke markieren die Turbocodes für UMTS. Diese sind Rate&ndash;1/3&ndash;Codes mit Gedächtnis <i>m</i> = 3. Die Leistungsfähigkeit hängt stark von der Interleavergröße ab. Mit <i>K</i> = 6144 liegt dieser Code nur etwa 1 dB rechts von der Shannon&ndash;Grenze. LTE verwendet die gleichen Turbocodes. Geringfügige Unterschiede ergeben sich aufgrund des unterschiedlichen Interleavers.<br>
 
  
*Die roten Kreuze markieren die Turbocodes nach CCSDS (<i>Consultative Comittee for Space Data Systems</i>), entwickelt für den Einsatz bei fernen Weltraummissionen. Diese Klasse geht von der einheitlichen Interleavergröße <i>K</i> = 6920 aus und stellt Codes der Rate 1/6, 1/4, 1/3 und  1/2 zur Verfügung. Die niedrigsten Coderaten erlauben einen Betrieb mit 10 &middot; lg (<i>E</i><sub>B</sub>/<i>N</i><sub>0</sub>) &asymp; 0 dB.<br>
+
Ähnliche <i>Repeat Accumulate Codes</i> sind für den Standard <i>DVB Return Channel Terrestrial</i> (RCS) sowie für den WiMax&ndash;Standard (IEEE 802.16) vorgesehen.
  
*Der grüne Kreis steht für einen sehr einfachen <i>Repeat&ndash;Accumulate</i> (RA) Code, einem seriell&ndash;verketteten Turbocode. Der äußere Decoder verwendet einen [http://www.lntwww.de/Kanalcodierung/Beispiele_bin%C3%A4rer_Blockcodes#Wiederholungscodes_.281.29 Wiederholungscode] (englisch:  <i>Repetition Code</i>), im gezeichneten Beispiel mit der Rate <i>R</i> = 1/3. Nach dem Interleaver folgt ein RSC&ndash;Code mit <i>G</i>(<i>D</i>) = 1/(1 + <i>D</i>) &nbsp;&#8658;&nbsp; Gedächtnis <i>m</i> = 1. Bei systematischer Ausführung ist die Gesamtcoderate <i>R</i> = 1/4 (zu jedem Informationsbit noch drei Paritybits). Aus der oberen Grafik erkennt man, dass dieser einfache RA&ndash;Code überraschend gut ist. Mit der Interleavergröße <i>K</i> = 300000 beträgt der Abstand von der Shannon&ndash;Grenze lediglich ca. 1.5 dB.<br>
 
  
[[Datei:P ID3064 KC T 4 3 S7c v1.png|<i>Repeat Accumulate</i> (RA) Code der Rate 1/4|class=fit]]<br>
 
  
In der oberen Grafik nicht eingetragen sind die Turbocodes für den Standard <i>DVB Return Channel Terrestrial</i> (RCS) sowie für den WiMax&ndash;Standard (IEEE 802.16), die ähnliche Turbocodes benutzen.<br>
 
  
== Aufgaben ==
+
== Aufgaben zum Kapitel ==
 
<br>
 
<br>
[[Aufgaben:4.8 Wiederholung zu den Faltungscodes|A4.8 Wiederholung zu den Faltungscodes]]
+
[[Aufgaben:Aufgabe_4.08:_Wiederholung_zu_den_Faltungscodes|Aufgabe 4.8: Wiederholung zu den Faltungscodes]]
  
[[Zusatzaufgaben:4.8 Grundlegendes zum Interleaving]]
+
[[Aufgaben:Aufgabe_4.08Z:_Grundlegendes_zum_Interleaving|Aufgabe 4.8Z: Grundlegendes zum Interleaving]]
  
[[Aufgaben:4.9 Wiederholung zu den RSC-Codes|A4.9 Wiederholung zu den RSC-Codes]]
+
[[Aufgaben:Aufgabe_4.09:_Recursive_Systematic_Convolutional_Codes|Aufgabe 4.9: Recursive Systematic Convolutional Codes]]
  
[[Aufgaben:4.10 UMTS/LTE–Turbocoder|A4.10 UMTS/LTE–Turbocoder]]
+
[[Aufgaben:Aufgabe_4.10:_Turbocoder_für_UMTS_und_LTE|Aufgabe 4.10: Turbocoder für UMTS und LTE]]
  
 
==Quellenverzeichnis==
 
==Quellenverzeichnis==

Aktuelle Version vom 9. Juli 2019, 17:25 Uhr

Grundstruktur eines Turbocodes


Alle heute (2017) aktuellen Kommunikationssysteme wie  UMTS  (Universal Mobile Telecommunications System   ⇒   3. Mobilfunkgeneration) und  LTE  (Long Term Evolution  ⇒   4. Mobilfunkgeneration) verwenden das Konzept der  symbolweisen iterativen Decodierung. Dass dies so ist, steht unmittelbar mit der Erfindung der  Turbocodes  im Jahre 1993 durch  Claude BerrouAlain Glavieux  und  Punya Thitimajshima  in Zusammenhang, denn erst mit diesen Codes konnte man sich der Shannon–Grenze mit vertretbarem Decodieraufwand annähern.

Turbocodes ergeben sich durch die parallele oder serielle Verkettung von Faltungscodes. Die Grafik zeigt die parallele Verkettung zweier Codes, jeweils mit den Parametern  $k = 1, \ n = 2$   ⇒   Rate $R = 1/2$.

Parallele Verkettung zweier Rate–$1/2$–Codes

In dieser Darstellung bezeichnet:

  • $u$  das aktuell betrachtete Bit der Informationssequenz  $\underline{u}$,
  • $x_{i,\hspace{0.03cm}j}$  das aktuell betrachtete Bit am Ausgang  $j$  von Coder  $i$  $($mit  $1 ≤ i ≤ 2, \ 1 ≤ j ≤ 2)$,
  • $\underline{X} = (x_{1,\hspace{0.03cm}1}, \ x_{1,\hspace{0.03cm}2}, \ x_{2,\hspace{0.03cm}1}, \ x_{2,\hspace{0.03cm}2})$  das Codewort für das aktuelle Informationsbit  $u$.

Die resultierende Rate des verketteten Codiersystems ist somit  $R = 1/4$.

Verwendet man systematische Komponentencodes, so ergibt sich das folgende Modell:

Rate–1/3–Turbocodierer (parallele Verkettung zweier Rate–$1/2$–Faltungscodes)

Die Modifikationen gegenüber der oberen Grafik lassen sich wie folgt begründen:

  • Bei systematischen Codes  $C_1$  und  $C_2$  ist sowohl  $x_{1,\hspace{0.03cm}1} = u$  als auch  $x_{2,\hspace{0.03cm}1} = u$. Deshalb kann man auf die Übertragung eines redundanten Bits  $($zum Beispiel $x_{2,\hspace{0.03cm}2})$  verzichten.
  • Mit dieser Reduktion ergibt sich ein Rate–$1/3$–Turbocode mit  $k = 1$  und  $n = 3$. Das Codewort lautet mit den Paritybits  $p_1$  (Coder 1) und  $p_2$  (Coder 2):
$$\underline{X} = \left (u, \ p_1, \ p_2 \right )\hspace{0.05cm}.$$


Weitere Modifizierung der Turbocode–Grundstruktur


Im Folgenden gehen wir stets von einem noch etwas weiter modifizierten Turbocoder–Modell aus:

  • Wie es für die Beschreibung von Faltungscodes erforderlich ist, liegt nun am Eingang anstelle des isolierten Informationsbits  $u$  die Informationssequenz  $\underline{u} = (u_1, \ u_2, \ \text{...}\hspace{0.05cm} , \ u_i , \ \text{...}\hspace{0.05cm} )$  an.
  • Die Codewortsequenz wird mit  $\underline{x} = (\underline{X}_1, \underline{X}_2, \ \text{...}\hspace{0.05cm} , \ \underline{X}_i, \ \text{...}\hspace{0.05cm} )$  bezeichnet. Um Verwechslungen zu vermeiden, wurden vorne die Codeworte  $\underline{X}_i = (u, \ p_1, \ p_2)$  mit Großbuchstaben eingeführt.
Rate–$1/3$–Turbocodierer mit Interleaver
  • Die Coder  $\mathcal{C}_1$  und  $\mathcal{C}_2$  werden (zumindest gedanklich) als  Digitale Filter  konzipiert und sind somit durch die  Übertragungsfunktionen  $G_1(D)$  und  $G_2(D)$  darstellbar.
  • Aus verschiedenen Gründen   ⇒   siehe  übernächste Seite  sollte die Eingangssequenz des zweiten Coders   ⇒   $\underline{u}_{\pi}$  gegenüber der Sequenz  $\underline{u}$  durch einen Interleaver  $(\Pi)$  verwürfelt sein.
  • Somit spricht nichts dagegen, beide Coder gleich zu wählen:   $G_1(D) = G_2(D) = G(D)$. Ohne Interleaver würde die Korrekturfähigkeit extrem eingeschränkt sein.

$\text{Beispiel 1:}$  Die Grafik zeigt die verschiedenen Sequenzen in angepassten Farben. Anzumerken ist:

  1.    Für  $\underline{u}_{\pi}$  ist eine  $3×4$–Interleaver–Matrix entsprechend  Aufgabe 4.8Z  berücksichtigt.
  2.    Die Paritysequenzen ergeben sich gemäß  $G_1(D) = G_2(D) = 1 + D^2$   ⇒   siehe  Aufgabe 4.8.
Beispielhafte Sequenzen beim Rate–$1/3$–Turbocodierer

Erste Voraussetzung für Turbocodes: Rekursive Komponentencodes


Nichtrekursive Übertragungsfunktionen zur Erzeugung der Paritysequenzen bewirken einen Turbocode mit unzureichend kleiner Minimaldistanz. Grund für diese Unzulänglichkeit ist die endliche Impulsantwort  $\underline{g} = (1, \ g_2, \ \text{...}\hspace{0.05cm} , \ g_m, \ 0, \ 0, \ \text{...}\hspace{0.05cm} )$  mit  $g_2, \ \text{...}\hspace{0.05cm} , \ g_m ∈ \{0, 1\}$. Hierbei bezeichnet  $m$  das Codegedächtnis.

Die Grafik zeigt das Zustandsübergangsdiagramm für das Beispiel  $\mathbf{G}(D) = \big [1, \ 1 + D^2 \big ]$. Die Übergänge sind mit „$u_i\hspace{0.05cm}|\hspace{0.05cm}u_i p_i$” beschriftet.

  • Die Abfolge  $S_0 → S_1 → S_2 → S_0 → S_0 → S_0 → \ \text{...}\hspace{0.05cm} \ $  führt bezüglich des Eingangs zur Informationssequenz  $\underline{u} = (1, 0, 0, 0, 0, \ \text{...}\hspace{0.05cm})$ 
  • und bezüglich des jeweils zweiten Codesymbols zur Paritysequenz   $\underline{p} = (1, 0, 1, 0, 0, \ \text{...}\hspace{0.05cm})$    ⇒   identisch mit der Impulsantwort  $\underline{g}$   ⇒   Gedächtnis $m = 2$.


Nichtrekursiver systematischer Turbocode und Zustandsübergangsdiagramm

Die untere Grafik gilt für einen so genannten  RSC–Code  (Recursive Systematic Convolutional) entsprechend  $\mathbf{G}(D) = \big [1, \ (1+ D^2)/(1 + D + D^2)\big ]$.

  • Hier führt die Folge  $S_0 → S_1 → S_3 → S_2 → S_1 → S_3 → S_2 → \ \text{...}\hspace{0.05cm} \ $  zur Impulsantwort  $\underline{g} = (1, 1, 1, 0, 1, 1, 0, 1, 1, \ \text{...}\hspace{0.05cm})$.
  • Diese Impulsantwort setzt sich aufgrund der Schleife  $S_1 → S_3 → S_2 → S_1$ bis ins Unendliche fort. Dies ermöglicht bzw. erleichtert die iterative Decodierung.


Nichtrekursiver systematischer Turbocode und Zustandsübergangsdiagramm

Mehr Details zu den Beispielen auf dieser Seite finden Sie in der  Aufgabe 4.8  und der  Aufgabe 4.9.

Zweite Voraussetzung für Turbocodes: Interleaving


Es ist offensichtlich, dass bei  $G_1(D) = G_2(D)$  ein Interleaver  $(\Pi)$  unerlässlich ist. Ein weiterer Grund ist, dass die Apriori–Information als unabhängig vorausgesetzt wird. Somit sollten benachbarte (und somit möglicherweise stark abhängige) Bits für den jeweils anderen Teilcode weit auseinander liegen.

Für jeden RSC–Code   ⇒   unendliche Impulsantwort  $\underline{g}$   ⇒   gebrochen–rationale Übertragungsfunktion  $G(D)$  gibt es nämlich gewisse Eingangssequenzen  $\underline{u}$, die zu sehr kurzen Paritysequenzen  $\underline{p} = \underline{u} ∗ \underline{g}$  mit geringem Hamming–Gewicht  $w_{\rm H}(\underline{p})$  führen.

Eine solche Sequenz ist beispielsweise in der unteren Grafik auf der  letzten Seite  angegeben:   $\underline{u} = (1, 1, 1, 0, 0, \ \text{...}\hspace{0.05cm})$. Dann gilt für die Ausgangssequenz:

\[P(D) = U(D) \cdot G(D) = (1+D+D^2) \cdot \frac{1+D^2}{1+D+D^2}= 1+D^2\hspace{0.3cm}\Rightarrow\hspace{0.3cm} \underline{p}= (\hspace{0.05cm}1\hspace{0.05cm},\hspace{0.05cm} 0\hspace{0.05cm},\hspace{0.05cm} 1\hspace{0.05cm},\hspace{0.05cm} 0\hspace{0.05cm},\hspace{0.05cm} 0\hspace{0.05cm},\hspace{0.05cm} \text{...}\hspace{0.05cm}\hspace{0.05cm})\hspace{0.05cm}. \]

$\text{Sinn und Zweck:}$  Durch  $\rm Interleaving$  (deutsch:   Verwürfelung) wird nun mit großer Wahrscheinlichkeit sichergestellt, dass diese Sequenz  $\underline{u} = (1, 1, 1, 0, 0, \ \text{...}\hspace{0.05cm})$  in eine Sequenz  $\underline{u}_{\pi}$  gewandelt wird,

  • die zwar ebenfalls nur drei Einsen beinhaltet,
  • deren Ausgangssequenz aber durch ein großes Hamming–Gewicht  $w_{\rm H}(\underline{p})$  gekennzeichnet ist.

Somit gelingt es dem Decoder, solche „Problemsequenzen” iterativ aufzulösen.


Zur Verdeutlichung von Block–Interleaving

Zur folgenden Beschreibung der Interleaver verwendet wir die Zuordnung  $I_{\rm In} → I_{\rm Out}$. Diese Bezeichnungen stehen für die Indizes von Ausgangs– bzw. Eingangsfolge. Die Interleavergröße wird mit  $I_{\rm max}$  benannt.

Es gibt mehrere, grundsätzlich verschiedene Interleaver–Konzepte:

Bei einem  Block–Interleaver  füllt man eine Matrix mit  $S$  Spalten und  $Z$  Zeilen spaltenweise und liest die Matrix zeilenweise aus. Damit wird ein Informationsblock mit  $I_{\rm max} = S \cdot Z$  Bit deterministisch verwürfelt.

Die rechte Grafik verdeutlicht das Prinzip für  $I_{\rm max} = 64$   ⇒   $1 ≤ I_{\rm In} \le 64$  und  $1 ≤ I_{\rm Out} \le 64$. Die Reihenfolge der Ausgangsbits lautet dann:   $1, 9, 17, 25, 33, 41, 49, 57, 2, 10, 18, \ \text{...}\hspace{0.05cm} , 48, 56, 64.$

Mehr Informationen zum Block–Interleaving gibt es in der  Aufgabe 4.8Z.

Zur Verdeutlichung von  $S$–Random–Interleaving





Turbocodes verwenden oft den  $S$–Random–Interleaver. Dieser pseudozufällige Algorithmus mit dem Parameter „$S$” garantiert, dass zwei am Eingang weniger als  $S$  auseinander liegende Indizes am Ausgang mindestens im Abstand  $S + 1$  auftreten. Die linke Grafik zeigt die  $S$–Random–Kennlinie  $I_{\rm Out}(I_{\rm In})$  für  $I_{\rm max} = 640$.

  • Auch dieser Algorithmus ist deterministisch, und man kann die Verwürfelung im Decoder rückgängig machen ⇒ De–Interleaving.
  • Die Verteilung wirkt trotzdem „zufälliger” als bei Block–Interleaving.


Symbolweise iterative Decodierung eines Turbocodes


Die Decodierung eines Turbocodes geschieht grundsätzlich wie im Abschnitt  Symbolweise Soft–in Soft–out_Decodierung  beschrieben. Aus der folgenden Grafik erkennt man aber auch einige nur für den Turbodecoder zutreffende Besonderheiten.

Iterativer Turbodecoder für die Rate  $R = 1/3$

Vorausgesetzt ist ein Rate–$1/3$–Turbocode entsprechend der Beschreibung auf der  ersten Seite dieses Abschnitts. Auch die Farbgebung für die Informationssequenz  $\underline{u}$  und die beiden Paritysequenzen  $\underline{p}_1$  und  $\underline{p}_2$  sind an die früheren Grafiken angepasst. Weiter ist zu bemerken:

  • Die Empfangsvektoren  $\underline{y}_0, \underline{y}_1$  und  $\underline{y}_2$  sind reellwertig und liefern die jeweilige Soft–Information bezüglich der Informationssequenz  $\underline{u}$  sowie der Sequenzen  $\underline{p}_1$  (Parity für Coder 1) und  $\underline{p}_2$  (Parity für Coder 2).
  • Der Decoder 1 erhält die erforderliche intrinsische Information in Form der  $L$–Werte $L_{\rm K,\hspace{0.03cm} 0}$  $($aus  $\underline{y}_0)$  und  $L_{\rm K,\hspace{0.03cm}1}$ $($aus  $\underline{y}_1)$  über jedes einzelne Bit der Sequenzen  $\underline{u}$  und  $\underline{p}_1$. Beim zweiten Decoder ist die Verwürfelung der Informationssequenz  $\underline{u}$  zu berücksichtigen. Die zu verarbeitenden  $L$–Werte sind somit  $\pi(L_{\rm K, \hspace{0.03cm}0})$  und  $L_{\rm K, \hspace{0.03cm}2}$.
  • Beim allgemeinen  SISO–Decoder  wurde der Informationsaustausch zwischen den beiden Komponentendecodern mit  $\underline{L}_{\rm A, \hspace{0.03cm}2} = \underline{L}_{\rm E, \hspace{0.03cm}1}$  sowie  $\underline{L}_{\rm A, \hspace{0.03cm}1} = \underline{L}_{\rm E, \hspace{0.03cm}2}$  angegeben. Ausgeschrieben auf Bitebene bedeuten diese Gleichungen mit  $1 ≤ i ≤ n$:
\[L_{\rm A, \hspace{0.03cm}2}(i) = L_{\rm E, \hspace{0.03cm}1}(i) \hspace{0.5cm}{\rm bzw.}\hspace{0.5cm} L_{\rm A, \hspace{0.03cm}1}(i) = L_{\rm E, \hspace{0.03cm}2}(i) \hspace{0.03cm}.\]
  • Beim Turbodecoder muss bei diesem Informationsaustausch auch der Interleaver berücksichtigt werden. Dann gilt für  $i = 1, \ \text{...}\hspace{0.05cm} , \ n$:
\[L_{\rm A, \hspace{0.03cm}2}\left ({\rm \pi}(i) \right ) = L_{\rm E, \hspace{0.03cm}1}(i) \hspace{0.5cm}{\rm bzw.}\hspace{0.5cm} L_{\rm A, \hspace{0.03cm}1}(i) = L_{\rm E, \hspace{0.03cm}2}\left ({\rm \pi}(i) \right ) \hspace{0.05cm}.\]
  • Der Aposteriori–$L$–Wert wird in obigem Modell (willkürlich) vom Decoder 1 abgegeben. Dies lässt sich damit begründen, dass eine Iteration für einen zweifachen Informationsaustausch steht.

Leistungsfähigkeit der Turbocodes


Bit– und Blockfehlerwahrscheinlichkeit von Turbocodes beim AWGN–Kanal

Wir betrachten wie auf den letzten Seiten den Rate–$1/$3–Turbocode

  • mit gleichen Filterfunktionen  $G_1(D) = G_2(D) = (1 + D^2)/(1 + D + D^2)$   ⇒   Gedächtnis  $m = 2$,
  • mit der Interleavergröße  $K$; zunächst gelte  $K = 10000,$
  • eine ausreichende Anzahl an Iterationen  $(I = 20)$, vom Ergebnis her nahezu gleichzusetzen mit „$I → ∞$”.

Die beiden RSC–Komponentencodes sind jeweils auf  $K$  Bit terminiert. Deshalb gruppieren wir

  • die Informationssequenz  $\underline{u}$  zu Blöcken mit je  $K$  Informationsbits, und
  • die Codesequenz $\underline{x}$ zu Blöcken mit je  $N = 3 \cdot K$  Codebits.

Alle Ergebnisse gelten für den  AWGN–Kanal. Die Daten entstammen dem Vorlesungsskript  [Liv15][1].

Die Grafik zeigt als grüne Kurve die  Blockfehlerwahrscheinlichkeit   ⇒   ${\rm Pr(Blockfehler)}$  in doppelt–logarithmischer Darstellung in Abhängigkeit der AWGN–Kenngröße  $10 \cdot {\rm lg} \, (E_{\rm B}/N_0)$. Man erkennt:

  • Die mit Kreuzen markierten Punkte ergaben sich aus den Gewichtsfunktionen des Turbocodes mit Hilfe der  „Union Bound”. Die Simulationsergebnisse – in der Grafik durch Kreise markiert – sind nahezu deckungsgleich mit den analytisch berechneten Werten.
  • Die „Union Bound” ist nur eine obere Schranke, basierend auf Maximum–Likelihood–Decodierung („ML”). Der iterative Decoder ist suboptimal (also schlecher als „ML”). Diese beiden Effekte heben sich scheinbar nahezu auf.
  • Etwa bei  $10 \cdot {\rm lg} \, (E_{\rm B}/N_0) = 1 \ \rm dB$  ist ein Knick im (grünen) Kurvenverlauf festzustellen, der mit der Steigungsänderung von  ${\rm Pr(Bitfehler)}$   ⇒   blaue Kurve korrespondiert.

Die blauen Kreuze (Berechnung) und die blauen Kreise (Simulation) bezeichnen die  Bitfehlerwahrscheinlichkeit  für die Interleavergröße  $K = 10000$ . Als Vergleichskurve eingezeichnet ist die (strichpunktierte) Kurve für uncodierte Übertragung. Zu diesen blauen Kurven ist anzumerken:

  • Bei kleinen Abszissenwerten ist der Kurvenabfall in der gewählten Darstellung nahezu linear und ausreichend steil. Zum Beispiel benötigt man für  ${\rm Pr(Bitfehler)} = 10^{-5}$  mindestens  $10 \cdot {\rm lg} \, (E_{\rm B}/N_0) \approx \, 0.8 \ \rm dB$.
  • Im Vergleich zur  Shannon–Grenze, die sich für die Coderate  $R = 1/3$  zu  $10 \cdot {\rm lg} \, (E_{\rm B}/N_0) \approx \, –0.55 \ \rm dB$  ergibt, liegt unser Standard–Turbocode  $($mit Gedächtnis  $m = 2)$  nur etwa  $1.35 \ \rm dB$  entfernt.
  • Ab  $10 \cdot {\rm lg} \, (E_{\rm B}/N_0) \approx 0.5 \ \rm dB$  verläuft die Kurve flacher. Ab ca.  $1.5 \ \rm dB$  ist der Verlauf wieder (nahezu) linear mit geringerer Steigung. Für  ${\rm Pr(Bitfehler)} = 10^{-7}$  benötigt man etwa  $10 \cdot {\rm lg} \, (E_{\rm B}/N_0) = 3 \ \rm dB$.

Wir versuchen nun, den flacheren Abfall der Bitfehlerwahrscheinlichkeit bei größerem  $E_{\rm B}/N_0$  zu erklären. Man spricht von einem  $\text{Error Floor}$:

  • Der Grund für dieses asymptotisch schlechtere Verhalten bei besserem Kanal  $($im Beispiel:   ab  $10 \cdot {\rm lg} \, E_{\rm B}/N_0 \approx 2 \ \rm dB)$  ist die Periode  $P$  der Coderimpulsantwort  $\underline{g}$, wie auf der Seite  Interleaving  nachgewiesen und in der  Aufgabe 4.10  an Beispielen erläutert.
  • Für  $m = 2$  ist die Periode $P = 2^m -1 = 3$. Dadurch ist für $\underline{u} = (1, 1, 1) ⇒ w_{\rm H}(\underline{u}) = 3$  trotz unbegrenzter Impulsantwort  $\underline{g}$  die Paritysequenz begrenzt:   $\underline{p} = (1, 0, 1)$   ⇒   $w_{\rm H}(\underline{p}) = 2$.
  • Die Sequenz  $\underline{u} = (0, \ \text{...}\hspace{0.05cm} , \ 0, \ 1, \ 0, \ 0, \ 1, \ 0, \ \text{...}\hspace{0.05cm})$   ⇒   $U(D) = D^x \cdot (1 + D^P)$  führt ebenfalls zu einem kleinen Hamming–Gewicht  $w_{\rm H}(\underline{p})$  am Ausgang, was den iterativen Decodierprozess erschwert.
  • Eine gewisse Abhilfe schafft der Interleaver, der dafür sorgt, dass nicht die beiden Sequenzen  $\underline{p}_1$  und  $\underline{p}_2$  gleichzeitig durch sehr kleine Hamming–Gewichte  $w_{\rm H}(\underline{p}_1)$  und  $w_{\rm H}(\underline{p}_2)$  belastet sind.
  • Aus der Grafik erkennt man auch, dass die Bitfehlerwahrscheinlichkeit umgekehrt proportional zur Interleavergröße  $K$  ist. Das heißt:   Bei großem  $K$  funktioniert die Entspreizung ungünstiger Eingangssequenzen besser.
  • Allerdings gilt die Näherung  $K \cdot {\rm Pr(Bitfehler) = const.}$  nur für größere  $E_{\rm B}/N_0$–Werte   ⇒   kleine Bitfehlerwahrscheinlichkeiten. Der beschriebene Effekt tritt zwar auch bei kleinerem  $E_{\rm B}/N_0$  auf, doch sind dann die Auswirkungen auf die Bitfehlerwahrscheinlichkeit geringer.

Dagegen gilt der flachere Verlauf der Blockfehlerwahrscheinlichkeit (grüne Kurve) weitgehend unabhängig von der Interleavergröße  $K$, also sowohl für  $K = 1000$  als auch für  $K = 10000$. Im Bereich ab  $10 \cdot {\rm lg} \, E_{\rm B}/N_0 > 2 \ \rm dB$  dominieren nämlich Einzelfehler, so dass hier die Näherung  ${\rm Pr(Blockfehler)} \approx {\rm Pr(Bitfehler)} \cdot K$  gültig ist.

$\text{Fazit:}$  Die beispielhaft gezeigten Kurven für Bitfehlerwahrscheinlichkeit und Blockfehlerwahrscheinlichkeit gelten qualitativ auch für  $m > 2$, zum Beispiel für den Turbocode von UMTS und LTE  $($jeweils mit  $m = 3)$, der in der  Aufgabe 4.10  analysiert wird. Es ergeben sich aber einige quantitative Unterschiede:

  • Die Kurve verläuft bei kleinem  $E_{\rm B}/N_0$  steiler und der Abstand von der Shannongrenze ist etwas geringer als im hier gezeigten Beispiel für  $m = 2$.
  • Auch für größeres  $m$  gibt es einen Error Floor. Der Knick in den dargestellten Kurven erfolgt dann aber später, also bei kleineren Fehlerwahrscheinlichkeiten.


Seriell verkettete Turbocodes – SCCC


Die bisher betrachteten Turbocodes werden manchmal auch als  Parallel Concatenated Convolutional Codes  (PCCC) bezeichnet.

Einige Jahre nach Berrou's Erfindung wurden von anderen Autoren auch  Serial Concatenated Convolutional Codes  (SCCC) entsprechend der folgenden Grafik vorgeschlagen.

  • Die Informationssequenz  $\underline{u}$  liegt am äußeren Faltungscoder  $\mathcal{C}_1$  an. Dessen Ausgangssequenz sei  $\underline{c}$.
  • Nach dem Interleaver  $(\Pi)$  folgt der innere Faltungscoder  $\mathcal{C}_2$. Die Codesequenz wird hier  $\underline{x}$  genannt.
  • Die resultierende Coderate ist  $R = R_1 \cdot R_2$. Bei Rate–$1/2$–Komponentencodes ist  $R = 1/4$.

Serial Concatenated Convolutional Codes (SCCC): Coder und Decoder

Die untere Grafik zeigt den SCCC–Decoder und verdeutlicht die Verarbeitung der  $L$–Werte und den Austausch der extrinsischen Information zwischen den beiden Komponentencoder:

  • Der innere Decoder  (für den Code  $\mathcal{C}_2)$  erhält vom Kanal die intrinsische Information  $\underline{L}_{\rm K}(\underline{x})$  und vom äußeren Decoder (nach Interleaving) die Apriori–Information  $\underline{L}_{\rm A}(\underline{w})$  mit  $\underline{w} = \pi(\underline{c})$. An den äußeren Decoder wird die extrinsische Information  $\underline{L}_{\rm E}(\underline{w})$  abgegeben.
  • Der äußere Decoder $($für  $\mathcal{C}_1)$  verarbeitet die Apriori–Information  $\underline{L}_{\rm A}(\underline{c})$, also die extrinsische Information  $\underline{L}_{\rm E}(\underline{w})$  nach dem De–Interleaving. Er liefert die extrinsische Information  $\underline{L}_{\rm E}(\underline{c})$.
  • Nach hinreichend vielen Iterationen ergibt sich das das gewünschte Decodierergebnis in Form der Aposteriori–$L$–Werte  $\underline{L}_{\rm APP}(\underline{u})$  der Informationssequenz  $\underline{u}$.

$\text{Fazit:}$  Wichtig für Serial Concatenated Convolutional Codes (SCCC) ist, dass der innere Code  $\mathcal{C}_2$  rekursiv ist (also ein RSC–Code). Der äußere Code  $\mathcal{C}_1$  kann auch nichtrekursiv sein.

Zur Leistungsfähigkeit solcher Codes ist anzumerken:

  • Ein SCCC ist bei großem  $E_{\rm B}/N_0$  oft besser als ein PCCC  ⇒  niedrigerer Error Floor. Die Aussage gilt schon für SCCC–Komponentencodes mit Gedächtnis  $m = 2$  (nur vier Trelliszustände), während bei PCCC das Gedächtnis  $m = 3$  bzw.  $m = 4$  (acht bzw. sechzehn Trelliszustände) sein sollte.
  • Im unteren Bereich $($kleines  $E_{\rm B}/N_0)$  ist dagegen der beste seriell verkettete Faltungscode (SCCC) um einige Zehntel Dezibel schlechter als der vergleichbare Turbocode gemäß Berrou (PCCC). Entsprechend größer ist auch der Abstand von der Shannongrenze.



Einige Anwendungsgebiete für Turbocodes


Einige standardisierte Turbocodes im Vergleich zur Shannon–Grenze

In fast allen neueren Kommunikationssystemen werden Turbocodes eingesetzt. Die Grafik zeigt deren Leistungsfähigkeit beim AWGN–Kanal im Vergleich zur  Shannonschen Kanalkapazität  (blaue Kurve).

Der grün hinterlegte Bereich „BPSK” gibt die Shannongrenze für Nachrichtensysteme mit binärem Eingang an, mit der nach dem  Kanalcodierungstheorem  eine fehlerfreie Übertragung gerade noch möglich ist.

Anzumerken ist, dass hier für die eingezeichneten Kanalcodes von standardisierten Systemen die Fehlerrate  $10^{-5}$  zugrunde liegt, während die informationstheoretischen Kapazitätskurven (Shannon, BPSK) für die Fehlerwahrscheinlichkeit  $0$  gelten.

  • Die blauen Rechtecke markieren die Turbocodes für UMTS. Diese sind Rate–$1/3$–Codes mit Gedächtnis  $m = 3$. Die Leistungsfähigkeit hängt stark von der Interleavergröße ab. Mit  $K = 6144$  liegt dieser Code nur etwa  $1 \ \rm dB$  rechts von der Shannon–Grenze. LTE verwendet die gleichen Turbocodes. Geringfügige Unterschiede ergeben sich aufgrund des unterschiedlichen Interleavers.
  • Die roten Kreuze markieren die Turbocodes nach CCSDS (Consultative Comittee for Space Data Systems), entwickelt für den Einsatz bei Weltraummissionen. Diese Klasse geht von der festen Interleavergröße  $K = 6920$  aus und stellt Codes der Rate  $1/6$,  $1/4$,  $1/3$  und  $1/2$  bereit. Die niedrigsten Coderaten erlauben einen Betrieb mit  $10 \cdot {\rm lg} \, (E_{\rm B}/N_0) \approx 0 \ \rm dB$.
  • Der grüne Kreis steht für einen sehr einfachen  Repeat–Accumulate  (RA) Code, einem seriell–verketteten Turbocode. Nachfolgend ist dessen Struktur skizziert:   Der äußere Decoder verwendet einen  Wiederholungscode  (englisch:  Repetition Code), im gezeichneten Beispiel mit der Rate  $R = 1/3$. Nach dem Interleaver folgt ein RSC–Code mit  $G(D) = 1/(1 + D)$   ⇒   Gedächtnis  $m = 1$. Bei systematischer Ausführung ist die Gesamtcoderate  $R = 1/4$  (zu jedem Informationsbit werden noch drei Paritybit hinzugefügt).
Repeat Accumulate (RA) Code der Rate $1/4$

Aus der Grafik rechts oben erkennt man, dass dieser einfache RA–Code überraschend gut ist. Mit der Interleavergröße  $K = 300000$  beträgt der Abstand von der Shannon–Grenze lediglich etwa  $1.5 \ \rm dB$  (grüner Punkt).

Ähnliche Repeat Accumulate Codes sind für den Standard DVB Return Channel Terrestrial (RCS) sowie für den WiMax–Standard (IEEE 802.16) vorgesehen.



Aufgaben zum Kapitel


Aufgabe 4.8: Wiederholung zu den Faltungscodes

Aufgabe 4.8Z: Grundlegendes zum Interleaving

Aufgabe 4.9: Recursive Systematic Convolutional Codes

Aufgabe 4.10: Turbocoder für UMTS und LTE

Quellenverzeichnis

  1. Liva, G.: Channels Codes for Iterative Decoding. Vorlesungsmanuskript, Lehrstuhl für Nachrichtentechnik, TU München und DLR Oberpfaffenhofen, 2015.