Exercise 4.4Z: Supplement to Exercise 4.4

• Return to book

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

Fragebogen

1

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

$p_1 = 0.2, \ p_2 = 0.9 \text{:} \hspace{0.2cm} {\rm Pr}[{\rm gerades} \ w_{\rm H}] \ = \ $

2

Berechnen Sie die gleiche Wahrscheinlichkeit für $\underline{x} = (x_1, \, x_2, \, x_3) \ \Rightarrow \ n = 3$.

$... \ , \ p_3 = 0.3 \text{:} \hspace{0.2cm} {\rm Pr}[{\rm gerades} \ w_{\rm H}] \ = \ $

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}[w_{\rm H}(\underline{x}) {\rm ist \ gerade}] \ = \ $

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

$Q = {\rm Pr(blau)/Pr(rot)} \ = \ $

4

Wie groß ist der extrinsische $L$–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$?

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

5

Wie änder 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

Solution

(1) 

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 Wahrscheinlicekiten

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

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

(3) 

(4) 

(5)