Aufgabe 4.4Z: Ergänzung zur Aufgabe 4.4

Hamming–Gewicht und Wahrscheinlichkeiten

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

Gegeben ist ein Zufallsvektor $\underline{x} = (x_1, \, x_2, \ ... \ , \, 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 Inex $i = 1, \ ... \ , \ 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 ein geradzahliges Hamming–Gewicht. Rote Schrift steht für „$w_{\rm H}(\underline{x})$ ist ungerade”.
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}]$.

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 ] \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 Aufgabe A4.4 dargelegt, lautet nämlich der extrinsischen $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.03cm} ... \hspace{0.08cm} , \hspace{0.03cm} x_{i-1}, \hspace{0.43cm} x_{i+1}, \hspace{0.03cm} ... \hspace{0.08cm} , x_{n} \hspace{0.03cm} \big )\hspace{0.03cm}. $$

Hinweise:

Die Aufgabe gehört zum Kapitel Soft–in Soft–out Decoder und ist als Ergänzung zur Aufgabe A4.4 gedacht.
Sollte die Eingabe des Zahlenwertes „0” erforderlich sein, so geben Sie bitte „0.” ein.$$ ==='"`UNIQ--h-0--QINU`"'Fragebogen=== '"`UNIQ--quiz-00000002-QINU`"' ==='"`UNIQ--h-1--QINU`"'Musterlösung=== '"`UNIQ--html-00000003-QINU`"' '''(1)''' [[Datei:P_ID2996__KC_Z_4_4a_v1.png|frame|right|Herleitung „$w_{\rm H}$ ist gerade” für $n = 2$]] Entsprechend nebenstehender 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) =$$ :$$\ = \ \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. '''(2)''' [[Datei: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 + $$ :$$+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. :$${\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) =$$ :$$\ = \ \hspace{-0.15cm} 0.5 + 0.5 \cdot (+0.6) \cdot (-0.8) \cdot (+0.4) = 0.404 \hspace{0.05cm}.$$ Anzumerken ist, dass diese Gleichung für alle $n$ und alle beliebigen Wahrscheinlichkeiten gültig ist. '''(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) =$$ :$$\ = \ \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 <i>Single Parity–check Code</i> 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.