Exercise 4.4Z: Supplement to Exercise 4.4
Der Informationstheoretiker Robert G. Gallager hat sich bereits 1963 mit folgender Fragestellung beschäftigt:
- Gegeben ist ein Zufallsvektor x_=(x1,x2, ... ,xn) mit n binären Elementen xi∈{0,1}.
- Bekannt sind alle Wahrscheinlichkeiten pi=Pr(xi=1) und qi=Pr(xi=0)=1−pi 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 Pr[wH(x_) ist gerade]?
Die Grafik verdeutlicht die Aufgabenstellung für das Beispiel n=4 sowie p1=0.2, p2=0.9, p3=0.3 und p4=0.6.
- Für die grün hinterlegte Zeile ⇒ x_=(1,0,0,1) gilt wH(x_)=2 und Pr(x_)=p1⋅q2⋅q3⋅p4=0.0084.
- Blaue Schrift bedeutet ein geradzahliges Hamming–Gewicht. Rote Schrift steht für „wH(x_) ist ungerade”.
- Die Wahrscheinlichkeite Pr[wH(x_) ist gerade] ist gleich der Summe der blauen Zahlen in der letzten Spalte. Die Summe der roten Zahlen ergibt Pr[wH(x_) ist ungerade]=1−Pr[wH(x_) ist gerade].
Gallager hat das Problem in analytischer Weise gelöst:
- Pr[wH(x_)istgerade] = 1/2⋅[1+π],
- Pr[wH(x_)istungerade] = 1/2⋅[1−π].
Hierbei ist die folgende Hilfsgröße verwendet:
- π=n∏i=1(1−2pi).
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 wH der verkürzten Folge x_(−i):
- LE(i)=lnPr[wH(x_(−i))istgerade|y_]Pr[wH(x_(−i))istungerade|y_].
Hierbei ist berücksichtigt, dass man für LE(i) nur die anderen Symbole (j≠i) heranziehen darf:
- x_(−i)=(x1,...,xi−1,xi+1,...,xn).
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)''' [[File: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)''' [[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 + :+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.
