Aufgaben:Exercise 4.3: Iterative Decoding at the BSC - Revision history

Guenter at 16:44, 30 November 2022

2022-11-30T16:44:56Z

Guenter at 16:32, 29 November 2022

2022-11-29T16:32:58Z

Show changes

Guenter at 15:27, 29 November 2022

2022-11-29T15:27:25Z

Guenter at 15:23, 29 November 2022

2022-11-29T15:23:59Z

Guenter at 15:20, 29 November 2022

2022-11-29T15:20:47Z

Guenter at 15:10, 29 November 2022

2022-11-29T15:10:36Z

Hwang at 19:14, 1 November 2022

2022-11-01T19:14:16Z

Noah at 17:05, 27 October 2022

2022-10-27T17:05:22Z

Noah at 17:04, 27 October 2022

2022-10-27T17:04:57Z

Show changes

Noah at 16:53, 27 October 2022

2022-10-27T16:53:59Z

@@ Line 1: / Line 1: @@
 {{quiz-Header|Buchseite=Channel_Coding/Soft-in_Soft-Out_Decoder}}
-[[File:P_ID2987__KC_A_4_3_v1.png|right|frame|BSC model and&nbsp; (above) <br>possible received values]]
+[[File:EN_KC_A_4_3.png|right|frame|BSC model and&nbsp; (above) <br>possible received values]]
 We consider in this exercise  two codes:
 * the&nbsp; "single parity&ndash;check code" &nbsp; &#8658; &nbsp; [[Channel_Coding/Examples_of_Binary_Block_Codes#Single_Parity-check_Codes| $\text{SPC (3, 2, 2)}$]]:

@@ Line 34: / Line 34: @@
 * the&nbsp; [[Channel_Coding/Decoding_of_Linear_Block_Codes#Generalization_of_syndrome_coding|"syndrome decoding"]],&nbsp; which follows the concept&nbsp; "hard decision maximum likelihood detection"&nbsp; $\rm (HD-ML)$&nbsp; for the codes under consideration. <br>$($because soft values are not available at the BSC$)$;
-* the symbol-wise&nbsp; [[Channel_Coding/Soft-in_Soft-Out_Decoder#Symbol-wise_soft-in_soft-out_decoding|"Soft&ndash;in Soft&ndash;out Decoding"]]&nbsp; $\rm (SISO)$&nbsp; according to this section.
+* the bit-wise&nbsp; [[Channel_Coding/Soft-in_Soft-Out_Decoder#Bit-wise_soft-in_soft-out_decoding|"Soft&ndash;in Soft&ndash;out Decoding"]]&nbsp; $\rm (SISO)$&nbsp; according to this section.
@@ Line 46: / Line 46: @@
 * Reference is made in particular to the sections
-:*[[Channel_Coding/Soft-in_Soft-Out_Decoder#Symbol-wise_soft-in_soft-out_decoding|"Symbol-wise Soft&ndash;in Soft&ndash;out Decoding"]],&nbsp;
+:*[[Channel_Coding/Soft-in_Soft-Out_Decoder#Bit-wise_soft-in_soft-out_decoding|"Bit-wise Soft&ndash;in Soft&ndash;out Decoding"]],&nbsp;
 :*[[Channel_Coding/Channel_Models_and_Decision_Structures#Binary_Symmetric_Channel_.E2.80.93_BSC|"Binary Symmetric Channel"]]
 * The code word selected by the decoder is denoted in the questions  by&nbsp; $\underline{z}$.
@@ Line 72: / Line 72: @@
 $\hspace{0.75cm} \ln {(S)} \ = \ ${ 1 3% }
-{What are the intrinsic log likelihood ratios for iterative symbol-wise decoding of the&nbsp; $\text{RC (3, 1)}$&nbsp; received word&nbsp; $\underline{y}_2 = (0, \, 1, \, 0)$?
+{What are the intrinsic log likelihood ratios for iterative bit-wise decoding of the&nbsp; $\text{RC (3, 1)}$&nbsp; received word&nbsp; $\underline{y}_2 = (0, \, 1, \, 0)$?
 |type="{}"}
 $L_{\rm K}(1) \ = \ ${ 1 3% }
@@ Line 137: / Line 137: @@
-'''(5)'''&nbsp; The adjacent table illustrates the iterative symbol-wise decoding starting from $\underline{y}_2 = (0, \, 1, \, 0)$.
+'''(5)'''&nbsp; The adjacent table illustrates the iterative bit-wise decoding starting from $\underline{y}_2 = (0, \, 1, \, 0)$.
 <br clear=all>
 These results can be interpreted as follows:

@@ Line 67: / Line 67: @@
 - The hard decision  syndrome decoding fails here.
-{How certain is this decision if we define reliability&nbsp; $($"security"$)$&nbsp; $S$&nbsp; as the quotient of the probabilities for a correct or an incorrect decision? <br>Set the falsificationtion probability of the BSC model to&nbsp; $\varepsilon = 26.9\%$.
+{How certain is this decision if we define reliability&nbsp; $($"security"$)$&nbsp; $S$&nbsp; as the quotient of the probabilities for a correct or an incorrect decision? <br>Set the falsification probability of the BSC model to&nbsp; $\varepsilon = 26.9\%$.
 |type="{}"}
 $S \ = \ ${ 2.717 3% }
@@ Line 88: / Line 88: @@
 - The iterative decoder decides correctly.
 + The iterative decoder decides wrong.
-+ The "reliability" for "$\underline{y}_6 \Rightarrow \underline{x}_0$" increases with increasing&nbsp; $I$.
++ The&nbsp; "reliability"&nbsp; for&nbsp; $\underline{y}_6 \Rightarrow \underline{x}_0$&nbsp; increases with increasing&nbsp; $I$.
 </quiz>

@@ Line 67: / Line 67: @@
 - The hard decision  syndrome decoding fails here.
-{How certain is this decision if we define certainty&nbsp; $($"security"$)$&nbsp; $S$&nbsp; as the quotient of the probabilities for a correct or an incorrect decision? <br>Set the falsificationtion probability of the BSC model to&nbsp; $\varepsilon = 26.9\%$.
+{How certain is this decision if we define reliability&nbsp; $($"security"$)$&nbsp; $S$&nbsp; as the quotient of the probabilities for a correct or an incorrect decision? <br>Set the falsificationtion probability of the BSC model to&nbsp; $\varepsilon = 26.9\%$.
 |type="{}"}
 $S \ = \ ${ 2.717 3% }
 $\hspace{0.75cm} \ln {(S)} \ = \ ${ 1 3% }
-{What are the intrinsic log likelihood ratios for iterative symbol-wise decoding of the&nbsp; $\text{RC (3, 1)}$ received word&nbsp; $\underline{y}_2 = (0, \, 1, \, 0)$?
+{What are the intrinsic log likelihood ratios for iterative symbol-wise decoding of the&nbsp; $\text{RC (3, 1)}$&nbsp; received word&nbsp; $\underline{y}_2 = (0, \, 1, \, 0)$?
 |type="{}"}
 $L_{\rm K}(1) \ = \ ${ 1 3% }
@@ Line 78: / Line 78: @@
 $L_{\rm K}(3) \ = \ ${ 1 3% }
-{Which statements are true for decoding the received word&nbsp; $\underline{y}_2 = (0, \, 1, \, 0)$&nbsp;? Continue to assume the&nbsp; $\text{RC (3, 1, 3)}$.
+{Which statements are true for decoding the received word&nbsp; $\underline{y}_2 = (0, \, 1, \, 0)$?&nbsp; Continue to assume the&nbsp; $\text{RC (3, 1, 3)}$.
 |type="[]"}
 + From the first iteration all signs of&nbsp; $L_{\rm APP}(i)$&nbsp; are positive.
 + Already after the second iteration&nbsp; ${\rm Pr}(\underline{x}_0\hspace{0.05cm} |\hspace{0.05cm} \underline{y}_2)$&nbsp; is greater than&nbsp; $99\%$.
-+ With each iteration the absolute values&nbsp; $L_{\rm APP}(i)$&nbsp; become larger.
++ With each iteration the absolute values&nbsp; $|L_{\rm APP}(i)|$&nbsp; become larger.
-{Which statements are true for decoding the received word&nbsp; $\underline{y}_6 = (1, 1, 0)$&nbsp; when&nbsp; $\underline{x}_0 = (0, 0, 0)$&nbsp; was sent?
+{Which statements are true for decoding the received word&nbsp; $\underline{y}_6 = (1, 1, 0)$,&nbsp; when&nbsp; $\underline{x}_0 = (0, 0, 0)$&nbsp; was sent?
 |type="[]"}
 - The iterative decoder decides correctly.

@@ Line 1: / Line 1: @@
 {{quiz-Header|Buchseite=Channel_Coding/Soft-in_Soft-Out_Decoder}}
-[[File:P_ID2987__KC_A_4_3_v1.png|right|frame|BSC model and possible received values]]
+[[File:P_ID2987__KC_A_4_3_v1.png|right|frame|BSC model and&nbsp; (above) <br>possible received values]]
-We consider two codes in this exercise:
+We consider in this exercise  two codes:
-* the Single Parity&ndash;Code &nbsp; &#8658; &nbsp; [[Channel_Coding/Examples_of_Binary_Block_Codes#Single_Parity-check_Codes| $\text{"SPC (3, 2, 2)"}$]]:
+* the&nbsp; "single parity&ndash;check code" &nbsp; &#8658; &nbsp; [[Channel_Coding/Examples_of_Binary_Block_Codes#Single_Parity-check_Codes| $\text{SPC (3, 2, 2)}$]]:
 :$$\underline{x} = \big (\hspace{0.05cm}(0, 0, 0), \hspace{0.1cm}
 (0, 1, 1), \hspace{0.1cm}
@@ Line 9: / Line 9: @@
 (1, 1, 0) \hspace{0.05cm} \big )
 \hspace{0.05cm}, $$
-* the repetition code &nbsp; &#8658; &nbsp; [[Channel_Coding/Examples_of_Binary_Block_Codes#Repetition_Codes| $\text{"RC (3, 1, 3)"}$]]:
+* the repetition code &nbsp; &#8658; &nbsp; [[Channel_Coding/Examples_of_Binary_Block_Codes#Repetition_Codes| $\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}.$$
-The channel is described at bit level by the&nbsp; [[Digital_Signal_Transmission/Binary_Symmetric_Channel|"BSC&ndash;model"]]&nbsp;. According to the graphic, the following applies:
+Here,&nbsp; $\varepsilon$&nbsp; denotes the falsification probability of the BSC model.
-Here,&nbsp; $\varepsilon$&nbsp; denotes the corruption probability of the BSC model.
+Except for the last subtask,&nbsp; the following received value is always assumed:
 :$$\underline{y} = (0, 1, 0) =\underline{y}_2
 \hspace{0.05cm}. $$
-The here chosen indexing of all possible received vectors can be taken from the graphic.
+The chosen indexing of all possible received vectors can be taken from the graphic.
-*The most considered vector&nbsp; $\underline{y}_2$&nbsp; is highlighted in red here.
+*The most considered vector&nbsp; $\underline{y}_2$&nbsp; is highlighted in red.
-*For the subtask '''(6)''' then applies:
 :$$\underline{y} = (1, 1, 0) =\underline{y}_6
 \hspace{0.05cm}. $$
 For decoding purposes, the exercise will examine:
-* the&nbsp; [[Channel_Coding/Decoding_of_Linear_Block_Codes#Generalization_of_syndrome_coding|"Syndrome Decoding"]], which follows the concept&nbsp; <i>hard decision maximum likelihood detection</i>&nbsp; (HD ML) for the codes under consideration. <br>(soft values are not available at the BSC),
+* the&nbsp; [[Channel_Coding/Decoding_of_Linear_Block_Codes#Generalization_of_syndrome_coding|"syndrome decoding"]],&nbsp; which follows the concept&nbsp; "hard decision maximum likelihood detection"&nbsp; $\rm (HD-ML)$&nbsp; for the codes under consideration. <br>$($because soft values are not available at the BSC$)$;
@@ Line 42: / Line 42: @@
+* Reference is made in particular to the sections
-Hints:
+:*[[Channel_Coding/Soft-in_Soft-Out_Decoder#Symbol-wise_soft-in_soft-out_decoding|"Symbol-wise Soft&ndash;in Soft&ndash;out Decoding"]],&nbsp;
-* This exercise refers to the chapter&nbsp; [[Channel_Coding/Soft-in_Soft-Out_Decoder| "Soft&ndash;in Soft&ndash;out Decoder"]].
+:*[[Channel_Coding/Channel_Models_and_Decision_Structures#Binary_Symmetric_Channel_.E2.80.93_BSC|"Binary Symmetric Channel"]]
-* Reference is made in particular to the pages
+* The code word selected by the decoder is denoted in the questions  by&nbsp; $\underline{z}$.
@@ Line 58: / Line 57: @@
 {Which statements are valid for decoding the&nbsp; $\text{SPC (3, 2, 2)}$?
 |type="()"}
-- The HD syndrome decoding yields the result&nbsp; $\underline{z} = (0, \, 1, \, 0)$.
+- The hard decision syndrome decoding yields the result&nbsp; $\underline{z} = (0, \, 1, \, 0)$.
-- The HD syndrome decoding returns the result&nbsp; $\underline{z} = (0, \, 0, \, 0)$.
+- The hard decision  syndrome decoding returns the result&nbsp; $\underline{z} = (0, \, 0, \, 0)$.
-+ The HD syndrome decoding fails here.
++ The hard decision  syndrome decoding fails here.
 {Which statements are valid for the&nbsp; $\text{ RC (3, 1, 3)}$?
 |type="()"}
-- The HD syndrome decoding returns the result&nbsp; $\underline{z} = (0, \, 1, \, 0)$.
+- The hard decision  syndrome decoding returns the result&nbsp; $\underline{z} = (0, \, 1, \, 0)$.
-+ The HD syndrome decoding returns the result&nbsp; $\underline{z} = (0, \, 0, \, 0)$.
++ The hard decision  syndrome decoding returns the result&nbsp; $\underline{z} = (0, \, 0, \, 0)$.
-- The HD syndrome decoding fails here.
+- The hard decision  syndrome decoding fails here.
-{How certain is this decision if we define certainty&nbsp; $S$&nbsp; as the quotient of the probabilities for a correct or incorrect decision? <br>Set the corruption probability of the BSC model to&nbsp; $\varepsilon = 26.9\%$.
+{How certain is this decision if we define certainty&nbsp; $($"security"$)$&nbsp; $S$&nbsp; as the quotient of the probabilities for a correct or an incorrect decision? <br>Set the falsificationtion probability of the BSC model to&nbsp; $\varepsilon = 26.9\%$.
 |type="{}"}
 $S \ = \ ${ 2.717 3% }
 $\hspace{0.75cm} \ln {(S)} \ = \ ${ 1 3% }
-{What are the intrinsic LLR for the iterative symbol-wise decoding of the&nbsp; $\text{RC (3, 1)}$ received word&nbsp; $\underline{y}_2 = (0, \, 1, \, 0)$?
+{What are the intrinsic log likelihood ratios for iterative symbol-wise decoding of the&nbsp; $\text{RC (3, 1)}$ received word&nbsp; $\underline{y}_2 = (0, \, 1, \, 0)$?
 |type="{}"}
 $L_{\rm K}(1) \ = \ ${ 1 3% }

@@ Line 49: / Line 49: @@
 ::[[Channel_Coding/Soft-in_Soft-Out_Decoder#Symbol-wise_soft-in_soft-out_decoding|"Symbol-wise Soft&ndash;in Soft&ndash;out_Decoding"]], as well as
 ::[[Channel_Coding/Channel_Models_and_Decision_Structures#Binary_Symmetric_Channel_.E2.80.93_BSC|''Binary Symmetric Channel'']]
-* The codeword selected by the decoder is denoted by&nbsp; $\underline{z}$&nbsp; in the questions.
+* The code word selected by the decoder is denoted by&nbsp; $\underline{z}$&nbsp; in the questions.
@@ Line 95: / Line 95: @@
 {{ML-Kopf}}
 '''(1)'''&nbsp; Correct is the <u>proposed solution 3</u>:
-*The received word $\underline{y}_2 = (0, 1, 0)$ is not a valid codeword of the <i>single parity&ndash;check code</i> SPC (3, 2). Thus, the first statement is false.
+*The received word $\underline{y}_2 = (0, 1, 0)$ is not a valid code word of the <i>single parity&ndash;check code</i> SPC (3, 2). Thus, the first statement is false.
 *In addition, since the SPC (3, 2) has only the minimum distance $d_{\rm min} = 2$, no error can be corrected.
@@ Line 101: / Line 101: @@
 '''(2)'''&nbsp; Correct is the <u>proposed solution 2</u>:
-*The possible codewords at RP (3, 1) are $\underline{x}_0 = (0, 0, 0)$ and $\underline{x}_1 = (1, 1, 1)$.
+*The possible code words at 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)$, $\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)$.

@@ Line 120: / Line 120: @@
 :$${\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)}}
+:$$\Rightarrow \hspace{0.3cm} S =  \frac{{\rm Pr(correct \hspace{0.15cm}decision)}}
 {{\rm Pr(wrong \hspace{0.15cm}decision) }} = \frac{(1-\varepsilon)^2 \cdot  \varepsilon}{\varepsilon^2 \cdot (1-\varepsilon)}= \frac{(1-\varepsilon)}{\varepsilon}\hspace{0.05cm}.$$

@@ Line 1: / Line 1: @@
-{{quiz-Header|Buchseite=Kanalcodierung/Soft–in Soft–out Decoder}}
+{{quiz-Header|Buchseite=Channel_Coding/Soft-in_Soft-Out_Decoder}}
-[[File:P_ID2987__KC_A_4_3_v1.png|right|frame|BSC–Modell und mögliche Empfangswerte]]
+[[File:P_ID2987__KC_A_4_3_v1.png|right|frame|BSC model and possible received values]]
 Wir betrachten in dieser Aufgabe zwei Codes:
-* den Single Parity&ndash;Code &nbsp; &#8658; &nbsp; [[Channel_Coding/Beispiele_bin%C3%A4rer_Blockcodes#Single_Parity.E2.80.93check_Codes_.281.29| $\text{SPC (3, 2, 2)}$]]:
+* den Single Parity&ndash;Code &nbsp; &#8658; &nbsp; [[Channel_Coding/Examples_of_Binary_Block_Codes#Single_Parity-check_Codes| $\text{"SPC (3, 2, 2)"}$]]:
 :$$\underline{x} = \big (\hspace{0.05cm}(0, 0, 0), \hspace{0.1cm}
 (0, 1, 1), \hspace{0.1cm}
@@ Line 9: / Line 9: @@
 (1, 1, 0) \hspace{0.05cm} \big )
 \hspace{0.05cm}, $$
-* den Wiederholungscode &nbsp; &#8658; &nbsp; [[Channel_Coding/Beispiele_bin%C3%A4rer_Blockcodes#Wiederholungscodes| $\text{RC (3, 1, 3)}$]]:
+* den Wiederholungscode &nbsp; &#8658; &nbsp; [[Channel_Coding/Examples_of_Binary_Block_Codes#Repetition_Codes| $\text{"RC (3, 1, 3)"}$]]:
 :$$\underline{x} = \big (\hspace{0.05cm}(0, 0, 0), \hspace{0.1cm}
 (1, 1, 1)  \hspace{0.05cm} \big )
@@ Line 15: / Line 15: @@
-Der Kanal wird auf Bitebene durch das&nbsp; [[Digitalsignal%C3%BCbertragung/Binary_Symmetric_Channel_(BSC)|BSC&ndash;Modell]]&nbsp; beschrieben. Entsprechend der Grafik gilt dabei:
+Der Kanal wird auf Bitebene durch das&nbsp; [[Digital_Signal_Transmission/Binary_Symmetric_Channel|"BSC&ndash;Modell"]]&nbsp; 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}.$$
@@ Line 32: / Line 32: @@
 Zur Decodierung sollen in der Aufgabe untersucht werden:
-* die&nbsp; [[Channel_Coding/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&nbsp; [[Channel_Coding/Decoding_of_Linear_Block_Codes#Generalization_of_syndrome_coding|"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&nbsp; [[Channel_Coding/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.
+* die symbolweise&nbsp; [[Channel_Coding/Soft-in_Soft-Out_Decoder#Symbol-wise_soft-in_soft-out_decoding|"Soft&ndash;in Soft&ndash;out Decodierung"]]&nbsp; (SISO) entsprechend dieses Abschnitts.
@@ Line 45: / Line 45: @@
 ''Hinweise:''
-* Die Aufgabe bezieht sich auf das Kapitel&nbsp; [[Channel_Coding/Soft%E2%80%93in_Soft%E2%80%93out_Decoder| Soft&ndash;in Soft&ndash;out Decoder]].
+* Die Aufgabe bezieht sich auf das Kapitel&nbsp; [[Channel_Coding/Soft-in_Soft-Out_Decoder| "Soft&ndash;in Soft&ndash;out Decoder"]].
 * Bezug genommen wird insbesondere auf die Seiten
-::[[Channel_Coding/Soft–in_Soft–out_Decoder#Symbolweise_Soft.E2.80.93in_Soft.E2.80.93out_Decodierung|Symbolweise Soft&ndash;in Soft&ndash;out_Decodierung]], sowie
+::[[Channel_Coding/Soft-in_Soft-Out_Decoder#Symbol-wise_soft-in_soft-out_decoding|"Symbolweise Soft&ndash;in Soft&ndash;out_Decodierung"]], sowie
-::[[Channel_Coding/Kanalmodelle_und_Entscheiderstrukturen#Binary_Symmetric_Channel_.E2.80.93_BSC|''Binary Symmetric Channel'']].
+::[[Channel_Coding/Channel_Models_and_Decision_Structures#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.