Aufgaben:Aufgabe 1.14: Bhattacharyya–Schranke für BEC

• Zurück zum Buch

Mögliche Empfangsvektoren für den  $(5, 2)$–Code und BEC

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},\hspace{0.2cm}\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, \ \text{...} \ , 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 Codewortfinder 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}.$$

Bitte beachten Sie:

• 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 für den Bhattacharyya–Parameter  $\beta = \lambda$  gilt und  $W(X)$  die  Gewichtsfunktion  angibt, 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 Kapitel  Schranken für die Blockfehlerwahrscheinlichkeit.

Fragebogen

1

Wie groß ist die paarweise Fehlerwahrscheinlichkeit zwischen den Codeworten $\underline{x}_{0} = (0, 0, 0, 0, 0)$ und $\underline{x}_{1} = (0, 1, 0, 1, 1)$?

${\rm Pr}[\underline{x}_{0} → \underline{x}_{1}] \ = \ $ $\ \cdot 10^{-3} $

2

Welche Aussagen stimmen bezüglich ${\rm Pr}[\underline{x}_{0} → \underline{x}_{i}]$ mit Laufindex $i = 1, \ \text{...} \ , 3$? $d_{{\rm H},\hspace{0.05cm}i}$ bezeichnet hier die Hamming–Distanz zwischen $x_{0}$ und $x_{i}$.

	Es gilt ${\rm Pr}[\underline{x}_{0} → \underline{x}_{i}] \ = \ \lambda ^{d_{{\rm H},\hspace{0.05cm}i}} \ · \ (1 – \lambda)^{n \hspace{0.05cm}– \hspace{0.05cm}d_{{\rm H},\hspace{0.05cm}i}}$.
	Es gilt ${\rm Pr}[\underline{x}_{0} → \underline{x}_{i}] \ = \ 1/2 · \lambda ^{d_{{\rm H},\hspace{0.05cm}i}}.$
	${\rm Pr}[\underline{x}_{0} → \underline{x}_{i}]$ ist die Verfälschungswahrscheinlichkeit von $x_{0}$ nach $x_{i}$.

3

Wie groß sind die Wahrscheinlichkeiten

$\ {\rm Pr}[\underline{x}_{0} → \underline{x}_{2}] \ = \ $ $\ \cdot 10^{-3} $

$\ {\rm Pr}[\underline{x}_{0} → \underline{x}_{3}] \ = \ $ $\ \cdot 10^{-3} $

4

Geben Sie die Union Bound für die Blockfehlerwahrscheinlichkeit an.

$\ {\rm Pr(Union Bound)} \ = \ $ $\ \cdot 10^{-3} $

5

Wie lautet im vorliegenden Fall die Bhattacharyya–Schranke?

$\ {\rm Pr(Bhattacharyya)} \ = \ $ $\ \cdot 10^{-3} $

Musterlösung

Musterlösung

(1)  Die Codeworte $\underline{x}_{0}$ und $\underline{x}_{1}$ unterscheiden sich in Bit $2, \ 4$ und $5$. Wird nur einer dieser drei Binärwerte richtig übertragen, ist damit das gesamte Codewort eindeutig bestimmt. Keine Information über das Codewort erhält man bei folgenden Empfangsvektoren (siehe Tabelle auf der Angabenseite):

• $\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.12cm}{\rm und}\hspace{0.12cm} \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 =\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{= 0.5 \cdot 10^{-3}} \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{= 0.5 \cdot 10^{-3}} \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{= 0.05 \cdot 10^{-3}} \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}] = 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) ≤ {\rm Pr(Union \hspace{0.15cm}Bound)} \le Pr(Bhattacharyya)} = 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.