Aufgabe 1.14: Bhattacharyya–Schranke für BEC

Aus LNTwww
Wechseln zu:Navigation, Suche

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


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

(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.