Aufgaben:Aufgabe 4.3: Iterative Decodierung beim BSC: Unterschied zwischen den Versionen

Aus LNTwww
Wechseln zu:Navigation, Suche
 
(38 dazwischenliegende Versionen von 3 Benutzern werden nicht angezeigt)
Zeile 3: Zeile 3:
 
[[Datei:P_ID2987__KC_A_4_3_v1.png|right|frame|BSC–Modell und mögliche Empfangswerte]]
 
[[Datei:P_ID2987__KC_A_4_3_v1.png|right|frame|BSC–Modell und mögliche Empfangswerte]]
 
Wir betrachten in dieser Aufgabe zwei Codes:
 
Wir betrachten in dieser Aufgabe zwei Codes:
* den Single Parity–Code  ⇒  [[SPC (3, 2, 2)]]:
+
* den Single Parity–Code   ⇒   [[Kanalcodierung/Beispiele_bin%C3%A4rer_Blockcodes#Single_Parity.E2.80.93check_Codes_.281.29| $\text{SPC (3, 2, 2)}$]]:
 
:$$\underline{x} = \big (\hspace{0.05cm}(0, 0, 0), \hspace{0.1cm}
 
:$$\underline{x} = \big (\hspace{0.05cm}(0, 0, 0), \hspace{0.1cm}
 
(0, 1, 1), \hspace{0.1cm}
 
(0, 1, 1), \hspace{0.1cm}
Zeile 9: Zeile 9:
 
(1, 1, 0) \hspace{0.05cm} \big )
 
(1, 1, 0) \hspace{0.05cm} \big )
 
\hspace{0.05cm}, $$
 
\hspace{0.05cm}, $$
* den Wiederholungscode  ⇒  [[RC (3, 1, 3]]:
+
* den Wiederholungscode   ⇒   [[Kanalcodierung/Beispiele_bin%C3%A4rer_Blockcodes#Wiederholungscodes| $\text{RC (3, 1, 3)}$]]:
 
:$$\underline{x} = \big (\hspace{0.05cm}(0, 0, 0), \hspace{0.1cm}
 
:$$\underline{x} = \big (\hspace{0.05cm}(0, 0, 0), \hspace{0.1cm}
 
(1, 1, 1)  \hspace{0.05cm} \big )
 
(1, 1, 1)  \hspace{0.05cm} \big )
Zeile 15: Zeile 15:
  
  
Der Kanal wird auf Bitebene durch das [[BSC–Modell]] beschrieben. Entsprechend der Grafik gilt dabei:
+
Der Kanal wird auf Bitebene durch das  [[Digitalsignal%C3%BCbertragung/Binary_Symmetric_Channel_(BSC)|BSC–Modell]]  beschrieben. Entsprechend der Grafik gilt dabei:
 
:$${\rm Pr}(y_i \ne x_i) \hspace{-0.15cm} \ = \  \hspace{-0.15cm}\varepsilon = 0.269\hspace{0.05cm},$$
 
:$${\rm Pr}(y_i \ne x_i) \hspace{-0.15cm} \ = \  \hspace{-0.15cm}\varepsilon = 0.269\hspace{0.05cm},$$
 
:$${\rm Pr}(y_i = x_i) \hspace{-0.15cm} \ = \ \hspace{-0.15cm}1-\varepsilon = 0.731\hspace{0.05cm}.$$
 
:$${\rm Pr}(y_i = x_i) \hspace{-0.15cm} \ = \ \hspace{-0.15cm}1-\varepsilon = 0.731\hspace{0.05cm}.$$
  
Hierbei bezeichnet $\epsilon$ die Verfälschungswahrscheinlichkeit.
+
Hierbei bezeichnet  $\varepsilon$  die Verfälschungswahrscheinlichkeit des BSC–Modells.
  
 
Bis auf die letzte Teilaufgabe wird stets von folgendem Empfangswert ausgegangen:
 
Bis auf die letzte Teilaufgabe wird stets von folgendem Empfangswert ausgegangen:
Zeile 25: Zeile 25:
 
\hspace{0.05cm}. $$
 
\hspace{0.05cm}. $$
  
Die hier gewählte Indizierung aller möglichen Empfangsvektoren kann der Grafik entnommen werden. Der meist betrachtete Vektor $\underline{y}_2$ ist hierbei rot hervorgehoben. Für die Teilaufgabe (6) gilt dann:
+
Die hier gewählte Indizierung aller möglichen Empfangsvektoren kann der Grafik entnommen werden.  
 +
*Der meistens betrachtete Vektor  $\underline{y}_2$  ist hierbei rot hervorgehoben.  
 +
*Für die Teilaufgabe '''(6)''' gilt dann:
 
:$$\underline{y} = (1, 1, 0) =\underline{y}_6
 
:$$\underline{y} = (1, 1, 0) =\underline{y}_6
 
\hspace{0.05cm}. $$
 
\hspace{0.05cm}. $$
  
 
Zur Decodierung sollen in der Aufgabe untersucht werden:
 
Zur Decodierung sollen in der Aufgabe untersucht werden:
* die [[Syndromdecodierung]], die bei den hier betrachteten Codes als <i>Hard Decision Maximum Likelihood Detection</i> (HD&ndash;ML) vornimmt. <i>Hinweis:</i> Softwerte liegen beim BSC nicht vor.
+
* die&nbsp; [[Kanalcodierung/Decodierung_linearer_Blockcodes#Verallgemeinerung_der_Syndromdecodierung|Syndromdecodierung]], die bei den betrachteten Codes dem Konzept&nbsp; <i>Hard Decision Maximum Likelihood Detection</i>&nbsp; (HD&ndash;ML) folgt <br>(Softwerte liegen beim BSC nicht vor),
* die symbolweise [[Soft&ndash;in Soft&ndash;out Decodierung]] (SISO) entsprechend dieses Abschnitts.
+
* die symbolweise&nbsp; [[Kanalcodierung/Soft%E2%80%93in_Soft%E2%80%93out_Decoder#Symbolweise_Soft.E2.80.93in_Soft.E2.80.93out_Decodierung|Soft&ndash;in Soft&ndash;out Decodierung]]&nbsp; (SISO) entsprechend dieses Abschnitts.
 +
 
 +
 
 +
 
 +
 
 +
 
 +
 
 +
 
 +
 
  
  
 
''Hinweise:''
 
''Hinweise:''
* Die Aufgabe bezieht sich auf das Kapitel [[Kanalcodierung/Soft%E2%80%93in_Soft%E2%80%93out_Decoder| Soft&ndash;in Soft&ndash;out Decoder]].
+
* Die Aufgabe bezieht sich auf das Kapitel&nbsp; [[Kanalcodierung/Soft%E2%80%93in_Soft%E2%80%93out_Decoder| Soft&ndash;in Soft&ndash;out Decoder]].
* Das vom Decoder ausgewählte Codewort wird in den Fragen mit $\underline{z}$ bezeichnet.
+
* Bezug genommen wird insbesondere auf die Seiten
 +
::[[Kanalcodierung/Soft–in_Soft–out_Decoder#Symbolweise_Soft.E2.80.93in_Soft.E2.80.93out_Decodierung|Symbolweise Soft&ndash;in Soft&ndash;out_Decodierung]], sowie
 +
::[[Kanalcodierung/Kanalmodelle_und_Entscheiderstrukturen#Binary_Symmetric_Channel_.E2.80.93_BSC|''Binary Symmetric Channel'']].
 +
* Das vom Decoder ausgewählte Codewort wird in den Fragen mit&nbsp; $\underline{z}$&nbsp; bezeichnet.
 +
  
  
Zeile 42: Zeile 56:
 
===Fragebogen===
 
===Fragebogen===
 
<quiz display=simple>
 
<quiz display=simple>
{Multiple-Choice
+
{Welche Aussagen gelten für die Decodierung des&nbsp; $\text{SPC (3, 2, 2)}$?
 +
|type="()"}
 +
- Die HD&ndash;Syndromdecodierung liefert das Ergebnis&nbsp; $\underline{z} = (0, \, 1, \, 0)$.
 +
- Die HD&ndash;Syndromdecodierung liefert das Ergebnis&nbsp; $\underline{z} = (0, \, 0, \, 0)$.
 +
+ Die HD&ndash;Syndromdecodierung versagt hier.
 +
 
 +
{Welche Aussagen gelten für den&nbsp; $\text{ RC (3, 1, 3)}$?
 +
|type="()"}
 +
- Die HD&ndash;Syndromdecodierung liefert das Ergebnis&nbsp; $\underline{z} = (0, \, 1, \, 0)$.
 +
+ Die HD&ndash;Syndromdecodierung liefert das Ergebnis&nbsp; $\underline{z} = (0, \, 0, \, 0)$.
 +
- Die HD&ndash;Syndromdecodierung versagt hier.
 +
 
 +
{Wie sicher ist diese Entscheidung, wenn man als Sicherheit&nbsp; $S$&nbsp; den Quotienten der Wahrscheinlichkeiten für eine richtige bzw. falsche Entscheidung definiert? <br>Setzen Sie  die Verfälschungswahrscheinlichkeit des BSC&ndash;Modells zu&nbsp; $\varepsilon = 26.9\%$.
 +
|type="{}"}
 +
$S \ = \ ${ 2.717 3% }
 +
$\hspace{0.75cm} \ln {(S)} \ = \ ${ 1 3% }
 +
 
 +
{Wie lauten die intrinsischen&nbsp; $L$&ndash;Werte für die iterative symbolweise Decodierung des&nbsp; $\text{RC (3, 1)}$&ndash;Empfangswortes&nbsp; $\underline{y}_2 = (0, \, 1, \, 0)$?
 +
|type="{}"}
 +
$L_{\rm K}(1) \ = \ ${ 1 3% }
 +
$L_{\rm K}(2) \ = \ ${ -1.03--0.97 }
 +
$L_{\rm K}(3) \ = \ ${ 1 3% }
 +
 
 +
{Welche Aussagen sind für die Decodierung des Empfangswortes&nbsp; $\underline{y}_2 = (0, \, 1, \, 0)$&nbsp; zutreffend? Gehen Sie weiterhin vom&nbsp; $\text{RC (3, 1, 3)}$ aus.
 
|type="[]"}
 
|type="[]"}
+ correct
+
+ Ab der ersten Iteration sind alle Vorzeichen von&nbsp; $L_{\rm APP}(i)$&nbsp; positiv.
- false
+
+ Bereits nach der zweiten Iteration ist&nbsp; ${\rm Pr}(\underline{x}_0\hspace{0.05cm} |\hspace{0.05cm} \underline{y}_2)$&nbsp; größer als&nbsp; $99\%$.
 +
+ Mit jeder Iteration werden die Beträge&nbsp; $L_{\rm APP}(i)$&nbsp; größer.
  
{Input-Box Frage
+
{Welche Aussagen sind für die Decodierung des Empfangswortes&nbsp; $\underline{y}_6 = (1, 1, 0)$&nbsp; zutreffend, wenn&nbsp; $\underline{x}_0 = (0, 0, 0)$&nbsp; gesendet wurde?
|type="{}"}
+
|type="[]"}
$xyz \ = \ ${ 5.4 3% } $ab$
+
- Der iterative Decoder entscheidet richtig.
 +
+ Der iterative Decoder entscheidet falsch.
 +
+ Die &bdquo;Zuverlässigkeit&rdquo; für &bdquo;$\underline{y}_6 \Rightarrow  \underline{x}_0$&rdquo; steigt mit wachsendem&nbsp; $I$.
 
</quiz>
 
</quiz>
  
 
===Musterlösung===
 
===Musterlösung===
 
{{ML-Kopf}}
 
{{ML-Kopf}}
'''(1)'''&nbsp;  
+
'''(1)'''&nbsp; Richtig ist der <u>Lösungsvorschlag 3</u>:
'''(2)'''&nbsp;  
+
*Das Empfangswort $\underline{y}_2 = (0, 1, 0)$ ist kein gültiges Codewort des <i>Single Parity&ndash;check Codes</i> SPC (3, 2). Somit ist die erste Aussage falsch.
'''(3)'''&nbsp;  
+
*Da der SPC (3, 2) zudem nur die minimale Distanz $d_{\rm min} = 2$ aufweist, kann auch kein Fehler korrigiert werden.
'''(4)'''&nbsp;  
+
 
'''(5)'''&nbsp;  
+
 
 +
 
 +
'''(2)'''&nbsp; Richtig ist der <u>Lösungsvorschlag 2</u>:
 +
*Die möglichen Codeworte beim RP (3, 1) sind $\underline{x}_0 = (0, 0, 0)$ und $\underline{x}_1 = (1, 1, 1)$.
 +
*Die minimale Distanz dieses Codes beträgt $d_{\rm min} = 3$, so dass $t = (d_{\rm min} \, - 1)/2 = 1$ Fehler korrigiert werden kann.
 +
*Neben $\underline{y}_0 = (0, 0, 0)$ werden auch $\underline{y}_1 = (0, 0, 1), \ \underline{y}_2 = (0, 1, 0)$ und $\underline{y}_4 = (1, 0, 0)$ dem Decodierergebnis $\underline{x}_0 = (0, 0, 0)$ zugeordnet.
 +
 
 +
 
 +
 
 +
'''(3)'''&nbsp; Entsprechend dem BSC&ndash;Modell gilt für die bedingte Wahrscheinlichkeit, dass $\underline{y}_2 = (0, 1, 0)$ empfangen wird, unter der Voraussetzung, dass $\underline{x}_0 = (0, 0, 0)$ gesendet wurde:
 +
:$${\rm Pr}(\underline{y} = \underline{y}_2 \hspace{0.1cm}| \hspace{0.1cm}\underline{x} =  \underline{x}_0 ) = (1-\varepsilon)^2 \cdot  \varepsilon\hspace{0.05cm}.$$
 +
 
 +
*Der erste Term $(1 \, &ndash;\varepsilon)^2$ gibt dabei die Wahrscheinlichkeit dafür an, dass das erste und das dritte Bit richtig übertragen wurden und $\varepsilon$ berücksichtigt die Verfälschungswahrscheinlichkeit für das zweite Bit.
 +
 
 +
*Entsprechend gilt für das zweite mögliche Codewort $\underline{x}_1 = (1, 1, 1)$:
 +
:$${\rm Pr}(\underline{y} = \underline{y}_2 \hspace{0.1cm}| \hspace{0.1cm}\underline{x} =  \underline{x}_1 ) = \varepsilon^2 \cdot (1-\varepsilon)  \hspace{0.05cm}.$$
 +
 
 +
*Nach dem Satz von Bayes gilt dann für die Rückschlusswahrscheinlichkeiten:
 +
:$${\rm Pr}(\hspace{0.1cm}\underline{x} =  \underline{x}_0 \hspace{0.1cm}| \hspace{0.1cm}\underline{y} = \underline{y}_2  ) \hspace{-0.15cm} \ = \ \hspace{-0.15cm} {\rm Pr}(\underline{y} = \underline{y}_2 \hspace{0.1cm}| \hspace{0.1cm}\underline{x} =  \underline{x}_0 )  \cdot \frac{{\rm Pr}(\underline{x} =  \underline{x}_0)}
 +
{{\rm Pr}(\underline{y} =  \underline{y}_2)} \hspace{0.05cm},$$
 +
:$${\rm Pr}(\hspace{0.1cm}\underline{x} =  \underline{x}_1 \hspace{0.1cm}| \hspace{0.1cm}\underline{y} = \underline{y}_2  ) \hspace{-0.15cm} \ = \ \hspace{-0.15cm} {\rm Pr}(\underline{y} = \underline{y}_2 \hspace{0.1cm}| \hspace{0.1cm}\underline{x} =  \underline{x}_1 )  \cdot \frac{{\rm Pr}(\underline{x} =  \underline{x}_1)}
 +
{{\rm Pr}(\underline{y} =  \underline{y}_2)} $$
 +
:$$\Rightarrow \hspace{0.3cm} S =  \frac{{\rm Pr(richtige \hspace{0.15cm}Entscheidung)}}
 +
{{\rm Pr(falsche \hspace{0.15cm}Entscheidung) }} = \frac{(1-\varepsilon)^2 \cdot  \varepsilon}{\varepsilon^2 \cdot (1-\varepsilon)}= \frac{(1-\varepsilon)}{\varepsilon}\hspace{0.05cm}.$$
 +
 
 +
*Mit $\varepsilon = 0.269$ erhält man folgende Zahlenwerte:
 +
:$$S =  {0.731}/{0.269}\hspace{0.15cm}\underline {= 2.717}\hspace{0.3cm}\Rightarrow 
 +
\hspace{0.3cm}{\rm ln}\hspace{0.15cm}(S)\hspace{0.15cm} \underline {= 1}\hspace{0.05cm}.$$
 +
 
 +
 
 +
 
 +
'''(4)'''&nbsp; Das Vorzeichen des Kanal&ndash;$L$&ndash;Wertes $L_{\rm K}(i)$ ist positiv, falls $y_i = 0$, und negativ für $y_i = 1$.
 +
*Der Betrag gibt die Zuverlässigkeit von $y_i$ an. Beim BSC&ndash;Modell gilt $|L_{\rm K}(i)| = \ln {(1 \, &ndash; \varepsilon)/\varepsilon} = 1$ für alle $i$. Also:
 +
[[Datei:P_ID2988__KC_A_4_3e_v1.png|rightr|frame| Iterative Decodierung von $(+1, –1, +1)$]]
 +
:$$\underline {L_{\rm K}}(1)\hspace{0.15cm} \underline {= +1}\hspace{0.05cm},\hspace{0.5cm}
 +
\underline {L_{\rm K}}(2)\hspace{0.15cm} \underline {= -1}\hspace{0.05cm},\hspace{0.5cm}
 +
\underline {L_{\rm K}}(3)\hspace{0.15cm} \underline {= +1}\hspace{0.05cm}.$$
 +
 
 +
 
 +
 
 +
'''(5)'''&nbsp; Die nebenstehende  Tabelle verdeutlicht die iterative symbolweise Decodierung ausgehend von $\underline{y}_2 = (0, \, 1, \, 0)$.
 +
<br clear=all>
 +
Diese Ergebnisse lassen sich wie folgt interpretieren:
 +
* Die Vorbelegung (Iteration $I = 0$) geschieht entsprechend $\underline{L}_{\rm APP} = \underline{L}_{\rm K}$. Eine harte Entscheidung &nbsp;&#8658;&nbsp; &bdquo;$\sign {\underline{L}_{\rm APP}(i)}$&rdquo; würde zum Decodierergebnis $(0, \, 1, \, 0)$ führen. Die Zuverlässigkeit dieses offensichtlich falschen Ergebnisses wird mit $|{\it \Sigma}| = 1$ angegeben. Dieser Wert stimmt mit dem in Teilaufgaben (3) berechneten &bdquo;$\ln (S)$&rdquo; überein.
 +
* Nach der ersten Iteration $(I = 1)$ sind alle Aposteriori&ndash;$L$&ndash;Werte $L_{\rm APP}(i) = +1$. Eine harte Entscheidung würde hier das (voraussichtlich) richtige Ergebnis $\underline{x}_{\rm APP} = (0, \, 0, \, 0)$ liefern. Die Wahrscheinlichkeit, dass dieses Ergebnis richtig ist, wird durch $|{\it \Sigma}_{\rm APP}| = 3$ quantifiziert:
 +
:$${\rm ln}\hspace{0.25cm}\frac{{\rm Pr}(\hspace{0.1cm}\underline{x} =  \underline{x}_0 \hspace{0.1cm}| \hspace{0.1cm}\underline{y}=\underline{y}_2)}{1-{\rm Pr}(\hspace{0.1cm}\underline{x} =  \underline{x}_0 \hspace{0.1cm}| \hspace{0.1cm}\underline{y}=\underline{y}_2)} = 3
 +
\hspace{0.3cm}\Rightarrow \hspace{0.3cm}
 +
\frac{{\rm Pr}(\hspace{0.1cm}\underline{x} =  \underline{x}_0 \hspace{0.1cm}| \hspace{0.1cm}\underline{y}=\underline{y}_2)}{1-{\rm Pr}(\hspace{0.1cm}\underline{x} =  \underline{x}_0 \hspace{0.1cm}| \hspace{0.1cm}\underline{y}=\underline{y}_2)} = {\rm e}^3 \approx 20$$
 +
:$$\hspace{0.3cm}\Rightarrow \hspace{0.3cm}{\rm Pr}(\hspace{0.1cm}\underline{x} =  \underline{x}_0 \hspace{0.1cm}| \hspace{0.1cm}\underline{y}=\underline{y}_2) = {20}/{21}
 +
{\approx 95.39\%}\hspace{0.05cm}.$$
 +
* Die zweite Iteration bestätigt das Decodierergebnis der ersten Iteration. Die Zuverlässigkeit wird hier sogar mit &bdquo;$9$&rdquo; beziffert. Dieser Wert kann wie folgt interpretiert werden:
 +
:$$\frac{{\rm Pr}(\hspace{0.1cm}\underline{x} =  \underline{x}_0 \hspace{0.1cm}| \hspace{0.1cm}\underline{y}=\underline{y}_2)}{1-{\rm Pr}(\hspace{0.1cm}\underline{x} =  \underline{x}_0 \hspace{0.1cm}| \hspace{0.1cm}\underline{y}=\underline{y}_2)} = {\rm e}^9
 +
\hspace{0.3cm}\Rightarrow \hspace{0.3cm}
 +
{\rm Pr}(\hspace{0.1cm}\underline{x} =  \underline{x}_0 \hspace{0.1cm}| \hspace{0.1cm}\underline{y}=\underline{y}_2) = {{\rm e}^9}/{({\rm e}^9+1)}
 +
\approx 99.99\% \hspace{0.05cm}.$$
 +
 
 +
*Mit jeder weiteren Iteration nimmt der Zuverlässigkeitswert und damit die Wahrscheinlichkeit ${\rm Pr}(\underline{x}_0 | \underline{y}_2)$ drastisch zu &nbsp;&#8658;&nbsp; <u>Alle Lösungsvorschläge</u> sind richtig.
 +
 
 +
 
 +
 
 +
[[Datei:P_ID2991__KC_A_4_3f_v1.png|right|frame|Iterative Decodierung von $(–1, –1, +1)$]]
 +
'''(6)'''&nbsp; Richtig sind <u>die Lösungsvorschläge 2 und 3</u>:
 +
*Für den Empfangsvektor $\underline{y}_6 = (1, \, 1, \, 0)$ gilt die zweite Tabelle.
 +
 
 +
*Der Decoder entscheidet sich nun für die Folge $\underline{x}_1 = (1, \, 1, \, 1)$.
 +
*Der Fall &bdquo;$\underline{y}_3 = (1, \, 1, \, 0)$ empfangen unter der Voraussetzung $\underline{x}_1 = (1, \, 1, \, 1)$ gesendet&rdquo; würde genau der in der letzten Teilaufgabe betrachteten Konstellation &bdquo;$\underline{y}_2 = (0, \, 1, \, 0)$ empfangen und $\underline{x}_0 = (0, \, 0, \, 0)$ gesendet&rdquo; entsprechen.
 +
*Da aber $\underline{x}_0 = (0, \, 0, \, 0)$ gesendet wurde, gibt es nun zwei Bitfehler mit folgender Konsequenz:
 +
:* Der iterative Decoder entscheidet falsch.
 +
:* Mit jeder weiteren Iteration wird die falsche Entscheidung als zuverlässiger deklariert.
 +
 
 +
 
 +
 
 
{{ML-Fuß}}
 
{{ML-Fuß}}
  

Aktuelle Version vom 29. November 2022, 17:39 Uhr

BSC–Modell und mögliche Empfangswerte

Wir betrachten in dieser Aufgabe zwei Codes:

$$\underline{x} = \big (\hspace{0.05cm}(0, 0, 0), \hspace{0.1cm} (0, 1, 1), \hspace{0.1cm} (1, 0, 1), \hspace{0.1cm} (1, 1, 0) \hspace{0.05cm} \big ) \hspace{0.05cm}, $$
$$\underline{x} = \big (\hspace{0.05cm}(0, 0, 0), \hspace{0.1cm} (1, 1, 1) \hspace{0.05cm} \big ) \hspace{0.05cm}.$$


Der Kanal wird auf Bitebene durch das  BSC–Modell  beschrieben. Entsprechend der Grafik gilt dabei:

$${\rm Pr}(y_i \ne x_i) \hspace{-0.15cm} \ = \ \hspace{-0.15cm}\varepsilon = 0.269\hspace{0.05cm},$$
$${\rm Pr}(y_i = x_i) \hspace{-0.15cm} \ = \ \hspace{-0.15cm}1-\varepsilon = 0.731\hspace{0.05cm}.$$

Hierbei bezeichnet  $\varepsilon$  die Verfälschungswahrscheinlichkeit des BSC–Modells.

Bis auf die letzte Teilaufgabe wird stets von folgendem Empfangswert ausgegangen:

$$\underline{y} = (0, 1, 0) =\underline{y}_2 \hspace{0.05cm}. $$

Die hier gewählte Indizierung aller möglichen Empfangsvektoren kann der Grafik entnommen werden.

  • Der meistens betrachtete Vektor  $\underline{y}_2$  ist hierbei rot hervorgehoben.
  • Für die Teilaufgabe (6) gilt dann:
$$\underline{y} = (1, 1, 0) =\underline{y}_6 \hspace{0.05cm}. $$

Zur Decodierung sollen in der Aufgabe untersucht werden:

  • die  Syndromdecodierung, die bei den betrachteten Codes dem Konzept  Hard Decision Maximum Likelihood Detection  (HD–ML) folgt
    (Softwerte liegen beim BSC nicht vor),
  • die symbolweise  Soft–in Soft–out Decodierung  (SISO) entsprechend dieses Abschnitts.






Hinweise:

Symbolweise Soft–in Soft–out_Decodierung, sowie
Binary Symmetric Channel.
  • Das vom Decoder ausgewählte Codewort wird in den Fragen mit  $\underline{z}$  bezeichnet.



Fragebogen

1

Welche Aussagen gelten für die Decodierung des  $\text{SPC (3, 2, 2)}$?

Die HD–Syndromdecodierung liefert das Ergebnis  $\underline{z} = (0, \, 1, \, 0)$.
Die HD–Syndromdecodierung liefert das Ergebnis  $\underline{z} = (0, \, 0, \, 0)$.
Die HD–Syndromdecodierung versagt hier.

2

Welche Aussagen gelten für den  $\text{ RC (3, 1, 3)}$?

Die HD–Syndromdecodierung liefert das Ergebnis  $\underline{z} = (0, \, 1, \, 0)$.
Die HD–Syndromdecodierung liefert das Ergebnis  $\underline{z} = (0, \, 0, \, 0)$.
Die HD–Syndromdecodierung versagt hier.

3

Wie sicher ist diese Entscheidung, wenn man als Sicherheit  $S$  den Quotienten der Wahrscheinlichkeiten für eine richtige bzw. falsche Entscheidung definiert?
Setzen Sie die Verfälschungswahrscheinlichkeit des BSC–Modells zu  $\varepsilon = 26.9\%$.

$S \ = \ $

$\hspace{0.75cm} \ln {(S)} \ = \ $

4

Wie lauten die intrinsischen  $L$–Werte für die iterative symbolweise Decodierung des  $\text{RC (3, 1)}$–Empfangswortes  $\underline{y}_2 = (0, \, 1, \, 0)$?

$L_{\rm K}(1) \ = \ $

$L_{\rm K}(2) \ = \ $

$L_{\rm K}(3) \ = \ $

5

Welche Aussagen sind für die Decodierung des Empfangswortes  $\underline{y}_2 = (0, \, 1, \, 0)$  zutreffend? Gehen Sie weiterhin vom  $\text{RC (3, 1, 3)}$ aus.

Ab der ersten Iteration sind alle Vorzeichen von  $L_{\rm APP}(i)$  positiv.
Bereits nach der zweiten Iteration ist  ${\rm Pr}(\underline{x}_0\hspace{0.05cm} |\hspace{0.05cm} \underline{y}_2)$  größer als  $99\%$.
Mit jeder Iteration werden die Beträge  $L_{\rm APP}(i)$  größer.

6

Welche Aussagen sind für die Decodierung des Empfangswortes  $\underline{y}_6 = (1, 1, 0)$  zutreffend, wenn  $\underline{x}_0 = (0, 0, 0)$  gesendet wurde?

Der iterative Decoder entscheidet richtig.
Der iterative Decoder entscheidet falsch.
Die „Zuverlässigkeit” für „$\underline{y}_6 \Rightarrow \underline{x}_0$” steigt mit wachsendem  $I$.


Musterlösung

(1)  Richtig ist der Lösungsvorschlag 3:

  • Das Empfangswort $\underline{y}_2 = (0, 1, 0)$ ist kein gültiges Codewort des Single Parity–check Codes SPC (3, 2). Somit ist die erste Aussage falsch.
  • Da der SPC (3, 2) zudem nur die minimale Distanz $d_{\rm min} = 2$ aufweist, kann auch kein Fehler korrigiert werden.


(2)  Richtig ist der Lösungsvorschlag 2:

  • Die möglichen Codeworte beim RP (3, 1) sind $\underline{x}_0 = (0, 0, 0)$ und $\underline{x}_1 = (1, 1, 1)$.
  • Die minimale Distanz dieses Codes beträgt $d_{\rm min} = 3$, so dass $t = (d_{\rm min} \, - 1)/2 = 1$ Fehler korrigiert werden kann.
  • Neben $\underline{y}_0 = (0, 0, 0)$ werden auch $\underline{y}_1 = (0, 0, 1), \ \underline{y}_2 = (0, 1, 0)$ und $\underline{y}_4 = (1, 0, 0)$ dem Decodierergebnis $\underline{x}_0 = (0, 0, 0)$ zugeordnet.


(3)  Entsprechend dem BSC–Modell gilt für die bedingte Wahrscheinlichkeit, dass $\underline{y}_2 = (0, 1, 0)$ empfangen wird, unter der Voraussetzung, dass $\underline{x}_0 = (0, 0, 0)$ gesendet wurde:

$${\rm Pr}(\underline{y} = \underline{y}_2 \hspace{0.1cm}| \hspace{0.1cm}\underline{x} = \underline{x}_0 ) = (1-\varepsilon)^2 \cdot \varepsilon\hspace{0.05cm}.$$
  • Der erste Term $(1 \, –\varepsilon)^2$ gibt dabei die Wahrscheinlichkeit dafür an, dass das erste und das dritte Bit richtig übertragen wurden und $\varepsilon$ berücksichtigt die Verfälschungswahrscheinlichkeit für das zweite Bit.
  • Entsprechend gilt für das zweite mögliche Codewort $\underline{x}_1 = (1, 1, 1)$:
$${\rm Pr}(\underline{y} = \underline{y}_2 \hspace{0.1cm}| \hspace{0.1cm}\underline{x} = \underline{x}_1 ) = \varepsilon^2 \cdot (1-\varepsilon) \hspace{0.05cm}.$$
  • Nach dem Satz von Bayes gilt dann für die Rückschlusswahrscheinlichkeiten:
$${\rm Pr}(\hspace{0.1cm}\underline{x} = \underline{x}_0 \hspace{0.1cm}| \hspace{0.1cm}\underline{y} = \underline{y}_2 ) \hspace{-0.15cm} \ = \ \hspace{-0.15cm} {\rm Pr}(\underline{y} = \underline{y}_2 \hspace{0.1cm}| \hspace{0.1cm}\underline{x} = \underline{x}_0 ) \cdot \frac{{\rm Pr}(\underline{x} = \underline{x}_0)} {{\rm Pr}(\underline{y} = \underline{y}_2)} \hspace{0.05cm},$$
$${\rm Pr}(\hspace{0.1cm}\underline{x} = \underline{x}_1 \hspace{0.1cm}| \hspace{0.1cm}\underline{y} = \underline{y}_2 ) \hspace{-0.15cm} \ = \ \hspace{-0.15cm} {\rm Pr}(\underline{y} = \underline{y}_2 \hspace{0.1cm}| \hspace{0.1cm}\underline{x} = \underline{x}_1 ) \cdot \frac{{\rm Pr}(\underline{x} = \underline{x}_1)} {{\rm Pr}(\underline{y} = \underline{y}_2)} $$
$$\Rightarrow \hspace{0.3cm} S = \frac{{\rm Pr(richtige \hspace{0.15cm}Entscheidung)}} {{\rm Pr(falsche \hspace{0.15cm}Entscheidung) }} = \frac{(1-\varepsilon)^2 \cdot \varepsilon}{\varepsilon^2 \cdot (1-\varepsilon)}= \frac{(1-\varepsilon)}{\varepsilon}\hspace{0.05cm}.$$
  • Mit $\varepsilon = 0.269$ erhält man folgende Zahlenwerte:
$$S = {0.731}/{0.269}\hspace{0.15cm}\underline {= 2.717}\hspace{0.3cm}\Rightarrow \hspace{0.3cm}{\rm ln}\hspace{0.15cm}(S)\hspace{0.15cm} \underline {= 1}\hspace{0.05cm}.$$


(4)  Das Vorzeichen des Kanal–$L$–Wertes $L_{\rm K}(i)$ ist positiv, falls $y_i = 0$, und negativ für $y_i = 1$.

  • Der Betrag gibt die Zuverlässigkeit von $y_i$ an. Beim BSC–Modell gilt $|L_{\rm K}(i)| = \ln {(1 \, – \varepsilon)/\varepsilon} = 1$ für alle $i$. Also:
Iterative Decodierung von $(+1, –1, +1)$
$$\underline {L_{\rm K}}(1)\hspace{0.15cm} \underline {= +1}\hspace{0.05cm},\hspace{0.5cm} \underline {L_{\rm K}}(2)\hspace{0.15cm} \underline {= -1}\hspace{0.05cm},\hspace{0.5cm} \underline {L_{\rm K}}(3)\hspace{0.15cm} \underline {= +1}\hspace{0.05cm}.$$


(5)  Die nebenstehende Tabelle verdeutlicht die iterative symbolweise Decodierung ausgehend von $\underline{y}_2 = (0, \, 1, \, 0)$.
Diese Ergebnisse lassen sich wie folgt interpretieren:

  • Die Vorbelegung (Iteration $I = 0$) geschieht entsprechend $\underline{L}_{\rm APP} = \underline{L}_{\rm K}$. Eine harte Entscheidung  ⇒  „$\sign {\underline{L}_{\rm APP}(i)}$” würde zum Decodierergebnis $(0, \, 1, \, 0)$ führen. Die Zuverlässigkeit dieses offensichtlich falschen Ergebnisses wird mit $|{\it \Sigma}| = 1$ angegeben. Dieser Wert stimmt mit dem in Teilaufgaben (3) berechneten „$\ln (S)$” überein.
  • Nach der ersten Iteration $(I = 1)$ sind alle Aposteriori–$L$–Werte $L_{\rm APP}(i) = +1$. Eine harte Entscheidung würde hier das (voraussichtlich) richtige Ergebnis $\underline{x}_{\rm APP} = (0, \, 0, \, 0)$ liefern. Die Wahrscheinlichkeit, dass dieses Ergebnis richtig ist, wird durch $|{\it \Sigma}_{\rm APP}| = 3$ quantifiziert:
$${\rm ln}\hspace{0.25cm}\frac{{\rm Pr}(\hspace{0.1cm}\underline{x} = \underline{x}_0 \hspace{0.1cm}| \hspace{0.1cm}\underline{y}=\underline{y}_2)}{1-{\rm Pr}(\hspace{0.1cm}\underline{x} = \underline{x}_0 \hspace{0.1cm}| \hspace{0.1cm}\underline{y}=\underline{y}_2)} = 3 \hspace{0.3cm}\Rightarrow \hspace{0.3cm} \frac{{\rm Pr}(\hspace{0.1cm}\underline{x} = \underline{x}_0 \hspace{0.1cm}| \hspace{0.1cm}\underline{y}=\underline{y}_2)}{1-{\rm Pr}(\hspace{0.1cm}\underline{x} = \underline{x}_0 \hspace{0.1cm}| \hspace{0.1cm}\underline{y}=\underline{y}_2)} = {\rm e}^3 \approx 20$$
$$\hspace{0.3cm}\Rightarrow \hspace{0.3cm}{\rm Pr}(\hspace{0.1cm}\underline{x} = \underline{x}_0 \hspace{0.1cm}| \hspace{0.1cm}\underline{y}=\underline{y}_2) = {20}/{21} {\approx 95.39\%}\hspace{0.05cm}.$$
  • Die zweite Iteration bestätigt das Decodierergebnis der ersten Iteration. Die Zuverlässigkeit wird hier sogar mit „$9$” beziffert. Dieser Wert kann wie folgt interpretiert werden:
$$\frac{{\rm Pr}(\hspace{0.1cm}\underline{x} = \underline{x}_0 \hspace{0.1cm}| \hspace{0.1cm}\underline{y}=\underline{y}_2)}{1-{\rm Pr}(\hspace{0.1cm}\underline{x} = \underline{x}_0 \hspace{0.1cm}| \hspace{0.1cm}\underline{y}=\underline{y}_2)} = {\rm e}^9 \hspace{0.3cm}\Rightarrow \hspace{0.3cm} {\rm Pr}(\hspace{0.1cm}\underline{x} = \underline{x}_0 \hspace{0.1cm}| \hspace{0.1cm}\underline{y}=\underline{y}_2) = {{\rm e}^9}/{({\rm e}^9+1)} \approx 99.99\% \hspace{0.05cm}.$$
  • Mit jeder weiteren Iteration nimmt der Zuverlässigkeitswert und damit die Wahrscheinlichkeit ${\rm Pr}(\underline{x}_0 | \underline{y}_2)$ drastisch zu  ⇒  Alle Lösungsvorschläge sind richtig.


Iterative Decodierung von $(–1, –1, +1)$

(6)  Richtig sind die Lösungsvorschläge 2 und 3:

  • Für den Empfangsvektor $\underline{y}_6 = (1, \, 1, \, 0)$ gilt die zweite Tabelle.
  • Der Decoder entscheidet sich nun für die Folge $\underline{x}_1 = (1, \, 1, \, 1)$.
  • Der Fall „$\underline{y}_3 = (1, \, 1, \, 0)$ empfangen unter der Voraussetzung $\underline{x}_1 = (1, \, 1, \, 1)$ gesendet” würde genau der in der letzten Teilaufgabe betrachteten Konstellation „$\underline{y}_2 = (0, \, 1, \, 0)$ empfangen und $\underline{x}_0 = (0, \, 0, \, 0)$ gesendet” entsprechen.
  • Da aber $\underline{x}_0 = (0, \, 0, \, 0)$ gesendet wurde, gibt es nun zwei Bitfehler mit folgender Konsequenz:
  • Der iterative Decoder entscheidet falsch.
  • Mit jeder weiteren Iteration wird die falsche Entscheidung als zuverlässiger deklariert.