Difference between revisions of "Channel Coding/Soft-in Soft-Out Decoder"

From LNTwww
m (Text replacement - "”" to """)
(41 intermediate revisions by 5 users not shown)
Line 6: Line 6:
 
}}
 
}}
  
== Hard Decision vs. Soft Decision (1) ==
+
== # ÜBERBLICK ZUM VIERTEN HAUPTKAPITEL # ==
 
<br>
 
<br>
Zur Hinleitung auf die Thematik dieses vierten und letzten Kapitels und zur Motivation betrachten wir das folgende Nachrichtenübertragungssystem mit Codierung.<br>
+
Das letzte Hauptkapitel des Kanalcodierungsbuches beschreibt&nbsp; ''iterative Decodierverfahren'', wie sie in den meisten heutigen (2017) Kommunikationssystemen eingesetzt werden. Dies hat folgende Gründe:
  
[[File:P ID2971 KC T 4 1 S1a v8.png|center|frame|Betrachtetes Nachrichtenübertragungssystem mit Codierung|class=fit]]<br>
+
*Um sich der Kanalkapazität anzunähern, benötigt man sehr lange Codes.
 +
*Für lange Codes ist aber eine blockweise&nbsp; ''Maximum–Likelihood–Decodierung''&nbsp; nahezu unmöglich.
  
Nachfolgend werden alle Symbole in bipolarer Darstellung angegeben: &bdquo;$0$&rdquo; &nbsp;&#8594;&nbsp; &bdquo;$+1$&rdquo; und &bdquo;$1$&rdquo; &nbsp;&#8594;&nbsp; &bdquo;$&ndash;1$&rdquo;.
 
*Die Symbolfolge $\underline{u} = (u_1, \ u_2)$ wird der Coderfolge $\underline{x} = (x_1, \ x_2, \ x_3) = (u_1, \ u_2, \ p)$ zugeordnet, wobei für das Paritybit $p = u_1 &oplus; u_2$ gilt &nbsp;&#8658;&nbsp; [[Kanalcodierung/Beispiele_bin%C3%A4rer_Blockcodes#Single_Parity.E2.80.93check_Codes_.281.29| Single Parity&ndash;check Code]] &nbsp;&#8658;&nbsp; ${\rm SPC} (3, 2, 2)$.<br>
 
  
*Der [[Kanalcodierung/Klassifizierung_von_Signalen#AWGN.E2.80.93Kanal_bei_bin.C3.A4rem_Eingang| AWGN&ndash;Kanal]] verändert die Binärsymbole $x_i &#8712; \{+1, \ &ndash;1\}$ zu reellwertigen Ausgangswerten $y_i$, z.B. im Block 4 der unteren Tabelle: &nbsp; $x_1 = +1$ &nbsp;&#8658;&nbsp; $y_1 = +0.9$ und $x_3 = \, &ndash;1$ &nbsp;&#8658;&nbsp; $y_3 = +0.1$.<br>
+
Die Decoder–Komplexität lässt sich bei nahezu gleicher Qualität deutlich herabsetzen, wenn man zwei (oder mehrere) kurze Kanalcodes miteinander verknüpft und beim Empfänger die jeweils neu gewonnene (Soft–)Information in mehreren Schritten – also iterativ – zwischen den Decodern austauscht.
  
*Die Decodierung geschieht gemäß dem Kriterium [[Kanalcodierung/Klassifizierung_von_Signalen#MAP.E2.80.93_und_ML.E2.80.93Kriterium_.282.29| Maximum Likelihood (block&ndash;wise ML)]], wobei zwischen <i>Hard Decision</i> (ML&ndash;HD) und <i>Soft Decision</i> (ML&ndash;SD) zu unterscheiden ist.<br>
+
Der Durchbruch auf dem Gebiet gelang Anfang der 1990er Jahre mit der Erfindung der&nbsp; ''Turbo–Codes''&nbsp; durch&nbsp; [https://de.wikipedia.org/wiki/Claude_Berrou Claude Berrou]&nbsp; und kurz darauf mit der Wiederentdeckung der&nbsp; ''Low–density Parity–check Codes''&nbsp; durch&nbsp; [https://en.wikipedia.org/wiki/David_J._C._MacKay David J. C. MacKay]&nbsp; und&nbsp; [https://en.wikipedia.org/wiki/Radford_M._Neal Radford M. Neal], nachdem die schon 1961 von&nbsp; [https://de.wikipedia.org/wiki/Robert_Gray_Gallager Robert G. Gallager]&nbsp; entwickelten LDPC–Codes zwischenzeitlich in Vergessenheit geraten waren.
  
*Das obige Blockschaltbild in seiner Gesamtheit entspricht ML&ndash;HD. Hier werden zur Detektion nur die Vorzeichen der AWGN&ndash;Ausgangswerte entsprechend $y_{\rm HD, \ \it i} = {\rm sign}[y_{\rm SD, \ \it i}]$ ausgewertet.<br>
+
Im Einzelnen werden im vierten Hauptkapitel behandelt:
  
*Bei <i>Soft Decision</i> (ML&ndash;SD) verzichtet man auf den schraffierten Block in obigem Blockschaltbild und wertet direkt die wertkontinuierlichen Eingangsgrößen $y_{\rm SD, \ \it i}$ aus.<br>
+
*Eine Gegenüberstellung von&nbsp; ''Hard Decision''&nbsp; und&nbsp; ''Soft Decision'',
 +
*die Quantifizierung von&nbsp; ''Zuverlässigkeitsinformation''&nbsp; durch&nbsp; ''Log Likelihood Ratios''&nbsp;(LLR),
 +
*das Prinzip der symbolweisen&nbsp; ''Soft–in Soft–out''&nbsp; (SISO) Decodierung,
 +
*die Definition von&nbsp; ''Apriori–L–Wert'',&nbsp; ''Aposteriori–L–Wert''&nbsp; und&nbsp; ''extrinsischem L–Wert'',
 +
*die Grundstruktur von&nbsp; ''seriell  verketteten''&nbsp; bzw.&nbsp; ''parallel verketteten''&nbsp; Codiersystemen,
 +
*die Eigenschaften von&nbsp; ''Produkt–Codes''&nbsp; und deren&nbsp; ''Hard Decision Decodierung'',
 +
*die Grundstruktur, der Decodieralgorithmus und die Leistungsfähigkeit der&nbsp; ''Turbo–Codes'',
 +
*Grundlegendes zu den&nbsp; ''Low–density Parity–check Codes''&nbsp; und deren Anwendungen.
  
[[File:P ID2972 KC T 4 1 S1b v4.png|center|frame|Gegenüberstellung von <i>Hard Decision</i> und <i>Soft Decision</i>|class=fit]]<br>
 
  
Aus der Beispieltabelle erkennt man:
 
*<b>Hard Decision</b> &nbsp;&#8658; die Symbolfolge $\underline{\upsilon}_{\rm HD}$ ergibt sich aus den hart entschiedenen Kanalwerten $\underline{y}_{\rm HD}$ (blaue Hinterlegung): Es werden nur die beiden ersten Blöcke fehlerfrei decodiert.<br>
 
  
*<b>Soft Decision</b> &nbsp;&#8658; die Symbolfolge $\underline{\upsilon}_{\rm SD}$ ergibt sich aus den &bdquo;weichen&rdquo; Kanalausgangswerten $\underline{y}_{\rm SD}$ (grüne Hinterlegung): Nun wird in diesem Beispiel auch der dritte Block richtig entschieden.<br><br>
+
== Hard Decision vs. Soft Decision==
 +
<br>
 +
Zur Hinleitung auf die hier behandelte Thematik betrachten wir das folgende Nachrichtenübertragungssystem mit Codierung.<br>
 +
 
 +
[[File:P ID2971 KC T 4 1 S1a v8.png|center|frame|Betrachtetes Nachrichtenübertragungssystem mit Codierung|class=fit]]
 +
 
 +
Im Weiteren werden alle Symbole in bipolarer Darstellung angegeben: &nbsp; "$0$" &nbsp;&#8594;&nbsp; "$+1$"&nbsp; und&nbsp; "$1$" &nbsp;&#8594;&nbsp; "$-1$".
 +
*Die Symbolfolge&nbsp; $\underline{u} = (u_1, \ u_2)$&nbsp; wird der Coderfolge&nbsp; $\underline{x} = (x_1, \ x_2, \ x_3) = (u_1, \ u_2, \ p)$&nbsp; zugeordnet, wobei für das Paritybit&nbsp; $p = u_1 &oplus; u_2$&nbsp; gilt &nbsp; &#8658; &nbsp; [[Channel_Coding/Beispiele_bin%C3%A4rer_Blockcodes#Single_Parity.E2.80.93check_Codes| Single Parity&ndash;check Code]] &nbsp; &#8658; &nbsp; ${\rm SPC} (3, 2, 2)$.<br>
 +
 
 +
*Der&nbsp; [[Channel_Coding/Signal_classification#AWGN.E2.80.93Kanal_bei_bin.C3.A4rem_Eingang| AWGN&ndash;Kanal]]&nbsp; verändert die Binärsymbole&nbsp; $x_i &#8712; \{+1, \ &ndash;1\}$&nbsp; zu reellwertigen Ausgangswerten&nbsp; $y_i$, zum Beispiel gemäß&nbsp; $\text{Kanal 4}$&nbsp; der unteren Tabelle: &nbsp; $x_1 = +1$ &nbsp; &#8658; &nbsp; $y_1 = +0.9$, &nbsp; $x_2 = \, -1$ &nbsp; &#8658; &nbsp; $y_2 = +0.1$&nbsp; und&nbsp; $x_3 = \, -1$ &nbsp; &#8658; &nbsp; $y_3 = +0.1$.<br>
 +
 
 +
*Die Decodierung geschieht gemäß dem Kriterium&nbsp; [[Channel_Coding/Kanalmodelle_und_Entscheiderstrukturen#Maximum-a-posteriori.E2.80.93_und_Maximum-Likelihood.E2.80.93Kriterium|Maximum-Likelihood]]  &nbsp;$\text{(blockwise ML)}$, wobei zwischen&nbsp; <i>Hard Decision</i>&nbsp; $\rm {(ML&ndash;HD)}$&nbsp; und&nbsp; <i>Soft Decision</i>&nbsp; $\rm {(ML&ndash;SD)}$&nbsp; zu unterscheiden ist.<br>
 +
 
 +
*Das gesamte Blockschaltbild entspricht &nbsp;$\rm ML&ndash;HD$. Hier werden zur Decodierung nur die Vorzeichen der AWGN&ndash;Ausgangswerte &nbsp; &rArr; &nbsp; $y_{\rm HD, \ \it i} = {\rm sign}\big [y_{\rm SD, \ \it i}\big ]$&nbsp; ausgewertet. Bei&nbsp; <i>Soft Decision</i>&nbsp; $\rm {(ML&ndash;SD)}$&nbsp; verzichtet man auf den schraffierten Block und wertet direkt die wertkontinuierlichen Eingangsgrößen&nbsp; $y_{\rm SD, \ \it i}$&nbsp; aus.<br>
 +
 
  
Die Bildbeschreibung wird auf der nächsten Seite fortgesetzt.<br>
+
[[File:P ID2972 KC T 4 1 S1b v4.png|center|frame|Gegenüberstellung von <i>Hard Decision</i> und <i>Soft Decision</i>|class=fit]]
 +
 
 +
Für alle Spalten dieser Tabelle wird vorausgesetzt:
 +
*der Nachrichtenblock&nbsp; $\underline{u} = (0, 1)$, bipolar darstellbar als&nbsp; $(+1, \, &ndash;1)$,<br>
 +
*der&nbsp; ${\rm SPC} \ (3, 2)$&ndash;codierte Block&nbsp; $\underline{x} = (0, 1, 1)$&nbsp; bzw.&nbsp; in Bipolardarstellung&nbsp; $(+1, \, -1, \, -1)$.<br>
  
== Hard Decision vs. Soft Decision (2) ==
 
<br>
 
Für alle Spalten der folgenden Tabelle wird vorausgesetzt:
 
*der Nachrichtenblock $\underline{u} = (0, 1)$, bipolar darstellbar als $(+1, \, &ndash;1)$,<br>
 
  
*der ${\rm SPC} \ (3, 2)$&ndash;codierte Block $\underline{x} = (0, 1, 1)$ bzw. in Bipolardarstellung $(+1, \, &ndash;1, \, &ndash;1)$.<br><br>
+
Die vier Spalten unterscheiden sich also nur durch unterschiedliche AWGN&ndash;Realisierungen.<br>
  
Die vier Blöcke unterscheiden sich also nur durch unterschiedliche AWGN&ndash;Realisierungen.<br>
+
{{BlaueBox|TEXT= 
 +
$\text{Definition:}$&nbsp;  Aus der Beispieltabelle erkennt man:
 +
*$\text{Hard Decision:}$ &nbsp; Die Symbolfolge&nbsp; $\underline{v}_{\rm HD}$&nbsp; ergibt sich aus den hart entschiedenen Kanalwerten&nbsp; $\underline{y}_{\rm HD}$ (blaue Hinterlegung). <br>Bei unserem Beispiel werden nur die Konstellationen gemäß&nbsp; $\text{Kanal 1}$&nbsp; und&nbsp; $\text{Kanal 2}$&nbsp; fehlerfrei decodiert.<br>
  
[[File:P ID2973 KC T 4 1 S1b v4.png|center|frame|Gegenüberstellung von <i>Hard Decision</i>  und <i>Soft Decision</i>|class=fit]]<br>
+
*$\text{Soft Decision:}$ &nbsp; Die Symbolfolge&nbsp; $\underline{v}_{\rm SD}$&nbsp; ergibt sich aus den "weichen" Kanalausgangswerten&nbsp; $\underline{y}_{\rm SD}$ (grüne Hinterlegung). <br>Nun wird in diesem Beispiel auch bei&nbsp; $\text{Kanal 3}$&nbsp; richtig entschieden.}}<br>
  
Die Tabelle ist wie folgt zu interpretieren:
+
Die Einträge in der obigen Beispieltabelle sind wie folgt zu interpretieren:
*Bei idealem Kanal entsprechend Block 1 &nbsp;&#8658;&nbsp; $\underline{x} = \underline{y}_{\rm SD} = \underline{y}_{\rm HD}$ gibt es keinen Unterschied zwischen der (blauen) herkömmlichen ML&ndash;HD &ndash;Variante und der (grünen) ML&ndash;SD &ndash;Variante.<br>
+
*Bei idealem Kanal &nbsp; &#8658; &nbsp; $\text{Kanal 1}$ &nbsp; &#8658; &nbsp; $\underline{x} = \underline{y}_{\rm SD} = \underline{y}_{\rm HD}$&nbsp; gibt es keinen Unterschied zwischen der (blauen) herkömmlichen ''Hard Decision''&ndash;Variante $\rm {(ML&ndash;HD)}$&nbsp; und der (grünen) ''Soft Decision''&ndash;Variante $\rm {(ML&ndash;SD)}$.<br>
  
*Der Block 2 demonstriert geringe Signalverfälschungen. Wegen $\underline{y}_{\rm HD} = \underline{x}$ (das heißt, dass der Kanal die Vorzeichen nicht  verfälscht) liefert auch ML&ndash;HD das richtige Ergebnis $\underline{\upsilon}_{\rm HD} = \underline{u}$.<br>
+
*Die Einstellung entsprechend&nbsp; $\text{Kanal 2}$&nbsp; demonstriert geringe Signalverfälschungen. Wegen&nbsp; $\underline{y}_{\rm HD} = \underline{x}$&nbsp; (das heißt, dass der Kanal die Vorzeichen nicht  verfälscht) liefert auch&nbsp; $\rm ML&ndash;HD$&nbsp; das richtige Ergebnis&nbsp; $\underline{v}_{\rm HD} = \underline{u}$.<br>
  
*Dagegen gilt im dritten Block $\underline{y}_{\rm HD} &ne; \underline{x}$ und es gibt auch keine ${\rm SPC} \ (3, 2)$&ndash;Zuordnung $\underline{u}$ &nbsp;&#8658;&nbsp; $\underline{y}_{\rm HD}$. Der ML&ndash;Decoder kann hier nur durch die Ausgabe $\underline{\upsilon}_{\rm HD} = \rm (E, \ E)$ vermelden, dass er bei der Decodierung dieses Blocks gescheitert ist. &bdquo;$\rm E$&rdquo; steht hierbei für [[Kanalcodierung/Klassifizierung_von_Signalen#Binary_Erasure_Channel_.E2.80.93_BEC| Erasure]] (deutsch: <i>Auslöschung</i>).<br>
+
*Beim&nbsp; $\text{Kanal 3}$&nbsp; gilt&nbsp; $\underline{y}_{\rm HD} &ne; \underline{x}$&nbsp; und es gibt auch keine&nbsp; ${\rm SPC} \ (3, 2)$&ndash;Zuordnung&nbsp; $\underline{u}$ &nbsp; &#8658; &nbsp; $\underline{y}_{\rm HD}$. Der ML&ndash;Decoder vermeldet hier durch die Ausgabe&nbsp; $\underline{v}_{\rm HD} = \rm (E, \ E)$, dass er bei der Decodierung dieses Blocks gescheitert ist. "$\rm E$" steht für&nbsp; [[Channel_Coding/Signal_classification#Binary_Erasure_Channel_.E2.80.93_BEC| Erasure]]&nbsp; (deutsch: &nbsp; Auslöschung).<br>
  
*Auch der <i>Soft Decision</i> Decoder erkennt, dass eine Decodierung anhand der Vorzeichen nicht funktioniert. Anhand der $\underline{y}_{\rm SD}$&ndash;Werte erkennt er aber, dass mit großer Wahrscheinlichkeit das zweite Bit verfälscht wurde und entscheidet sich für die richtige Symbolfolge $\underline{\upsilon}_{\rm SD} = (+1, \, &ndash;1) = \underline{u}$.<br>
+
*Auch der&nbsp; <i>Soft Decision</i>&nbsp; Decoder erkennt, dass eine Decodierung anhand der Vorzeichen nicht funktioniert. Anhand der&nbsp; $\underline{y}_{\rm SD}$&ndash;Werte erkennt er aber, dass mit großer Wahrscheinlichkeit das zweite Bit verfälscht wurde und entscheidet sich für die richtige Symbolfolge&nbsp; $\underline{v}_{\rm SD} = (+1, \, -1) = \underline{u}$.<br>
  
*Im vierten Block werden durch den AWGN&ndash;Kanal sowohl die Vorzeichen von Bit 2 als auch von Bit 3 verändert, was zum Ergebnis $\underline{\upsilon}_{\rm HD} = (+1, +1) &ne; \underline{u}(+1, \, &ndash;1)$ führt &nbsp;&#8658;&nbsp; ein Blockfehler und gleichzeitig ein Bitfehler. Auch der <i>Soft Decision</i> Decoder liefert hier das gleiche falsche Ergebnis.<br><br>
+
*Bei&nbsp; $\text{Kanal 4}$&nbsp; werden durch den AWGN&ndash;Kanal sowohl die Vorzeichen von Bit 2 als auch von Bit 3 verändert, was zum Ergebnis&nbsp; $\underline{v}_{\rm HD} = (+1, +1) &ne; \underline{u}(+1, \, -1)$&nbsp; führt &nbsp; &#8658; &nbsp; ein Blockfehler und gleichzeitig ein Bitfehler. Auch der <i>Soft Decision</i> Decoder liefert hier das gleiche falsche Ergebnis.<br><br>
  
Die Decodiervariante ML&ndash;SD bietet gegenüber ML&ndash;HD zudem den Vorteil, dass man relativ einfach jedes Decodierergebnis mit einem Zuverlässigkeitswert versehen kann (in obiger Tabelle ist dieser allerdings nicht angegeben). Dieser Zuverlässigkeitswert
+
Die Decodiervariante "ML&ndash;SD" bietet gegenüber "ML&ndash;HD" zudem den Vorteil, dass man relativ einfach jedes Decodierergebnis mit einem Zuverlässigkeitswert versehen kann (in obiger Tabelle ist dieser allerdings nicht angegeben). Dieser Zuverlässigkeitswert
*hätte bei Block 1 seinen Maximalwert,<br>
+
*hätte bei&nbsp; $\text{Kanal 1}$&nbsp; seinen Maximalwert,<br>
  
*wäre bei Block 2 deutlich kleiner,<br>
+
*wäre bei&nbsp; $\text{Kanal 2}$&nbsp; deutlich kleiner,<br>
  
*läge bei Block 3 und 4 nahe bei $0$.<br>
+
*läge bei&nbsp; $\text{Kanal 3}$&nbsp; und&nbsp; $\text{Kanal 4}$&nbsp; nahe bei Null.<br>
  
== Zuverlässigkeitsinformation – Log Likelihood Ratio (1) ==
+
== Zuverlässigkeitsinformation – Log Likelihood Ratio==
 
<br>
 
<br>
Es sei $x &#8712; \{+1, \, &ndash;1\}$ eine binäre Zufallsvariable mit den Wahrscheinlichkeiten ${\rm Pr}(x = +1)$ und ${\rm Pr}(x = \, &ndash;1)$. Für die Codierungstheorie erweist es sich als zweckmäßig hinsichtlich der Rechenzeiten, wenn man anstelle der Wahrscheinlichkeiten ${\rm Pr}(x = &plusmn;1)$ den natürlichen Logarithmus des Quotienten heranzieht.<br>
+
Es sei&nbsp; $x &#8712; \{+1, \, -1\}$&nbsp; eine binäre Zufallsvariable mit den Wahrscheinlichkeiten&nbsp; ${\rm Pr}(x = +1)$&nbsp; und&nbsp; ${\rm Pr}(x = \, -1)$. Für die Codierungstheorie erweist es sich als zweckmäßig hinsichtlich der Rechenzeiten, wenn man anstelle der Wahrscheinlichkeiten&nbsp; ${\rm Pr}(x = &plusmn;1)$&nbsp; den natürlichen Logarithmus des Quotienten heranzieht.<br>
 
 
{{Definition}}''':''' Das <b>Log&ndash;Likelihood&ndash;Verhältnis</b> (kurz: der $L$&ndash;Wert, englisch: <i>Log&ndash;Likelihood Ratio</i>, LLR) der Zufallsgröße $x &#8712; \{+1, \, &ndash;1\}$ lautet:
 
  
:<math>L(x)={\rm ln} \hspace{0.15cm} \frac{{\rm Pr}(x = +1)}{{\rm Pr}(x = -1)}\hspace{0.05cm}.</math>
+
{{BlaueBox|TEXT= 
 +
$\text{Definition:}$&nbsp;  Das&nbsp; <b>Log&ndash;Likelihood&ndash;Verhältnis</b>&nbsp; (kurz: &nbsp; der $L$&ndash;Wert, englisch: <i>Log&ndash;Likelihood Ratio</i>, LLR)&nbsp; der Zufallsgröße&nbsp; $x &#8712; \{+1, \, -1\}$&nbsp; lautet:
  
Bei unipolarer/symbolhafter Darstellung ($+1&nbsp;&#8594;&nbsp;0$ &nbsp;und&nbsp; $&ndash;1&nbsp;&#8594;&nbsp;1$) gilt entsprechend mit $\xi &#8712; \{0, 1\}$:
+
::<math>L(x)={\rm ln} \hspace{0.15cm} \frac{ {\rm Pr}(x = +1)}{ {\rm Pr}(x = -1)}\hspace{0.05cm}.</math>
  
:<math>L(\xi)={\rm ln} \hspace{0.15cm} \frac{{\rm Pr}(\xi = 0)}{{\rm Pr}(\xi = 1)}\hspace{0.05cm}.</math>{{end}}<br>
+
Bei unipolarer/symbolhafter Darstellung&nbsp; $(+1&nbsp; &#8594; &nbsp;0$ &nbsp; und &nbsp; $-1&nbsp; &#8594; &nbsp;1)$&nbsp; gilt entsprechend mit&nbsp; $\xi &#8712; \{0, \, 1\}$:
  
Nachfolgend ist der nichtlineare Zusammenhang zwischen ${\rm Pr}(x = &plusmn;1)$ und $L(x)$ angegeben. Ersetzt man ${\rm Pr}(x = +1)$ durch ${\rm Pr}(\xi = 0)$, so gibt die mittlere Zeile den $L$&ndash;Wert der unipolaren Zufallsgröße $\xi$ an.<br>
+
::<math>L(\xi)={\rm ln} \hspace{0.15cm} \frac{ {\rm Pr}(\xi = 0)}{ {\rm Pr}(\xi = 1)}\hspace{0.05cm}.</math>}}<br>
  
[[File:P ID2975 KC T 4 1 S2a v1.png|Wahrscheinlichkeit und <i>L</i>–Wert|class=fit]]<br>
+
Nachfolgend ist der nichtlineare Zusammenhang zwischen&nbsp; ${\rm Pr}(x = &plusmn;1)$&nbsp; und&nbsp; $L(x)$&nbsp; angegeben. Ersetzt man&nbsp; ${\rm Pr}(x = +1)$&nbsp; durch&nbsp; ${\rm Pr}(\xi = 0)$, so gibt die mittlere Zeile den&nbsp; $L$&ndash;Wert der unipolaren Zufallsgröße&nbsp; $\xi$ an.<br>
  
 +
[[File:P ID2975 KC T 4 1 S2a v1.png|center|frame|Wahrscheinlichkeit und &nbsp;$L$–Wert|class=fit]]
 
Man erkennt:
 
Man erkennt:
*Der wahrscheinlichere Zufallswert von $x &#8712; \{+1, \, &ndash;1\}$ ist durch ${\rm sign} \, L(x)$ &nbsp;&#8658;&nbsp; <b>Vorzeichen</b> gegeben.<br>
+
*Der wahrscheinlichere Zufallswert von&nbsp; $x &#8712; \{+1, \, -1\}$&nbsp; ist durch das&nbsp; <b>Vorzeichen</b> &nbsp; &#8658; &nbsp; ${\rm sign} \ L(x)$&nbsp; gegeben.<br>
  
*Dagegen gibt der <b>Betrag</b> $|L(x)|$ die Zuverlässigkeit für das Ergebnis ${\rm sign}(L(x))$ an.<br><br>
+
*Dagegen gibt der&nbsp; <b>Betrag</b>&nbsp; &nbsp; &#8658; &nbsp; $|L(x)|$&nbsp; die Zuverlässigkeit für das Ergebnis&nbsp; ${\rm sign}(L(x))$&nbsp; an.<br><br>
  
{{Beispiel}}''':'''
+
[[File:P ID2976 KC T 4 1 S2b v2.png|right|frame|BSC–Modell]]  
[[File:P ID2976 KC T 4 1 S2b v2.png|right|frame|BSC–Modell]] Wir betrachten das  skizzierte [[Kanalcodierung/Klassifizierung_von_Signalen#Binary_Symmetric_Channel_.E2.80.93_BSC| BSC&ndash;Modell]] mit bipolarer Darstellung. Hier gilt mit  der Verfälschungswahrscheinlichkeit $\epsilon = 0.1$ sowie den beiden Zufallsgrößen $x &#8712; \{+1, \, &ndash;1\}$ und $y &#8712; \{+1, \, &ndash;1\}$ am Eingang und Ausgang des Kanals:
+
{{GraueBox|TEXT= 
 +
$\text{Beispiel 1:}$&nbsp;  Wir betrachten das  skizzierte&nbsp; [[Channel_Coding/Kanalmodelle_und_Entscheiderstrukturen#Binary_Symmetric_Channel_.E2.80.93_BSC| BSC&ndash;Modell]]&nbsp; mit bipolarer Darstellung. Hier gilt mit  der Verfälschungswahrscheinlichkeit&nbsp; $\varepsilon = 0.1$&nbsp; sowie den beiden Zufallsgrößen&nbsp; $x &#8712; \{+1, \, -1\}$&nbsp; und&nbsp; $y &#8712; \{+1, \, -1\}$&nbsp; am Eingang und Ausgang des Kanals:
  
:<math>L(y\hspace{0.05cm}|\hspace{0.05cm}x) \hspace{-0.15cm}  = \hspace{-0.15cm}
+
::<math>L(y\hspace{0.05cm}\vert\hspace{0.05cm}x) =
{\rm ln} \hspace{0.15cm} \frac{{\rm Pr}(y\hspace{0.05cm}|\hspace{0.05cm}x = +1)}{{\rm Pr}(y\hspace{0.05cm}|\hspace{0.05cm}x = -1)}  = </math>
+
{\rm ln} \hspace{0.15cm} \frac{ {\rm Pr}(y\hspace{0.05cm}\vert\hspace{0.05cm}x = +1) }{ {\rm Pr}(y\hspace{0.05cm}\vert\hspace{0.05cm}x = -1)}  =  
:<math>\hspace{-0.15cm}  =  \hspace{-0.15cm}
+
\left\{ \begin{array}{c} {\rm ln} \hspace{0.15cm} \big[(1 - \varepsilon)/\varepsilon \big]\\
\left\{ \begin{array}{c} {\rm ln} \hspace{0.15cm} [(1 - \varepsilon)/\varepsilon]\\
+
  {\rm ln} \hspace{0.15cm}\big [\varepsilon/(1 - \varepsilon)\big]  \end{array} \right.\quad
  {\rm ln} \hspace{0.15cm} [\varepsilon/(1 - \varepsilon)]  \end{array} \right.\quad
 
 
\begin{array}{*{1}c} {\rm f\ddot{u}r} \hspace{0.15cm} y = +1,
 
\begin{array}{*{1}c} {\rm f\ddot{u}r} \hspace{0.15cm} y = +1,
 
\\  {\rm f\ddot{u}r} \hspace{0.15cm} y = -1. \\ \end{array}</math>
 
\\  {\rm f\ddot{u}r} \hspace{0.15cm} y = -1. \\ \end{array}</math>
  
Beispielsweise ergeben sich für $\epsilon = 0.1$ folgende Zahlenwerte (vergleiche obere Tabelle):
+
Beispielsweise ergeben sich für&nbsp; $\varepsilon = 0.1$&nbsp; folgende Zahlenwerte (vergleiche obere Tabelle):
  
:<math>L(y = +1\hspace{0.05cm}|\hspace{0.05cm}x) =
+
::<math>L(y = +1\hspace{0.05cm}\vert\hspace{0.05cm}x) =
{\rm ln} \hspace{0.15cm} \frac{0.9}{0.1}  = +2.197\hspace{0.05cm}, \hspace{0.2cm}
+
{\rm ln} \hspace{0.15cm} \frac{0.9}{0.1}  = +2.197\hspace{0.05cm}, \hspace{0.8cm}
  L(y = -1\hspace{0.05cm}|\hspace{0.05cm}x) = -2.197\hspace{0.05cm}.</math>
+
  L(y = -1\hspace{0.05cm}\vert\hspace{0.05cm}x) = -2.197\hspace{0.05cm}.</math>
  
Dieses Beispiel zeigt, dass man die sog. $L$&ndash;Wert&ndash;Algebra auch auf bedingte Wahrscheinlichkeiten anwenden kann. In Aufgabe Z4.1 wird das BEC&ndash;Modell in ähnlicher Weise beschrieben.{{end}}<br>
+
Dieses Beispiel zeigt, dass man die so genannte&nbsp; $L$&ndash;Wert&ndash;Algebra auch auf bedingte Wahrscheinlichkeiten anwenden kann. <br>In der&nbsp; [[Aufgaben:Aufgabe_4.1Z:_L–Werte_des_BEC–Modells|Aufgabe 4.1Z]]&nbsp; wird das BEC&ndash;Modell in ähnlicher Weise beschrieben.}}<br>
  
== Zuverlässigkeitsinformation – Log Likelihood Ratio (2) ==
+
{{GraueBox|TEXT=
<br>
+
$\text{Beispiel 2:}$&nbsp; 
Wir betrachten nun den AWGN&ndash;Kanal mit den beiden bedingten Wahrscheinlichkeitsdichtefunktionen
+
In einem weiteren Beispiel  betrachten nun den&nbsp; [[Channel_Coding/Kanalmodelle_und_Entscheiderstrukturen#AWGN.E2.80.93Kanal_bei_bin.C3.A4rem_Eingang|AWGN&ndash;Kanal]]&nbsp; mit den bedingten Wahrscheinlichkeitsdichtefunktionen
 +
[[File:P ID2977 KC T 4 1 S2c v3.png|right|frame|Bedingte AWGN–Dichtefunktionen|class=fit]]
  
:<math>f_{y \hspace{0.03cm}| \hspace{0.03cm}x=+1 } \hspace{0.05cm} (y \hspace{0.05cm}| \hspace{0.05cm}x=+1 )\hspace{-0.1cm} =  \hspace{-0.1cm}
+
::<math>f_{y \hspace{0.03cm}\vert \hspace{0.03cm}x=+1 } \hspace{0.05cm} (y \hspace{0.05cm}\vert\hspace{0.05cm}x=+1 )\hspace{-0.1cm} =  \hspace{-0.1cm}
 
\frac {1}{\sqrt{2\pi} \cdot \sigma } \cdot {\rm e} ^{ -  {(y-1)^2}/(2\sigma^2) } \hspace{0.05cm},</math>  
 
\frac {1}{\sqrt{2\pi} \cdot \sigma } \cdot {\rm e} ^{ -  {(y-1)^2}/(2\sigma^2) } \hspace{0.05cm},</math>  
:<math>f_{y \hspace{0.03cm}| \hspace{0.03cm}x=-1 } \hspace{0.05cm} (y \hspace{0.05cm}| \hspace{0.05cm}x=-1 )\hspace{-0.1cm} =  \hspace{-0.1cm}
+
::<math>f_{y \hspace{0.03cm}\vert \hspace{0.03cm}x=-1 } \hspace{0.05cm} (y \hspace{0.05cm}\vert\hspace{0.05cm}x=-1 )\hspace{-0.1cm} =  \hspace{-0.1cm}
 
\frac {1}{\sqrt{2\pi} \cdot \sigma } \cdot {\rm e} ^{ -  {(y+1)^2}/(2\sigma^2) } \hspace{0.05cm}.</math>
 
\frac {1}{\sqrt{2\pi} \cdot \sigma } \cdot {\rm e} ^{ -  {(y+1)^2}/(2\sigma^2) } \hspace{0.05cm}.</math>
  
 
In der Grafik sind zwei beispielhafte Gaußfunktionen als blaue bzw. rote Kurve dargestellt.<br>
 
In der Grafik sind zwei beispielhafte Gaußfunktionen als blaue bzw. rote Kurve dargestellt.<br>
 +
<br clear=all>
 +
Die gesamte WDF des Ausgangssignals&nbsp;$y$&nbsp; ergibt sich aus der (gleich) gewichteten Summe:
  
[[File:P ID2977 KC T 4 1 S2c v3.png|center|frame|Bedingte AWGN–Dichtefunktionen|class=fit]]<br>
+
::<math>f_{y  } \hspace{0.05cm} (y  ) = 1/2 \cdot \big [ f_{y \hspace{0.03cm}\vert \hspace{0.03cm}x=+1 } \hspace{0.05cm} (y \hspace{0.05cm}\vert\hspace{0.05cm}x=+1 ) \hspace{0.1cm} +  \hspace{0.1cm}
 
+
f_{y \hspace{0.03cm}\vert \hspace{0.03cm}x=-1 } \hspace{0.05cm} (y \hspace{0.05cm}\vert \hspace{0.05cm}x=-1 )
Die gesamte WDF des Ausgangssignals $y$ ergibt sich aus der (gleich) gewichteten Summe:
 
 
 
:<math>f_{y  } \hspace{0.05cm} (y  ) = 1/2 \cdot \big [ f_{y \hspace{0.03cm}| \hspace{0.03cm}x=+1 } \hspace{0.05cm} (y \hspace{0.05cm}| \hspace{0.05cm}x=+1 ) \hspace{0.1cm} +  \hspace{0.1cm}
 
f_{y \hspace{0.03cm}| \hspace{0.03cm}x=-1 } \hspace{0.05cm} (y \hspace{0.05cm}| \hspace{0.05cm}x=-1 )
 
 
\big ]
 
\big ]
 
\hspace{0.05cm}.</math>
 
\hspace{0.05cm}.</math>
  
Berechnen wir nun die Wahrscheinlichkeit, dass der Empfangswert $y$ in einem (sehr) schmalen Intervall der Breite $\Delta$ um $y_0 = 0.25$ liegt, so erhält man näherungsweise
+
Wir berechnen nun die Wahrscheinlichkeit, dass der Empfangswert&nbsp; $y$&nbsp; in einem (sehr) schmalen Intervall der Breite&nbsp; $\Delta$&nbsp; um&nbsp; $y_0 = 0.25$&nbsp; liegt. Man erhält näherungsweise
  
:<math>{\rm Pr} (|y - y_0| \le{\it  \Delta}/2 \hspace{0.05cm}
+
::<math>{\rm Pr} (\vert y - y_0\vert  \le{\it  \Delta}/2 \hspace{0.05cm}
\Big \hspace{0.05cm}x=+1 )\hspace{-0.1cm} \approx  \hspace{-0.1cm}
+
\Big \vert  \hspace{0.05cm}x=+1 )\hspace{-0.1cm} \approx  \hspace{-0.1cm}
 
\frac {\it  \Delta}{\sqrt{2\pi} \cdot \sigma } \cdot {\rm e} ^{ -  {(y_0-1)^2}/(2\sigma^2) } \hspace{0.05cm},</math>  
 
\frac {\it  \Delta}{\sqrt{2\pi} \cdot \sigma } \cdot {\rm e} ^{ -  {(y_0-1)^2}/(2\sigma^2) } \hspace{0.05cm},</math>  
:<math>{\rm Pr} (|y - y_0| \le {\it  \Delta}/2 \hspace{0.05cm}
+
::<math>{\rm Pr} (\vert y - y_0\vert  \le {\it  \Delta}/2 \hspace{0.05cm}
\Big \hspace{0.05cm}x=-1 )\hspace{-0.1cm} \approx  \hspace{-0.1cm}
+
\Big \vert  \hspace{0.05cm}x=-1 )\hspace{-0.1cm} \approx  \hspace{-0.1cm}
 
\frac {\it  \Delta}{\sqrt{2\pi} \cdot \sigma } \cdot {\rm e} ^{ -  {(y_0+1)^2}/(2\sigma^2) } \hspace{0.05cm}.</math>
 
\frac {\it  \Delta}{\sqrt{2\pi} \cdot \sigma } \cdot {\rm e} ^{ -  {(y_0+1)^2}/(2\sigma^2) } \hspace{0.05cm}.</math>
  
 
Die etwas größeren senkrechten Striche bezeichnen die Bedingungen, die kleineren die Betragsbildung.<br>
 
Die etwas größeren senkrechten Striche bezeichnen die Bedingungen, die kleineren die Betragsbildung.<br>
  
Der $L$&ndash;Wert der bedingten Wahrscheinlichkeit in Vorwärtsrichtung (das bedeutet: Ausgang $y$ für einen gegebenen Eingang $x$) ergibt sich somit als der Logarithmus des Quotienten beider Ausdrücke:
+
Der&nbsp; $L$&ndash;Wert der bedingten Wahrscheinlichkeit in Vorwärtsrichtung&nbsp; $($das bedeutet: &nbsp; Ausgang &nbsp;$y$&nbsp; für einen gegebenen Eingang&nbsp; $x)$&nbsp; ergibt sich somit als der Logarithmus des Quotienten beider Ausdrücke:
  
:<math>L(y = y_0\hspace{0.05cm}|\hspace{0.05cm}x) \hspace{-0.1cm} = \hspace{-0.1cm}
+
::<math>L(y = y_0\hspace{0.05cm}\vert\hspace{0.05cm}x) =
 
{\rm ln} \hspace{0.15cm} \left [ \frac{{\rm e} ^{ -  {(y_0-1)^2}/(2\sigma^2)}}{{\rm e} ^{ -  {(y_0+1)^2}/(2\sigma^2)}}  \right ] =  
 
{\rm ln} \hspace{0.15cm} \left [ \frac{{\rm e} ^{ -  {(y_0-1)^2}/(2\sigma^2)}}{{\rm e} ^{ -  {(y_0+1)^2}/(2\sigma^2)}}  \right ] =  
{\rm ln} \left [ {\rm e} ^{ - [ {(y_0-1)^2}+{(y_0+1)^2}]/(2\sigma^2)}  \right ]\hspace{0.15cm} = </math>
+
{\rm ln} \left [ {\rm e} ^{ - [ {(y_0-1)^2}+{(y_0+1)^2}]/(2\sigma^2)}  \right ] =  \frac{(y_0+1)^2-(y_0-1)^2}{2\cdot \sigma^2} = \frac{2 \cdot y_0}{\sigma^2}\hspace{0.05cm}. </math>
:<math>\hspace{2.4cm} \hspace{-0.1cm} \frac{(y_0+1)^2-(y_0-1)^2}{2\cdot \sigma^2} = \frac{2 \cdot y_0}{\sigma^2}\hspace{0.05cm}. </math>
 
  
Ersetzen wir nun die Hilfsgröße $y_0$ durch die (allgemeine) Zufallsgröße $y$ am AWGN&ndash;Ausgang, so lautet das Endergebnis:
+
Ersetzen wir nun die Hilfsgröße&nbsp; $y_0$&nbsp; durch die (allgemeine) Zufallsgröße&nbsp; $y$&nbsp; am AWGN&ndash;Ausgang, so lautet das Endergebnis:
  
:<math>L(y \hspace{0.05cm}|\hspace{0.05cm}x) = {2  \cdot y}/{\sigma^2} =K_{\rm L} \cdot y\hspace{0.05cm}. </math>
+
::<math>L(y \hspace{0.05cm}\vert\hspace{0.05cm}x) = {2  \cdot y}/{\sigma^2} =K_{\rm L} \cdot y\hspace{0.05cm}. </math>
  
Hierbei ist $K_{\rm L} = 2/\sigma^2$ eine Konstante, die allein von der Streuung der Gaußschen Störung abhängt.<br>
+
Hierbei ist&nbsp; $K_{\rm L} = 2/\sigma^2$&nbsp; eine Konstante, die allein von der Streuung der Gaußschen Störung abhängt.}}<br>
  
 
== Symbolweise Soft–in Soft–out Decodierung ==
 
== Symbolweise Soft–in Soft–out Decodierung ==
 
<br>
 
<br>
Wir gehen  nun von einem $(n, \ k)$&ndash;Blockcode aus, wobei das Codewort $\underline{x} = (x_1, \ ... \ , \ x_n)$ durch den Kanal in das Empfangswort $\underline{y} = (y_1, \ ... \ , \ y_n)$ verfälscht wird. Bei langen Codes ist eine <i>Maximum&ndash;a&ndash;posteriori&ndash;Entscheidung auf Blockebene</i> &ndash; kurz: <b>[[Kanalcodierung/Klassifizierung_von_Signalen#MAP.E2.80.93_und_ML.E2.80.93Kriterium_.282.29| block&ndash;wise MAP]]</b> &ndash; sehr aufwändig. Man müsste unter den $2^k$ zulässigen Codeworten $\underline{x}_j &#8712; C$ dasjenige mit der größten Rückschlusswahrscheinlichkeit (englisch: <i>A Posteriori Probability</i>, APP) finden. Das auszugebende Codewort $\underline{z}$ wäre in diesem Fall
+
Wir gehen  nun von einem&nbsp; $(n, \ k)$&ndash;Blockcode aus, wobei das Codewort&nbsp; $\underline{x} = (x_1, \ \text{...} \ , \ x_n)$&nbsp; durch den Kanal in das Empfangswort&nbsp; $\underline{y} = (y_1, \ \text{...} \ , \ y_n)$&nbsp; verfälscht wird.  
 +
*Bei langen Codes ist eine&nbsp; <i>Maximum&ndash;a&ndash;posteriori&ndash;Entscheidung auf Blockebene</i>&nbsp; &ndash; kurz: &nbsp;<b>[[Channel_Coding/Kanalmodelle_und_Entscheiderstrukturen#Maximum-a-posteriori.E2.80.93_und_Maximum-Likelihood.E2.80.93Kriterium|$\text{ block&ndash;wise MAP}$]]</b>&nbsp; &ndash; sehr aufwändig.  
 +
*Man müsste unter den&nbsp; $2^k&nbsp;$ zulässigen Codeworten&nbsp; $\underline{x}_j &#8712; \mathcal{C}$&nbsp; dasjenige mit der größten Rückschlusswahrscheinlichkeit (englisch:&nbsp; <i>A Posteriori Probability</i>, APP) finden.  
 +
*Das auszugebende Codewort&nbsp; $\underline{z}$&nbsp; wäre in diesem Fall&nbsp; $\underline{z} = {\rm arg} \max_{\underline{x}_{\hspace{0.03cm}j} \hspace{0.03cm} \in \hspace{0.05cm} \mathcal{C}} \hspace{0.1cm} {\rm Pr}( \underline{x}_{\hspace{0.03cm}j} |\hspace{0.05cm} \underline{y} ) \hspace{0.05cm}.$
  
:<math>\underline{z} = {\rm arg} \max_{\underline{x}_{\hspace{0.03cm}j} \hspace{0.03cm} \in \hspace{0.05cm} \mathcal{C}} \hspace{0.1cm} {\rm Pr}( \underline{x}_{\hspace{0.03cm}j} |\hspace{0.05cm} \underline{y} ) \hspace{0.05cm}.</math>
 
  
[[File:P ID2981 KC T 4 1 S3a v6.png|center|frame|Modell der symbolweisen Soft–in Soft–out Decodierung|class=fit]]<br>
+
[[File:P ID2981 KC T 4 1 S3a v6.png|center|frame|Modell der symbolweisen Soft–in Soft–out Decodierung|class=fit]]
  
Eine zweite Möglichkeit ist die Decodierung auf Bitebene. Der dargestellte symbolweise (oder bitweise) <span style="font-weight: bold;">Soft&ndash;in Soft&ndash;out Decoder</span> hat die Aufgabe, alle Codewortbits $x_i &#8712; \{0, 1\}$ entsprechend maximaler Rückschlusswahrscheinlichkeit ${\rm Pr}(x_i | \underline{y})$ zu decodieren. Mit der Laufvariablen $i = 1, \ ... , \ n$ gilt dabei:
+
Eine zweite Möglichkeit ist die Decodierung auf Bitebene. Der dargestellte symbolweise (oder bitweise)&nbsp; $\text{Soft&ndash;in Soft&ndash;out Decoder}$&nbsp; hat die Aufgabe, alle Codewortbits&nbsp; $x_i &#8712; \{0, \, 1\}$&nbsp; entsprechend maximaler Rückschlusswahrscheinlichkeit&nbsp; ${\rm Pr}(x_i | \underline{y})$&nbsp; zu decodieren. Mit der Laufvariablen&nbsp; $i = 1, \text{...} , \ n$&nbsp; gilt dabei:
  
*Der entsprechende $L$&ndash;Wert (englisch: <i>Log Likelihood Ratio</i>, LLR) für das $i$&ndash;te Codebit lautet:
+
*Der entsprechende&nbsp; $L$&ndash;Wert&nbsp; (englisch: &nbsp;<i>Log Likelihood Ratio</i>, LLR) für das&nbsp; $i$&ndash;te Codebit lautet:
  
 
::<math>L_{\rm APP} (i) = L(x_i\hspace{0.05cm}|\hspace{0.05cm}\underline{y}) =
 
::<math>L_{\rm APP} (i) = L(x_i\hspace{0.05cm}|\hspace{0.05cm}\underline{y}) =
 
{\rm ln} \hspace{0.15cm} \frac{{\rm Pr}(x_i = 0\hspace{0.05cm}|\hspace{0.05cm}\underline{y})}{{\rm Pr}(x_i = 1\hspace{0.05cm}|\hspace{0.05cm}\underline{y})}\hspace{0.05cm} . </math>
 
{\rm ln} \hspace{0.15cm} \frac{{\rm Pr}(x_i = 0\hspace{0.05cm}|\hspace{0.05cm}\underline{y})}{{\rm Pr}(x_i = 1\hspace{0.05cm}|\hspace{0.05cm}\underline{y})}\hspace{0.05cm} . </math>
  
*Der Decoder arbeitet iterativ. Bei der Initialisierung (gekennzeichnet durch den Parameter $I = 0$) ist $L_{\rm APP}(i) = L_{\rm K}(i)$, wobei das Kanal&ndash;LLR $L_{\rm K}(i)$ durch den Empfangswert $y_i$ gegeben ist.<br>
+
*Der Decoder arbeitet iterativ. Bei der Initialisierung $($in der Grafik gekennzeichnet durch den Parameter&nbsp; $I = 0)$&nbsp; ist&nbsp; $L_{\rm APP}(i) = L_{\rm K}(i)$, wobei das Kanal&ndash;LLR&nbsp; $L_{\rm K}(i)$&nbsp; durch den Empfangswert&nbsp; $y_i$&nbsp; gegeben ist.<br>
  
*Berechnet wird zudem  der extrinsische $L$&ndash;Wert $L_{\rm E}(i)$, der die gesamte Information quantifiziert, die alle anderen Bits $(j &ne; i)$ aufgrund der Code&ndash;Eigenschaften über das betrachtete $i$&ndash;te Bit liefern.<br>
+
*Berechnet wird zudem  der extrinsische&nbsp; $L$&ndash;Wert&nbsp; $L_{\rm E}(i)$, der die gesamte Information quantifiziert, die alle anderen Bits&nbsp; $(j &ne; i)$&nbsp; aufgrund der Code&ndash;Eigenschaften über das betrachtete&nbsp; $i$&ndash;te Bit liefern.<br>
  
*Bei der  nächsten Iteration (ab $I = 1$) wird $L_{\rm E}(i)$ bei der Berechnung von $L_{\rm APP}(i)$ als Apriori&ndash;Information $L_{\rm A}(i)$ berücksichtigt. Für das neue Aposteriori&ndash;LLR in der Iteration $I + 1$ gilt somit:
+
*Bei der  nächsten Iteration&nbsp; $($ab&nbsp; $I = 1)$&nbsp; wird&nbsp; $L_{\rm E}(i)$&nbsp; bei der Berechnung von&nbsp; $L_{\rm APP}(i)$&nbsp; als Apriori&ndash;Information&nbsp; $L_{\rm A}(i)$&nbsp; berücksichtigt. Für das neue Aposteriori&ndash;LLR in der Iteration&nbsp; $I + 1$&nbsp; gilt somit:
  
 
::<math>L_{\hspace{0.1cm}\rm APP}^{(I+1)} (i) = L_{\hspace{0.1cm}\rm APP}^{(I)} (i) + L_{\hspace{0.1cm}\rm A}^{(I+1)} (i) = L_{\hspace{0.1cm}\rm APP}^{(I)} (i) + L_{\hspace{0.1cm}\rm E}^{(I)} (i)\hspace{0.05cm} .  </math>
 
::<math>L_{\hspace{0.1cm}\rm APP}^{(I+1)} (i) = L_{\hspace{0.1cm}\rm APP}^{(I)} (i) + L_{\hspace{0.1cm}\rm A}^{(I+1)} (i) = L_{\hspace{0.1cm}\rm APP}^{(I)} (i) + L_{\hspace{0.1cm}\rm E}^{(I)} (i)\hspace{0.05cm} .  </math>
  
*Die Iterationen werden fortgesetzt, bis alle $|L_{\rm APP}(i)|$ größer sind als ein vorzugebender Wert. Das wahrscheinlichste Codewort $\underline{z}$ ergibt sich dann aus den Vorzeichen aller $L_{\rm APP}(i)$, mit $i = 1, \ ... , \ n$.<br>
+
*Die Iterationen werden fortgesetzt, bis alle Beträge&nbsp; $|L_{\rm APP}(i)|$&nbsp; größer sind als ein vorzugebender Wert. Das wahrscheinlichste Codewort&nbsp; $\underline{z}$&nbsp; ergibt sich dann aus den Vorzeichen aller&nbsp; $L_{\rm APP}(i)$, mit&nbsp; $i = 1, \ \text{...} , \ n$.<br>
  
*Bei einem [[Kanalcodierung/Allgemeine_Beschreibung_linearer_Blockcodes#Systematische_Codes_.282.29| systematischen Code]] geben die ersten $k \ {\rm Bit}$ von $\underline{z}$ das gesuchte Informationswort an, das mit großer Wahrscheinlichkeit mit der gesendeten  Nachricht $\underline{u}$ übereinstimmen wird.<br><br>
+
*Bei einem&nbsp; [[Channel_Coding/Allgemeine_Beschreibung_linearer_Blockcodes#Systematische_Codes| systematischen Code]]&nbsp; geben die ersten&nbsp; $k$&nbsp; Bit von&nbsp; $\underline{z}$&nbsp; das gesuchte Informationswort an, das mit großer Wahrscheinlichkeit mit der gesendeten  Nachricht&nbsp; $\underline{u}$ übereinstimmen wird.<br><br>
  
Diese Beschreibung des SISO&ndash;Decodierers nach [Bos98]<ref>Bossert, M.: ''Kanalcodierung.'' Stuttgart: B. G. Teubner, 1998.</ref> soll in erster Linie die unterschiedlichen $L$&ndash;Werte verdeutlichen. Das große Potential der symbolweisen Decodierung erkennt man allerdings erst im Zusammenhang mit [http://en.lntwww.de/Kanalcodierung/Soft%E2%80%93in_Soft%E2%80%93out_Decoder#Grundstruktur_von_verketteten_Codiersystemen verketteten Codiersystemen.]<br>
+
Diese Beschreibung des SISO&ndash;Decodierers nach&nbsp; [Bos98]<ref name='Bos98'>Bossert, M.: ''Kanalcodierung.'' Stuttgart: B. G. Teubner, 1998.</ref>&nbsp; soll an dieser Stelle in erster Linie die unterschiedlichen&nbsp; $L$&ndash;Werte verdeutlichen. Das große Potential der symbolweisen Decodierung erkennt man erst im Zusammenhang mit&nbsp; [[Channel_Coding/Soft%E2%80%93in_Soft%E2%80%93out_Decoder#Grundstruktur_von_verketteten_Codiersystemen| verketteten Codiersystemen.]]<br>
  
== Zur Berechnung der extrinsischen L–Werte (1) ==
+
== Zur Berechnung der extrinsischen L–Werte ==
 
<br>
 
<br>
Die Schwierigkeit bei der symbolweisen iterativen Decodierung ist im allgemeinen die Bereitstellung der extrinsischen $L$&ndash;Werte $L_{\rm E}(i)$. Bei einem Code der Länge $n$ gilt hierbei für die Laufvariable: $i = 1, \ ... , \ n$.<br>
+
Die Schwierigkeit bei der symbolweisen iterativen Decodierung ist im allgemeinen die Bereitstellung der extrinsischen&nbsp; $L$&ndash;Werte&nbsp; $L_{\rm E}(i)$. Bei einem Code der Länge&nbsp; $n$&nbsp; gilt hierbei für die Laufvariable:&nbsp; $i = 1, \ \text{...} , \ n$.<br>
 +
 
 +
{{BlaueBox|TEXT= 
 +
$\text{Definition:}$&nbsp;  Der&nbsp; <b> extrinsische $L$&ndash;Wert</b>&nbsp; (englisch: &nbsp;<i>extrinsic LLR</i> )&nbsp; ist ein Maß für die Informationen, den die anderen Symbole&nbsp; $(j &ne; i)$&nbsp; des Codewortes über das&nbsp; $i$&ndash;te Codesymbol liefern, ausgedrückt als Log&ndash;Likelihood&ndash;Verhältnis. Wir benennen diesen Kennwert mit&nbsp; $L_{\rm E}(i)$.}}
 +
 
  
{{Definition}}''':''' Der <b> extrinsische $L$&ndash;Wert</b> (englisch: <i>extrinsic LLR</i>) ist ein Maß für die Informationen, den die anderen Symbole $(j &ne; i)$ des Codewortes über das $i$&ndash;te Codesymbol liefern, ausgedrückt als Log&ndash;Likelihood&ndash;Verhältnis. Wir benennen diesen Kennwert mit $L_{\rm E}(i)$.{{end}}<br>
+
Wir berechnen nun die extrinsischen&nbsp; $L$&ndash;Werte&nbsp; $L_{\rm E}(i)$&nbsp; für zwei beispielhafte Codes.<br>
  
Wir berechnen nun die extrinsischen $L$&ndash;Werte $L_{\rm E}(i)$ für zwei beispielhafte Codes.<br><br>
 
  
<b>Repetition Code &#8658; ${\rm RC} \ (n, 1, n)$</b><br>
+
$\text{Repetition Code}$ &nbsp; &#8658; &nbsp; ${\rm RC} \ (n, 1, n)$</b><br>
  
Ein Wiederholungscode zeichnet sich dadurch aus, dass alle $n$ Codesymbole $x_i &#8712; \{0, 1\}$ identisch sind. Der extrinsische $L$&ndash;Wert für das $i$&ndash;ten Symbol ist hier sehr einfach anzugeben und lautet:
+
Ein Wiederholungscode zeichnet sich dadurch aus, dass alle&nbsp; $n$&nbsp; Codesymbole&nbsp; $x_i &#8712; \{0, \, 1\}$&nbsp; identisch sind. Der extrinsische&nbsp; $L$&ndash;Wert für das&nbsp; $i$&ndash;ten Symbol ist hier sehr einfach anzugeben und lautet:
  
:<math>L_{\rm E}(i) = \hspace{0.05cm}\sum_{j \ne i} \hspace{0.1cm} L_j  
+
::<math>L_{\rm E}(i) = \hspace{0.05cm}\sum_{j \ne i} \hspace{0.1cm} L_j  
 
\hspace{0.3cm}{\rm mit}\hspace{0.3cm}L_j = L_{\rm APP}(j)
 
\hspace{0.3cm}{\rm mit}\hspace{0.3cm}L_j = L_{\rm APP}(j)
 
\hspace{0.05cm}.</math>
 
\hspace{0.05cm}.</math>
  
Ist die Summe über alle $L_{j &ne; i}$ positiv, so bedeutet dies aus Sicht der anderen $L$&ndash;Werte eine Präferenz für &bdquo;$x_i = 0$&rdquo;. Bei negativer Summe ist &bdquo;$x_i = 1$&rdquo; wahrscheinlicher. $L_{\rm E}(i) = 0$ erlaubt keine Vorhersage.<br>
+
*Ist die Summe über alle&nbsp; $L_{j &ne; i}$&nbsp; positiv, so bedeutet dies aus Sicht der anderen&nbsp; $L$&ndash;Werte eine Präferenz für die Entscheidung &nbsp; $x_i = 0$.  
 +
*Bei negativer Summe ist dagegen&nbsp; $x_i = 1$&nbsp; wahrscheinlicher.  
 +
*$L_{\rm E}(i) = 0$&nbsp; erlaubt keine Vorhersage.<br>
 +
 
 +
 
 +
{{GraueBox|TEXT= 
 +
$\text{Beispiel 5:}$&nbsp; Wir betrachten die Decodierung des Wiederholungscodes&nbsp; $\text{RC (4, 1,4)}$. Wir gehen dabei von drei verschiedene Annnahmen für das&nbsp; <i>Log Likelihood Ratio</i>&nbsp; $\underline{L}_{\rm A}^{(I=0)} = \underline{L}_{\rm APP}$&nbsp; aus.
 +
 
 +
[[File:P ID3094 KC T 4 4 S3a neu v2.png|right|frame|Decodierbeispiel &nbsp;$\rm (A)$&nbsp; für den&nbsp; ${\rm RC} \ (4, 1, 4)$|class=fit]]
 +
$\text{Decodierbeispiel (A):}$
 +
:$$\underline{L}_{\rm APP} = (+1,  -1, +3, -1)\text{:}$$ 
 +
::$$L_{\rm E}(1) = -1+3-1 = +1\hspace{0.05cm},$$
 +
::$$L_{\rm E}(2) = +1+3-1 = +3\hspace{0.05cm},$$
 +
::$$L_{\rm E}(3) = +1-1 -1= -1\hspace{0.05cm},$$
 +
::$$L_{\rm E}(4) = +1-1 +3 = +3\hspace{0.05cm}$$
 +
:$$\hspace{0.3cm}\Rightarrow\hspace{0.3cm}\underline{L}_{\rm E}^{(I=0)}= (+1, +3, -1, +3)
 +
\hspace{0.3cm}\Rightarrow\hspace{0.3cm}\underline{L}_{\rm A}^{(I=1)}=\underline{L}_{\rm A}^{(I=0)}+ \underline{L}_{\rm E}^{(I=0)}= (+2, +2, +2, +2)$$
 +
*Zu Beginn&nbsp; $(I=0)$&nbsp; weisen die positiven&nbsp; $L_{\rm E}$&ndash;Werte auf &nbsp;$x_1 = 0$,&nbsp;$x_2 = 0$&nbsp; und &nbsp;$x_4 = 0$&nbsp; hin, während &nbsp;$x_3 =1$&nbsp; wahrscheinlicher ist.
 +
*Bereits nach einer Iteration&nbsp; $(I=1)$&nbsp; sind alle&nbsp; $L_{\rm A}$&ndash;Werte positiv  &nbsp; &#8658; &nbsp; Informationsbit wird als&nbsp; $u = 0$&nbsp; decodiert.
 +
*Weitere Iterationen bringen nichts.<br>
 +
 
  
{{Beispiel}}''':''' Wir betrachten die Decodierung eines Wiederholungscodes $(n = 4)$, wobei gelten soll:
+
[[File:P ID3096 KC T 4 4 S3c neu v1.png|right|frame|Decodierbeispiel &nbsp;$\rm (B)$&nbsp; für den&nbsp;  ${\rm RC} \ (4, 1, 4)$]]
* $\underline{L} = (+1, \, &ndash;1, +3, \, &ndash;1)$ &nbsp;&#8658;&nbsp; $\underline{L}_{\rm E} = (+1, +3, \, &ndash;1, +3) \text{:} \, L_{\rm E}(1)$ ist positiv, obwohl zwei der anderen $L$&ndash;Werte (Mehrheit) negativ sind &nbsp;&#8658;&nbsp; Präferenz für &bdquo;$x_1 = 0$&rdquo;. Alle Aposteriori&ndash;$L$&ndash;Werte sind nach einer Iteration positiv &nbsp;&#8658;&nbsp; Informationsbit ist $u = 0$. Weitere Iterationen bringen nichts.<br>
+
$\text{Decodierbeispiel (B):}$
 +
$$\underline{L}_{\rm APP} = (+1, +1, -4, +1)\text{:}$$
 +
$$\underline{L}_{\rm E}^{(I=0)} = \ (-2,  -2, +3, -2)$$
  
[[File:P ID3094 KC T 4 4 S3a neu v2.png|center|frame|Decodierbeispiel 1 für den ${\rm RC} \ (3, 1)$|class=fit]]<br>
+
*Obwohl zu Beginn drei Vorzeichen falsch waren,  sind nach zwei Iterationen alle  $L_{\rm A}$&ndash;Werte negativ.
 +
* Das Informationsbit wird als&nbsp; $u = 1$&nbsp; decodiert.
  
* $\underline{L} = (+1, +1, \, &ndash;4, +1) &nbsp;&#8658;&nbsp; \underline{L}_{\rm E} = (&ndash;2, \, &ndash;2, +3, \, &ndash;2) \text{:} \, $ Alle Aposteriori&ndash;<i>L</i>&ndash;Werte sind nach zwei Iterationen negativ &nbsp;&#8658;&nbsp; Informationsbit ist $u = 1$ &nbsp;&#8658;&nbsp; zu Beginn waren drei Vorzeichen falsch.<br>
+
[[File:P ID3095 KC T 4 4 S3b neu v1.png|right|frame|Decodierbeispiel &nbsp;$\rm (C)$&nbsp; für den&nbsp;  ${\rm RC} \ (4, 1, 4)$]]<br>
 +
$\text{Decodierbeispiel (C):}$
 +
$$\underline{L}_{\rm APP} = (+1, +1, -3, +1)\text{:}$$
 +
$$\underline{L}_{\rm E}^{(I=0)} = (-1, -1, +3, -1)$$
  
[[File:P ID3096 KC T 4 4 S3c neu v1.png|center|frame|Decodierbeispiel 2 für den ${\rm RC} \ (3, 1)$|class=fit]]<br>
+
*Alle&nbsp; $L_{\rm A}$&ndash;Werte sind schon nach einer Iteration Null.
 +
*Das Informationsbit kann nicht decodiert werden, obwohl die Ausgangslage nicht viel schlechter war als bei&nbsp;  $\rm (B)$.
 +
*Weitere Iterationen bringen auch hier nichts.<br>}}
  
* $\underline{L} = (+1, +1, \, &ndash;3, +1) &nbsp;&#8658;&nbsp; \underline{L}_{\rm E} = (&ndash;1, \, &ndash;1, +3, \, &ndash;1) \text{:} \, $ Alle Aposteriori&ndash;$L$&ndash;Werte sind nach einer Iteration $0$ &nbsp;&#8658;&nbsp; Informationsbit kann nicht decodiert werden. Weitere Iterationen bringen nichts.<br>
 
  
[[File:P ID3095 KC T 4 4 S3b neu v1.png|center|frame|Decodierbeispiel 3 für den ${\rm RC} \ (3, 1)$|class=fit]]{{end}}<br>
 
  
== Zur Berechnung der extrinsischen L–Werte (2) ==
+
$\text{Single Parity&ndash;check Code}$ &nbsp; &#8658; &nbsp; ${\rm SPC} \ (n, \ n \, -1, \ 2)$
 
<br>
 
<br>
<b>Single Parity&ndash;check Code &#8658; ${\rm SPC} \ (n, \ n \, &ndash;1, \ 2)$
 
</b><br>
 
  
Bei jedem <i>Single Parity&ndash;check Code</i> ist die Anzahl der Einsen in jedem Codewort geradzahlig. Oder anders ausgedrückt: Für jedes Codewort $\underline{x}$ ist das [[Kanalcodierung/Zielsetzung_der_Kanalcodierung#Einige_wichtige_Definitionen_zur_Blockcodierung Hamming&ndash;Gewicht]] $w_{\rm H}(\underline{x})$ geradzahlig.<br>
+
Bei jedem&nbsp; <i>Single Parity&ndash;check Code</i>&nbsp; ist die Anzahl der Einsen in jedem Codewort geradzahlig. Oder anders ausgedrückt: &nbsp; Für jedes Codewort&nbsp; $\underline{x}$&nbsp; ist das&nbsp; [[Channel_Coding/Zielsetzung_der_Kanalcodierung#Einige_wichtige_Definitionen_zur_Blockcodierung|Hamming&ndash;Gewicht]]&nbsp; $w_{\rm H}(\underline{x})$&nbsp; geradzahlig.<br>
  
Das Codewort $\underline{x}^{(&ndash;i)}$ beinhalte alle Symbole mit Ausnahme von $x_i$ &nbsp;&#8658;&nbsp; Vektor der Länge $n \, &ndash;1$. Damit lautet der extrinsische $L$&ndash;Wert bezüglich dieses $i$&ndash;ten Symbols, wenn $\underline{x}$ empfangen wurde:
+
{{BlaueBox|TEXT= 
 +
$\text{Definition:}$&nbsp; Das Codewort&nbsp; $\underline{x}^{(&ndash;i)}$&nbsp; beinhalte alle Symbole mit Ausnahme von&nbsp; $x_i$ &nbsp; &#8658; &nbsp; Vektor der Länge&nbsp; $n -1$. Damit lautet der &nbsp;$\text{extrinsische }L\text{&ndash;Wert}$&nbsp; bezüglich des&nbsp; $i$&ndash;ten Symbols, wenn&nbsp; $\underline{x}$&nbsp; empfangen wurde:
  
:<math>L_{\rm E}(i) = {\rm ln} \hspace{0.15cm}\frac{{\rm Pr} \left [w_{\rm H}(\underline{x}^{(-i)})\hspace{0.15cm}{\rm ist \hspace{0.15cm} gerade} \hspace{0.05cm} | \hspace{0.05cm}\underline{y} \hspace{0.05cm}\right ]}{{\rm Pr} \left [w_{\rm H}(\underline{x}^{(-i)})\hspace{0.15cm}{\rm ist \hspace{0.15cm} ungerade} \hspace{0.05cm} | \hspace{0.05cm}\underline{y} \hspace{0.05cm}\right ]}
+
::<math>L_{\rm E}(i) = {\rm ln} \hspace{0.15cm}\frac{ {\rm Pr} \left [w_{\rm H}(\underline{x}^{(-i)})\hspace{0.15cm}{\rm ist \hspace{0.15cm} gerade} \hspace{0.05cm} \vert\hspace{0.05cm}\underline{y} \hspace{0.05cm}\right ]}{ {\rm Pr} \left [w_{\rm H}(\underline{x}^{(-i)})\hspace{0.15cm}{\rm ist \hspace{0.15cm} ungerade} \hspace{0.05cm} \vert \hspace{0.05cm}\underline{y} \hspace{0.05cm}\right ]}
 
  \hspace{0.05cm}.</math>
 
  \hspace{0.05cm}.</math>
  
Wie in der Aufgabe A4.4 gezeigt werden soll, kann hierfür auch geschrieben werden:
+
Wie in der&nbsp; [[Aufgaben:Aufgabe_4.4:_Extrinsische_L–Werte_beim_SPC|Aufgabe 4.4]]&nbsp; gezeigt werden soll, kann hierfür auch geschrieben werden:
  
:<math>L_{\rm E}(i) = 2 \cdot {\rm tanh}^{-1} \hspace{0.1cm} \left [  \prod\limits_{j \ne i}^{n} \hspace{0.15cm}{\rm tanh}(L_j/2) \right ]
+
::<math>L_{\rm E}(i) = 2 \cdot {\rm tanh}^{-1} \hspace{0.1cm} \left [  \prod\limits_{j \ne i}^{n} \hspace{0.15cm}{\rm tanh}(L_j/2) \right ]
 
\hspace{0.3cm}{\rm mit}\hspace{0.3cm}L_j = L_{\rm APP}(j)
 
\hspace{0.3cm}{\rm mit}\hspace{0.3cm}L_j = L_{\rm APP}(j)
  \hspace{0.05cm}.</math>
+
  \hspace{0.05cm}.</math>}}
  
{{Beispiel}}''':''' Wir gehen vom <i>Single Parity&ndash;check Code</i> mit $n = 3, \ k = 2$ &nbsp;&#8658;&nbsp; kurz ${\rm SPC} \ (3, \ 2, \ 2)$ aus. Die $2^k = 4$ gültigen Codeworte $\underline{x} = \{x_1, x_2, x_3\}$ lauten bei bipolarer Beschreibung &nbsp;&#8658;&nbsp; $x_i &#8712; \{&plusmn;1\}$:
 
  
:<math> \underline{x}_0 \hspace{-0.05cm}=\hspace{-0.05cm} (+1\hspace{-0.03cm},\hspace{-0.05cm}+1\hspace{-0.03cm},\hspace{-0.05cm}+1)\hspace{-0.05cm}, \hspace{0.3cm}
+
{{GraueBox|TEXT=
\underline{x}_1  \hspace{-0.05cm}=\hspace{-0.05cm} (+1\hspace{-0.03cm},\hspace{-0.05cm} -1\hspace{-0.03cm},\hspace{-0.05cm} -1)\hspace{-0.05cm}, \hspace{0.3cm}
+
$\text{Beispiel 6:}$&nbsp; Wir gehen vom&nbsp; <i>Single Parity&ndash;check Code</i>&nbsp; mit&nbsp; $n = 3, \ k = 2$ &nbsp; &#8658; &nbsp; kurz&nbsp; ${\rm SPC} \ (3, \ 2, \ 2)$&nbsp; aus.
\underline{x}_2  \hspace{-0.05cm}=\hspace{-0.05cm} (-1\hspace{-0.03cm},\hspace{-0.05cm} +1\hspace{-0.03cm},\hspace{-0.05cm} -1)\hspace{-0.05cm}, \hspace{0.3cm}
+
\underline{x}_3  \hspace{-0.05cm}=\hspace{-0.05cm} (-1\hspace{-0.03cm},\hspace{-0.05cm} -1\hspace{-0.03cm},\hspace{-0.05cm} +1)\hspace{-0.05cm}. </math>
+
Die&nbsp; $2^k = 4$&nbsp; gültigen Codeworte&nbsp; $\underline{x} = \{x_1, x_2, x_3\}$&nbsp; lauten bei bipolarer Beschreibung &nbsp; &#8658; &nbsp; $x_i &#8712; \{&plusmn;1\}$:
 +
[[File:P ID3098 KC T 4 1 S3e v1.png|right|frame|Decodierbeispiel für den&nbsp; ${\rm SPC} \ (3, 2, 2)$|class=fit]]
  
Bei diesem Code ist also das Produkt $x_1 \cdot x_2 \cdot x_3$ stets positiv.<br>
+
:$$ \underline{x}_0 \hspace{-0.05cm}=\hspace{-0.05cm} (+1\hspace{-0.03cm},\hspace{-0.05cm}+1\hspace{-0.03cm},\hspace{-0.05cm}+1)\hspace{-0.05cm}, $$
 +
:$$\underline{x}_1  \hspace{-0.05cm}=\hspace{-0.05cm} (+1\hspace{-0.03cm},\hspace{-0.05cm} -1\hspace{-0.03cm},\hspace{-0.05cm} -1)\hspace{-0.05cm}, $$
 +
:$$\underline{x}_2  \hspace{-0.05cm}=\hspace{-0.05cm} (-1\hspace{-0.03cm},\hspace{-0.05cm} +1\hspace{-0.03cm},\hspace{-0.05cm} -1)\hspace{-0.05cm}, $$
 +
:$$\underline{x}_3  \hspace{-0.05cm}=\hspace{-0.05cm} (-1\hspace{-0.03cm},\hspace{-0.05cm} -1\hspace{-0.03cm},\hspace{-0.05cm} +1)\hspace{-0.05cm}. $$
  
[[File:P ID3098 KC T 4 1 S3e v1.png|center|frame|Decodierbeispiel für den ${\rm SPC} \ (3, 2)$|class=fit]]<br>
+
Bei diesem Code ist also das Produkt&nbsp; $x_1 \cdot x_2 \cdot x_3$&nbsp; stets positiv.<br>
  
Die Tabelle zeigt den Decodiervorgang für $\underline{L}_{\rm APP} = (+2.0, +0.4, \, &ndash;1.6)$. Die harte Entscheidung nach den Vorzeichen von $L_{\rm APP}(i)$ ergäbe hier $(+1, +1, \, &ndash;1)$, also kein gültiges Codewort des ${\rm SP}(3, \ 2, \ 2)$.<br>
+
Die obige Tabelle zeigt den Decodiervorgang für&nbsp; $\underline{L}_{\rm APP} = (+2.0, +0.4, \, &ndash;1.6)$. Die harte Entscheidung nach den Vorzeichen von&nbsp; $L_{\rm APP}(i)$&nbsp; ergäbe hier&nbsp; $(+1, +1, \, -1)$, also kein gültiges Codewort des&nbsp; ${\rm SP}(3, \ 2, \ 2)$.<br>
  
Rechts sind in der Tabelle die dazugehörigen extrinsischen $L$&ndash;Werte eingetragen:<br>
+
Rechts in der Tabelle sind die dazugehörigen extrinsischen&nbsp; $L$&ndash;Werte eingetragen:<br>
  
:<math>L_{\rm E}(1) \hspace{-0.15cm}  = \hspace{-0.15cm}  2 \cdot {\rm tanh}^{-1} \hspace{0.05cm}
+
::<math>L_{\rm E}(1) = 2 \cdot {\rm tanh}^{-1} \hspace{0.05cm}
 
  \left [  {\rm tanh} (0.2) \cdot {\rm tanh} (-0.8)\hspace{0.05cm}\right ] = -0.131\hspace{0.05cm}, </math>
 
  \left [  {\rm tanh} (0.2) \cdot {\rm tanh} (-0.8)\hspace{0.05cm}\right ] = -0.131\hspace{0.05cm}, </math>
:<math>L_{\rm E}(2) \hspace{-0.15cm}  = \hspace{-0.15cm}2 \cdot {\rm tanh}^{-1} \hspace{0.05cm}
+
::<math>L_{\rm E}(2) =2 \cdot {\rm tanh}^{-1} \hspace{0.05cm}
 
  \left [  {\rm tanh} (1.0) \cdot {\rm tanh} (-0.8)\hspace{0.05cm}\right ] = -0.518\hspace{0.05cm}, </math>
 
  \left [  {\rm tanh} (1.0) \cdot {\rm tanh} (-0.8)\hspace{0.05cm}\right ] = -0.518\hspace{0.05cm}, </math>
:<math>L_{\rm E}(3) \hspace{-0.15cm}  = \hspace{-0.15cm}2 \cdot {\rm tanh}^{-1} \hspace{0.05cm}
+
::<math>L_{\rm E}(3) =2 \cdot {\rm tanh}^{-1} \hspace{0.05cm}
 
  \left [  {\rm tanh} (1.0) \cdot {\rm tanh} (0.2)\hspace{0.05cm}\right ] = +0.151\hspace{0.05cm}.</math>
 
  \left [  {\rm tanh} (1.0) \cdot {\rm tanh} (0.2)\hspace{0.05cm}\right ] = +0.151\hspace{0.05cm}.</math>
  
 
Die zweite Gleichung lässt sich wie folgt interpretieren:
 
Die zweite Gleichung lässt sich wie folgt interpretieren:
* $L_{\rm APP}(1) = +2.0$ und $L_{\rm APP}(3) = \, &ndash;1.6$ sagen aus, dass Bit 1 eher &bdquo;$+1$&rdquo; als &bdquo;$&ndash;1$&rdquo; ist und Bit 3 eher &bdquo;$&ndash;1$&rdquo; als &bdquo;$+1$&rdquo;. Die Zuverlässigkeit (Betrag) ist beim ersten Bit etwas größer als beim dritten.<br>
+
* $L_{\rm APP}(1) = +2.0$&nbsp; und&nbsp; $L_{\rm APP}(3) = \, -1.6$&nbsp; sagen aus, dass das erste Bit eher &nbsp;$+1$&nbsp; als &nbsp;$-1$&nbsp; ist und das dritte Bit eher &nbsp;$-1$&nbsp; als &nbsp;$+1$. Die Zuverlässigkeit (der Betrag) ist beim ersten Bit etwas größer als beim dritten.<br>
  
*Die extrinsische Information $L_{\rm E}(2) = \, &ndash;0.518$ berücksichtigt nur die Informationen von Bit 1 und Bit 3 über Bit 2. Aus deren Sicht ist das zweite Bit eine &bdquo;$&ndash;1$&rdquo; mit der Zuverlässigkeit $0.518$.<br>
+
*Die extrinsische Information&nbsp; $L_{\rm E}(2) = \, -0.518$ berücksichtigt nur die Informationen von Bit 1 und Bit 3 über Bit 2. Aus deren Sicht ist das zweite Bit eine &nbsp;$-1$&nbsp; mit der Zuverlässigkeit&nbsp; $0.518$.<br>
  
*Der vom Empfangswert $y_2$ abgeleitete $L$&ndash;Wert &nbsp;&#8658;&nbsp; $L_{\rm APP}(2) = +0.4$ hat für das zweite Bit eine &bdquo;$+1$&rdquo; vermuten lassen. Die Diskrepanz wird hier bereits in der Iteration $I = 1$ aufgelöst.<br>
+
*Der vom Empfangswert&nbsp; $y_2$&nbsp; abgeleitete&nbsp; $L$&ndash;Wert &nbsp; &#8658; &nbsp; $L_{\rm APP}(2) = +0.4$&nbsp; hat für das zweite Bit eine &nbsp;$+1$&nbsp; vermuten lassen. Die Diskrepanz wird hier bereits in der Iteration&nbsp; $I = 1$&nbsp; aufgelöst.<br>
  
*Entschieden wird hier für das Codewort $\underline{x}_1$. Bei $0.518 < L_{\rm APP}(2) < 1.6$ würde das Ergebnis $\underline{x}_1$ erst nach mehreren Iterationen vorliegen. Für $L_{\rm APP}(2) > 1.6$ liefert der Decoder dagegen $\underline{x}_0$.{{end}}<br>
+
*Entschieden wird hier für das Codewort&nbsp; $\underline{x}_1$. Bei&nbsp; $0.518 < L_{\rm APP}(2) < 1.6$&nbsp; würde das Ergebnis&nbsp; $\underline{x}_1$&nbsp; erst nach mehreren Iterationen vorliegen. Für&nbsp; $L_{\rm APP}(2) > 1.6$&nbsp; liefert der Decoder dagegen&nbsp; $\underline{x}_0$.}}<br>
  
 
== BCJR–Decodierung: Vorwärts–Rückwärts–Algorithmus ==
 
== BCJR–Decodierung: Vorwärts–Rückwärts–Algorithmus ==
 
<br>
 
<br>
Ein Beispiel für die iterative Decodierung von Faltungscodes ist der <i>BCJR&ndash;Algorithmus</i>, benannt nach dessen Erfindern L. R. Bahl, J. Cocke, F. Jelinek und J. Raviv &nbsp;&#8658;&nbsp; [BCJR74]<ref>Bahl, L.R.; Cocke, J.; Jelinek, F.; Raviv, J.: ''Optimal Decoding of Linear Codes for Minimizing Symbol Error Rate.'' In: IEEE Transactions on Information Theory, Vol. IT-20, S. 284-287, 1974.</ref>. Der Algorithmus weist viele Parallelen zur sieben Jahren älteren Viterbi&ndash;Decodierung auf, doch auch signifikante Unterschiede:
+
Ein Beispiel für die iterative Decodierung von Faltungscodes ist der&nbsp; <i>BCJR&ndash;Algorithmus</i>, benannt nach dessen Erfindern L. R. Bahl, J. Cocke, F. Jelinek und J. Raviv &nbsp;&#8658;&nbsp; [BCJR74]<ref name='BCJR74'>Bahl, L.R.; Cocke, J.; Jelinek, F.; Raviv, J.: ''Optimal Decoding of Linear Codes for Minimizing Symbol Error Rate.'' In: IEEE Transactions on Information Theory, Vol. IT-20, S. 284-287, 1974.</ref>. Der Algorithmus weist viele Parallelen zur sieben Jahren älteren Viterbi&ndash;Decodierung auf, doch auch einige signifikante Unterschiede:
*Während Viterbi die Gesamtsequenz schätzt &nbsp;&#8658;&nbsp; [[Kanalcodierung/Klassifizierung_von_Signalen#MAP.E2.80.93_und_ML.E2.80.93Kriterium_.282.29| block&ndash;wise Maximum Likelihood]], minimiert der BCJR&ndash;Algorithmus die Bitfehlerwahrscheinlichkeit &nbsp;&#8658;&nbsp; [http://en.lntwww.de/Kanalcodierung/Klassifizierung_von_Signalen#MAP.E2.80.93_und_ML.E2.80.93Kriterium_.282.29 bit&ndash;wise MAP.]<br>
+
*Während Viterbi die Gesamtsequenz schätzt &nbsp; &#8658; &nbsp; [[Channel_Coding/Kanalmodelle_und_Entscheiderstrukturen#Definitionen_der_verschiedenen_Optimalempf.C3.A4nger| $\text{block&ndash;wise Maximum Likelihood}$]], minimiert der BCJR&ndash;Algorithmus die Bitfehlerwahrscheinlichkeit &nbsp; &#8658; &nbsp; [[Channel_Coding/Kanalmodelle_und_Entscheiderstrukturen#Definitionen_der_verschiedenen_Optimalempf.C3.A4nger|$\text{ bit&ndash;wise MAP}$]].<br>
  
 
*Der Viterbi&ndash;Algorithmus kann (in seiner ursprünglichen Form) keine Softinformation verarbeiten. Dagegen gibt der BCJR&ndash;Algorithmus bei jeder Iteration für jedes einzelne Symbol (Bit) einen Zuverlässigkeitswert an, der bei späteren Iterationen berücksichtigt wird.<br>
 
*Der Viterbi&ndash;Algorithmus kann (in seiner ursprünglichen Form) keine Softinformation verarbeiten. Dagegen gibt der BCJR&ndash;Algorithmus bei jeder Iteration für jedes einzelne Symbol (Bit) einen Zuverlässigkeitswert an, der bei späteren Iterationen berücksichtigt wird.<br>
  
[[File:P ID3024 KC T 4 1 S5 v2.png|center|frame|Gegenüberstellung von Viterbi– und BCJR–Algorithmus|class=fit]]<br>
 
  
Die Abbildung soll &ndash; fast unzulässig vereinfacht &ndash; die unterschiedliche Vorgehensweise von Viterbi&ndash;Algorithmus (links) und BCJR&ndash;Algorithmus (rechts) verdeutlichen. Zugrunde liegt ein Faltungscode mit dem Gedächtnis $m = 1$ und der Länge $L = 4$ &nbsp;&#8658;&nbsp; Gesamtlänge $L' = 5$ (mit Terminierung).
+
[[File:P ID3024 KC T 4 1 S5 v2.png|center|frame|Gegenüberstellung von Viterbi– und BCJR–Algorithmus|class=fit]]
*Der Viterbi&ndash;Algorithmus sucht und findet den wahrscheinlichsten Pfad von $\Gamma_0(S_0)$ nach $\Gamma_5(S_0)$, nämlich $S_0 &#8594; S_1 &#8594; S_0 &#8594; S_0 &#8594; S_1$. Wir verweisen auf die Musterlösung zur Aufgabe Z3.9.<br><br>
+
 
 +
Die Abbildung soll &ndash; fast unzulässig vereinfacht &ndash; die unterschiedliche Vorgehensweise von Viterbi&ndash;Algorithmus (links) und BCJR&ndash;Algorithmus (rechts) verdeutlichen. Zugrunde liegt ein Faltungscode mit dem Gedächtnis&nbsp; $m = 1$&nbsp; und der Länge&nbsp; $L = 4$ &nbsp; &#8658; &nbsp; Gesamtlänge (mit Terminierung)&nbsp; $L' = 5$.
 +
*Der Viterbi&ndash;Algorithmus sucht und findet den wahrscheinlichsten Pfad von&nbsp; ${\it \Gamma}_0(S_0)$&nbsp; nach&nbsp; ${\it \Gamma}_5(S_0)$, nämlich&nbsp; $S_0 &#8594; S_1 &#8594; S_0 &#8594; S_0 &#8594; S_1&#8594; S_0 $. Wir verweisen auf die Musterlösung zur&nbsp; [[Aufgaben:Aufgabe_3.09Z:_Nochmals_Viterbi–Algorithmus|Aufgabe 3.9Z]].<br><br>
  
Die Skizze für den BCJR&ndash;Algorithmus verdeutlicht die Gewinnung des extrinsischen $L$&ndash;Wertes für das dritte Symbol &nbsp;&#8658;&nbsp; $L_{\rm E}(3)$. Der relevante Bereich im Trellis ist schraffiert:
+
Die Skizze für den BCJR&ndash;Algorithmus verdeutlicht die Gewinnung des extrinsischen&nbsp; $L$&ndash;Wertes für das dritte Symbol &nbsp; &#8658; &nbsp; $L_{\rm E}(3)$. Der relevante Bereich im Trellis ist schraffiert:
*Bei der Abarbeitung des Trellisdiagramms in Vorwärtsrichtung  gewinnt man &ndash; in gleicher Weise wie bei Viterbi &ndash; die Metriken $\alpha_1, \ \alpha_2, \ ... , \ \alpha_5$. Zur Berechnung von $L_{\rm E}(3)$ benötigt man hiervon $\alpha_2$.<br>
+
* Bei der Abarbeitung des Trellisdiagramms in Vorwärtsrichtung  gewinnt man &ndash; in gleicher Weise wie bei Viterbi &ndash; die Metriken&nbsp; $\alpha_1, \ \alpha_2, \ \text{...}\hspace{0.05cm} , \ \alpha_5$. Zur Berechnung von&nbsp; $L_{\rm E}(3)$&nbsp; benötigt man hiervon&nbsp; $\alpha_2$.<br>
  
*Anschließend durchläuft man das Trellisdiagramm rückwärts (also von rechts nach links) und erhält damit die Metriken $\beta_4, \ \beta_3, \ ... , \ \beta_0$ entsprechend der unteren Skizze.<br>
+
* Anschließend durchläuft man das Trellisdiagramm rückwärts (also von rechts nach links) und erhält damit die Metriken&nbsp; $\beta_4, \ \beta_3, \ \text{...}\hspace{0.05cm} , \ \beta_0$&nbsp; entsprechend der unteren Skizze.<br>
  
*Der gesuchte extrinsische $L$&ndash;Wert $L_{\rm E}(3)$ ergibt sich aus den Metriken $\alpha_2$ (in Vorwärtsrichtung) und $\beta_3$ (in Rückwärtsrichtung) sowie der Apriori&ndash;Information $\gamma_3$ über das Symbol $i = 3$.<br>
+
* Der gesuchte extrinsische&nbsp; $L$&ndash;Wert&nbsp; $L_{\rm E}(3)$&nbsp; ergibt sich aus den Metriken&nbsp; $\alpha_2$&nbsp; (in Vorwärtsrichtung) und&nbsp; $\beta_3$&nbsp; (in Rückwärtsrichtung) sowie der Apriori&ndash;Information&nbsp; $\gamma_3$&nbsp; über das Symbol&nbsp; $i = 3$.<br>
  
 
== Grundstruktur von verketteten Codiersystemen ==
 
== Grundstruktur von verketteten Codiersystemen ==
 
<br>
 
<br>
Die wichtigsten Kommunikationssysteme der letzten Jahre verwenden zwei unterschiedliche Kanalcodes. Man spricht dann von <span style="font-weight: bold;">verketteten Codiersystemen</span> (englisch: <i>Concatenated Codes</i>). Auch bei relativ kurzen Komponentencodes <i>C</i><sub>1</sub> und <i>C</i><sub>2</sub>  ergibt sich für den verketteten Code <i>C</i> eine hinreichend große Codewortlänge <i>n</i>, die ja bekanntlich erforderlich ist, um sich der Kanalkapazität anzunähern.<br>
+
Die wichtigsten Kommunikationssysteme der letzten Jahre verwenden zwei unterschiedliche Kanalcodes. Man spricht dann von&nbsp; '''verketteten Codiersystemen'''&nbsp; (englisch:&nbsp; <i>Concatenated Codes</i>). Auch bei relativ kurzen Komponentencodes&nbsp; $\mathcal{C}_1$&nbsp; und&nbsp; $\mathcal{C}_2$&nbsp; ergibt sich für den verketteten Code&nbsp; $\mathcal{C}$&nbsp; eine hinreichend große Codewortlänge&nbsp; $n$, die ja bekanntlich erforderlich ist, um sich der Kanalkapazität anzunähern.<br>
  
 
Zunächst seien einige Beispiele aus dem Mobilfunk genannt:
 
Zunächst seien einige Beispiele aus dem Mobilfunk genannt:
*Bei GSM (<i>Global System for Mobile Communications</i>, zweite Mobilfunkgeneration) wird zunächst die Datenbitrate von 9.6 kbit/s auf 12 kbit/s erhöht, um auch in leitungsvermittelten Netzen eine Fehlererkennung zu ermöglichen. Anschließend folgt ein punktierter Faltungscode mit der Ausgangsbitrate 22.8 kbit/s. Die Gesamtcoderate beträgt somit etwa 42.1%.
+
*Bei&nbsp; [[Examples_of_Communication_Systems/Allgemeine_Beschreibung_von_GSM#.23_.C3.9CBERBLICK_ZUM_DRITTEN_HAUPTKAPITEL_.23|GSM]]&nbsp; (<i>Global System for Mobile Communications</i>, zweite Mobilfunkgeneration) wird zunächst die Datenbitrate von&nbsp; $9.6 \ \rm kbit/s$&nbsp; auf&nbsp; $12 \ \rm kbit/s$&nbsp; erhöht, um auch in leitungsvermittelten Netzen eine Fehlererkennung zu ermöglichen. Anschließend folgt ein punktierter Faltungscode mit der Ausgangsbitrate&nbsp; $22.8 \ \rm kbit/s$. Die Gesamtcoderate beträgt somit etwa&nbsp; $42.1\%$.
 +
 
 +
*Beim 3G&ndash;Mobilfunksystem&nbsp; [[Examples_of_Communication_Systems/Allgemeine_Beschreibung_von_UMTS#.23_.C3.9CBERBLICK_ZUM_VIERTEN_HAUPTKAPITEL_.23|UMTS]]&nbsp; (<i>Universal Mobile Telecommunications System</i>) verwendet man je nach den Randbedingungen (guter/schlechter Kanal, wenige/viele Teilnehmer in der Zelle) einen&nbsp; [[Channel_Coding/Grundlagen_der_Faltungscodierung#.23_.C3.9CBERBLICK_ZUM_DRITTEN_HAUPTKAPITEL_.23|Faltungscode]]&nbsp; oder einen&nbsp; [[Channel_Coding/Grundlegendes_zu_den_Turbocodes#Grundstruktur_eines_Turbocodes| Turbocode]]&nbsp; (darunter versteht man per se die Verkettung zweier Faltungscodierer). Beim 4G&ndash;Mobilfunksystem&nbsp; [[Mobile_Communications/Allgemeines_zum_Mobilfunkstandard_LTE#.23_.C3.9CBERSICHT_ZUM_VIERTEN_HAUPTKAPITEL_.23|LTE]]&nbsp; (<i>Long Term Evolution</i>) verwendet man für kurze Kontrollsignale einen Faltungscode  und für die längeren Payload-Daten einen Turbocode.<br>
  
*Beim 3G&ndash;Mobilfunksystem UMTS (<i>Universal Mobile Telecommunications System</i>) verwendet man je nach den Randbedingungen (guter/schlechter Kanal, wenige/viele Teilnehmer in der Zelle) einen Faltungscode oder einen [http://en.lntwww.de/Kanalcodierung/Grundlegendes_zu_den_Turbocodes#Grundstruktur_eines_Turbocodes_.281.29 Turbocode] (darunter versteht man per se die Verkettung zweier Faltungscodierer). Beim 4G&ndash;Mobilfunksystem LTE (<i>Long Term Evolution</i>) verwendet man für kurze Kontrollsignale einen Faltungscode  und für die längeren Payload-Daten einen Turbocode.<br>
 
  
[[File:P ID2998 KC T 4 1 S6 v1.png|Parallel verkettetes Codiersystem|class=fit]]<br>
+
[[File:P ID2998 KC T 4 1 S6 v1.png|center|frame|Parallel verkettetes Codiersystem|class=fit]]
  
Die Grafik zeigt die Grundstruktur eines parallel verketteten Codiersystems. Alle Vektoren bestehen aus <i>n</i> Elementen: <u><i>L</i></u> = (<i>L</i>(1), ... , <i>L</i>(<i>n</i>)). Die Berechnung aller <i>L</i>&ndash;Werte geschieht also auf Symbolebene. Nicht dargestellt ist hier der [http://en.lntwww.de/Kanalcodierung/Grundlegendes_zu_den_Turbocodes#Zweite_Voraussetzung_f.C3.BCr_Turbocodes:_Interleaving Interleaver,] der zum Beispiel bei den Turbocodes obligatorisch ist.
+
Die Grafik zeigt die Grundstruktur eines parallel verketteten Codiersystems. Alle Vektoren bestehen aus&nbsp; $n$&nbsp; Elementen:&nbsp; $\underline{L} = (L(1), \ \text{...}\hspace{0.05cm} , \ L(n))$. Die Berechnung aller&nbsp; $L$&ndash;Werte geschieht also auf Symbolebene. Nicht dargestellt ist hier der&nbsp; [[Channel_Coding/Grundlegendes_zu_den_Turbocodes#Zweite_Voraussetzung_f.C3.BCr_Turbocodes:_Interleaving| Interleaver]], der zum Beispiel bei den Turbocodes obligatorisch ist.
*Die Codesequenzen <u><i>x</i></u><sub>1</sub> und <u><i>x</i></u><sub>2</sub> werden zur gemeinsamen Übertragung über den Kanal durch einen Multiplexer zum Vektor <u><i>x</i></u> zusammengefügt. Am Empfänger wird die Sequenz <u><i>y</i></u> wieder in die Einzelteile <u><i>y</i></u><sub>1</sub> und <u><i>y</i></u><sub>2</sub> zerlegt. Daraus werden die Kanal&ndash;<i>L</i>&ndash;Werte <u><i>L</i></u><sub>K,1</sub> und <u><i>L</i></u><sub>K,2</sub> gebildet.<br>
+
*Die Codesequenzen&nbsp; $\underline{x}_1$&nbsp; und&nbsp; $\underline{x}_2$&nbsp; werden zur gemeinsamen Übertragung über den Kanal durch einen Multiplexer zum Vektor&nbsp; $\underline{x}$&nbsp; zusammengefügt. Am Empfänger wird die Sequenz&nbsp; $\underline{y}$&nbsp; wieder in die Einzelteile&nbsp; $\underline{y}_1$&nbsp; und&nbsp; $\underline{y}_2$&nbsp; zerlegt. Daraus werden die Kanal&ndash;$L$&ndash;Werte&nbsp; $\underline{L}_{\rm K,\hspace{0.05cm}1}&nbsp;$ und&nbsp; $\underline{L}_{\rm K,\hspace{0.05cm}2}$&nbsp; gebildet.<br>
  
*Der symbolweise Decoder ermittelt entsprechend der vorne beschriebenen [http://en.lntwww.de/Kanalcodierung/Soft%E2%80%93in_Soft%E2%80%93out_Decoder#Zur_Berechnung_der_extrinsischen_L.E2.80.93Werte_.281.29 Vorgehensweise] die extrinsischen <i>L</i>&ndash;Werte <u><i>L</i></u><sub>E,1</sub> und <u><i>L</i></u><sub>E,2</sub>, die gleichzeitig die Apriori&ndash;Informationen <u><i>L</i></u><sub>A,2</sub> und <u><i>L</i></u><sub>A,1</sub> für den jeweils anderen Decoder darstellen. <br>
+
*Der symbolweise Decoder ermittelt entsprechend der vorne beschriebenen&nbsp; [[Channel_Coding/Soft%E2%80%93in_Soft%E2%80%93out_Decoder#Zur_Berechnung_der_extrinsischen_L.E2.80.93Werte| Vorgehensweise]]&nbsp; die extrinsischen $L$&ndash;Werte&nbsp; $\underline{L}_{\rm E,\hspace{0.05cm} 1}$&nbsp; und&nbsp; $\underline{L}_{\rm E,\hspace{0.05cm} 2}$, die gleichzeitig die Apriori&ndash;Informationen&nbsp; $\underline{L}_{\rm A,\hspace{0.05cm} 2}$&nbsp; und&nbsp; $\underline{L}_{\rm A,\hspace{0.05cm} 1}$&nbsp; für den jeweils anderen Decoder darstellen. <br>
  
*Nach ausreichend vielen Iterationen (also dann, wenn ein Abbruchkriterium erfüllt ist) liegt am Decoderausgang der Vektor der Aposteriori&ndash;Werte &nbsp;&#8658;&nbsp; <u><i>L</i></u><sub>APP</sub> an. Im Beispiel wird willkürlich der Wert im oberen Zweig genommen. Möglich wäre aber auch der untere <i>L</i>&ndash;Wert.<br><br>
+
*Nach ausreichend vielen Iterationen (also dann, wenn ein Abbruchkriterium erfüllt ist) liegt am Decoderausgang der Vektor der Aposteriori&ndash;Werte &nbsp; &#8658; &nbsp; $\underline{L}_{\rm APP}$&nbsp; an. Im Beispiel wird willkürlich der Wert im oberen Zweig genommen. Möglich wäre aber auch der untere&nbsp; $L$&ndash;Wert.<br><br>
  
Das obige Modell gilt insbesondere auch für die Decodierung der Turbo&ndash;Codes gemäß [http://en.lntwww.de/Kanalcodierung/Grundlegendes_zu_den_Turbocodes#Grundstruktur_eines_Turbocodes_.281.29 Kapitel 4.3.]<br>
+
Das obige Modell gilt insbesondere auch für die Decodierung der Turbo&ndash;Codes gemäß dem Kapitel&nbsp; [[Channel_Coding/Grundlegendes_zu_den_Turbocodes#Grundstruktur_eines_Turbocodes| Grundlegendes zu den Turbocodes]].<br>
  
== Aufgaben ==
+
== Aufgaben zum Kapitel==
 
<br>
 
<br>
[[Aufgaben:4.1 Zum „Log Likelihood Ratio”|A4.1 Zum „Log Likelihood Ratio”]]
+
[[Aufgaben:Aufgabe_4.1:_Zum_„Log_Likelihood_Ratio”|Aufgabe 4.1: Zum „Log Likelihood Ratio”]]
 +
 
 +
[[Aufgaben:Aufgabe_4.1Z:_L–Werte_des_BEC–Modells|Aufgabe 4.1Z: L–Werte des BEC–Modells]]
 +
 
 +
[[Aufgaben:Aufgabe_4.2:_Kanal–LLR_bei_AWGN|Aufgabe 4.2: Kanal–LLR bei AWGN]]
  
[[Zusatzaufgaben:4.1 L–Werte des BEC–Modells]]
+
[[Aufgaben:Aufgabe_4.3:_Iterative_Decodierung_beim_BSC|Aufgabe 4.3: Iterative Decodierung beim BSC]]
  
[[Aufgaben:4.2 Kanal–LLR bei AWGN|A4.2 Kanal–LLR bei AWGN]]
+
[[Aufgaben:Aufgabe_4.3Z:_Umrechnungen_von_L–Wert_und_S–Wert|Aufgabe 4.3Z: Umrechnungen von L–Wert und S–Wert]]
  
[[Aufgaben:4.3 Iterative Decodierung beim BSC|A4.3 Iterative Decodierung beim BSC]]
+
[[Aufgaben:Aufgabe_4.4:_Extrinsische_L–Werte_beim_SPC|Aufgabe 4.4: Extrinsische L–Werte beim SPC]]
  
[[Zusatzaufgaben:4.3 Umrechnung von L–Wert und S–Wert]]
+
[[Aufgaben:Aufgabe_4.4Z:_Ergänzung_zur_Aufgabe_4.4|Aufgabe 4.4Z: Ergänzung zur Aufgabe 4.4]]
  
[[Aufgaben:4.4 Extrinsische L–Werte beim SPC|A4.4 Extrinsische L–Werte beim SPC]]
+
[[Aufgaben:Aufgabe_4.5:_Nochmals_zu_den_extrinsischen_L–Werten|Aufgabe 4.5: Nochmals zu den extrinsischen L–Werten]]
  
[[Zusatzaufgaben:4.4 Ergänzung zur Aufgabe A4.4]]
+
[[Aufgaben:Aufgabe_4.5Z:_Tangens_Hyperbolikus_und_Inverse|Aufgabe 4.5Z: Tangens Hyperbolikus und Inverse]]
  
 
==Quellenverzeichnis==
 
==Quellenverzeichnis==

Revision as of 15:19, 28 May 2021

# ÜBERBLICK ZUM VIERTEN HAUPTKAPITEL #


Das letzte Hauptkapitel des Kanalcodierungsbuches beschreibt  iterative Decodierverfahren, wie sie in den meisten heutigen (2017) Kommunikationssystemen eingesetzt werden. Dies hat folgende Gründe:

  • Um sich der Kanalkapazität anzunähern, benötigt man sehr lange Codes.
  • Für lange Codes ist aber eine blockweise  Maximum–Likelihood–Decodierung  nahezu unmöglich.


Die Decoder–Komplexität lässt sich bei nahezu gleicher Qualität deutlich herabsetzen, wenn man zwei (oder mehrere) kurze Kanalcodes miteinander verknüpft und beim Empfänger die jeweils neu gewonnene (Soft–)Information in mehreren Schritten – also iterativ – zwischen den Decodern austauscht.

Der Durchbruch auf dem Gebiet gelang Anfang der 1990er Jahre mit der Erfindung der  Turbo–Codes  durch  Claude Berrou  und kurz darauf mit der Wiederentdeckung der  Low–density Parity–check Codes  durch  David J. C. MacKay  und  Radford M. Neal, nachdem die schon 1961 von  Robert G. Gallager  entwickelten LDPC–Codes zwischenzeitlich in Vergessenheit geraten waren.

Im Einzelnen werden im vierten Hauptkapitel behandelt:

  • Eine Gegenüberstellung von  Hard Decision  und  Soft Decision,
  • die Quantifizierung von  Zuverlässigkeitsinformation  durch  Log Likelihood Ratios (LLR),
  • das Prinzip der symbolweisen  Soft–in Soft–out  (SISO) Decodierung,
  • die Definition von  Apriori–L–WertAposteriori–L–Wert  und  extrinsischem L–Wert,
  • die Grundstruktur von  seriell verketteten  bzw.  parallel verketteten  Codiersystemen,
  • die Eigenschaften von  Produkt–Codes  und deren  Hard Decision Decodierung,
  • die Grundstruktur, der Decodieralgorithmus und die Leistungsfähigkeit der  Turbo–Codes,
  • Grundlegendes zu den  Low–density Parity–check Codes  und deren Anwendungen.


Hard Decision vs. Soft Decision


Zur Hinleitung auf die hier behandelte Thematik betrachten wir das folgende Nachrichtenübertragungssystem mit Codierung.

Betrachtetes Nachrichtenübertragungssystem mit Codierung

Im Weiteren werden alle Symbole in bipolarer Darstellung angegeben:   "$0$"  →  "$+1$"  und  "$1$"  →  "$-1$".

  • Die Symbolfolge  $\underline{u} = (u_1, \ u_2)$  wird der Coderfolge  $\underline{x} = (x_1, \ x_2, \ x_3) = (u_1, \ u_2, \ p)$  zugeordnet, wobei für das Paritybit  $p = u_1 ⊕ u_2$  gilt   ⇒   Single Parity–check Code   ⇒   ${\rm SPC} (3, 2, 2)$.
  • Der  AWGN–Kanal  verändert die Binärsymbole  $x_i ∈ \{+1, \ –1\}$  zu reellwertigen Ausgangswerten  $y_i$, zum Beispiel gemäß  $\text{Kanal 4}$  der unteren Tabelle:   $x_1 = +1$   ⇒   $y_1 = +0.9$,   $x_2 = \, -1$   ⇒   $y_2 = +0.1$  und  $x_3 = \, -1$   ⇒   $y_3 = +0.1$.
  • Die Decodierung geschieht gemäß dem Kriterium  Maximum-Likelihood  $\text{(blockwise ML)}$, wobei zwischen  Hard Decision  $\rm {(ML–HD)}$  und  Soft Decision  $\rm {(ML–SD)}$  zu unterscheiden ist.
  • Das gesamte Blockschaltbild entspricht  $\rm ML–HD$. Hier werden zur Decodierung nur die Vorzeichen der AWGN–Ausgangswerte   ⇒   $y_{\rm HD, \ \it i} = {\rm sign}\big [y_{\rm SD, \ \it i}\big ]$  ausgewertet. Bei  Soft Decision  $\rm {(ML–SD)}$  verzichtet man auf den schraffierten Block und wertet direkt die wertkontinuierlichen Eingangsgrößen  $y_{\rm SD, \ \it i}$  aus.


Gegenüberstellung von Hard Decision und Soft Decision

Für alle Spalten dieser Tabelle wird vorausgesetzt:

  • der Nachrichtenblock  $\underline{u} = (0, 1)$, bipolar darstellbar als  $(+1, \, –1)$,
  • der  ${\rm SPC} \ (3, 2)$–codierte Block  $\underline{x} = (0, 1, 1)$  bzw.  in Bipolardarstellung  $(+1, \, -1, \, -1)$.


Die vier Spalten unterscheiden sich also nur durch unterschiedliche AWGN–Realisierungen.

$\text{Definition:}$  Aus der Beispieltabelle erkennt man:

  • $\text{Hard Decision:}$   Die Symbolfolge  $\underline{v}_{\rm HD}$  ergibt sich aus den hart entschiedenen Kanalwerten  $\underline{y}_{\rm HD}$ (blaue Hinterlegung).
    Bei unserem Beispiel werden nur die Konstellationen gemäß  $\text{Kanal 1}$  und  $\text{Kanal 2}$  fehlerfrei decodiert.
  • $\text{Soft Decision:}$   Die Symbolfolge  $\underline{v}_{\rm SD}$  ergibt sich aus den "weichen" Kanalausgangswerten  $\underline{y}_{\rm SD}$ (grüne Hinterlegung).
    Nun wird in diesem Beispiel auch bei  $\text{Kanal 3}$  richtig entschieden.


Die Einträge in der obigen Beispieltabelle sind wie folgt zu interpretieren:

  • Bei idealem Kanal   ⇒   $\text{Kanal 1}$   ⇒   $\underline{x} = \underline{y}_{\rm SD} = \underline{y}_{\rm HD}$  gibt es keinen Unterschied zwischen der (blauen) herkömmlichen Hard Decision–Variante $\rm {(ML–HD)}$  und der (grünen) Soft Decision–Variante $\rm {(ML–SD)}$.
  • Die Einstellung entsprechend  $\text{Kanal 2}$  demonstriert geringe Signalverfälschungen. Wegen  $\underline{y}_{\rm HD} = \underline{x}$  (das heißt, dass der Kanal die Vorzeichen nicht verfälscht) liefert auch  $\rm ML–HD$  das richtige Ergebnis  $\underline{v}_{\rm HD} = \underline{u}$.
  • Beim  $\text{Kanal 3}$  gilt  $\underline{y}_{\rm HD} ≠ \underline{x}$  und es gibt auch keine  ${\rm SPC} \ (3, 2)$–Zuordnung  $\underline{u}$   ⇒   $\underline{y}_{\rm HD}$. Der ML–Decoder vermeldet hier durch die Ausgabe  $\underline{v}_{\rm HD} = \rm (E, \ E)$, dass er bei der Decodierung dieses Blocks gescheitert ist. "$\rm E$" steht für  Erasure  (deutsch:   Auslöschung).
  • Auch der  Soft Decision  Decoder erkennt, dass eine Decodierung anhand der Vorzeichen nicht funktioniert. Anhand der  $\underline{y}_{\rm SD}$–Werte erkennt er aber, dass mit großer Wahrscheinlichkeit das zweite Bit verfälscht wurde und entscheidet sich für die richtige Symbolfolge  $\underline{v}_{\rm SD} = (+1, \, -1) = \underline{u}$.
  • Bei  $\text{Kanal 4}$  werden durch den AWGN–Kanal sowohl die Vorzeichen von Bit 2 als auch von Bit 3 verändert, was zum Ergebnis  $\underline{v}_{\rm HD} = (+1, +1) ≠ \underline{u}(+1, \, -1)$  führt   ⇒   ein Blockfehler und gleichzeitig ein Bitfehler. Auch der Soft Decision Decoder liefert hier das gleiche falsche Ergebnis.

Die Decodiervariante "ML–SD" bietet gegenüber "ML–HD" zudem den Vorteil, dass man relativ einfach jedes Decodierergebnis mit einem Zuverlässigkeitswert versehen kann (in obiger Tabelle ist dieser allerdings nicht angegeben). Dieser Zuverlässigkeitswert

  • hätte bei  $\text{Kanal 1}$  seinen Maximalwert,
  • wäre bei  $\text{Kanal 2}$  deutlich kleiner,
  • läge bei  $\text{Kanal 3}$  und  $\text{Kanal 4}$  nahe bei Null.

Zuverlässigkeitsinformation – Log Likelihood Ratio


Es sei  $x ∈ \{+1, \, -1\}$  eine binäre Zufallsvariable mit den Wahrscheinlichkeiten  ${\rm Pr}(x = +1)$  und  ${\rm Pr}(x = \, -1)$. Für die Codierungstheorie erweist es sich als zweckmäßig hinsichtlich der Rechenzeiten, wenn man anstelle der Wahrscheinlichkeiten  ${\rm Pr}(x = ±1)$  den natürlichen Logarithmus des Quotienten heranzieht.

$\text{Definition:}$  Das  Log–Likelihood–Verhältnis  (kurz:   der $L$–Wert, englisch: Log–Likelihood Ratio, LLR)  der Zufallsgröße  $x ∈ \{+1, \, -1\}$  lautet:

\[L(x)={\rm ln} \hspace{0.15cm} \frac{ {\rm Pr}(x = +1)}{ {\rm Pr}(x = -1)}\hspace{0.05cm}.\]

Bei unipolarer/symbolhafter Darstellung  $(+1  →  0$   und   $-1  →  1)$  gilt entsprechend mit  $\xi ∈ \{0, \, 1\}$:

\[L(\xi)={\rm ln} \hspace{0.15cm} \frac{ {\rm Pr}(\xi = 0)}{ {\rm Pr}(\xi = 1)}\hspace{0.05cm}.\]


Nachfolgend ist der nichtlineare Zusammenhang zwischen  ${\rm Pr}(x = ±1)$  und  $L(x)$  angegeben. Ersetzt man  ${\rm Pr}(x = +1)$  durch  ${\rm Pr}(\xi = 0)$, so gibt die mittlere Zeile den  $L$–Wert der unipolaren Zufallsgröße  $\xi$ an.

Wahrscheinlichkeit und  $L$–Wert

Man erkennt:

  • Der wahrscheinlichere Zufallswert von  $x ∈ \{+1, \, -1\}$  ist durch das  Vorzeichen   ⇒   ${\rm sign} \ L(x)$  gegeben.
  • Dagegen gibt der  Betrag    ⇒   $|L(x)|$  die Zuverlässigkeit für das Ergebnis  ${\rm sign}(L(x))$  an.

BSC–Modell

$\text{Beispiel 1:}$  Wir betrachten das skizzierte  BSC–Modell  mit bipolarer Darstellung. Hier gilt mit der Verfälschungswahrscheinlichkeit  $\varepsilon = 0.1$  sowie den beiden Zufallsgrößen  $x ∈ \{+1, \, -1\}$  und  $y ∈ \{+1, \, -1\}$  am Eingang und Ausgang des Kanals:

\[L(y\hspace{0.05cm}\vert\hspace{0.05cm}x) = {\rm ln} \hspace{0.15cm} \frac{ {\rm Pr}(y\hspace{0.05cm}\vert\hspace{0.05cm}x = +1) }{ {\rm Pr}(y\hspace{0.05cm}\vert\hspace{0.05cm}x = -1)} = \left\{ \begin{array}{c} {\rm ln} \hspace{0.15cm} \big[(1 - \varepsilon)/\varepsilon \big]\\ {\rm ln} \hspace{0.15cm}\big [\varepsilon/(1 - \varepsilon)\big] \end{array} \right.\quad \begin{array}{*{1}c} {\rm f\ddot{u}r} \hspace{0.15cm} y = +1, \\ {\rm f\ddot{u}r} \hspace{0.15cm} y = -1. \\ \end{array}\]

Beispielsweise ergeben sich für  $\varepsilon = 0.1$  folgende Zahlenwerte (vergleiche obere Tabelle):

\[L(y = +1\hspace{0.05cm}\vert\hspace{0.05cm}x) = {\rm ln} \hspace{0.15cm} \frac{0.9}{0.1} = +2.197\hspace{0.05cm}, \hspace{0.8cm} L(y = -1\hspace{0.05cm}\vert\hspace{0.05cm}x) = -2.197\hspace{0.05cm}.\]

Dieses Beispiel zeigt, dass man die so genannte  $L$–Wert–Algebra auch auf bedingte Wahrscheinlichkeiten anwenden kann.
In der  Aufgabe 4.1Z  wird das BEC–Modell in ähnlicher Weise beschrieben.


$\text{Beispiel 2:}$  In einem weiteren Beispiel betrachten nun den  AWGN–Kanal  mit den bedingten Wahrscheinlichkeitsdichtefunktionen

Bedingte AWGN–Dichtefunktionen
\[f_{y \hspace{0.03cm}\vert \hspace{0.03cm}x=+1 } \hspace{0.05cm} (y \hspace{0.05cm}\vert\hspace{0.05cm}x=+1 )\hspace{-0.1cm} = \hspace{-0.1cm} \frac {1}{\sqrt{2\pi} \cdot \sigma } \cdot {\rm e} ^{ - {(y-1)^2}/(2\sigma^2) } \hspace{0.05cm},\]
\[f_{y \hspace{0.03cm}\vert \hspace{0.03cm}x=-1 } \hspace{0.05cm} (y \hspace{0.05cm}\vert\hspace{0.05cm}x=-1 )\hspace{-0.1cm} = \hspace{-0.1cm} \frac {1}{\sqrt{2\pi} \cdot \sigma } \cdot {\rm e} ^{ - {(y+1)^2}/(2\sigma^2) } \hspace{0.05cm}.\]

In der Grafik sind zwei beispielhafte Gaußfunktionen als blaue bzw. rote Kurve dargestellt.

Die gesamte WDF des Ausgangssignals $y$  ergibt sich aus der (gleich) gewichteten Summe:

\[f_{y } \hspace{0.05cm} (y ) = 1/2 \cdot \big [ f_{y \hspace{0.03cm}\vert \hspace{0.03cm}x=+1 } \hspace{0.05cm} (y \hspace{0.05cm}\vert\hspace{0.05cm}x=+1 ) \hspace{0.1cm} + \hspace{0.1cm} f_{y \hspace{0.03cm}\vert \hspace{0.03cm}x=-1 } \hspace{0.05cm} (y \hspace{0.05cm}\vert \hspace{0.05cm}x=-1 ) \big ] \hspace{0.05cm}.\]

Wir berechnen nun die Wahrscheinlichkeit, dass der Empfangswert  $y$  in einem (sehr) schmalen Intervall der Breite  $\Delta$  um  $y_0 = 0.25$  liegt. Man erhält näherungsweise

\[{\rm Pr} (\vert y - y_0\vert \le{\it \Delta}/2 \hspace{0.05cm} \Big \vert \hspace{0.05cm}x=+1 )\hspace{-0.1cm} \approx \hspace{-0.1cm} \frac {\it \Delta}{\sqrt{2\pi} \cdot \sigma } \cdot {\rm e} ^{ - {(y_0-1)^2}/(2\sigma^2) } \hspace{0.05cm},\]
\[{\rm Pr} (\vert y - y_0\vert \le {\it \Delta}/2 \hspace{0.05cm} \Big \vert \hspace{0.05cm}x=-1 )\hspace{-0.1cm} \approx \hspace{-0.1cm} \frac {\it \Delta}{\sqrt{2\pi} \cdot \sigma } \cdot {\rm e} ^{ - {(y_0+1)^2}/(2\sigma^2) } \hspace{0.05cm}.\]

Die etwas größeren senkrechten Striche bezeichnen die Bedingungen, die kleineren die Betragsbildung.

Der  $L$–Wert der bedingten Wahrscheinlichkeit in Vorwärtsrichtung  $($das bedeutet:   Ausgang  $y$  für einen gegebenen Eingang  $x)$  ergibt sich somit als der Logarithmus des Quotienten beider Ausdrücke:

\[L(y = y_0\hspace{0.05cm}\vert\hspace{0.05cm}x) = {\rm ln} \hspace{0.15cm} \left [ \frac{{\rm e} ^{ - {(y_0-1)^2}/(2\sigma^2)}}{{\rm e} ^{ - {(y_0+1)^2}/(2\sigma^2)}} \right ] = {\rm ln} \left [ {\rm e} ^{ - [ {(y_0-1)^2}+{(y_0+1)^2}]/(2\sigma^2)} \right ] = \frac{(y_0+1)^2-(y_0-1)^2}{2\cdot \sigma^2} = \frac{2 \cdot y_0}{\sigma^2}\hspace{0.05cm}. \]

Ersetzen wir nun die Hilfsgröße  $y_0$  durch die (allgemeine) Zufallsgröße  $y$  am AWGN–Ausgang, so lautet das Endergebnis:

\[L(y \hspace{0.05cm}\vert\hspace{0.05cm}x) = {2 \cdot y}/{\sigma^2} =K_{\rm L} \cdot y\hspace{0.05cm}. \]

Hierbei ist  $K_{\rm L} = 2/\sigma^2$  eine Konstante, die allein von der Streuung der Gaußschen Störung abhängt.


Symbolweise Soft–in Soft–out Decodierung


Wir gehen nun von einem  $(n, \ k)$–Blockcode aus, wobei das Codewort  $\underline{x} = (x_1, \ \text{...} \ , \ x_n)$  durch den Kanal in das Empfangswort  $\underline{y} = (y_1, \ \text{...} \ , \ y_n)$  verfälscht wird.

  • Bei langen Codes ist eine  Maximum–a–posteriori–Entscheidung auf Blockebene  – kurz:  $\text{ block–wise MAP}$  – sehr aufwändig.
  • Man müsste unter den  $2^k $ zulässigen Codeworten  $\underline{x}_j ∈ \mathcal{C}$  dasjenige mit der größten Rückschlusswahrscheinlichkeit (englisch:  A Posteriori Probability, APP) finden.
  • Das auszugebende Codewort  $\underline{z}$  wäre in diesem Fall  $\underline{z} = {\rm arg} \max_{\underline{x}_{\hspace{0.03cm}j} \hspace{0.03cm} \in \hspace{0.05cm} \mathcal{C}} \hspace{0.1cm} {\rm Pr}( \underline{x}_{\hspace{0.03cm}j} |\hspace{0.05cm} \underline{y} ) \hspace{0.05cm}.$


Modell der symbolweisen Soft–in Soft–out Decodierung

Eine zweite Möglichkeit ist die Decodierung auf Bitebene. Der dargestellte symbolweise (oder bitweise)  $\text{Soft–in Soft–out Decoder}$  hat die Aufgabe, alle Codewortbits  $x_i ∈ \{0, \, 1\}$  entsprechend maximaler Rückschlusswahrscheinlichkeit  ${\rm Pr}(x_i | \underline{y})$  zu decodieren. Mit der Laufvariablen  $i = 1, \text{...} , \ n$  gilt dabei:

  • Der entsprechende  $L$–Wert  (englisch:  Log Likelihood Ratio, LLR) für das  $i$–te Codebit lautet:
\[L_{\rm APP} (i) = L(x_i\hspace{0.05cm}|\hspace{0.05cm}\underline{y}) = {\rm ln} \hspace{0.15cm} \frac{{\rm Pr}(x_i = 0\hspace{0.05cm}|\hspace{0.05cm}\underline{y})}{{\rm Pr}(x_i = 1\hspace{0.05cm}|\hspace{0.05cm}\underline{y})}\hspace{0.05cm} . \]
  • Der Decoder arbeitet iterativ. Bei der Initialisierung $($in der Grafik gekennzeichnet durch den Parameter  $I = 0)$  ist  $L_{\rm APP}(i) = L_{\rm K}(i)$, wobei das Kanal–LLR  $L_{\rm K}(i)$  durch den Empfangswert  $y_i$  gegeben ist.
  • Berechnet wird zudem der extrinsische  $L$–Wert  $L_{\rm E}(i)$, der die gesamte Information quantifiziert, die alle anderen Bits  $(j ≠ i)$  aufgrund der Code–Eigenschaften über das betrachtete  $i$–te Bit liefern.
  • Bei der nächsten Iteration  $($ab  $I = 1)$  wird  $L_{\rm E}(i)$  bei der Berechnung von  $L_{\rm APP}(i)$  als Apriori–Information  $L_{\rm A}(i)$  berücksichtigt. Für das neue Aposteriori–LLR in der Iteration  $I + 1$  gilt somit:
\[L_{\hspace{0.1cm}\rm APP}^{(I+1)} (i) = L_{\hspace{0.1cm}\rm APP}^{(I)} (i) + L_{\hspace{0.1cm}\rm A}^{(I+1)} (i) = L_{\hspace{0.1cm}\rm APP}^{(I)} (i) + L_{\hspace{0.1cm}\rm E}^{(I)} (i)\hspace{0.05cm} . \]
  • Die Iterationen werden fortgesetzt, bis alle Beträge  $|L_{\rm APP}(i)|$  größer sind als ein vorzugebender Wert. Das wahrscheinlichste Codewort  $\underline{z}$  ergibt sich dann aus den Vorzeichen aller  $L_{\rm APP}(i)$, mit  $i = 1, \ \text{...} , \ n$.
  • Bei einem  systematischen Code  geben die ersten  $k$  Bit von  $\underline{z}$  das gesuchte Informationswort an, das mit großer Wahrscheinlichkeit mit der gesendeten Nachricht  $\underline{u}$ übereinstimmen wird.

Diese Beschreibung des SISO–Decodierers nach  [Bos98][1]  soll an dieser Stelle in erster Linie die unterschiedlichen  $L$–Werte verdeutlichen. Das große Potential der symbolweisen Decodierung erkennt man erst im Zusammenhang mit  verketteten Codiersystemen.

Zur Berechnung der extrinsischen L–Werte


Die Schwierigkeit bei der symbolweisen iterativen Decodierung ist im allgemeinen die Bereitstellung der extrinsischen  $L$–Werte  $L_{\rm E}(i)$. Bei einem Code der Länge  $n$  gilt hierbei für die Laufvariable:  $i = 1, \ \text{...} , \ n$.

$\text{Definition:}$  Der  extrinsische $L$–Wert  (englisch:  extrinsic LLR )  ist ein Maß für die Informationen, den die anderen Symbole  $(j ≠ i)$  des Codewortes über das  $i$–te Codesymbol liefern, ausgedrückt als Log–Likelihood–Verhältnis. Wir benennen diesen Kennwert mit  $L_{\rm E}(i)$.


Wir berechnen nun die extrinsischen  $L$–Werte  $L_{\rm E}(i)$  für zwei beispielhafte Codes.


$\text{Repetition Code}$   ⇒   ${\rm RC} \ (n, 1, n)$

Ein Wiederholungscode zeichnet sich dadurch aus, dass alle  $n$  Codesymbole  $x_i ∈ \{0, \, 1\}$  identisch sind. Der extrinsische  $L$–Wert für das  $i$–ten Symbol ist hier sehr einfach anzugeben und lautet:

\[L_{\rm E}(i) = \hspace{0.05cm}\sum_{j \ne i} \hspace{0.1cm} L_j \hspace{0.3cm}{\rm mit}\hspace{0.3cm}L_j = L_{\rm APP}(j) \hspace{0.05cm}.\]
  • Ist die Summe über alle  $L_{j ≠ i}$  positiv, so bedeutet dies aus Sicht der anderen  $L$–Werte eine Präferenz für die Entscheidung   $x_i = 0$.
  • Bei negativer Summe ist dagegen  $x_i = 1$  wahrscheinlicher.
  • $L_{\rm E}(i) = 0$  erlaubt keine Vorhersage.


$\text{Beispiel 5:}$  Wir betrachten die Decodierung des Wiederholungscodes  $\text{RC (4, 1,4)}$. Wir gehen dabei von drei verschiedene Annnahmen für das  Log Likelihood Ratio  $\underline{L}_{\rm A}^{(I=0)} = \underline{L}_{\rm APP}$  aus.

Decodierbeispiel  $\rm (A)$  für den  ${\rm RC} \ (4, 1, 4)$

$\text{Decodierbeispiel (A):}$

$$\underline{L}_{\rm APP} = (+1, -1, +3, -1)\text{:}$$
$$L_{\rm E}(1) = -1+3-1 = +1\hspace{0.05cm},$$
$$L_{\rm E}(2) = +1+3-1 = +3\hspace{0.05cm},$$
$$L_{\rm E}(3) = +1-1 -1= -1\hspace{0.05cm},$$
$$L_{\rm E}(4) = +1-1 +3 = +3\hspace{0.05cm}$$
$$\hspace{0.3cm}\Rightarrow\hspace{0.3cm}\underline{L}_{\rm E}^{(I=0)}= (+1, +3, -1, +3) \hspace{0.3cm}\Rightarrow\hspace{0.3cm}\underline{L}_{\rm A}^{(I=1)}=\underline{L}_{\rm A}^{(I=0)}+ \underline{L}_{\rm E}^{(I=0)}= (+2, +2, +2, +2)$$
  • Zu Beginn  $(I=0)$  weisen die positiven  $L_{\rm E}$–Werte auf  $x_1 = 0$, $x_2 = 0$  und  $x_4 = 0$  hin, während  $x_3 =1$  wahrscheinlicher ist.
  • Bereits nach einer Iteration  $(I=1)$  sind alle  $L_{\rm A}$–Werte positiv   ⇒   Informationsbit wird als  $u = 0$  decodiert.
  • Weitere Iterationen bringen nichts.


Decodierbeispiel  $\rm (B)$  für den  ${\rm RC} \ (4, 1, 4)$

$\text{Decodierbeispiel (B):}$ $$\underline{L}_{\rm APP} = (+1, +1, -4, +1)\text{:}$$ $$\underline{L}_{\rm E}^{(I=0)} = \ (-2, -2, +3, -2)$$

  • Obwohl zu Beginn drei Vorzeichen falsch waren, sind nach zwei Iterationen alle $L_{\rm A}$–Werte negativ.
  • Das Informationsbit wird als  $u = 1$  decodiert.
Decodierbeispiel  $\rm (C)$  für den  ${\rm RC} \ (4, 1, 4)$

$\text{Decodierbeispiel (C):}$ $$\underline{L}_{\rm APP} = (+1, +1, -3, +1)\text{:}$$ $$\underline{L}_{\rm E}^{(I=0)} = (-1, -1, +3, -1)$$

  • Alle  $L_{\rm A}$–Werte sind schon nach einer Iteration Null.
  • Das Informationsbit kann nicht decodiert werden, obwohl die Ausgangslage nicht viel schlechter war als bei  $\rm (B)$.
  • Weitere Iterationen bringen auch hier nichts.


$\text{Single Parity–check Code}$   ⇒   ${\rm SPC} \ (n, \ n \, -1, \ 2)$

Bei jedem  Single Parity–check Code  ist die Anzahl der Einsen in jedem Codewort geradzahlig. Oder anders ausgedrückt:   Für jedes Codewort  $\underline{x}$  ist das  Hamming–Gewicht  $w_{\rm H}(\underline{x})$  geradzahlig.

$\text{Definition:}$  Das Codewort  $\underline{x}^{(–i)}$  beinhalte alle Symbole mit Ausnahme von  $x_i$   ⇒   Vektor der Länge  $n -1$. Damit lautet der  $\text{extrinsische }L\text{–Wert}$  bezüglich des  $i$–ten Symbols, wenn  $\underline{x}$  empfangen wurde:

\[L_{\rm E}(i) = {\rm ln} \hspace{0.15cm}\frac{ {\rm Pr} \left [w_{\rm H}(\underline{x}^{(-i)})\hspace{0.15cm}{\rm ist \hspace{0.15cm} gerade} \hspace{0.05cm} \vert\hspace{0.05cm}\underline{y} \hspace{0.05cm}\right ]}{ {\rm Pr} \left [w_{\rm H}(\underline{x}^{(-i)})\hspace{0.15cm}{\rm ist \hspace{0.15cm} ungerade} \hspace{0.05cm} \vert \hspace{0.05cm}\underline{y} \hspace{0.05cm}\right ]} \hspace{0.05cm}.\]

Wie in der  Aufgabe 4.4  gezeigt werden soll, kann hierfür auch geschrieben werden:

\[L_{\rm E}(i) = 2 \cdot {\rm tanh}^{-1} \hspace{0.1cm} \left [ \prod\limits_{j \ne i}^{n} \hspace{0.15cm}{\rm tanh}(L_j/2) \right ] \hspace{0.3cm}{\rm mit}\hspace{0.3cm}L_j = L_{\rm APP}(j) \hspace{0.05cm}.\]


$\text{Beispiel 6:}$  Wir gehen vom  Single Parity–check Code  mit  $n = 3, \ k = 2$   ⇒   kurz  ${\rm SPC} \ (3, \ 2, \ 2)$  aus.

Die  $2^k = 4$  gültigen Codeworte  $\underline{x} = \{x_1, x_2, x_3\}$  lauten bei bipolarer Beschreibung   ⇒   $x_i ∈ \{±1\}$:

Decodierbeispiel für den  ${\rm SPC} \ (3, 2, 2)$
$$ \underline{x}_0 \hspace{-0.05cm}=\hspace{-0.05cm} (+1\hspace{-0.03cm},\hspace{-0.05cm}+1\hspace{-0.03cm},\hspace{-0.05cm}+1)\hspace{-0.05cm}, $$
$$\underline{x}_1 \hspace{-0.05cm}=\hspace{-0.05cm} (+1\hspace{-0.03cm},\hspace{-0.05cm} -1\hspace{-0.03cm},\hspace{-0.05cm} -1)\hspace{-0.05cm}, $$
$$\underline{x}_2 \hspace{-0.05cm}=\hspace{-0.05cm} (-1\hspace{-0.03cm},\hspace{-0.05cm} +1\hspace{-0.03cm},\hspace{-0.05cm} -1)\hspace{-0.05cm}, $$
$$\underline{x}_3 \hspace{-0.05cm}=\hspace{-0.05cm} (-1\hspace{-0.03cm},\hspace{-0.05cm} -1\hspace{-0.03cm},\hspace{-0.05cm} +1)\hspace{-0.05cm}. $$

Bei diesem Code ist also das Produkt  $x_1 \cdot x_2 \cdot x_3$  stets positiv.

Die obige Tabelle zeigt den Decodiervorgang für  $\underline{L}_{\rm APP} = (+2.0, +0.4, \, –1.6)$. Die harte Entscheidung nach den Vorzeichen von  $L_{\rm APP}(i)$  ergäbe hier  $(+1, +1, \, -1)$, also kein gültiges Codewort des  ${\rm SP}(3, \ 2, \ 2)$.

Rechts in der Tabelle sind die dazugehörigen extrinsischen  $L$–Werte eingetragen:

\[L_{\rm E}(1) = 2 \cdot {\rm tanh}^{-1} \hspace{0.05cm} \left [ {\rm tanh} (0.2) \cdot {\rm tanh} (-0.8)\hspace{0.05cm}\right ] = -0.131\hspace{0.05cm}, \]
\[L_{\rm E}(2) =2 \cdot {\rm tanh}^{-1} \hspace{0.05cm} \left [ {\rm tanh} (1.0) \cdot {\rm tanh} (-0.8)\hspace{0.05cm}\right ] = -0.518\hspace{0.05cm}, \]
\[L_{\rm E}(3) =2 \cdot {\rm tanh}^{-1} \hspace{0.05cm} \left [ {\rm tanh} (1.0) \cdot {\rm tanh} (0.2)\hspace{0.05cm}\right ] = +0.151\hspace{0.05cm}.\]

Die zweite Gleichung lässt sich wie folgt interpretieren:

  • $L_{\rm APP}(1) = +2.0$  und  $L_{\rm APP}(3) = \, -1.6$  sagen aus, dass das erste Bit eher  $+1$  als  $-1$  ist und das dritte Bit eher  $-1$  als  $+1$. Die Zuverlässigkeit (der Betrag) ist beim ersten Bit etwas größer als beim dritten.
  • Die extrinsische Information  $L_{\rm E}(2) = \, -0.518$ berücksichtigt nur die Informationen von Bit 1 und Bit 3 über Bit 2. Aus deren Sicht ist das zweite Bit eine  $-1$  mit der Zuverlässigkeit  $0.518$.
  • Der vom Empfangswert  $y_2$  abgeleitete  $L$–Wert   ⇒   $L_{\rm APP}(2) = +0.4$  hat für das zweite Bit eine  $+1$  vermuten lassen. Die Diskrepanz wird hier bereits in der Iteration  $I = 1$  aufgelöst.
  • Entschieden wird hier für das Codewort  $\underline{x}_1$. Bei  $0.518 < L_{\rm APP}(2) < 1.6$  würde das Ergebnis  $\underline{x}_1$  erst nach mehreren Iterationen vorliegen. Für  $L_{\rm APP}(2) > 1.6$  liefert der Decoder dagegen  $\underline{x}_0$.


BCJR–Decodierung: Vorwärts–Rückwärts–Algorithmus


Ein Beispiel für die iterative Decodierung von Faltungscodes ist der  BCJR–Algorithmus, benannt nach dessen Erfindern L. R. Bahl, J. Cocke, F. Jelinek und J. Raviv  ⇒  [BCJR74][2]. Der Algorithmus weist viele Parallelen zur sieben Jahren älteren Viterbi–Decodierung auf, doch auch einige signifikante Unterschiede:

  • Der Viterbi–Algorithmus kann (in seiner ursprünglichen Form) keine Softinformation verarbeiten. Dagegen gibt der BCJR–Algorithmus bei jeder Iteration für jedes einzelne Symbol (Bit) einen Zuverlässigkeitswert an, der bei späteren Iterationen berücksichtigt wird.


Gegenüberstellung von Viterbi– und BCJR–Algorithmus

Die Abbildung soll – fast unzulässig vereinfacht – die unterschiedliche Vorgehensweise von Viterbi–Algorithmus (links) und BCJR–Algorithmus (rechts) verdeutlichen. Zugrunde liegt ein Faltungscode mit dem Gedächtnis  $m = 1$  und der Länge  $L = 4$   ⇒   Gesamtlänge (mit Terminierung)  $L' = 5$.

  • Der Viterbi–Algorithmus sucht und findet den wahrscheinlichsten Pfad von  ${\it \Gamma}_0(S_0)$  nach  ${\it \Gamma}_5(S_0)$, nämlich  $S_0 → S_1 → S_0 → S_0 → S_1→ S_0 $. Wir verweisen auf die Musterlösung zur  Aufgabe 3.9Z.

Die Skizze für den BCJR–Algorithmus verdeutlicht die Gewinnung des extrinsischen  $L$–Wertes für das dritte Symbol   ⇒   $L_{\rm E}(3)$. Der relevante Bereich im Trellis ist schraffiert:

  • Bei der Abarbeitung des Trellisdiagramms in Vorwärtsrichtung gewinnt man – in gleicher Weise wie bei Viterbi – die Metriken  $\alpha_1, \ \alpha_2, \ \text{...}\hspace{0.05cm} , \ \alpha_5$. Zur Berechnung von  $L_{\rm E}(3)$  benötigt man hiervon  $\alpha_2$.
  • Anschließend durchläuft man das Trellisdiagramm rückwärts (also von rechts nach links) und erhält damit die Metriken  $\beta_4, \ \beta_3, \ \text{...}\hspace{0.05cm} , \ \beta_0$  entsprechend der unteren Skizze.
  • Der gesuchte extrinsische  $L$–Wert  $L_{\rm E}(3)$  ergibt sich aus den Metriken  $\alpha_2$  (in Vorwärtsrichtung) und  $\beta_3$  (in Rückwärtsrichtung) sowie der Apriori–Information  $\gamma_3$  über das Symbol  $i = 3$.

Grundstruktur von verketteten Codiersystemen


Die wichtigsten Kommunikationssysteme der letzten Jahre verwenden zwei unterschiedliche Kanalcodes. Man spricht dann von  verketteten Codiersystemen  (englisch:  Concatenated Codes). Auch bei relativ kurzen Komponentencodes  $\mathcal{C}_1$  und  $\mathcal{C}_2$  ergibt sich für den verketteten Code  $\mathcal{C}$  eine hinreichend große Codewortlänge  $n$, die ja bekanntlich erforderlich ist, um sich der Kanalkapazität anzunähern.

Zunächst seien einige Beispiele aus dem Mobilfunk genannt:

  • Bei  GSM  (Global System for Mobile Communications, zweite Mobilfunkgeneration) wird zunächst die Datenbitrate von  $9.6 \ \rm kbit/s$  auf  $12 \ \rm kbit/s$  erhöht, um auch in leitungsvermittelten Netzen eine Fehlererkennung zu ermöglichen. Anschließend folgt ein punktierter Faltungscode mit der Ausgangsbitrate  $22.8 \ \rm kbit/s$. Die Gesamtcoderate beträgt somit etwa  $42.1\%$.
  • Beim 3G–Mobilfunksystem  UMTS  (Universal Mobile Telecommunications System) verwendet man je nach den Randbedingungen (guter/schlechter Kanal, wenige/viele Teilnehmer in der Zelle) einen  Faltungscode  oder einen  Turbocode  (darunter versteht man per se die Verkettung zweier Faltungscodierer). Beim 4G–Mobilfunksystem  LTE  (Long Term Evolution) verwendet man für kurze Kontrollsignale einen Faltungscode und für die längeren Payload-Daten einen Turbocode.


Parallel verkettetes Codiersystem

Die Grafik zeigt die Grundstruktur eines parallel verketteten Codiersystems. Alle Vektoren bestehen aus  $n$  Elementen:  $\underline{L} = (L(1), \ \text{...}\hspace{0.05cm} , \ L(n))$. Die Berechnung aller  $L$–Werte geschieht also auf Symbolebene. Nicht dargestellt ist hier der  Interleaver, der zum Beispiel bei den Turbocodes obligatorisch ist.

  • Die Codesequenzen  $\underline{x}_1$  und  $\underline{x}_2$  werden zur gemeinsamen Übertragung über den Kanal durch einen Multiplexer zum Vektor  $\underline{x}$  zusammengefügt. Am Empfänger wird die Sequenz  $\underline{y}$  wieder in die Einzelteile  $\underline{y}_1$  und  $\underline{y}_2$  zerlegt. Daraus werden die Kanal–$L$–Werte  $\underline{L}_{\rm K,\hspace{0.05cm}1} $ und  $\underline{L}_{\rm K,\hspace{0.05cm}2}$  gebildet.
  • Der symbolweise Decoder ermittelt entsprechend der vorne beschriebenen  Vorgehensweise  die extrinsischen $L$–Werte  $\underline{L}_{\rm E,\hspace{0.05cm} 1}$  und  $\underline{L}_{\rm E,\hspace{0.05cm} 2}$, die gleichzeitig die Apriori–Informationen  $\underline{L}_{\rm A,\hspace{0.05cm} 2}$  und  $\underline{L}_{\rm A,\hspace{0.05cm} 1}$  für den jeweils anderen Decoder darstellen.
  • Nach ausreichend vielen Iterationen (also dann, wenn ein Abbruchkriterium erfüllt ist) liegt am Decoderausgang der Vektor der Aposteriori–Werte   ⇒   $\underline{L}_{\rm APP}$  an. Im Beispiel wird willkürlich der Wert im oberen Zweig genommen. Möglich wäre aber auch der untere  $L$–Wert.

Das obige Modell gilt insbesondere auch für die Decodierung der Turbo–Codes gemäß dem Kapitel  Grundlegendes zu den Turbocodes.

Aufgaben zum Kapitel


Aufgabe 4.1: Zum „Log Likelihood Ratio”

Aufgabe 4.1Z: L–Werte des BEC–Modells

Aufgabe 4.2: Kanal–LLR bei AWGN

Aufgabe 4.3: Iterative Decodierung beim BSC

Aufgabe 4.3Z: Umrechnungen von L–Wert und S–Wert

Aufgabe 4.4: Extrinsische L–Werte beim SPC

Aufgabe 4.4Z: Ergänzung zur Aufgabe 4.4

Aufgabe 4.5: Nochmals zu den extrinsischen L–Werten

Aufgabe 4.5Z: Tangens Hyperbolikus und Inverse

Quellenverzeichnis

  1. Bossert, M.: Kanalcodierung. Stuttgart: B. G. Teubner, 1998.
  2. Bahl, L.R.; Cocke, J.; Jelinek, F.; Raviv, J.: Optimal Decoding of Linear Codes for Minimizing Symbol Error Rate. In: IEEE Transactions on Information Theory, Vol. IT-20, S. 284-287, 1974.