Aufgaben:Aufgabe 4.3: Iterative Decodierung beim BSC: Unterschied zwischen den Versionen
(27 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 ⇒ [[Kanalcodierung/Beispiele_bin%C3%A4rer_Blockcodes#Single_Parity.E2.80.93check_Codes_.281.29| 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 ⇒ [[Kanalcodierung/Beispiele_bin%C3%A4rer_Blockcodes#Wiederholungscodes| 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 [[Digitalsignal%C3%BCbertragung/Binary_Symmetric_Channel_(BSC)|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 $\ | + | 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 | + | 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 [[Kanalcodierung/Decodierung_linearer_Blockcodes#Verallgemeinerung_der_Syndromdecodierung|Syndromdecodierung]], die bei den | + | * die [[Kanalcodierung/Decodierung_linearer_Blockcodes#Verallgemeinerung_der_Syndromdecodierung|Syndromdecodierung]], die bei den betrachteten Codes dem Konzept <i>Hard Decision Maximum Likelihood Detection</i> (HD–ML) folgt <br>(Softwerte liegen beim BSC nicht vor), |
− | * die symbolweise [[Kanalcodierung/Soft%E2%80%93in_Soft%E2%80%93out_Decoder#Symbolweise_Soft.E2.80.93in_Soft.E2.80.93out_Decodierung|Soft–in Soft–out Decodierung]] (SISO) entsprechend dieses Abschnitts. | + | * die symbolweise [[Kanalcodierung/Soft%E2%80%93in_Soft%E2%80%93out_Decoder#Symbolweise_Soft.E2.80.93in_Soft.E2.80.93out_Decodierung|Soft–in Soft–out Decodierung]] (SISO) entsprechend dieses Abschnitts. |
+ | |||
+ | |||
+ | |||
+ | |||
+ | |||
+ | |||
+ | |||
+ | |||
''Hinweise:'' | ''Hinweise:'' | ||
− | * Die Aufgabe bezieht sich auf das Kapitel [[Kanalcodierung/Soft%E2%80%93in_Soft%E2%80%93out_Decoder| Soft–in Soft–out Decoder]]. | + | * Die Aufgabe bezieht sich auf das Kapitel [[Kanalcodierung/Soft%E2%80%93in_Soft%E2%80%93out_Decoder| Soft–in Soft–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–in Soft–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 $\underline{z}$ bezeichnet. | ||
+ | |||
Zeile 43: | Zeile 56: | ||
===Fragebogen=== | ===Fragebogen=== | ||
<quiz display=simple> | <quiz display=simple> | ||
− | {Welche Aussagen gelten für die Decodierung des SPC (3, 2, 2)? | + | {Welche Aussagen gelten für die Decodierung des $\text{SPC (3, 2, 2)}$? |
− | |type=" | + | |type="()"} |
− | - Die HD–Syndromdecodierung liefert das Ergebnis $\underline{z} = (0, \, 1, \, 0)$ | + | - 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 liefert das Ergebnis $\underline{z} = (0, \, 0, \, 0)$. |
+ Die HD–Syndromdecodierung versagt hier. | + Die HD–Syndromdecodierung versagt hier. | ||
− | {Welche Aussagen gelten für den RC (3, 1, 3)? | + | {Welche Aussagen gelten für den $\text{ RC (3, 1, 3)}$? |
− | |type=" | + | |type="()"} |
− | - Die HD–Syndromdecodierung liefert das Ergebnis $\underline{z} = (0, \, 1, \, 0)$ | + | - 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 liefert das Ergebnis $\underline{z} = (0, \, 0, \, 0)$. |
- Die HD–Syndromdecodierung versagt hier. | - Die HD–Syndromdecodierung versagt hier. | ||
− | {Wie sicher ist diese Entscheidung, wenn man als Sicherheit $S$ den Quotienten der Wahrscheinlichkeiten für eine richtige bzw. falsche Entscheidung definiert? | + | {Wie sicher ist diese Entscheidung, wenn man als Sicherheit $S$ den Quotienten der Wahrscheinlichkeiten für eine richtige bzw. falsche Entscheidung definiert? <br>Setzen Sie die Verfälschungswahrscheinlichkeit des BSC–Modells zu $\varepsilon = 26.9\%$. |
|type="{}"} | |type="{}"} | ||
− | $ | + | $S \ = \ ${ 2.717 3% } |
− | $\ln {(S)} \ = \ ${ 1 3% } | + | $\hspace{0.75cm} \ln {(S)} \ = \ ${ 1 3% } |
− | {Wie lauten die intrinsischen $L$–Werte für die iterative symbolweise Decodierung des RC (3, 1)–Empfangswortes $\underline{y}_2 = (0, \, 1, \, 0)$? | + | {Wie lauten die intrinsischen $L$–Werte für die iterative symbolweise Decodierung des $\text{RC (3, 1)}$–Empfangswortes $\underline{y}_2 = (0, \, 1, \, 0)$? |
|type="{}"} | |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 $\underline{y}_2 = (0, \, 1, \, 0)$ zutreffend? Gehen Sie weiterhin vom RC (3, 1, 3) aus. | + | {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. |
|type="[]"} | |type="[]"} | ||
− | + Ab der ersten Iteration sind alle Vorzeichen von $L_{\rm APP}(i)$ positiv. | + | + 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\%$. | + | + 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. | + | + Mit jeder Iteration werden die Beträge $L_{\rm APP}(i)$ größer. |
− | {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? | + | {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? |
|type="[]"} | |type="[]"} | ||
- Der iterative Decoder entscheidet richtig. | - Der iterative Decoder entscheidet richtig. | ||
+ Der iterative Decoder entscheidet falsch. | + Der iterative Decoder entscheidet falsch. | ||
− | + Die „Zuverlässigkeit” für „$\underline{y}_6 \Rightarrow \underline{x}_0$” steigt mit wachsendem $I$. | + | + Die „Zuverlässigkeit” für „$\underline{y}_6 \Rightarrow \underline{x}_0$” steigt mit wachsendem $I$. |
</quiz> | </quiz> | ||
===Musterlösung=== | ===Musterlösung=== | ||
{{ML-Kopf}} | {{ML-Kopf}} | ||
− | '''(1)''' | + | '''(1)''' Richtig ist der <u>Lösungsvorschlag 3</u>: |
− | '''(2)''' | + | *Das Empfangswort $\underline{y}_2 = (0, 1, 0)$ ist kein gültiges Codewort des <i>Single Parity–check Codes</i> SPC (3, 2). Somit ist die erste Aussage falsch. |
− | '''(3)''' | + | *Da der SPC (3, 2) zudem nur die minimale Distanz $d_{\rm min} = 2$ aufweist, kann auch kein Fehler korrigiert werden. |
− | '''(4)''' | + | |
− | '''(5)''' | + | |
+ | |||
+ | '''(2)''' 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)''' 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: | ||
+ | [[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)''' 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 ⇒ „$\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 ⇒ <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)''' 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 „$\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. | ||
+ | |||
+ | |||
+ | |||
{{ML-Fuß}} | {{ML-Fuß}} | ||
Aktuelle Version vom 29. November 2022, 17:39 Uhr
Wir betrachten in dieser Aufgabe zwei Codes:
- den Single Parity–Code ⇒ $\text{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 ⇒ $\text{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 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:
- Die Aufgabe bezieht sich auf das Kapitel Soft–in Soft–out Decoder.
- Bezug genommen wird insbesondere auf die Seiten
- Das vom Decoder ausgewählte Codewort wird in den Fragen mit $\underline{z}$ bezeichnet.
Fragebogen
Musterlösung
- 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:
- $$\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.
(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.