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  $\rm (BEC)$  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 folgenden 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 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},$$

$$ {\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.