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

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:

This exercise belongs to the chapter "Soft–in Soft–out Decoder".

Reference is made in particular to the section "For calculating the extrinsic log likelihood ratios".

The exercise is intended as a supplement to $\text{Exercise 4.4}$ .

Questions

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

${\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} = \ $

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

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

@@ 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–Gewicht und Wahrscheinlichkeiten ]]
+[[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 [https://en.wikipedia.org/wiki/Robert_G._Gallager| Robert G. Gallager] 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 $\underline{x} = (x_1, \, x_2, \ ... \ , \, x_n)$ mit $n$ binären Elementen $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 $p_i = {\rm Pr}(x_i = 1)$ und $q_i = {\rm Pr}(x_i = 0) = 1 - p_i$ mit Inex $i = 1, \ ... \ , \ n$.
-* Gesucht ist die Wahrscheinlichkeit, dass die Anzahl der Einsen in diesem Vektor geradzahlig ist.
-* Oder ausgedrückt mit dem [[Hamming&ndash;Gewicht]]: Wie groß ist die Wahrscheinlichkeit ${\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 $n = 4$ sowie $p_1 = 0.2, \ p_2 = 0.9, \ p_3 = 0.3$ und $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)$ gilt $w_{\rm H}(\underline{x}) = 2$ und ${\rm Pr}(\underline{x}) = p_1 \cdot q_2 \cdot q_3 \cdot p_4 = 0.0084$.
-* Blaue Schrift bedeutet ein geradzahliges Hamming&ndash;Gewicht. Rote Schrift steht für &bdquo;$w_{\rm H}(\underline{x})$ ist ungerade&rdquo;.
-* Die Wahrscheinlichkeite ${\rm Pr}[w_{\rm H}(\underline{x}) {\rm \ ist \ gerade}]$ ist gleich der Summe der blauen Zahlen in der letzten Spalte. Die Summe der roten Zahlen ergibt ${\rm Pr}[w_{\rm H}(\underline{x}) {\rm \ ist \ ungerade}] = 1 - {\rm Pr}[w_{\rm H}(\underline{x} {\rm \ ist \ gerade}]$.
+* 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}]$?
-Gallager hat das Problem in analytischer Weise gelöst:
-:$$\hspace{0.2cm} {\rm Pr} \left [w_{\rm H}(\underline{x})\hspace{0.15cm}{\rm ist \hspace{0.15cm} gerade} \right ]
+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.$$
+* 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."
+*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 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 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}.$$
+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,&nbsp; for example,&nbsp; to calculate the extrinsic&nbsp; L&ndash;values of a&nbsp; "single parity&ndash;check code".
+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 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&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}. $$
-===Fragebogen===
+<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;.
+===Questions===
 <quiz display=simple>
-{Wir betrachten den Vektor $\underline{x} = (x_1, \, x_2) \ \Rightarrow \ n = 2$ mit $x_i &#8712; \{0, \, 1\}$. Wie groß ist die Wahrscheinlichkeit, dass $\underline{x}$ 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="{}"}
-$p_1 = 0.2, \ p_2 = 0.9 \text{:} \hspace{0.2cm} {\rm Pr}[{\rm gerades} \ w_{\rm H}] \ = \ ${ 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 $\underline{x} = (x_1, \, x_2, \, x_3) \ \Rightarrow \ n = 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="{}"}
-$... \ , \ p_3 = 0.3 \text{:} \hspace{0.2cm} {\rm Pr}[{\rm gerades} \ w_{\rm H}] \ = \ ${ 0.404 3% }
+${\rm Pr}\big [w_{\rm H}(\underline{x}) \ {\rm is \ even}\big ] \ = \ ${ 0.404 3% }
-{Nun gelte $n = 4$ und $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="{}"}
-${\rm Pr(blau) = Pr}[w_{\rm H}(\underline{x}) {\rm ist \ gerade}] \ = \ ${ 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}[w_{\rm H}(\underline{x}) {\rm ist \ ungerade}] \ = \ ${ 0.4808 3% }
+${\rm Pr(red) = Pr}\big [w_{\rm H}(\underline{x}) \ {\rm is \ odd}\big ] \hspace{0.1cm} = \ ${ 0.4808 3% }
-$Q = {\rm Pr(blau)/Pr(rot)} \ = \ ${ 1.0799 3% }
+$\text{Quotient }Q = {\rm Pr(blau)/Pr(rot)} \hspace{0.4cm} = \ ${ 1.0799 3% }
-{Wie groß ist der extrinsische $L$&ndash;Wert für das Symbol $i = 5$ beim SPC (5, 4, 2) mit $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="{}"}
 $L_{\rm E}(i = 5) \ = \ ${ 0.077 3% }
-{Wie änder sich $L_{\rm E}(i = 5)$, wenn man stattdessen von $p_5 = 0.1$ 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)$ wird größer.
+- $L_{\rm E}(i = 5)$&nbsp; becomes larger.
-- $L_{\rm E}(i = 5)$ wird kleiner.
+- $L_{\rm E}(i = 5)$&nbsp; becomes smaller.
-+ $L_{\rm E}(i = 5)$ wird gegenüber Teilaufgabe (4) nicht verändert.
++ $L_{\rm E}(i = 5)$&nbsp; is not changed compared to subtask&nbsp; '''(4)'''.
 </quiz>
-===Musterlösung===
+===Solution===
 {{ML-Kopf}}
-'''(1)'''&nbsp; [[File:P_ID2996__KC_Z_4_4a_v1.png|frame|right|Herleitung „$w_{\rm H}$ ist gerade” für $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;  According to the adjacent table applies:
-Entsprechend nebenstehender Tabelle gilt:
+:$${\rm Pr} \left [w_{\rm H}(\underline{x})\hspace{0.10cm}{\rm is \hspace{0.10cm} even}\right ] =
-:$${\rm Pr} \left [w_{\rm H}(\underline{x})\hspace{0.10cm}{\rm ist \hspace{0.10cm} gerade}\right ] =
 {\rm Pr} \left [w_{\rm H} = 0 \right] + {\rm Pr} \left [w_{\rm H} = 2 \right]
 \hspace{0.05cm}. $$
-Mit den Wahrscheinlicekiten
+*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$$
-erhält man:
+: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
@@ Line 69: / Line 101: @@
 :$${\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 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}.$$
-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) =$$
+:$${\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.15cm} 0.5 + 0.5 \cdot  (1 - 2 \cdot 0.2)\cdot  (1 - 2 \cdot 0.9) = 0.26
 \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; [[File:P_ID2997__KC_Z_4_4b_v1.png|right|frame|Herleitung „$w_{\rm H}$ ist gerade” für $n = 3$]] In der nebenstehenden 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 ist \hspace{0.15cm} gerade}\right] =  0.056 + $$
+'''(2)'''&nbsp; In the second table,&nbsp; the four combinations with an even number of&nbsp; "ones"&nbsp; are marked in blue.&nbsp;
-:$$+0.216 + 0.006 + 0.126 \hspace{0.15cm} \underline{= 0.404}
+[[File:P_ID2997__KC_Z_4_4b_v1.png|right|frame|Derivation "$w_{\rm H}$ is even"&nbsp;  for code length&nbsp; $n = 3$.]]
+*The occurrence probabilities   of each combination are given in the last column.&nbsp; Thus,&nbsp; 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}.$$
-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 + $$
+:$$ {\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
-:$$+0.504 + 0.014 + 0.054= 0.596
 \hspace{0.05cm}.$$
-Die Gallager&ndash;Gleichung liefert auch hier wieder das exakt gleiche Ergebnis.
+*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) $$
-:$$\ = \ \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}.$$
-'''(3)'''&nbsp;
+'''(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) $$
+:$$\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}. $$
-'''(4)'''&nbsp;
+*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 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}. $$
-'''(5)'''&nbsp;
-{{ML-Fuß}}
+'''(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},$$
-[[Category:Aufgaben zu  Kanalcodierung|^4.1 Soft–in Soft–out Decoder
+*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&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) =
+(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&nbsp; '''(3)'''&nbsp; shows that&nbsp; $L_{\rm E}(i = 5) = \ln {Q} = \ln {(1.0799)} \ \underline{\approx 0.077}$.
+'''(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ß}}
-^]]
+[[Category:Channel Coding: Exercises|^4.1 Soft–in Soft–out Decoder^]]