The channel is described at bit level by the [[Digital_Signal_Transmission/Binary_Symmetric_Channel|$\text{BSC model}$]]. According to the graphic, the following applies:
Der Kanal wird auf Bitebene durch das [[Digitalsignal%C3%BCbertragung/Binary_Symmetric_Channel_(BSC)|BSC–Modell]] beschrieben. Entsprechend der Grafik gilt dabei:
Here, $\varepsilon$ denotes the falsification probability of the BSC model.
*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 [[Channel_Coding/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 [[Channel_Coding/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.
For decoding purposes, the exercise will examine:
* the [[Channel_Coding/Decoding_of_Linear_Block_Codes#Generalization_of_syndrome_coding|"syndrome decoding"]], which follows the concept "hard decision maximum likelihood detection" $\rm (HD-ML)$ for the codes under consideration. <br>$($because soft values are not available at the BSC$)$;
* the bit-wise [[Channel_Coding/Soft-in_Soft-Out_Decoder#Bit-wise_soft-in_soft-out_decoding|"Soft–in Soft–out Decoding"]] $\rm (SISO)$ according to this section.
Line 43:
Line 34:
<u>Hints:</u>
* This exercise refers to the chapter [[Channel_Coding/Soft-in_Soft-Out_Decoder| "Soft–in Soft–out Decoder"]].
''Hinweise:''
* Reference is made in particular to the sections
* Die Aufgabe bezieht sich auf das Kapitel [[Channel_Coding/Soft%E2%80%93in_Soft%E2%80%93out_Decoder| Soft–in Soft–out Decoder]].
::[[Channel_Coding/Soft–in_Soft–out_Decoder#Symbolweise_Soft.E2.80.93in_Soft.E2.80.93out_Decodierung|Symbolweise Soft–in Soft–out_Decodierung]], sowie
* The code word selected by the decoder is denoted in the questions by $\underline{z}$.
* Das vom Decoder ausgewählte Codewort wird in den Fragen mit $\underline{z}$ bezeichnet.
===Fragebogen===
===Questions===
<quiz display=simple>
<quiz display=simple>
{Welche Aussagen gelten für die Decodierung des $\text{SPC (3, 2, 2)}$?
{Which statements are valid for decoding the $\text{SPC (3, 2, 2)}$?
|type="()"}
|type="()"}
- Die HD–Syndromdecodierung liefert das Ergebnis $\underline{z} = (0, \, 1, \, 0)$.
- The hard decision syndrome decoding yields the result $\underline{z} = (0, \, 1, \, 0)$.
- Die HD–Syndromdecodierung liefert das Ergebnis $\underline{z} = (0, \, 0, \, 0)$.
- The hard decision syndrome decoding returns the result $\underline{z} = (0, \, 0, \, 0)$.
+ Die HD–Syndromdecodierung versagt hier.
+ The hard decision syndrome decoding fails here.
{Welche Aussagen gelten für den $\text{ RC (3, 1, 3)}$?
{Which statements are valid for the $\text{ RC (3, 1, 3)}$?
|type="()"}
|type="()"}
- Die HD–Syndromdecodierung liefert das Ergebnis $\underline{z} = (0, \, 1, \, 0)$.
- The hard decision syndrome decoding returns the result $\underline{z} = (0, \, 1, \, 0)$.
+ Die HD–Syndromdecodierung liefert das Ergebnis $\underline{z} = (0, \, 0, \, 0)$.
+ The hard decision syndrome decoding returns the result $\underline{z} = (0, \, 0, \, 0)$.
- Die HD–Syndromdecodierung versagt hier.
- The hard decision syndrome decoding fails here.
{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\%$.
{How certain is this decision if we define reliability $($"security"$)$ $S$ as the quotient of the probabilities for a correct or an incorrect decision? <br>Set the falsification probability of the BSC model to $\varepsilon = 26.9\%$.
|type="{}"}
|type="{}"}
$S \ = \ ${ 2.717 3% }
$S \ = \ ${ 2.717 3% }
$\hspace{0.75cm} \ln {(S)} \ = \ ${ 1 3% }
$\hspace{0.75cm} \ln {(S)} \ = \ ${ 1 3% }
{Wie lauten die intrinsischen $L$–Werte für die iterative symbolweise Decodierung des $\text{RC (3, 1)}$–Empfangswortes $\underline{y}_2 = (0, \, 1, \, 0)$?
{What are the intrinsic log likelihood ratios for iterative bit-wise decoding of the $\text{RC (3, 1)}$ received word $\underline{y}_2 = (0, \, 1, \, 0)$?
|type="{}"}
|type="{}"}
$L_{\rm K}(1) \ = \ ${ 1 3% }
$L_{\rm K}(1) \ = \ ${ 1 3% }
Line 79:
Line 70:
$L_{\rm K}(3) \ = \ ${ 1 3% }
$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 $\text{RC (3, 1, 3)}$ aus.
{Which statements are true for decoding the received word $\underline{y}_2 = (0, \, 1, \, 0)$? Continue to assume the $\text{RC (3, 1, 3)}$.
|type="[]"}
|type="[]"}
+ Ab der ersten Iteration sind alle Vorzeichen von $L_{\rm APP}(i)$ positiv.
+ From the first iteration all signs of $L_{\rm APP}(i)$ are positive.
+ Bereits nach der zweiten Iteration ist ${\rm Pr}(\underline{x}_0\hspace{0.05cm} |\hspace{0.05cm} \underline{y}_2)$ größer als $99\%$.
+ Already after the second iteration ${\rm Pr}(\underline{x}_0\hspace{0.05cm} |\hspace{0.05cm} \underline{y}_2)$ is greater than $99\%$.
+ Mit jeder Iteration werden die Beträge $L_{\rm APP}(i)$ größer.
+ With each iteration the absolute values $|L_{\rm APP}(i)|$ become larger.
{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?
{Which statements are true for decoding the received word $\underline{y}_6 = (1, 1, 0)$, when $\underline{x}_0 = (0, 0, 0)$ was sent?
|type="[]"}
|type="[]"}
- Der iterative Decoder entscheidet richtig.
- The iterative decoder decides correctly.
+ Der iterative Decoder entscheidet falsch.
+ The iterative decoder decides wrong.
+ Die "Zuverlässigkeit" für "$\underline{y}_6 \Rightarrow \underline{x}_0$" steigt mit wachsendem $I$.
'''(1)''' Richtig ist der <u>Lösungsvorschlag 3</u>:
'''(1)''' Correct is the <u>proposed solution 3</u>:
*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.
*The received word $\underline{y}_2 = (0, 1, 0)$ is not a valid code word of the single parity–check code $\text{SPC (3, 2)}$. Thus, the first statement is false.
*Da der SPC (3, 2) zudem nur die minimale Distanz $d_{\rm min} = 2$ aufweist, kann auch kein Fehler korrigiert werden.
*In addition, since the $\text{SPC (3, 2)}$ has only the minimum distance $d_{\rm min} = 2$, no error can be corrected.
'''(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.
'''(2)''' Correct is the <u>proposed solution 2</u>:
*The possible code words at the $\text{RP (3, 1)}$ are $\underline{x}_0 = (0, 0, 0)$ and $\underline{x}_1 = (1, 1, 1)$.
*The minimum distance of this code is $d_{\rm min} = 3$, so $t = (d_{\rm min} \, - 1)/2 = 1$ error can be corrected.
*In addition to $\underline{y}_0 = (0, 0, 0)$, the received words $\underline{y}_1 = (0, 0, 1), \ \underline{y}_2 = (0, 1, 0)$, and $\underline{y}_4 = (1, 0, 0)$ are also assigned to the decoding result $\underline{x}_0 = (0, 0, 0)$.
'''(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:
'''(3)''' According to the BSC model, the conditional probability that $\underline{y}_2 = (0, 1, 0)$ is received, given that $\underline{x}_0 = (0, 0, 0)$ was sent:
*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.
*The first term $(1 \, –\varepsilon)^2$ indicates the probability that the first and third bit were transmitted correctly. $\varepsilon$ describes the falsification probability for the second bit.
*Entsprechend gilt für das zweite mögliche Codewort $\underline{x}_1 = (1, 1, 1)$:
*Correspondingly, for the second possible code word $\underline{x}_1 = (1, 1, 1)$:
'''(4)''' Das Vorzeichen des Kanal–$L$–Wertes $L_{\rm K}(i)$ ist positiv, falls $y_i = 0$, und negativ für $y_i = 1$.
'''(5)''' The adjacent table illustrates the iterative bit-wise decoding starting from $\underline{y}_2 = (0, \, 1, \, 0)$.
*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:
[[File:P_ID2988__KC_A_4_3e_v1.png|rightr|frame| Iterative Decodierung von $(+1, –1, +1)$]]
* The preassignment $($iteration $I = 0)$ happens according to $\underline{L}_{\rm APP} = \underline{L}_{\rm K}$. A hard decision ⇒ "$\sign \ {\underline{L}_{\rm APP}(i)}$" would lead to the decoding result $(0, \, 1, \, 0)$.
*The reliability of this obviously incorrect result is given as $|{\it \Sigma}_{\rm APP}| = 1$. This value agrees with $\ln (S)$ calculated in subtask '''(3)'''.
'''(5)''' Die nebenstehende Tabelle verdeutlicht die iterative symbolweise Decodierung ausgehend von $\underline{y}_2 = (0, \, 1, \, 0)$.
* After the first iteration $(I = 1)$ all a-posteriori log likelihood ratios are $L_{\rm APP}(i) = +1$. A hard decision here would yield the $($expected$)$ correct result $\underline{x}_{\rm APP} = (0, \, 0, \, 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:
* 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:
*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.
*The probability that this outcome is correct is quantified by $|{\it \Sigma}_{\rm APP}| = 3$:
* The second iteration confirms the decoding result of the first iteration. The reliability is even quantified here with $9$. This value can be interpreted as follows:
*With each further iteration the reliability value and thus the probability ${\rm Pr}(\underline{x}_0 | \underline{y}_2)$ increases drastically ⇒ <u>All proposed solutions</u> are correct.
[[File: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>:
'''(6)''' Correct are <u>the proposed solutions 2 and 3</u>:
*Für den Empfangsvektor $\underline{y}_6 = (1, \, 1, \, 0)$ gilt die zweite Tabelle.
*For the received vector $\underline{y}_6 = (1, \, 1, \, 0)$, the second table applies.
*The decoder now decides for the sequence $\underline{x}_1 = (1, \, 1, \, 1)$.
*The case »$\underline{y}_6 = (1, \, 1, \, 0)$ received under the condition $\underline{x}_1 = (1, \, 1, \, 1)$ sent« would correspond exactly to the constellation »$\underline{y}_2 = (0, \, 1, \, 0)$ received and $\underline{x}_0 = (0, \, 0, \, 0)$ sent« considered in the last subtask.
*But since $\underline{x}_0 = (0, \, 0, \, 0)$ was sent, there are now two bit errors with the following consequence:
:* The iterative decoder decides incorrectly.
*Der Decoder entscheidet sich nun für die Folge $\underline{x}_1 = (1, \, 1, \, 1)$.
:* With each further iteration the wrong decision is declared as more reliable.
*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.
the "syndrome decoding", which follows the concept "hard decision maximum likelihood detection" $\rm (HD-ML)$ for the codes under consideration. $($because soft values are not available at the BSC$)$;
The received word $\underline{y}_2 = (0, 1, 0)$ is not a valid code word of the single parity–check code $\text{SPC (3, 2)}$. Thus, the first statement is false.
In addition, since the $\text{SPC (3, 2)}$ has only the minimum distance $d_{\rm min} = 2$, no error can be corrected.
(2) Correct is the proposed solution 2:
The possible code words at the $\text{RP (3, 1)}$ are $\underline{x}_0 = (0, 0, 0)$ and $\underline{x}_1 = (1, 1, 1)$.
The minimum distance of this code is $d_{\rm min} = 3$, so $t = (d_{\rm min} \, - 1)/2 = 1$ error can be corrected.
In addition to $\underline{y}_0 = (0, 0, 0)$, the received words $\underline{y}_1 = (0, 0, 1), \ \underline{y}_2 = (0, 1, 0)$, and $\underline{y}_4 = (1, 0, 0)$ are also assigned to the decoding result $\underline{x}_0 = (0, 0, 0)$.
(3) According to the BSC model, the conditional probability that $\underline{y}_2 = (0, 1, 0)$ is received, given that $\underline{x}_0 = (0, 0, 0)$ was sent:
The first term $(1 \, –\varepsilon)^2$ indicates the probability that the first and third bit were transmitted correctly. $\varepsilon$ describes the falsification probability for the second bit.
Correspondingly, for the second possible code word $\underline{x}_1 = (1, 1, 1)$:
(5) The adjacent table illustrates the iterative bit-wise decoding starting from $\underline{y}_2 = (0, \, 1, \, 0)$.
These results can be interpreted as follows:
The preassignment $($iteration $I = 0)$ happens according to $\underline{L}_{\rm APP} = \underline{L}_{\rm K}$. A hard decision ⇒ "$\sign \ {\underline{L}_{\rm APP}(i)}$" would lead to the decoding result $(0, \, 1, \, 0)$.
The reliability of this obviously incorrect result is given as $|{\it \Sigma}_{\rm APP}| = 1$. This value agrees with $\ln (S)$ calculated in subtask (3).
After the first iteration $(I = 1)$ all a-posteriori log likelihood ratios are $L_{\rm APP}(i) = +1$. A hard decision here would yield the $($expected$)$ correct result $\underline{x}_{\rm APP} = (0, \, 0, \, 0)$.
The probability that this outcome is correct is quantified by $|{\it \Sigma}_{\rm APP}| = 3$:
The second iteration confirms the decoding result of the first iteration. The reliability is even quantified here with $9$. This value can be interpreted as follows:
With each further iteration the reliability value and thus the probability ${\rm Pr}(\underline{x}_0 | \underline{y}_2)$ increases drastically ⇒ All proposed solutions are correct.
Iterative decoding of $(–1, –1, +1)$
(6) Correct are the proposed solutions 2 and 3:
For the received vector $\underline{y}_6 = (1, \, 1, \, 0)$, the second table applies.
The decoder now decides for the sequence $\underline{x}_1 = (1, \, 1, \, 1)$.
The case »$\underline{y}_6 = (1, \, 1, \, 0)$ received under the condition $\underline{x}_1 = (1, \, 1, \, 1)$ sent« would correspond exactly to the constellation »$\underline{y}_2 = (0, \, 1, \, 0)$ received and $\underline{x}_0 = (0, \, 0, \, 0)$ sent« considered in the last subtask.
But since $\underline{x}_0 = (0, \, 0, \, 0)$ was sent, there are now two bit errors with the following consequence:
The iterative decoder decides incorrectly.
With each further iteration the wrong decision is declared as more reliable.
