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

From LNTwww
m (Textersetzung - „* Sollte die Eingabe des Zahlenwertes „0” erforderlich sein, so geben Sie bitte „0.” ein.“ durch „ “)
Line 2: Line 2:
  
 
[[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–Gewichte und Sequenzwahrscheinlichkeiten ]]
Der Informationstheoretiker [https://de.wikipedia.org/wiki/Robert_Gray_Gallager Robert G. Gallager] hat sich bereits 1963 mit folgender Fragestellung beschäftigt:
+
Der Informationstheoretiker  [https://de.wikipedia.org/wiki/Robert_Gray_Gallager Robert G. Gallager]  hat sich bereits 1963 mit folgender Fragestellung beschäftigt:
* Gegeben ist ein Zufallsvektor $\underline{x} = (x_1, \, x_2, \hspace{-0.04cm} \text{ ...} \hspace{0.08cm} , x_n)$ mit $n$ binären Elementen $x_i ∈ \{0, \, 1\}$.
+
* Gegeben ist ein Zufallsvektor  $\underline{x} = (x_1, \, x_2, \hspace{-0.04cm} \text{ ...} \hspace{0.08cm} , x_n)$  mit  $n$  binären Elementen  $x_i ∈ \{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 Index $i = 1, \hspace{-0.04cm}\text{ ...} \hspace{0.08cm} ,\ n$.
+
* Bekannt sind alle Wahrscheinlichkeiten  $p_i = {\rm Pr}(x_i = 1)$  und  $q_i = {\rm Pr}(x_i = 0) = 1 - p_i$  mit Index  $i = 1, \hspace{-0.04cm}\text{ ...} \hspace{0.08cm} ,\ n$.
 
* Gesucht ist die Wahrscheinlichkeit, dass die Anzahl der Einsen in diesem Vektor geradzahlig ist.
 
* Gesucht ist die Wahrscheinlichkeit, dass die Anzahl der Einsen in diesem Vektor geradzahlig ist.
* Oder ausgedrückt mit dem [[Kanalcodierung/Zielsetzung_der_Kanalcodierung#Einige_wichtige_Definitionen_zur_Blockcodierung|Hamming–Gewicht]]: Wie groß ist die Wahrscheinlichkeit ${\rm Pr}[w_{\rm H}(\underline{x}) {\rm \ ist \ gerade}]$?
+
* Oder ausgedrückt mit dem  [[Kanalcodierung/Zielsetzung_der_Kanalcodierung#Einige_wichtige_Definitionen_zur_Blockcodierung|Hamming–Gewicht]]:   Wie groß ist die Wahrscheinlichkeit  ${\rm Pr}[w_{\rm H}(\underline{x}) {\rm \ ist \ gerade}]$?
  
  
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$.  
+
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$.  
* Für die grün hinterlegte Zeile   ⇒   $\underline{x} = (1, \, 0, \, 0, \, 1)$ gilt $w_{\rm H}(\underline{x}) = 2$ und  
+
* Für die grün hinterlegte Zeile   ⇒   $\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.$$
 
:$${\rm Pr}(\underline{x}) = p_1 \cdot q_2 \cdot q_3 \cdot p_4 = 0.0084.$$
 
* Blaue Schrift bedeutet „$w_{\rm H}(\underline{x})$ ist gerade”. Rote Schrift steht für „$w_{\rm H}(\underline{x})$ ist ungerade”.
 
* Blaue Schrift bedeutet „$w_{\rm H}(\underline{x})$ ist gerade”. Rote Schrift steht für „$w_{\rm H}(\underline{x})$ ist ungerade”.
* Die Wahrscheinlichkeit ${\rm Pr}[w_{\rm H}(\underline{x}) {\rm \ ist \ gerade}]$ ist die Summe der blauen Zahlen in der letzten Spalte.  
+
* Die Wahrscheinlichkeit  ${\rm Pr}[w_{\rm H}(\underline{x}) {\rm \ ist \ gerade}]$  ist die 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}]$.
+
*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}]$.
  
  
Line 27: Line 27:
 
  \hspace{0.05cm}.$$
 
  \hspace{0.05cm}.$$
  
Die Gleichung wendet man zum Beispiel an, um die extrinsischen $L$&ndash;Werte eines <i>Single Parity&ndash;check Codes</i> zu berechnen. Wie bereits in [[Aufgaben:4.4_Extrinsische_L%E2%80%93Werte_beim_SPC| Aufgabe A4.4]] dargelegt, lautet nämlich der extrinsische $L$&ndash;Wert mit dem Hamming&ndash;Gewicht $w_{\rm H}$ der verkürzten Folge $\underline{x}^{(-i)}$:
+
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.  
 +
 
 +
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)}$:
 
:$$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 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 ]}
 
  \hspace{0.05cm}.$$
 
  \hspace{0.05cm}.$$
  
Hierbei ist berücksichtigt, dass man für $L_{\rm E}(i)$ nur die anderen Symbole $(j &ne; i)$ heranziehen darf:
+
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:
 
:$$\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 40: Line 45:
  
 
''Hinweise:''
 
''Hinweise:''
* Die Aufgabe gehört zum Kapitel [[Kanalcodierung/Soft%E2%80%93in_Soft%E2%80%93out_Decoder| Soft&ndash;in Soft&ndash;out Decoder]].
+
* 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 [[Kanalcodierung/Soft–in_Soft–out_Decoder#Zur_Berechnung_der_extrinsischen_L.E2.80.93Werte|Zur Berechnung der extrinsischen L&ndash;Werte]].  
+
*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]].  
*Sie ist als Ergänzung zur [[Aufgaben:Aufgabe_4.4:_Extrinsische_L–Werte_beim_SPC| Aufgabe 4.4]] gedacht.
+
*Die Aufgabe ist als Ergänzung zur&nbsp; [[Aufgaben:Aufgabe_4.4:_Extrinsische_L–Werte_beim_SPC| Aufgabe 4.4]]&nbsp; gedacht.
 
   
 
   
  
Line 49: Line 54:
 
===Fragebogen===
 
===Fragebogen===
 
<quiz display=simple>
 
<quiz display=simple>
{Wir betrachten den Vektor $\underline{x} = (x_1, \, x_2) \ \Rightarrow \ n = 2$ mit $x_i &#8712; \{0, \, 1\}$ und $p_1 = 0.2, \ p_2 = 0.9$.  <br>Wie groß ist die Wahrscheinlichkeit, dass $\underline{x}$ eine gerade Anzahl an Einsen beinhaltet?
+
{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?
 
|type="{}"}
 
|type="{}"}
${\rm Pr}[w_{\rm H}(\underline{x}) \ {\rm ist \ gerade}] \ = \ ${ 0.26 3% }
+
${\rm Pr}\big [w_{\rm H}(\underline{x}) \ {\rm ist \ gerade}\big ] \ = \ ${ 0.26 3% }
  
{Berechnen Sie die gleiche Wahrscheinlichkeit für $\underline{x} = (x_1, \, x_2, \, x_3) \ \Rightarrow \ n = 3$ für  und $p_1 = 0.2, \ p_2 = 0.9, \ p_3 = 0.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$.
 
|type="{}"}
 
|type="{}"}
${\rm Pr}[w_{\rm H}(\underline{x}) \ {\rm ist \ gerade}] \ = \ ${ 0.404 3% }
+
${\rm Pr}\big [w_{\rm H}(\underline{x}) \ {\rm ist \ gerade}\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:
+
{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:
 
|type="{}"}
 
|type="{}"}
${\rm Pr(blau) = Pr}[w_{\rm H}(\underline{x}) \ {\rm ist \ gerade}] \hspace{0.33cm} = \ ${ 0.5192 3% }
+
${\rm Pr(blau) = Pr}\big [w_{\rm H}(\underline{x}) \ {\rm ist \ gerade}\big ] \hspace{0.33cm} = \ ${ 0.5192 3% }
${\rm Pr(rot) = Pr}[w_{\rm H}(\underline{x}) \ {\rm ist \ ungerade}] \hspace{0.1cm} = \ ${ 0.4808 3% }
+
${\rm Pr(rot) = Pr}\big [w_{\rm H}(\underline{x}) \ {\rm ist \ ungerade}\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 $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$?
+
{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$?
 
|type="{}"}
 
|type="{}"}
 
$L_{\rm E}(i = 5) \ = \ ${ 0.077 3% }
 
$L_{\rm E}(i = 5) \ = \ ${ 0.077 3% }
  
{Wie ändert sich $L_{\rm E}(i = 5)$, wenn man stattdessen von $p_5 = 0.1$ ausgeht?
+
{Wie ändert sich&nbsp; $L_{\rm E}(i = 5)$, wenn man stattdessen von&nbsp; $p_5 = 0.1$&nbsp; ausgeht?
|type="[]"}
+
|type="()"}
- $L_{\rm E}(i = 5)$ wird größer.
+
- $L_{\rm E}(i = 5)$&nbsp; wird größer.
- $L_{\rm E}(i = 5)$ wird kleiner.
+
- $L_{\rm E}(i = 5)$&nbsp; wird kleiner.
+ $L_{\rm E}(i = 5)$ wird gegenüber Teilaufgabe (4) nicht verändert.
+
+ $L_{\rm E}(i = 5)$&nbsp; wird gegenüber Teilaufgabe '''(4)''' nicht verändert.
 
</quiz>
 
</quiz>
  

Revision as of 13:41, 5 July 2019

Hamming–Gewichte und Sequenzwahrscheinlichkeiten

Der Informationstheoretiker  Robert G. Gallager  hat sich bereits 1963 mit folgender Fragestellung beschäftigt:

  • Gegeben ist ein Zufallsvektor  $\underline{x} = (x_1, \, x_2, \hspace{-0.04cm} \text{ ...} \hspace{0.08cm} , x_n)$  mit  $n$  binären Elementen  $x_i ∈ \{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 Index  $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  Hamming–Gewicht:   Wie groß ist die Wahrscheinlichkeit  ${\rm Pr}[w_{\rm H}(\underline{x}) {\rm \ ist \ gerade}]$?


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

  • Für die grün hinterlegte Zeile   ⇒   $\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 „$w_{\rm H}(\underline{x})$ ist gerade”. Rote Schrift steht für „$w_{\rm H}(\underline{x})$ ist ungerade”.
  • Die Wahrscheinlichkeit  ${\rm Pr}[w_{\rm H}(\underline{x}) {\rm \ ist \ gerade}]$  ist die 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}]$.


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 ] \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} \right ] \hspace{-0.15cm} \ = \ \hspace{-0.15cm} 1/2 \cdot [1 - \pi]\hspace{0.05cm}.$$

Hierbei ist die folgende Hilfsgröße verwendet:

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

Die Gleichung wendet man zum Beispiel an, um die extrinsischen  $L$–Werte eines  Single Parity–check Codes  zu berechnen.

Wie bereits in der  Aufgabe A4.4  dargelegt, lautet nämlich der extrinsische $L$–Wert mit dem Hamming–Gewicht  $w_{\rm H}$  der verkürzten Folge  $\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 ]} \hspace{0.05cm}.$$

Hierbei ist berücksichtigt, dass man für  $L_{\rm E}(i)$  nur die anderen Symbole  $(j ≠ i)$  heranziehen darf:

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





Hinweise:



Fragebogen

1

Wir betrachten den Vektor  $\underline{x} = (x_1, \, x_2) \ \Rightarrow \ n = 2$  mit  $x_i ∈ \{0, \, 1\}$  und  $p_1 = 0.2, \ p_2 = 0.9$.
Wie groß ist die Wahrscheinlichkeit, dass  $\underline{x}$  eine gerade Anzahl an Einsen beinhaltet?

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

2

Berechnen Sie die gleiche Wahrscheinlichkeit für  $\underline{x} = (x_1, \, x_2, \, x_3) \ \Rightarrow \ n = 3$  und  $p_1 = 0.2, \ p_2 = 0.9, \ p_3 = 0.3$.

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

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–Gleichung folgende Größen:

${\rm Pr(blau) = Pr}\big [w_{\rm H}(\underline{x}) \ {\rm ist \ gerade}\big ] \hspace{0.33cm} = \ $

${\rm Pr(rot) = Pr}\big [w_{\rm H}(\underline{x}) \ {\rm ist \ ungerade}\big ] \hspace{0.1cm} = \ $

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

4

Wie groß ist der extrinsische  $L$–Wert für das Symbol  $i = 5$  beim  $\text{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$?

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

5

Wie ändert sich  $L_{\rm E}(i = 5)$, wenn man stattdessen von  $p_5 = 0.1$  ausgeht?

$L_{\rm E}(i = 5)$  wird größer.
$L_{\rm E}(i = 5)$  wird kleiner.
$L_{\rm E}(i = 5)$  wird gegenüber Teilaufgabe (4) nicht verändert.


Musterlösung

Herleitung „$w_{\rm H}$ ist gerade” für die Codelänge $n = 2$

(1)  Entsprechend der nebenstehenden Tabelle gilt:

$${\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 Wahrscheinlichkeiten

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

$${\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 ist \hspace{0.15cm} gerade}\right] = 0.8 + 0.18 \hspace{0.15cm} \underline{= 0.26} \hspace{0.05cm}.$$

Die Gallager–Gleichung liefert für den gleichen Parametersatz:

$${\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 \hspace{0.05cm}.$$

Die von Gallager 1963 angegebene Gleichung wurde hiermit für $n = 2$ verifiziert.


Herleitung „$w_{\rm H}$ ist gerade” für die Codelänge $n = 3$

(2)  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 ist \hspace{0.15cm} gerade}\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:

$$ {\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 \hspace{0.05cm}.$$

Die Gallager–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:

$${\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) $$
$$\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 \hspace{0.05cm}.$$


(3)  Entsprechend der Angabenseite gilt:

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

Daraus lassen sich berechnen:

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

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:

$$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} \hspace{0.05cm}. $$


(4)  Für den Single Parity–check Code wurde der extrinsische $L$–Wert bezüglich des $i$–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 ]} \hspace{0.05cm},$$

oder:

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

Beim SPC (5, 4, 2)  ⇒  $n = 5$ ergibt sich dieses Produkt für $i = 5$ aus folgenden vier Multiplikanden:

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

Der Vergleich mit der Teilaufgabe (3) zeigt, dass $L_{\rm E}(i = 5) = \ln {Q} = \ln {(1.0799)} \ \underline{\approx 0.077}$ ist.


(5)  Richtig ist der Lösungsvorschlag 3, weil das Ergebnis für $L_{\rm E}(i = 5)$ unabhängig von $p_5$ ist.