Exercise 4.3: Iterative Decoding at the BSC

• Return to book

BSC–Modell und mögliche Empfangswerte

Wir betrachten in dieser Aufgabe zwei Codes:

• den Single Parity–Code  ⇒  SPC (3, 2, 2):

$$\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},$$

• den Wiederholungscode  ⇒  RC (3, 1, 3):

$$\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 meist 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 hier betrachteten Codes als Hard Decision Maximum Likelihood Detection (HD–ML) vornimmt (Softwerte liegen beim BSC nicht vor).
• die symbolweise Soft–in Soft–out Decodierung (SISO) entsprechend dieses Abschnitts.

Hinweise:

• Die Aufgabe bezieht sich auf das Kapitel Soft–in Soft–out Decoder.
• Bezug genommen wird insbesondere auf die Seiten Symbolweise Soft–in Soft–out_Decodierung sowie Binary Symmetric Channel.
• Das vom Decoder ausgewählte Codewort wird in den Fragen mit $\underline{z}$ bezeichnet.
• Sollte die Eingabe des Zahlenwertes „0” erforderlich sein, so geben Sie bitte „0.” ein.

Fragebogen

1

Welche Aussagen gelten für die Decodierung des 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 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 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 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 | \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

Solution

(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 \, – \epsilon)/\epsilon} = 1$ für alle $i$. Also:

$$\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}.$$

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

(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 = (1, \, 0, \, 1)$ 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.