Difference between revisions of "Aufgaben:Exercise 4.4Z: Supplement to Exercise 4.4"

From LNTwww
 
(16 intermediate revisions by 3 users not shown)
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_ID2994__KC_Z_4_4_v3.png |right|frame|Hamming–Gewichte und Sequenzwahrscheinlichkeiten ]]
+
[[File:P_ID2994__KC_Z_4_4_v3.png |right|frame|Hamming weights&nbsp; $w_{\rm H}(\underline{x})$, <br>sequence probabilities&nbsp; ${\rm Pr}(\underline{x})$ ]]
Der Informationstheoretiker&nbsp; [https://de.wikipedia.org/wiki/Robert_Gray_Gallager Robert G. Gallager]&nbsp; hat sich bereits 1963 mit folgender Fragestellung beschäftigt:
+
The information theorist&nbsp; [https://en.wikipedia.org/wiki/Robert_G._Gallager $\text{Robert G. Gallager}$]&nbsp; dealt already in 1963 with the following problem:
* Gegeben ist ein Zufallsvektor&nbsp; $\underline{x} = (x_1, \, x_2, \hspace{-0.04cm} \text{ ...} \hspace{0.08cm} , x_n)$&nbsp; mit&nbsp; $n$&nbsp; binären Elementen&nbsp; $x_i &#8712; \{0, \, 1\}$.
+
* Given a random vector&nbsp; $\underline{x} = (x_1, \, x_2, \hspace{-0.04cm} \text{ ...} \hspace{0.08cm} , x_n)$&nbsp; with&nbsp; $n$&nbsp; binary elements&nbsp; $x_i &#8712; \{0, \, 1\}$.
* Bekannt sind alle Wahrscheinlichkeiten&nbsp; $p_i = {\rm Pr}(x_i = 1)$&nbsp; und&nbsp; $q_i = {\rm Pr}(x_i = 0) = 1 - p_i$&nbsp; mit Index&nbsp; $i = 1, \hspace{-0.04cm}\text{ ...} \hspace{0.08cm} ,\ n$.
 
* Gesucht ist die Wahrscheinlichkeit, dass die Anzahl der Einsen in diesem Vektor geradzahlig ist.
 
* Oder ausgedrückt mit dem&nbsp; [[Kanalcodierung/Zielsetzung_der_Kanalcodierung#Einige_wichtige_Definitionen_zur_Blockcodierung|Hamming&ndash;Gewicht]]: &nbsp; Wie groß ist die Wahrscheinlichkeit&nbsp; ${\rm Pr}[w_{\rm H}(\underline{x}) {\rm \ ist \ gerade}]$?
 
  
 +
* Known are all probabilities&nbsp; $p_i = {\rm Pr}(x_i = 1)$&nbsp; and&nbsp; $q_i = {\rm Pr}(x_i = 0) = 1 - p_i$&nbsp; with index&nbsp; $i = 1, \hspace{-0.04cm}\text{ ...} \hspace{0.08cm} ,\ n$.
  
Die Grafik verdeutlicht die Aufgabenstellung für das Beispiel&nbsp; $n = 4$&nbsp; sowie&nbsp; $p_1 = 0.2$,&nbsp; $p_2 = 0.9$,&nbsp; $p_3 = 0.3$&nbsp; und&nbsp; $p_4 = 0.6$.  
+
* What we are looking for is the probability that the number of&nbsp; "ones"&nbsp; in this vector is even.
* Für die grün hinterlegte Zeile &nbsp; &#8658; &nbsp; $\underline{x} = (1, \, 0, \, 0, \, 1)$&nbsp; gilt&nbsp; $w_{\rm H}(\underline{x}) = 2$&nbsp; und
+
 
 +
* Or expressed using the&nbsp; [[Channel_Coding/Objective_of_Channel_Coding#Important_definitions_for_block_coding|"Hamming weight"]]: &nbsp; What is the probability&nbsp; ${\rm Pr}[w_{\rm H}(\underline{x}) {\rm \ is \ even}]$?
 +
 
 +
 
 +
The graph illustrates the task for the example&nbsp; $n = 4$&nbsp; and&nbsp; $p_1 = 0.2$,&nbsp; $p_2 = 0.9$,&nbsp; $p_3 = 0.3$&nbsp; and&nbsp; $p_4 = 0.6$.  
 +
* For the row highlighted in green &nbsp; &#8658; &nbsp; $\underline{x} = (1, \, 0, \, 0, \, 1)$&nbsp; holds&nbsp; $w_{\rm H}(\underline{x}) = 2$&nbsp; and
 
:$${\rm Pr}(\underline{x}) = p_1 \cdot q_2 \cdot q_3 \cdot p_4 = 0.0084.$$
 
:$${\rm Pr}(\underline{x}) = p_1 \cdot q_2 \cdot q_3 \cdot p_4 = 0.0084.$$
* Blaue Schrift bedeutet &bdquo;$w_{\rm H}(\underline{x})$ ist gerade&rdquo;. Rote Schrift steht für &bdquo;$w_{\rm H}(\underline{x})$ ist ungerade&rdquo;.
+
* Blue font means&nbsp; "$w_{\rm H}(\underline{x})$&nbsp; is even".&nbsp; Red font stands for&nbsp; "$w_{\rm H}(\underline{x})$&nbsp; is odd."
* Die Wahrscheinlichkeit&nbsp; ${\rm Pr}[w_{\rm H}(\underline{x}) {\rm \ ist \ gerade}]$&nbsp; ist die Summe der blauen Zahlen in der letzten Spalte.
 
*Die Summe der roten Zahlen ergibt&nbsp; ${\rm Pr}[w_{\rm H}(\underline{x}) {\rm \ ist \ ungerade}] = 1 - {\rm Pr}[w_{\rm H}(\underline{x}) {\rm \ ist \ gerade}]$.
 
  
 +
*The probability&nbsp; ${\rm Pr}[w_{\rm H}(\underline{x}) {\rm \ is \ even}]$&nbsp; is the sum of the blue numbers in the last column.
 +
 +
*The sum of the red numbers gives&nbsp; ${\rm Pr}[w_{\rm H}(\underline{x}) {\rm \ is \ odd}] = 1 - {\rm Pr}[w_{\rm H}(\underline{x}) {\rm \ is \ even}]$.
  
Gallager hat das Problem in analytischer Weise gelöst:
+
 
:$$ {\rm Pr} \left [w_{\rm H}(\underline{x})\hspace{0.15cm}{\rm ist \hspace{0.15cm} gerade} \right ]
+
Gallager solved the problem in an analytical way:
 +
:$$ {\rm Pr} \left [w_{\rm H}(\underline{x})\hspace{0.15cm}{\rm is \hspace{0.15cm} even} \right ]
 
\hspace{-0.15cm} \ = \ \hspace{-0.15cm} 1/2 \cdot [1 + \pi]\hspace{0.05cm},$$
 
\hspace{-0.15cm} \ = \ \hspace{-0.15cm} 1/2 \cdot [1 + \pi]\hspace{0.05cm},$$
:$${\rm Pr} \left [w_{\rm H}(\underline{x})\hspace{0.15cm}{\rm ist \hspace{0.15cm} ungerade}
+
:$${\rm Pr} \left [w_{\rm H}(\underline{x})\hspace{0.15cm}{\rm is \hspace{0.15cm} odd}
 
\right ] \hspace{-0.15cm} \ = \ \hspace{-0.15cm} 1/2 \cdot [1 - \pi]\hspace{0.05cm}.$$
 
\right ] \hspace{-0.15cm} \ = \ \hspace{-0.15cm} 1/2 \cdot [1 - \pi]\hspace{0.05cm}.$$
  
Hierbei ist die folgende Hilfsgröße verwendet:
+
Here the following auxiliary variable is used:
 
:$$\pi = \prod\limits_{i =1}^{n} \hspace{0.25cm}(1-2p_i)  
 
:$$\pi = \prod\limits_{i =1}^{n} \hspace{0.25cm}(1-2p_i)  
 
  \hspace{0.05cm}.$$
 
  \hspace{0.05cm}.$$
  
Die Gleichung wendet man zum Beispiel an, um die extrinsischen&nbsp; $L$&ndash;Werte eines&nbsp; <i>Single Parity&ndash;check Codes</i>&nbsp; zu berechnen.  
+
One applies the equation,&nbsp; for example,&nbsp; to calculate the extrinsic&nbsp; L&ndash;values of a&nbsp; "single parity&ndash;check code".  
  
Wie bereits in der&nbsp; [[Aufgaben:4.4_Extrinsische_L%E2%80%93Werte_beim_SPC| Aufgabe A4.4]]&nbsp; dargelegt, lautet nämlich der extrinsische $L$&ndash;Wert mit dem Hamming&ndash;Gewicht&nbsp; $w_{\rm H}$&nbsp; der verkürzten Folge&nbsp; $\underline{x}^{(-i)}$:
+
Indeed,&nbsp; as already pointed out in&nbsp; [[Aufgaben:Exercise_4.4:_Extrinsic_L-values_at_SPC| $\text{Exercise 4.4}$]]&nbsp; the extrinsic log likelihood ratio with Hamming&ndash;weight&nbsp; $w_{\rm H}$&nbsp; is the truncated sequence&nbsp; $\underline{x}^{(-i)}$:
:$$L_{\rm E}(i) = {\rm ln} \hspace{0.15cm}\frac{{\rm Pr} \left [w_{\rm H}(\underline{x}^{(-i)})\hspace{0.15cm}{\rm ist \hspace{0.15cm} gerade} \hspace{0.05cm} | \hspace{0.05cm}\underline{y} \hspace{0.05cm}\right ]}{{\rm Pr} \left [w_{\rm H}(\underline{x}^{(-i)})\hspace{0.15cm}{\rm ist \hspace{0.15cm} ungerade} \hspace{0.05cm} | \hspace{0.05cm}\underline{y} \hspace{0.05cm}\right ]}
+
:$$L_{\rm E}(i) = {\rm ln} \hspace{0.15cm}\frac{{\rm Pr} \left [w_{\rm H}(\underline{x}^{(-i)})\hspace{0.15cm}{\rm is \hspace{0.15cm} even} \hspace{0.05cm} | \hspace{0.05cm}\underline{y} \hspace{0.05cm}\right ]}{{\rm Pr} \left [w_{\rm H}(\underline{x}^{(-i)})\hspace{0.15cm}{\rm is \hspace{0.15cm} odd} \hspace{0.05cm} | \hspace{0.05cm}\underline{y} \hspace{0.05cm}\right ]}
 
  \hspace{0.05cm}.$$
 
  \hspace{0.05cm}.$$
  
Hierbei ist berücksichtigt, dass man für&nbsp; $L_{\rm E}(i)$&nbsp; nur die anderen Symbole&nbsp; $(j &ne; i)$&nbsp; heranziehen darf:
+
Here it is taken into account that for&nbsp; $L_{\rm E}(i)$&nbsp; one may refer only to the other symbols&nbsp; $(j &ne; i)$&nbsp;:
 
:$$\underline{x}^{(-i)} = \big ( \hspace{0.03cm}x_1, \hspace{-0.04cm} \text{ ...} \hspace{0.08cm}  , \hspace{0.03cm} x_{i-1}, \hspace{0.43cm} x_{i+1},  \hspace{-0.04cm} \text{ ...} \hspace{0.08cm}  , x_{n} \hspace{0.03cm} \big )\hspace{0.03cm}. $$
 
:$$\underline{x}^{(-i)} = \big ( \hspace{0.03cm}x_1, \hspace{-0.04cm} \text{ ...} \hspace{0.08cm}  , \hspace{0.03cm} x_{i-1}, \hspace{0.43cm} x_{i+1},  \hspace{-0.04cm} \text{ ...} \hspace{0.08cm}  , x_{n} \hspace{0.03cm} \big )\hspace{0.03cm}. $$
  
Line 41: Line 46:
  
  
 +
<u>Hints:</u>
 +
*This exercise belongs to the chapter&nbsp; [[Channel_Coding/Soft%E2%80%93in_Soft%E2%80%93out_Decoder|"Soft&ndash;in Soft&ndash;out Decoder"]].
  
 +
*Reference is made in particular to the section&nbsp; [[Channel_Coding/Soft-in_Soft-Out_Decoder#Calculation_of_extrinsic_log_likelihood_ratios|"For calculating the extrinsic log likelihood ratios"]].
  
 
+
*The exercise is intended as a supplement to&nbsp; [[Aufgaben:Exercise_4.4:_Extrinsic_L-values_at_SPC| $\text{Exercise 4.4}$]]&nbsp;.
''Hinweise:''
 
* Die Aufgabe gehört zum Kapitel&nbsp; [[Kanalcodierung/Soft%E2%80%93in_Soft%E2%80%93out_Decoder| Soft&ndash;in Soft&ndash;out Decoder]].
 
*Bezug genommen wird insbesondere auf die Seite&nbsp; [[Kanalcodierung/Soft–in_Soft–out_Decoder#Zur_Berechnung_der_extrinsischen_L.E2.80.93Werte|Zur Berechnung der extrinsischen L&ndash;Werte]].
 
*Die Aufgabe ist als Ergänzung zur&nbsp; [[Aufgaben:Aufgabe_4.4:_Extrinsische_L–Werte_beim_SPC| Aufgabe 4.4]]&nbsp; gedacht.
 
 
   
 
   
  
  
  
===Fragebogen===
+
===Questions===
 
<quiz display=simple>
 
<quiz display=simple>
{Wir betrachten den Vektor&nbsp; $\underline{x} = (x_1, \, x_2) \ \Rightarrow \ n = 2$&nbsp; mit&nbsp; $x_i &#8712; \{0, \, 1\}$&nbsp; und&nbsp; $p_1 = 0.2, \ p_2 = 0.9$.  <br>Wie groß ist die Wahrscheinlichkeit, dass&nbsp; $\underline{x}$&nbsp; eine gerade Anzahl an Einsen beinhaltet?
+
{We consider the vector&nbsp; $\underline{x} = (x_1, \, x_2) \ \Rightarrow \ n = 2$&nbsp; with&nbsp; $x_i &#8712; \{0, \, 1\}$&nbsp; and&nbsp; $p_1 = 0.2, \ p_2 = 0.9$.  <br>What is the probability that &nbsp; $\underline{x}$ &nbsp; contains an even number of&nbsp; "ones"&nbsp;?
 
|type="{}"}
 
|type="{}"}
${\rm Pr}\big [w_{\rm H}(\underline{x}) \ {\rm ist \ gerade}\big ] \ = \ ${ 0.26 3% }
+
${\rm Pr}\big [w_{\rm H}(\underline{x}) \ {\rm is \ even}\big ] \ = \ ${ 0.26 3% }
  
{Berechnen Sie die gleiche Wahrscheinlichkeit für&nbsp; $\underline{x} = (x_1, \, x_2, \, x_3) \ \Rightarrow \ n = 3$&nbsp;  und&nbsp; $p_1 = 0.2, \ p_2 = 0.9, \ p_3 = 0.3$.
+
{Compute the same probability for&nbsp; $\underline{x} = (x_1, \, x_2, \, x_3) \ \Rightarrow \ n = 3$&nbsp;  and&nbsp; $p_1 = 0.2, \ p_2 = 0.9, \ p_3 = 0.3$.
 
|type="{}"}
 
|type="{}"}
${\rm Pr}\big [w_{\rm H}(\underline{x}) \ {\rm ist \ gerade}\big ] \ = \ ${ 0.404 3% }
+
${\rm Pr}\big [w_{\rm H}(\underline{x}) \ {\rm is \ even}\big ] \ = \ ${ 0.404 3% }
  
{Nun gelte&nbsp; $n = 4$&nbsp; und&nbsp; $p_1 = 0.2, \ p_2 = 0.9, \ p_3 = 0.3, \ p_4 = 0.6$. Berechnen Sie nach der Gallager&ndash;Gleichung folgende Größen:
+
{Now let be&nbsp; $n = 4$&nbsp; and&nbsp; $p_1 = 0.2, \ p_2 = 0.9, \ p_3 = 0.3, \ p_4 = 0.6$.&nbsp; Calculate the following quantities according to Gallager's equation:
 
|type="{}"}
 
|type="{}"}
${\rm Pr(blau) = Pr}\big [w_{\rm H}(\underline{x}) \ {\rm ist \ gerade}\big ] \hspace{0.33cm} = \ ${ 0.5192 3% }
+
${\rm Pr(blue) = Pr}\big [w_{\rm H}(\underline{x}) \ {\rm is \ even}\big ] \hspace{0.33cm} = \ ${ 0.5192 3% }
${\rm Pr(rot) = Pr}\big [w_{\rm H}(\underline{x}) \ {\rm ist \ ungerade}\big ] \hspace{0.1cm} = \ ${ 0.4808 3% }
+
${\rm Pr(red) = Pr}\big [w_{\rm H}(\underline{x}) \ {\rm is \ odd}\big ] \hspace{0.1cm} = \ ${ 0.4808 3% }
 
$\text{Quotient }Q = {\rm Pr(blau)/Pr(rot)} \hspace{0.4cm} = \ ${ 1.0799 3% }
 
$\text{Quotient }Q = {\rm Pr(blau)/Pr(rot)} \hspace{0.4cm} = \ ${ 1.0799 3% }
  
{Wie groß ist der extrinsische&nbsp; $L$&ndash;Wert für das Symbol&nbsp; $i = 5$&nbsp; beim&nbsp; $\text{SPC (5, 4, 2)}$&nbsp; mit&nbsp; $p_1 = 0.2, \ p_2 = 0.9, \ p_3 = 0.3, \ p_4 = 0.6, \ p_5 = 0.9$?
+
{What is the extrinsic log likelihood ratio for the symbol&nbsp; $i = 5$&nbsp; at&nbsp; $\text{SPC (5, 4, 2)}$&nbsp; with&nbsp; $p_1 = 0.2, \ p_2 = 0.9, \ p_3 = 0.3, \ p_4 = 0.6, \ p_5 = 0.9$?
 
|type="{}"}
 
|type="{}"}
 
$L_{\rm E}(i = 5) \ = \ ${ 0.077 3% }
 
$L_{\rm E}(i = 5) \ = \ ${ 0.077 3% }
  
{Wie ändert sich&nbsp; $L_{\rm E}(i = 5)$, wenn man stattdessen von&nbsp; $p_5 = 0.1$&nbsp; ausgeht?
+
{How does&nbsp; $L_{\rm E}(i = 5)$&nbsp; change if we assume&nbsp; $p_5 = 0.1$&nbsp; instead?
 
|type="()"}
 
|type="()"}
- $L_{\rm E}(i = 5)$&nbsp; wird größer.
+
- $L_{\rm E}(i = 5)$&nbsp; becomes larger.
- $L_{\rm E}(i = 5)$&nbsp; wird kleiner.
+
- $L_{\rm E}(i = 5)$&nbsp; becomes smaller.
+ $L_{\rm E}(i = 5)$&nbsp; wird gegenüber Teilaufgabe '''(4)''' nicht verändert.
+
+ $L_{\rm E}(i = 5)$&nbsp; is not changed compared to subtask&nbsp; '''(4)'''.
 
</quiz>
 
</quiz>
  
===Musterlösung===
+
===Solution===
 
{{ML-Kopf}}
 
{{ML-Kopf}}
[[File:P_ID2996__KC_Z_4_4a_v1.png|frame|right|Herleitung „$w_{\rm H}$ ist gerade” für die Codelänge $n = 2$]]
+
[[File:P_ID2996__KC_Z_4_4a_v1.png|frame|right|Derivation&nbsp; "$w_{\rm H}$ is even"&nbsp; for code length&nbsp; $n = 2$.]]
'''(1)'''&nbsp;  Entsprechend der nebenstehenden Tabelle gilt:
+
'''(1)'''&nbsp;  According to the adjacent table applies:
:$${\rm Pr} \left [w_{\rm H}(\underline{x})\hspace{0.10cm}{\rm ist \hspace{0.10cm} gerade}\right ] =
+
:$${\rm Pr} \left [w_{\rm H}(\underline{x})\hspace{0.10cm}{\rm is \hspace{0.10cm} even}\right ] =
 
{\rm Pr} \left [w_{\rm H} = 0 \right] + {\rm Pr} \left [w_{\rm H} = 2 \right]
 
{\rm Pr} \left [w_{\rm H} = 0 \right] + {\rm Pr} \left [w_{\rm H} = 2 \right]
 
\hspace{0.05cm}. $$
 
\hspace{0.05cm}. $$
  
Mit den Wahrscheinlichkeiten
+
*With the probabilities
 
:$$p_1 = {\rm Pr} (x_1 = 1) \hspace{-0.15cm} \ = \ \hspace{-0.15cm} 0.2\hspace{0.05cm},\hspace{0.3cm}q_1 = {\rm Pr} (x_1 = 0) = 0.8\hspace{0.05cm},$$
 
:$$p_1 = {\rm Pr} (x_1 = 1) \hspace{-0.15cm} \ = \ \hspace{-0.15cm} 0.2\hspace{0.05cm},\hspace{0.3cm}q_1 = {\rm Pr} (x_1 = 0) = 0.8\hspace{0.05cm},$$
 
:$$p_2 = {\rm Pr} (x_2 = 1) \hspace{-0.15cm} \ = \ \hspace{-0.15cm} 0.9\hspace{0.05cm},\hspace{0.3cm}q_2 = {\rm Pr} (x_2 = 0) = 0.1$$
 
:$$p_2 = {\rm Pr} (x_2 = 1) \hspace{-0.15cm} \ = \ \hspace{-0.15cm} 0.9\hspace{0.05cm},\hspace{0.3cm}q_2 = {\rm Pr} (x_2 = 0) = 0.1$$
  
erhält man:
+
:one obtains:
 
:$${\rm Pr} \left [w_{\rm H}(\underline{x}) = 0\right] \hspace{-0.15cm} \ = \ \hspace{-0.15cm}  
 
:$${\rm Pr} \left [w_{\rm H}(\underline{x}) = 0\right] \hspace{-0.15cm} \ = \ \hspace{-0.15cm}  
 
{\rm Pr} \left [(x_1 = 0)\cap (x_2 = 0) \right] = q_1 \cdot q_2 = 0.8 \cdot 0.1
 
{\rm Pr} \left [(x_1 = 0)\cap (x_2 = 0) \right] = q_1 \cdot q_2 = 0.8 \cdot 0.1
Line 97: Line 101:
 
:$${\rm Pr} \left [w_{\rm H}(\underline{x}) = 2\right] \hspace{-0.15cm} \ = \ \hspace{-0.15cm}  
 
:$${\rm Pr} \left [w_{\rm H}(\underline{x}) = 2\right] \hspace{-0.15cm} \ = \ \hspace{-0.15cm}  
 
{\rm Pr} \left [(x_1 = 1)\cap (x_2 = 1) \right] = p_1 \cdot p_2 = 0.2 \cdot 0.9 = 0.18$$
 
{\rm Pr} \left [(x_1 = 1)\cap (x_2 = 1) \right] = p_1 \cdot p_2 = 0.2 \cdot 0.9 = 0.18$$
:$$\Rightarrow \hspace{0.3cm} {\rm Pr} \left [w_{\rm H}(\underline{x})\hspace{0.15cm}{\rm ist \hspace{0.15cm} gerade}\right] = 0.8 + 0.18 \hspace{0.15cm} \underline{= 0.26}
+
:$$\Rightarrow \hspace{0.3cm} {\rm Pr} \left [w_{\rm H}(\underline{x})\hspace{0.15cm}{\rm is \hspace{0.15cm} even}\right] = 0.8 + 0.18 \hspace{0.15cm} \underline{= 0.26}
 
\hspace{0.05cm}.$$
 
\hspace{0.05cm}.$$
  
Die Gallager&ndash;Gleichung liefert für den gleichen Parametersatz:
+
*The Gallager's equation provides for the same set of parameters:
:$${\rm Pr} \left [w_{\rm H}(\underline{x})\hspace{0.15cm}{\rm ist \hspace{0.15cm} gerade}\right] \hspace{-0.15cm} \ = \ \hspace{-0.15cm}  0.5 + 0.5 \cdot \prod\limits_{i =1}^{2} \hspace{0.25cm}(1-2\cdot p_i) = 0.5 + 0.5 \cdot  (1 - 2 \cdot 0.2)\cdot  (1 - 2 \cdot 0.9) = 0.26
+
:$${\rm Pr} \left [w_{\rm H}(\underline{x})\hspace{0.15cm}{\rm is \hspace{0.15cm} even}\right] \hspace{-0.15cm} \ = \ \hspace{-0.15cm}  0.5 + 0.5 \cdot \prod\limits_{i =1}^{2} \hspace{0.25cm}(1-2\cdot p_i) = 0.5 + 0.5 \cdot  (1 - 2 \cdot 0.2)\cdot  (1 - 2 \cdot 0.9) = 0.26
 
\hspace{0.05cm}.$$
 
\hspace{0.05cm}.$$
  
Die von Gallager 1963 angegebene Gleichung wurde hiermit für $n = 2$ verifiziert.
+
*The equation given by Gallager 1963 was hereby verified for&nbsp; $n = 2$.
 +
 
 +
 
  
 +
'''(2)'''&nbsp; In the second table,&nbsp; the four combinations with an even number of&nbsp; "ones"&nbsp; are marked in blue.&nbsp;
 +
[[File:P_ID2997__KC_Z_4_4b_v1.png|right|frame|Derivation "$w_{\rm H}$ is even"&nbsp;  for code length&nbsp; $n = 3$.]]
  
[[File:P_ID2997__KC_Z_4_4b_v1.png|right|frame|Herleitung „$w_{\rm H}$ ist gerade” für die Codelänge $n = 3$]]
+
*The occurrence probabilities  of each combination are given in the last column.&nbsp; Thus,&nbsp; the result is:
'''(2)'''&nbsp; In der zweiten Tabelle sind die vier Kombinationen mit einer geraden Anzahl an Einsen blau markiert. Die Auftrittswahrscheinlichkeiten der einzelnen Kombinationen sind in der letzten Spalte angegeben. Somit ergibt sich hier:
+
:$$ {\rm Pr} \left [w_{\rm H}(\underline{x})\hspace{0.15cm}{\rm is \hspace{0.15cm} even}\right] =  0.056 + 0.216 + 0.006 + 0.126 \hspace{0.15cm} \underline{= 0.404}
:$$ {\rm Pr} \left [w_{\rm H}(\underline{x})\hspace{0.15cm}{\rm ist \hspace{0.15cm} gerade}\right] =  0.056 + 0.216 + 0.006 + 0.126 \hspace{0.15cm} \underline{= 0.404}
 
 
\hspace{0.05cm}.$$
 
\hspace{0.05cm}.$$
  
Die roten Zeilen liefern das Komplementärereignis:
+
*The red rows provide the complementary event:
:$$ {\rm Pr} \left [w_{\rm H}(\underline{x})\hspace{0.15cm}{\rm ist \hspace{0.15cm} ungerade}\right] =  0.024 + 0.504 + 0.014 + 0.054= 0.596
+
:$$ {\rm Pr} \left [w_{\rm H}(\underline{x})\hspace{0.15cm}{\rm is \hspace{0.15cm} odd}\right] =  0.024 + 0.504 + 0.014 + 0.054= 0.596
 
\hspace{0.05cm}.$$
 
\hspace{0.05cm}.$$
  
Die Gallager&ndash;Gleichung liefert auch hier wieder das exakt gleiche Ergebnis, wobei anzumerken ist, dass diese Gleichung für alle $n$ und alle beliebigen Wahrscheinlichkeiten gültig ist:
+
*Gallager's equation again gives the exact same result,&nbsp; although it should be noted that this equation is valid for all&nbsp; $n$&nbsp; and all arbitrary probabilities:
:$${\rm Pr} \left [w_{\rm H}(\underline{x})\hspace{0.15cm}{\rm ist \hspace{0.15cm} gerade}\right] \hspace{-0.15cm} \ = \ \hspace{-0.15cm}  0.5 + 0.5 \cdot \prod\limits_{i =1}^{3} \hspace{0.25cm}(1-2\cdot p_i) $$
+
:$${\rm Pr} \left [w_{\rm H}(\underline{x})\hspace{0.15cm}{\rm is \hspace{0.15cm} even}\right] \hspace{-0.15cm} \ = \ \hspace{-0.15cm}  0.5 + 0.5 \cdot \prod\limits_{i =1}^{3} \hspace{0.25cm}(1-2\cdot p_i) $$
:$$\Rightarrow\hspace{0.3cm}{\rm Pr} \left [w_{\rm H}(\underline{x})\hspace{0.15cm}{\rm ist \hspace{0.15cm} gerade}\right] \hspace{-0.15cm} \ = \ \hspace{-0.15cm} 0.5 + 0.5 \cdot  (+0.6) \cdot  (-0.8) \cdot  (+0.4) = 0.404
+
:$$\Rightarrow\hspace{0.3cm}{\rm Pr} \left [w_{\rm H}(\underline{x})\hspace{0.15cm}{\rm is \hspace{0.15cm} even}\right] \hspace{-0.15cm} \ = \ \hspace{-0.15cm} 0.5 + 0.5 \cdot  (+0.6) \cdot  (-0.8) \cdot  (+0.4) = 0.404
 
\hspace{0.05cm}.$$
 
\hspace{0.05cm}.$$
  
  
'''(3)'''&nbsp; Entsprechend der Angabenseite gilt:
+
'''(3)'''&nbsp; According to the specification page applies:
 
:$$\pi = \prod\limits_{i =1}^{4} \hspace{0.25cm}(1-2\cdot p_i) \hspace{-0.15cm} \ = \ \hspace{-0.15cm} (1 - 2 \cdot 0.2) \cdot  (1 - 2 \cdot 0.9) \cdot  (1 - 2 \cdot 0.3) \cdot  (1 - 2 \cdot 0.6) $$
 
:$$\pi = \prod\limits_{i =1}^{4} \hspace{0.25cm}(1-2\cdot p_i) \hspace{-0.15cm} \ = \ \hspace{-0.15cm} (1 - 2 \cdot 0.2) \cdot  (1 - 2 \cdot 0.9) \cdot  (1 - 2 \cdot 0.3) \cdot  (1 - 2 \cdot 0.6) $$
 
:$$\Rightarrow\hspace{0.3cm}\pi = \prod\limits_{i =1}^{4} \hspace{0.25cm}(1-2\cdot p_i) \hspace{-0.15cm} \ = \ \hspace{-0.15cm}(+0.6) \cdot  (-0.8) \cdot  (+0.4) \cdot  (-0.2) = 0.0384  
 
:$$\Rightarrow\hspace{0.3cm}\pi = \prod\limits_{i =1}^{4} \hspace{0.25cm}(1-2\cdot p_i) \hspace{-0.15cm} \ = \ \hspace{-0.15cm}(+0.6) \cdot  (-0.8) \cdot  (+0.4) \cdot  (-0.2) = 0.0384  
 
  \hspace{0.05cm}.$$
 
  \hspace{0.05cm}.$$
  
Daraus lassen sich berechnen:
+
*From this can be calculated:
:$${\rm Pr}({\rm blau}) = {\rm Pr} \left [w_{\rm H}(\underline{x})\hspace{0.15cm}{\rm ist \hspace{0.15cm} gerade}\right] \hspace{-0.15cm} \ = \ \hspace{-0.15cm}  0.5 + 0.5 \cdot \pi  = 0.5 + 0.5 \cdot 0.0384\hspace{0.15cm} \underline{= 0.5192}\hspace{0.05cm},$$
+
:$${\rm Pr}({\rm blue}) = {\rm Pr} \left [w_{\rm H}(\underline{x})\hspace{0.15cm}{\rm is \hspace{0.15cm} even}\right] \hspace{-0.15cm} \ = \ \hspace{-0.15cm}  0.5 + 0.5 \cdot \pi  = 0.5 + 0.5 \cdot 0.0384\hspace{0.15cm} \underline{= 0.5192}\hspace{0.05cm},$$
:$${\rm Pr}({\rm rot}) = {\rm Pr} \left [w_{\rm H}(\underline{x})\hspace{0.15cm}{\rm ist \hspace{0.15cm} ungerade}\right] \hspace{-0.15cm} \ = \ \hspace{-0.15cm}  0.5 - 0.5 \cdot \pi  = 0.5 - 0.5 \cdot 0.0384\hspace{0.15cm} \underline{= 0.4808}\hspace{0.05cm}. $$
+
:$${\rm Pr}({\rm red}) = {\rm Pr} \left [w_{\rm H}(\underline{x})\hspace{0.15cm}{\rm is \hspace{0.15cm} odd}\right] \hspace{-0.15cm} \ = \ \hspace{-0.15cm}  0.5 - 0.5 \cdot \pi  = 0.5 - 0.5 \cdot 0.0384\hspace{0.15cm} \underline{= 0.4808}\hspace{0.05cm}. $$
  
Addiert man die blauen bzw. die roten Wahrscheinlichkeiten auf der Angabenseite, so erhält man exakt die hier berechneten Werte. Für den Quotienten ergibt sich:
+
*If you add up the blue and red probabilities on the information page,V you get exactly the values calculated here.&nbsp; For the quotient we get:
:$$Q = \frac{{\rm Pr} \left [w_{\rm H}(\underline{x})\hspace{0.15cm}{\rm ist \hspace{0.15cm} gerade}\right]} { {\rm Pr} \left [w_{\rm H}(\underline{x})\hspace{0.15cm}{\rm ist \hspace{0.15cm} ungerade}\right]} = \frac{0.5192}{0.4808}\hspace{0.15cm} \underline{= 1.0799}
+
:$$Q = \frac{{\rm Pr} \left [w_{\rm H}(\underline{x})\hspace{0.15cm}{\rm is \hspace{0.15cm} even}\right]} { {\rm Pr} \left [w_{\rm H}(\underline{x})\hspace{0.15cm}{\rm is \hspace{0.15cm} odd}\right]} = \frac{0.5192}{0.4808}\hspace{0.15cm} \underline{= 1.0799}
 
\hspace{0.05cm}. $$
 
\hspace{0.05cm}. $$
  
  
'''(4)'''&nbsp; Für den <i>Single Parity&ndash;check Code</i> wurde der extrinsische $L$&ndash;Wert bezüglich des $i$&ndash;ten Bits wie folgt angegeben:
+
 
:$$L_{\rm E}(i) = {\rm ln} \hspace{0.15cm}\frac{{\rm Pr} \left [w_{\rm H}(\underline{x}^{(-i)})\hspace{0.15cm}{\rm ist \hspace{0.15cm} gerade} \hspace{0.05cm} | \hspace{0.05cm}\underline{y} \hspace{0.05cm}\right ]}{{\rm Pr} \left [w_{\rm H}(\underline{x}^{(-i)})\hspace{0.15cm}{\rm ist \hspace{0.15cm} ungerade} \hspace{0.05cm} | \hspace{0.05cm}\underline{y} \hspace{0.05cm}\right ]}
+
'''(4)'''&nbsp; For the&nbsp; "single parity&ndash;check code",&nbsp; the extrinsic log likelihood ratio with respect to the&nbsp; $i^{th}$&nbsp; bit was specified as follows:
 +
:$$L_{\rm E}(i) = {\rm ln} \hspace{0.15cm}\frac{{\rm Pr} \left [w_{\rm H}(\underline{x}^{(-i)})\hspace{0.15cm}{\rm is \hspace{0.15cm} even} \hspace{0.05cm} | \hspace{0.05cm}\underline{y} \hspace{0.05cm}\right ]}{{\rm Pr} \left [w_{\rm H}(\underline{x}^{(-i)})\hspace{0.15cm}{\rm is \hspace{0.15cm} odd} \hspace{0.05cm} | \hspace{0.05cm}\underline{y} \hspace{0.05cm}\right ]}
 
  \hspace{0.05cm},$$
 
  \hspace{0.05cm},$$
  
oder:
+
*Or:
 
:$$L_{\rm E}(i) = {\rm ln} \hspace{0.15cm}\frac{1+\prod_{j \ne i} \hspace{0.25cm}(1-2\cdot p_j)}{1-\prod_{j \ne i} \hspace{0.25cm}(1-2\cdot p_j)}
 
:$$L_{\rm E}(i) = {\rm ln} \hspace{0.15cm}\frac{1+\prod_{j \ne i} \hspace{0.25cm}(1-2\cdot p_j)}{1-\prod_{j \ne i} \hspace{0.25cm}(1-2\cdot p_j)}
 
  \hspace{0.05cm}.$$
 
  \hspace{0.05cm}.$$
  
Beim SPC (5, 4, 2) &nbsp;&#8658;&nbsp; $n = 5$ ergibt sich dieses Produkt für $i = 5$ aus folgenden vier Multiplikanden:
+
*At&nbsp; $\text{SPC (5, 4, 2}$) &nbsp; &#8658; &nbsp; $n = 5$,&nbsp; this product for&nbsp; $i = 5$&nbsp; results from the following four factors:
 
:$$\pi = \prod\limits_{j = 1,  \hspace{0.05cm}2,  \hspace{0.05cm}3,  \hspace{0.05cm}4} \hspace{0.05cm}(1-2\cdot p_j) =  
 
:$$\pi = \prod\limits_{j = 1,  \hspace{0.05cm}2,  \hspace{0.05cm}3,  \hspace{0.05cm}4} \hspace{0.05cm}(1-2\cdot p_j) =  
 
(1-2\cdot p_1) \cdot (1-2\cdot p_2) \cdot (1-2\cdot p_3) \cdot (1-2\cdot p_4)
 
(1-2\cdot p_1) \cdot (1-2\cdot p_2) \cdot (1-2\cdot p_3) \cdot (1-2\cdot p_4)
 
  \hspace{0.05cm}.$$
 
  \hspace{0.05cm}.$$
  
Der Vergleich mit der Teilaufgabe (3) zeigt, dass $L_{\rm E}(i = 5) = \ln {Q} = \ln {(1.0799)} \ \underline{\approx 0.077}$ ist.
+
The comparison with subtask&nbsp; '''(3)'''&nbsp; shows that&nbsp; $L_{\rm E}(i = 5) = \ln {Q} = \ln {(1.0799)} \ \underline{\approx 0.077}$.
  
  
'''(5)'''&nbsp; Richtig ist der <u>Lösungsvorschlag 3</u>, weil das Ergebnis für $L_{\rm E}(i = 5)$ unabhängig von $p_5$ ist.
+
'''(5)'''&nbsp; Correct is the&nbsp; <u>proposed solution 3</u>&nbsp; because the result for&nbsp; $L_{\rm E}(i = 5)$&nbsp; is independent of&nbsp; $p_5$.
 
{{ML-Fuß}}
 
{{ML-Fuß}}
  
  
[[Category:Aufgaben zu  Kanalcodierung|^4.1 Soft–in Soft–out Decoder^]]
+
[[Category:Channel Coding: Exercises|^4.1 Soft–in Soft–out Decoder^]]

Latest revision as of 15:29, 3 December 2022

Hamming weights  $w_{\rm H}(\underline{x})$,
sequence probabilities  ${\rm Pr}(\underline{x})$

The information theorist  $\text{Robert G. Gallager}$  dealt already in 1963 with the following problem:

  • Given a random vector  $\underline{x} = (x_1, \, x_2, \hspace{-0.04cm} \text{ ...} \hspace{0.08cm} , x_n)$  with  $n$  binary elements  $x_i ∈ \{0, \, 1\}$.
  • Known are all probabilities  $p_i = {\rm Pr}(x_i = 1)$  and  $q_i = {\rm Pr}(x_i = 0) = 1 - p_i$  with index  $i = 1, \hspace{-0.04cm}\text{ ...} \hspace{0.08cm} ,\ n$.
  • What we are looking for is the probability that the number of  "ones"  in this vector is even.
  • Or expressed using the  "Hamming weight":   What is the probability  ${\rm Pr}[w_{\rm H}(\underline{x}) {\rm \ is \ even}]$?


The graph illustrates the task for the example  $n = 4$  and  $p_1 = 0.2$,  $p_2 = 0.9$,  $p_3 = 0.3$  and  $p_4 = 0.6$.

  • For the row highlighted in green   ⇒   $\underline{x} = (1, \, 0, \, 0, \, 1)$  holds  $w_{\rm H}(\underline{x}) = 2$  and
$${\rm Pr}(\underline{x}) = p_1 \cdot q_2 \cdot q_3 \cdot p_4 = 0.0084.$$
  • Blue font means  "$w_{\rm H}(\underline{x})$  is even".  Red font stands for  "$w_{\rm H}(\underline{x})$  is odd."
  • The probability  ${\rm Pr}[w_{\rm H}(\underline{x}) {\rm \ is \ even}]$  is the sum of the blue numbers in the last column.
  • The sum of the red numbers gives  ${\rm Pr}[w_{\rm H}(\underline{x}) {\rm \ is \ odd}] = 1 - {\rm Pr}[w_{\rm H}(\underline{x}) {\rm \ is \ even}]$.


Gallager solved the problem in an analytical way:

$$ {\rm Pr} \left [w_{\rm H}(\underline{x})\hspace{0.15cm}{\rm is \hspace{0.15cm} even} \right ] \hspace{-0.15cm} \ = \ \hspace{-0.15cm} 1/2 \cdot [1 + \pi]\hspace{0.05cm},$$
$${\rm Pr} \left [w_{\rm H}(\underline{x})\hspace{0.15cm}{\rm is \hspace{0.15cm} odd} \right ] \hspace{-0.15cm} \ = \ \hspace{-0.15cm} 1/2 \cdot [1 - \pi]\hspace{0.05cm}.$$

Here the following auxiliary variable is used:

$$\pi = \prod\limits_{i =1}^{n} \hspace{0.25cm}(1-2p_i) \hspace{0.05cm}.$$

One applies the equation,  for example,  to calculate the extrinsic  L–values of a  "single parity–check code".

Indeed,  as already pointed out in  $\text{Exercise 4.4}$  the extrinsic log likelihood ratio with Hamming–weight  $w_{\rm H}$  is the truncated sequence  $\underline{x}^{(-i)}$:

$$L_{\rm E}(i) = {\rm ln} \hspace{0.15cm}\frac{{\rm Pr} \left [w_{\rm H}(\underline{x}^{(-i)})\hspace{0.15cm}{\rm is \hspace{0.15cm} even} \hspace{0.05cm} | \hspace{0.05cm}\underline{y} \hspace{0.05cm}\right ]}{{\rm Pr} \left [w_{\rm H}(\underline{x}^{(-i)})\hspace{0.15cm}{\rm is \hspace{0.15cm} odd} \hspace{0.05cm} | \hspace{0.05cm}\underline{y} \hspace{0.05cm}\right ]} \hspace{0.05cm}.$$

Here it is taken into account that for  $L_{\rm E}(i)$  one may refer only to the other symbols  $(j ≠ i)$ :

$$\underline{x}^{(-i)} = \big ( \hspace{0.03cm}x_1, \hspace{-0.04cm} \text{ ...} \hspace{0.08cm} , \hspace{0.03cm} x_{i-1}, \hspace{0.43cm} x_{i+1}, \hspace{-0.04cm} \text{ ...} \hspace{0.08cm} , x_{n} \hspace{0.03cm} \big )\hspace{0.03cm}. $$




Hints:



Questions

1

We consider the vector  $\underline{x} = (x_1, \, x_2) \ \Rightarrow \ n = 2$  with  $x_i ∈ \{0, \, 1\}$  and  $p_1 = 0.2, \ p_2 = 0.9$.
What is the probability that   $\underline{x}$   contains an even number of  "ones" ?

${\rm Pr}\big [w_{\rm H}(\underline{x}) \ {\rm is \ even}\big ] \ = \ $

2

Compute the same probability for  $\underline{x} = (x_1, \, x_2, \, x_3) \ \Rightarrow \ n = 3$  and  $p_1 = 0.2, \ p_2 = 0.9, \ p_3 = 0.3$.

${\rm Pr}\big [w_{\rm H}(\underline{x}) \ {\rm is \ even}\big ] \ = \ $

3

Now let be  $n = 4$  and  $p_1 = 0.2, \ p_2 = 0.9, \ p_3 = 0.3, \ p_4 = 0.6$.  Calculate the following quantities according to Gallager's equation:

${\rm Pr(blue) = Pr}\big [w_{\rm H}(\underline{x}) \ {\rm is \ even}\big ] \hspace{0.33cm} = \ $

${\rm Pr(red) = Pr}\big [w_{\rm H}(\underline{x}) \ {\rm is \ odd}\big ] \hspace{0.1cm} = \ $

$\text{Quotient }Q = {\rm Pr(blau)/Pr(rot)} \hspace{0.4cm} = \ $

4

What is the extrinsic log likelihood ratio for the symbol  $i = 5$  at  $\text{SPC (5, 4, 2)}$  with  $p_1 = 0.2, \ p_2 = 0.9, \ p_3 = 0.3, \ p_4 = 0.6, \ p_5 = 0.9$?

$L_{\rm E}(i = 5) \ = \ $

5

How does  $L_{\rm E}(i = 5)$  change if we assume  $p_5 = 0.1$  instead?

$L_{\rm E}(i = 5)$  becomes larger.
$L_{\rm E}(i = 5)$  becomes smaller.
$L_{\rm E}(i = 5)$  is not changed compared to subtask  (4).


Solution

Derivation  "$w_{\rm H}$ is even"  for code length  $n = 2$.

(1)  According to the adjacent table applies:

$${\rm Pr} \left [w_{\rm H}(\underline{x})\hspace{0.10cm}{\rm is \hspace{0.10cm} even}\right ] = {\rm Pr} \left [w_{\rm H} = 0 \right] + {\rm Pr} \left [w_{\rm H} = 2 \right] \hspace{0.05cm}. $$
  • With the probabilities
$$p_1 = {\rm Pr} (x_1 = 1) \hspace{-0.15cm} \ = \ \hspace{-0.15cm} 0.2\hspace{0.05cm},\hspace{0.3cm}q_1 = {\rm Pr} (x_1 = 0) = 0.8\hspace{0.05cm},$$
$$p_2 = {\rm Pr} (x_2 = 1) \hspace{-0.15cm} \ = \ \hspace{-0.15cm} 0.9\hspace{0.05cm},\hspace{0.3cm}q_2 = {\rm Pr} (x_2 = 0) = 0.1$$
one obtains:
$${\rm Pr} \left [w_{\rm H}(\underline{x}) = 0\right] \hspace{-0.15cm} \ = \ \hspace{-0.15cm} {\rm Pr} \left [(x_1 = 0)\cap (x_2 = 0) \right] = q_1 \cdot q_2 = 0.8 \cdot 0.1 = 0.08 \hspace{0.05cm},$$
$${\rm Pr} \left [w_{\rm H}(\underline{x}) = 2\right] \hspace{-0.15cm} \ = \ \hspace{-0.15cm} {\rm Pr} \left [(x_1 = 1)\cap (x_2 = 1) \right] = p_1 \cdot p_2 = 0.2 \cdot 0.9 = 0.18$$
$$\Rightarrow \hspace{0.3cm} {\rm Pr} \left [w_{\rm H}(\underline{x})\hspace{0.15cm}{\rm is \hspace{0.15cm} even}\right] = 0.8 + 0.18 \hspace{0.15cm} \underline{= 0.26} \hspace{0.05cm}.$$
  • The Gallager's equation provides for the same set of parameters:
$${\rm Pr} \left [w_{\rm H}(\underline{x})\hspace{0.15cm}{\rm is \hspace{0.15cm} even}\right] \hspace{-0.15cm} \ = \ \hspace{-0.15cm} 0.5 + 0.5 \cdot \prod\limits_{i =1}^{2} \hspace{0.25cm}(1-2\cdot p_i) = 0.5 + 0.5 \cdot (1 - 2 \cdot 0.2)\cdot (1 - 2 \cdot 0.9) = 0.26 \hspace{0.05cm}.$$
  • The equation given by Gallager 1963 was hereby verified for  $n = 2$.


(2)  In the second table,  the four combinations with an even number of  "ones"  are marked in blue. 

Derivation "$w_{\rm H}$ is even"  for code length  $n = 3$.
  • The occurrence probabilities of each combination are given in the last column.  Thus,  the result is:
$$ {\rm Pr} \left [w_{\rm H}(\underline{x})\hspace{0.15cm}{\rm is \hspace{0.15cm} even}\right] = 0.056 + 0.216 + 0.006 + 0.126 \hspace{0.15cm} \underline{= 0.404} \hspace{0.05cm}.$$
  • The red rows provide the complementary event:
$$ {\rm Pr} \left [w_{\rm H}(\underline{x})\hspace{0.15cm}{\rm is \hspace{0.15cm} odd}\right] = 0.024 + 0.504 + 0.014 + 0.054= 0.596 \hspace{0.05cm}.$$
  • Gallager's equation again gives the exact same result,  although it should be noted that this equation is valid for all  $n$  and all arbitrary probabilities:
$${\rm Pr} \left [w_{\rm H}(\underline{x})\hspace{0.15cm}{\rm is \hspace{0.15cm} even}\right] \hspace{-0.15cm} \ = \ \hspace{-0.15cm} 0.5 + 0.5 \cdot \prod\limits_{i =1}^{3} \hspace{0.25cm}(1-2\cdot p_i) $$
$$\Rightarrow\hspace{0.3cm}{\rm Pr} \left [w_{\rm H}(\underline{x})\hspace{0.15cm}{\rm is \hspace{0.15cm} even}\right] \hspace{-0.15cm} \ = \ \hspace{-0.15cm} 0.5 + 0.5 \cdot (+0.6) \cdot (-0.8) \cdot (+0.4) = 0.404 \hspace{0.05cm}.$$


(3)  According to the specification page applies:

$$\pi = \prod\limits_{i =1}^{4} \hspace{0.25cm}(1-2\cdot p_i) \hspace{-0.15cm} \ = \ \hspace{-0.15cm} (1 - 2 \cdot 0.2) \cdot (1 - 2 \cdot 0.9) \cdot (1 - 2 \cdot 0.3) \cdot (1 - 2 \cdot 0.6) $$
$$\Rightarrow\hspace{0.3cm}\pi = \prod\limits_{i =1}^{4} \hspace{0.25cm}(1-2\cdot p_i) \hspace{-0.15cm} \ = \ \hspace{-0.15cm}(+0.6) \cdot (-0.8) \cdot (+0.4) \cdot (-0.2) = 0.0384 \hspace{0.05cm}.$$
  • From this can be calculated:
$${\rm Pr}({\rm blue}) = {\rm Pr} \left [w_{\rm H}(\underline{x})\hspace{0.15cm}{\rm is \hspace{0.15cm} even}\right] \hspace{-0.15cm} \ = \ \hspace{-0.15cm} 0.5 + 0.5 \cdot \pi = 0.5 + 0.5 \cdot 0.0384\hspace{0.15cm} \underline{= 0.5192}\hspace{0.05cm},$$
$${\rm Pr}({\rm red}) = {\rm Pr} \left [w_{\rm H}(\underline{x})\hspace{0.15cm}{\rm is \hspace{0.15cm} odd}\right] \hspace{-0.15cm} \ = \ \hspace{-0.15cm} 0.5 - 0.5 \cdot \pi = 0.5 - 0.5 \cdot 0.0384\hspace{0.15cm} \underline{= 0.4808}\hspace{0.05cm}. $$
  • If you add up the blue and red probabilities on the information page,V you get exactly the values calculated here.  For the quotient we get:
$$Q = \frac{{\rm Pr} \left [w_{\rm H}(\underline{x})\hspace{0.15cm}{\rm is \hspace{0.15cm} even}\right]} { {\rm Pr} \left [w_{\rm H}(\underline{x})\hspace{0.15cm}{\rm is \hspace{0.15cm} odd}\right]} = \frac{0.5192}{0.4808}\hspace{0.15cm} \underline{= 1.0799} \hspace{0.05cm}. $$


(4)  For the  "single parity–check code",  the extrinsic log likelihood ratio with respect to the  $i^{th}$  bit was specified as follows:

$$L_{\rm E}(i) = {\rm ln} \hspace{0.15cm}\frac{{\rm Pr} \left [w_{\rm H}(\underline{x}^{(-i)})\hspace{0.15cm}{\rm is \hspace{0.15cm} even} \hspace{0.05cm} | \hspace{0.05cm}\underline{y} \hspace{0.05cm}\right ]}{{\rm Pr} \left [w_{\rm H}(\underline{x}^{(-i)})\hspace{0.15cm}{\rm is \hspace{0.15cm} odd} \hspace{0.05cm} | \hspace{0.05cm}\underline{y} \hspace{0.05cm}\right ]} \hspace{0.05cm},$$
  • Or:
$$L_{\rm E}(i) = {\rm ln} \hspace{0.15cm}\frac{1+\prod_{j \ne i} \hspace{0.25cm}(1-2\cdot p_j)}{1-\prod_{j \ne i} \hspace{0.25cm}(1-2\cdot p_j)} \hspace{0.05cm}.$$
  • At  $\text{SPC (5, 4, 2}$)   ⇒   $n = 5$,  this product for  $i = 5$  results from the following four factors:
$$\pi = \prod\limits_{j = 1, \hspace{0.05cm}2, \hspace{0.05cm}3, \hspace{0.05cm}4} \hspace{0.05cm}(1-2\cdot p_j) = (1-2\cdot p_1) \cdot (1-2\cdot p_2) \cdot (1-2\cdot p_3) \cdot (1-2\cdot p_4) \hspace{0.05cm}.$$

The comparison with subtask  (3)  shows that  $L_{\rm E}(i = 5) = \ln {Q} = \ln {(1.0799)} \ \underline{\approx 0.077}$.


(5)  Correct is the  proposed solution 3  because the result for  $L_{\rm E}(i = 5)$  is independent of  $p_5$.