Aufgaben:Aufgabe 1.14: Bhattacharyya–Schranke für BEC: Unterschied zwischen den Versionen
Zeile 89: | Zeile 89: | ||
Die Wahrscheinlichkeit, dass aufgrund des spezifischen Empfangsvektors $\underline{y}$ das Codewort $\underline{x}_{1}$ genau so wahrscheinlich ist wie $\underline{x}_{0}$, ergibt sich zu | Die Wahrscheinlichkeit, dass aufgrund des spezifischen Empfangsvektors $\underline{y}$ das Codewort $\underline{x}_{1}$ genau so wahrscheinlich ist wie $\underline{x}_{0}$, ergibt sich zu | ||
− | :$$\ {\rm Pr}\ [ | + | :$$\ {\rm Pr}\ [\underline{x}_0 \hspace{0.15cm}{\rm und}\hspace{0.15cm} \underline{x}_1 \hspace{0.15cm}{\rm sind \hspace{0.15cm}gleichwahrscheinlich}] = \lambda^3 \cdot (1- \lambda)^2 + 2 \cdot \lambda^4 \cdot (1- \lambda) + \lambda^5 =$$ |
:$$ \hspace{-0.35cm}\ = \ \hspace{-0.15cm} \lambda^3 \cdot \left [ (1- \lambda)^2 + 2 \cdot \lambda \cdot (1- \lambda) + \lambda^2 \right ] = \lambda^3 \hspace{0.05cm}.$$ | :$$ \hspace{-0.35cm}\ = \ \hspace{-0.15cm} \lambda^3 \cdot \left [ (1- \lambda)^2 + 2 \cdot \lambda \cdot (1- \lambda) + \lambda^2 \right ] = \lambda^3 \hspace{0.05cm}.$$ | ||
Version vom 20. Dezember 2017, 23:16 Uhr
Wir betrachten in dieser Aufgabe den systematischen $(5, 2)$–Code mit der $2×5$–Generatormatrix
- $${ \boldsymbol{\rm G}}_{(5, 2)} = \begin{pmatrix} 1 &0 &1 &1 &0\\ 0 &1 &0 &1 &1 \end{pmatrix} \hspace{0.05cm},$$
der $3 × 5$–Prüfmatrix
- $${ \boldsymbol{\rm H}}_{(5, 2)} = \begin{pmatrix} 1 &0 &1 &0 &0\\ 1 &1 &0 &1 &0\\ 0 &1 &0 &0 &1 \end{pmatrix} \hspace{0.05cm},$$
und den $2^k = 4$ Codeworten
- $$\underline{x}_0 \hspace{-0.15cm}\ = \ \hspace{-0.15cm} (0, 0, 0, 0, 0) \hspace{0.05cm},\hspace{0.2cm}\underline{x}_1 = (0, 1, 0, 1, 1)\hspace{0.05cm},$$
- $$\underline{x}_2 \hspace{-0.15cm}\ = \ \hspace{-0.15cm} (1, 0, 1, 1, 0) \hspace{0.05cm},\hspace{0.2cm}\underline{x}_3 = (1, 1, 1, 0, 1)\hspace{0.05cm}.$$
Am Ausgang des digitalen Kanals, der durch das BEC–Modell (Binary Erasure Channel) mit der Auslöschungswahrscheinlichkeit $\lambda = 0.001$ festgelegt wird, tritt der Empfangsvektor
- $$\underline{y} = (y_1, \hspace{0.05cm}y_2, \hspace{0.05cm}y_3, \hspace{0.05cm}y_4, \hspace{0.05cm}y_5)$$
auf, wobei für $i = 1, \ ... \ , 5$ gilt: $y_{i} \in \{0, 1, \rm E\}$. Der BEC–Kanal zeichnet sich dadurch aus, dass
- Verfälschungen $(0 → 1, 1 → 0)$ ausgeschlossen sind,
- es aber zu Auslöschungen $(0 → \rm E, 1 → E)$ kommen kann.
Die Grafik zeigt explizit alle möglichen Empfangsvektoren $\underline{y}$ mit drei oder mehr Auslöschungen (englisch: Erasures, abgekürzt $\rm E$) unter der Voraussetzung, dass der Nullvektor $(0, 0, 0, 0, 0)$ gesendet wurde. Bei weniger als drei Auslöschungen liefert bei dem betrachteten $(5, 2)$–Code der Codewortschätzer immer die richtige Entscheidung: $\underline{z} = \underline{x}$.
Bei drei oder mehr Auslöschungen kann es dagegen zu Fehlentscheidungen kommen. In diesem Fall gilt für die Blockfehlerwahrscheinlichkeit
- $$ {\rm Pr(Blockfehler)}= {\rm Pr} (\underline{z} \ne \underline{x}) = {\rm Pr}\left \{ \hspace{0.1cm} [\underline{x}_{\hspace{0.02cm}0} \mapsto \underline{x}_{\hspace{0.02cm}1}] \hspace{0.05cm}\cup\hspace{0.05cm}[\underline{x}_{\hspace{0.02cm}0} \mapsto \underline{x}_{\hspace{0.02cm}2}] \hspace{0.05cm}\cup \hspace{0.05cm}[\underline{x}_{\hspace{0.02cm}0} \mapsto \underline{x}_{\hspace{0.02cm}3}] \hspace{0.1cm}\right \} \hspace{0.05cm}.$$
Das Ereignis $[\underline{x}_{0} → \underline{x}_{1}]$ sagt nicht unbedingt aus, dass beim betrachteten Empfangsvektor $\underline{y}$ tatsächlich für das Codewort $\underline{x}_{1}$ entschieden wird, sondern lediglich, dass die Entscheidung für $x_{1}$ aufgrund der Statistik sinnvoller wäre als die Entscheidung für $\underline{x}_{0}$. Es könnte aber auch für $\underline{x}_{2}$ oder $\underline{x}_{3}$ entschieden werden, wenn das Maximum–Likelihood–Kriterium hierfür spricht. Die Berechnung der Blockfehlerwahrscheinlichkeit ist schwierig, da die Ereignisse $[\underline{x}_{0} → \underline{x}_{1}]$ , $[\underline{x}_{0} → \underline{x}_{2}]$ und $[\underline{x}_{0} → \underline{x}_{3}]$ nicht notwendigerweise disjunkt sind. Eine obere Schranke liefert die Union Bound:
- $${\rm Pr(Union \hspace{0.15cm}Bound)} = {\rm Pr}[\underline{x}_{\hspace{0.02cm}0} \hspace{-0.02cm}\mapsto \hspace{-0.02cm}\underline{x}_{\hspace{0.02cm}1}] +{\rm Pr}[\underline{x}_{\hspace{0.02cm}0} \hspace{-0.02cm}\mapsto \hspace{-0.02cm} \underline{x}_{\hspace{0.02cm}2}] +{\rm Pr}[\underline{x}_{\hspace{0.02cm}0} \hspace{-0.02cm}\mapsto \hspace{-0.02cm} \underline{x}_{\hspace{0.02cm}3}] \ge {\rm Pr(Blockfehler)} \hspace{0.05cm}.$$
Eine weitere Schranke wurde von Bhattacharyya angegeben:
- $${\rm Pr(Bhattacharyya)} = W(\beta)-1 \ge {\rm Pr(Union \hspace{0.15cm}Bound)} \ge {\rm Pr(Blockfehler)} \hspace{0.05cm},$$
wobei beim Binary Erasure Channel $\beta = \lambda$ gilt. $W(X)$ ist die Gewichtsfunktion, wobei die Pseudo–Variable $X$ hier durch den Bhattacharyya–Parameter $\lambda$ zu ersetzen ist. Die Bhattacharyya–Schranke liegt je nach Kanal mehr oder weniger weit oberhalb der Union Bound. Ihre Bedeutung liegt darin, dass die Schranke für unterschiedliche Kanäle in gleicher Weise angebbar ist.
Hinweis:
- Die Aufgabe gehört zum Themengebiet von Kapitel Schranken für die Blockfehlerwahrscheinlichkeit.
Fragebogen
Musterlösung
- $\underline{y} = (0, {\rm E}, 0, {\rm E}, {\rm E})$ mit Wahrscheinlichkeit $\lambda^3 \ · \ (1 – \lambda)^2$,
- $\underline{y} = (0, {\rm E}, {\rm E}, {\rm E}, {\rm E})$ mit Wahrscheinlichkeit $\lambda^4 \ · \ (1 – \lambda)$,
- $\underline{y} = ({\rm E}, {\rm E}, 0, {\rm E}, {\rm E})$ mit Wahrscheinlichkeit $\lambda^4 \ · \ (1 – \lambda)$,
- $\underline{y} = ({\rm E}, {\rm E}, {\rm E}, {\rm E}, {\rm E})$ mit Wahrscheinlichkeit $\lambda^5$.
Die Wahrscheinlichkeit, dass aufgrund des spezifischen Empfangsvektors $\underline{y}$ das Codewort $\underline{x}_{1}$ genau so wahrscheinlich ist wie $\underline{x}_{0}$, ergibt sich zu
- $$\ {\rm Pr}\ [\underline{x}_0 \hspace{0.15cm}{\rm und}\hspace{0.15cm} \underline{x}_1 \hspace{0.15cm}{\rm sind \hspace{0.15cm}gleichwahrscheinlich}] = \lambda^3 \cdot (1- \lambda)^2 + 2 \cdot \lambda^4 \cdot (1- \lambda) + \lambda^5 =$$
- $$ \hspace{-0.35cm}\ = \ \hspace{-0.15cm} \lambda^3 \cdot \left [ (1- \lambda)^2 + 2 \cdot \lambda \cdot (1- \lambda) + \lambda^2 \right ] = \lambda^3 \hspace{0.05cm}.$$
In diesem Fall entscheidet man sich nach dem Zufallsprinzip entweder für $\underline{x}_{0}$ (wäre richtig) oder für $\underline{x}_{1}$ (leider falsch), und zwar mit gleicher Wahrscheinlichkeit. Daraus folgt:
- $${\rm Pr} [\underline{x}_{\hspace{0.02cm}0} \mapsto \underline{x}_{\hspace{0.02cm}1}] = 1/2 \cdot \lambda^3 \hspace{0.15cm} \underline{= 5 \cdot 10^{-4}} \hspace{0.05cm}.$$
(2) Nach Teilaufgabe (1) ist die Antwort 2 richtig und nicht die Antwort 1. Auch die Aussage 3 ist falsch: ${\rm Pr}[\underline{x}_{0} → \underline{x}_{1}]$ sagt nicht aus, dass mit dieser Wahrscheinlickeit das Codewort $\underline{x}_{0}$ tatsächlich in das falsche Codewort $\underline{x}_{1}$ übergeht, sondern nur, dass es mit dieser Wahrscheinlichkeit zu $\underline{x}_{1}$ übergehen könnte. ${\rm Pr}[\underline{x}_{0} → \underline{x}_{1}]$ beinhaltet auch Konstellationen, bei denen die Entscheidung tatsächlich für $\underline{x}_{2}$ bzw. $\underline{x}_{3}$ fällt.
(3) Wegen $d_{\rm H}(\underline{x}_{0}, \underline{x}_{2}) = 3$ und $d_{\rm H}(\underline{x}_{0}, \underline{x}_{3}) = 4$ ergibt sich hierfür
- $${\rm Pr} [\underline{x}_{\hspace{0.02cm}0} \mapsto \underline{x}_{\hspace{0.02cm}2}] = 1/2 \cdot \lambda^3 \hspace{0.15cm} \underline{= 5 \cdot 10^{-4}} \hspace{0.05cm},\hspace{0.2cm} {\rm Pr} [\underline{x}_{\hspace{0.02cm}0} \mapsto \underline{x}_{\hspace{0.02cm}3}] = 1/2 \cdot \lambda^4 \hspace{0.15cm} \underline{= 5 \cdot 10^{-5}} \hspace{0.05cm}.$$
(4) Die Blockfehlerwahrscheinlichkeit ist nie größer (mit einer gewissen Wahrscheinlichkeit eher kleiner) als die so genannte Union Bound:
- $${\rm Pr(Union \hspace{0.15cm}Bound)} \hspace{-0.15cm}\ = \ \hspace{-0.15cm} {\rm Pr}[\underline{x}_{\hspace{0.02cm}0} \hspace{-0.02cm}\mapsto \hspace{-0.02cm}\underline{x}_{\hspace{0.02cm}1}] +{\rm Pr}[\underline{x}_{\hspace{0.02cm}0} \hspace{-0.02cm}\mapsto \hspace{-0.02cm} \underline{x}_{\hspace{0.02cm}2}] +{\rm Pr}[\underline{x}_{\hspace{0.02cm}0} \hspace{-0.02cm}\mapsto \hspace{-0.02cm} \underline{x}_{\hspace{0.02cm}3}] =$$
- $$ \hspace{3cm}\ = \ \hspace{-0.15cm} 2 \cdot \lambda^3/2 + \lambda^4/2 = 0.001 + 0.00005 \hspace{0.15cm} \underline{= 1.05 \cdot 10^{-3}} \hspace{0.05cm}.$$
(5) Allgemein gilt: ${\rm Pr(Blockfehler) ≤ Pr(Bhattacharyya)} = {\rm W}(\beta) - 1$. Für das Distanzspektrum bzw. die Gewichtsfunktion erhält man im vorliegenden Fall:
- $$W_0 = 1 \hspace{0.05cm}, \hspace{0.2cm} W_3 = 2 \hspace{0.05cm}, \hspace{0.2cm}W_4 = 1 \hspace{0.3cm} \Rightarrow \hspace{0.3cm} W(X) = 1+ 2 \cdot X^{3} +X^{4} \hspace{0.05cm}.$$
Beim BEC–Kanal gilt zudem $\beta = \lambda$. Daraus folgt als Endergebnis für $\lambda = 0.001$:
- $${\rm Pr(Bhattacharyya)} = 2 \cdot \lambda^3 + \lambda^4 \hspace{0.15cm} \underline{= 2.1 \cdot 10^{-3}} \hspace{0.05cm}.$$
Anzumerken ist, dass beim BEC–Modell die Bhattacharyya–Schranke stets doppelt so groß ist wie die Union Bound, die ja selbst wieder eine obere Schranke für die Blockfehlerwahrscheinlichkeit darstellt.