Quelltext der Seite Kanalcodierung/Soft–in Soft–out Decoder

 
{{Header
|Untermenü=Iterative Decodierverfahren
|Vorherige Seite=Distanzeigenschaften und Fehlerwahrscheinlichkeitsschranken
|Nächste Seite=Grundlegendes zu den Produktcodes
}}

== Hard Decision vs. Soft Decision (1) ==
<br>
Zur Hinleitung auf die Thematik dieses vierten und letzten Kapitels und zur Motivation betrachten wir das folgende Nachrichtenübertragungssystem mit Codierung.<br>

[[Datei:P ID2971 KC T 4 1 S1a v8.png|Betrachtetes Nachrichtenübertragungssystem mit Codierung|class=fit]]<br>

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 <u><i>u</i></u> = (<i>u</i><sub>1</sub>, <i>u</i><sub>2</sub>) wird der Coderfolge <u><i>x</i></u> = (<i>x</i><sub>1</sub>, <i>x</i><sub>2</sub>, <i>x</i><sub>3</sub>) = (<i>u</i><sub>1</sub>, <i>u</i><sub>2</sub>, <i>p</i>) zugeordnet, wobei für das Paritybit <i>p</i> = <i>u</i><sub>1</sub> &oplus; <i>u</i><sub>2</sub> gilt &nbsp;&#8658;&nbsp; Single Parity&ndash;check Code &nbsp;&#8658;&nbsp; SPC (3, 2, 2).<br>

*Der AWGN&ndash;Kanal verändert die Binärsymbole <i>x<sub>i</sub></i> &#8712; {+1, &ndash;1} zu reellwertigen Ausgangswerten <i>y</i><sub><i>i</i></sub>, z.B. im Block 4 der unteren Tabelle: &nbsp; <i>x</i><sub>1</sub> = +1 &nbsp;&#8658;&nbsp; <i>y</i><sub>1</sub> = +0.9&nbsp; und &nbsp; <i>x</i><sub>3</sub> = &ndash;1 &nbsp;&#8658;&nbsp; <i>y</i><sub>3</sub> = +0.1.<br>

*Die Decodierung geschieht gemäß dem Kriterium 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>

*Das obige Blockschaltbild in seiner Gesamtheit entspricht ML&ndash;HD. Hier werden zur Detektion nur die Vorzeichen der AWGN&ndash;Ausgangswerte entsprechend &nbsp;<i>y</i><sub>HD, <i>i</i></sub> = sign[<i>y</i><sub>SD, <i>i</i></sub>]&nbsp; ausgewertet.<br>

*Bei <i>Soft Decision</i> (ML&ndash;SD) verzichtet man auf den schraffierten Block in obigem Blockschaltbild und wertet direkt die wertkontinuierlichen Eingangsgrößen <i>y</i><sub>SD, </sub><sub><i>i</i></sub> aus.<br>

[[Datei:P ID2972 KC T 4 1 S1b v4.png|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 <u><i>&upsilon;</i></u><sub>HD</sub> ergibt sich aus den hart entschiedenen Kanalwerten <u><i>y</i></u><sub>HD</sub> (blaue Hinterlegung): Es werden nur die beiden ersten Blöcke fehlerfrei decodiert.<br>

*<b>Soft Decision</b> &nbsp;&#8658; die Symbolfolge <u><i>&upsilon;</i></u><sub>SD</sub> ergibt sich aus den &bdquo;weichen&rdquo; Kanalausgangswerten <u><i>y</i></u><sub>SD</sub> (grüne Hinterlegung): Nun wird in diesem Beispiel auch der dritte Block richtig entschieden.<br><br>

Die Bildbeschreibung wird auf der nächsten Seite fortgesetzt.<br>

== Hard Decision vs. Soft Decision (2) ==
<br>
Für alle Spalten der folgenden Tabelle wird vorausgesetzt: 
*der Nachrichtenblock <u><i>u</i></u> = (0, 1), bipolar darstellbar als (+1, &ndash;1),<br>

*der SPC (3, 2)&ndash;codierte Block <u><i>x</i></u> = (0, 1, 1) bzw. in Bipolardarstellung (+1, &ndash;1, &ndash;1).<br><br>

Die vier Blöcke unterscheiden sich also nur durch unterschiedliche AWGN&ndash;Realisierungen.<br>

[[Datei:P ID2973 KC T 4 1 S1b v4.png|Gegenüberstellung von <i>Hard Decision</i>  und <i>Soft Decision</i>|class=fit]]<br>

Die Tabelle ist wie folgt zu interpretieren:
*Bei idealem Kanal entsprechend Block 1 &nbsp;&#8658;&nbsp; <u><i>x</i></u> = <u><i>y</i></u><sub>SD</sub> = <u><i>y</i></u><sub>HD</sub> gibt es keinen Unterschied zwischen der (blauen) herkömmlichen ML&ndash;HD &ndash;Variante und der (grünen) ML&ndash;SD &ndash;Variante.<br>

*Der Block 2 demonstriert geringe Signalverfälschungen. Wegen <u><i>y</i></u><sub>HD</sub> = <u><i>x</i></u> (das heißt, dass der Kanal die Vorzeichen nicht  verfälscht) liefert auch ML&ndash;HD das richtige Ergebnis <u><i>&upsilon;</i></u><sub>HD</sub> = <u><i>u</i></u>.<br>

*Dagegen gilt im dritten Block <u><i>y</i></u><sub>HD</sub> &ne; <u><i>x</i></u> und es gibt auch keine SPC (3, 2)&ndash;Zuordnung <u><i>u</i></u> &nbsp;&#8658;&nbsp; <u><i>y</i></u><sub>HD</sub>. Der ML&ndash;Decoder kann hier nur durch die Ausgabe <u><i>&upsilon;</i></u><sub>HD</sub> = (E, E) vermelden, dass er bei der Decodierung dieses Blocks gescheitert ist. &bdquo;E&rdquo; steht hierbei für Erasure (deutsch: <i>Auslöschung</i>).<br>

*Auch der <i>Soft Decision</i> Decoder erkennt, dass eine Decodierung anhand der Vorzeichen nicht funktioniert. Anhand der <u><i>y</i></u><sub>SD</sub>&ndash;Werte erkennt er aber, dass mit großer Wahrscheinlichkeit das zweite Bit verfälscht wurde und entscheidet sich für die richtige Symbolfolge <u><i>&upsilon;</i></u><sub>SD</sub> = (+1, &ndash;1) = <u><i>u</i></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 <u><i>&upsilon;</i></u><sub>HD</sub> = (+1, +1) &ne; <u><i>u</i></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>

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>

*wäre bei Block 2 deutlich kleiner,<br>

*läge bei Block 3 und 4 nahe bei 0.<br>

== Zuverlässigkeitsinformation – Log Likelihood Ratio (1) ==
<br>
Es sei <i>x</i> &#8712; {+1, &ndash;1} eine binäre Zufallsvariable mit den Wahrscheinlichkeiten Pr(<i>x</i>&nbsp;=&nbsp;+1) und Pr(<i>x</i>&nbsp;=&nbsp;&ndash;1). Für die Codierungstheorie erweist es sich als zweckmäßig hinsichtlich der Rechenzeiten, wenn man anstelle der Wahrscheinlichkeiten Pr(<i>x</i> = &plusmn;1) den natürlichen Logarithmus des Quotienten heranzieht.<br>

{{Definition}}''':''' Das <b>Log&ndash;Likelihood&ndash;Verhältnis</b> (kurz: der <i>L</i>&ndash;Wert, englisch: <i>Log&ndash;Likelihood Ratio</i>, LLR) der Zufallsgröße <i>x</i> &#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>

Bei unipolarer/symbolhafter Darstellung (+1&nbsp;&#8594;&nbsp;0 &nbsp;und&nbsp; &ndash;1&nbsp;&#8594;&nbsp;1) gilt entsprechend mit <i>&xi;</i>&nbsp;&#8712;&nbsp;{0,&nbsp;1}:

:<math>L(\xi)={\rm ln} \hspace{0.15cm} \frac{{\rm Pr}(\xi = 0)}{{\rm Pr}(\xi = 1)}\hspace{0.05cm}.</math>{{end}}<br>

Nachfolgend ist der nichtlineare Zusammenhang zwischen Pr(<i>x</i> = &plusmn;1) und <i>L</i>(<i>x</i>) angegeben. Ersetzt man Pr(<i>x</i> = +1) durch Pr(<i>&xi;</i> = 0), so gibt die mittlere Zeile den <i>L</i>&ndash;Wert der unipolaren Zufallsgröße <i>&xi;</i> an.<br>

[[Datei:P ID2975 KC T 4 1 S2a v1.png|Wahrscheinlichkeit und <i>L</i>–Wert|class=fit]]<br>

Man erkennt:
*Der wahrscheinlichere Zufallswert von <i>x</i> &#8712; {+1, &ndash;1} ist durch sign <i>L</i>(<i>x</i>) &nbsp;&#8658;&nbsp; <b>Vorzeichen</b> gegeben.<br>

*Dagegen gibt der <b>Betrag</b> |<i>L</i>(<i>x</i>)| die Zuverlässigkeit für das Ergebnis sign(<i>L</i>(<i>x</i>)) an.<br><br>

{{Beispiel}}''':''' 
[[Datei:P ID2976 KC T 4 1 S2b v2.png|rahmenlos|rechts|BSC–Modell]] Wir betrachten das  skizzierte BSC&ndash;Modell mit bipolarer Darstellung. Hier gilt mit  der Verfälschungswahrscheinlichkeit <i>&epsilon;</i> = 0.1 sowie den beiden Zufallsgrößen <i>x</i> &#8712; {+1, &ndash;1} und <i>y</i> &#8712; {+1, &ndash;1} am Eingang und Ausgang des Kanals:

:<math>L(y\hspace{0.05cm}|\hspace{0.05cm}x) \hspace{-0.15cm}  = \hspace{-0.15cm} 
{\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>
:<math>\hspace{-0.15cm}  =  \hspace{-0.15cm}
\left\{ \begin{array}{c} {\rm ln} \hspace{0.15cm} [(1 - \varepsilon)/\varepsilon]\\
 {\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,
\\  {\rm f\ddot{u}r} \hspace{0.15cm} y = -1. \\ \end{array}</math>

Beispielsweise ergeben sich für <i>&epsilon;</i> = 0.1 folgende Zahlenwerte (vergleiche obere Tabelle):

:<math>L(y = +1\hspace{0.05cm}|\hspace{0.05cm}x) =
{\rm ln} \hspace{0.15cm} \frac{0.9}{0.1}  = +2.197\hspace{0.05cm}, \hspace{0.2cm}
 L(y = -1\hspace{0.05cm}|\hspace{0.05cm}x) = -2.197\hspace{0.05cm}.</math>

Dieses Beispiel zeigt, dass man die sog. <i>L</i>&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>

== Zuverlässigkeitsinformation – Log Likelihood Ratio (2) ==
<br>
Wir betrachten nun den AWGN&ndash;Kanal mit den beiden bedingten Wahrscheinlichkeitsdichtefunktionen

:<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}
\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}
\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>

[[Datei:P ID2977 KC T 4 1 S2c v3.png|Bedingte AWGN–Dichtefunktionen|class=fit]]<br>

Die gesamte WDF des Ausgangssignals <i>y</i> 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 ]
\hspace{0.05cm}.</math>

Berechnen wir nun die Wahrscheinlichkeit, dass der Empfangswert <i>y</i> in einem (sehr) schmalen Intervall der Breite <i>&Delta;</i> um <i>y</i><sub>0</sub> = 0.25 liegt, so erhält man näherungsweise

:<math>{\rm Pr} (|y - y_0| \le{\it  \Delta}/2 \hspace{0.05cm}
\Big |  \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> 
:<math>{\rm Pr} (|y - y_0| \le {\it  \Delta}/2 \hspace{0.05cm}
\Big |  \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>

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

Der <i>L</i>&ndash;Wert der bedingten Wahrscheinlichkeit in Vorwärtsrichtung (das bedeutet: Ausgang <i>y</i> für einen gegebenen Eingang <i>x</i>) 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}
{\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>
:<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 <i>y</i><sub>0</sub> durch die (allgemeine) Zufallsgröße <i>y</i> 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>

Hierbei ist <i>K</i><sub>L</sub> = 2/<i>&sigma;</i><sup>2</sup> eine Konstante, die allein von der Streuung der Gaußschen Störung abhängt.<br>

== Symbolweise Soft–in Soft–out Decodierung ==
<br>
Wir gehen  nun von einem (<i>n</i>, <i>k</i>)&ndash;Blockcode aus, wobei das Codewort <u><i>x</i></u> = (<i>x</i><sub>1</sub>, ... , <i>x<sub>n</sub></i>) durch den Kanal in das Empfangswort <u><i>y</i></u> = (<i>y</i><sub>1</sub>, ... , <i>y<sub>n</sub></i>) verfälscht wird. Bei langen Codes ist eine <i>Maximum&ndash;a&ndash;posteriori&ndash;Entscheidung auf Blockebene</i> &ndash; kurz: <b>block&ndash;wise MAP</b> &ndash; sehr aufwändig. Man müsste unter den 2<sup><i>k</i></sup> zulässigen Codeworten <i><u>x</u></i><sub><i>j</i></sub> &#8712; <i>C</i> dasjenige mit der größten Rückschlusswahrscheinlichkeit (englisch: <i>A Posteriori Probability</i>, APP) finden. Das auszugebende Codewort <i><u>z</u></i> wäre in diesem Fall

:<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>

[[Datei:P ID2981 KC T 4 1 S3a v6.png|Modell der symbolweisen Soft–in Soft–out Decodierung|class=fit]]<br>

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 <i>x<sub>i</sub></i> &#8712; {0, 1} entsprechend maximaler Rückschlusswahrscheinlichkeit Pr(<i>x<sub>i</sub></i> | <u><i>y</i></u>) zu decodieren. Mit der Laufvariablen <i>i</i> = 1, ... , <i>n</i> gilt dabei:

*Der entsprechende <i>L</i>&ndash;Wert (englisch: <i>Log Likelihood Ratio</i>, LLR) für das <i>i</i>&ndash;te Codebit lautet:

::<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>

*Der Decoder arbeitet iterativ. Bei der Initialisierung (gekennzeichnet durch den Parameter <i>I</i>&nbsp;=&nbsp;0) ist <i>L</i><sub>APP</sub>(<i>i</i>) = <i>L</i><sub>K</sub>(<i>i</i>), wobei das Kanal&ndash;LLR <i>L</i><sub>K</sub>(<i>i</i>) durch den Empfangswert <i>y<sub>i</sub></i> gegeben ist.<br>

*Berechnet wird zudem  der extrinsische <i>L</i>&ndash;Wert <i>L</i><sub>E</sub>(<i>i</i>), der die gesamte Information quantifiziert, die alle anderen Bits (<i>j</i> &ne; <i>i</i>) aufgrund der Code&ndash;Eigenschaften über das betrachtete <i>i</i>&ndash;te Bit liefern.<br>

*Bei der  nächsten Iteration (ab <i>I</i> = 1) wird <i>L</i><sub>E</sub>(<i>i</i>) bei der Berechnung von <i>L</i><sub>APP</sub>(<i>i</i>) als Apriori&ndash;Information  <i>L</i><sub>A</sub>(<i>i</i>) berücksichtigt. Für das neue Aposteriori&ndash;LLR in der Iteration <i>I</i>&nbsp;+&nbsp;1 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>

*Die Iterationen werden fortgesetzt, bis alle |<i>L</i><sub>APP</sub>(<i>i</i>)| größer sind als ein vorzugebender Wert. Das wahrscheinlichste Codewort <i><u>z</u></i> ergibt sich dann aus den Vorzeichen aller <i>L</i><sub>APP</sub>(<i>i</i>), mit <i>i</i>&nbsp;=&nbsp;1,&nbsp;... ,&nbsp;<i>n</i>.<br>

*Bei einem systematischen Code geben die ersten <i>k</i> Bit von <u><i>z</i></u> das gesuchte Informationswort an, das mit großer Wahrscheinlichkeit mit der gesendeten  Nachricht <u><i>u</i></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 <i>L</i>&ndash;Werte verdeutlichen. Das große Potential der symbolweisen Decodierung erkennt man allerdings erst im Zusammenhang mit verketteten Codiersystemen.<br>




==Quellenverzeichnis==
<references/>

{{Display}}