Aufgabe 1.15: Distanzspektren von HC (7, 4, 3) und HC (8, 4, 4)

Aus LNTwww
Wechseln zu:Navigation, Suche

Codetabellen des (7, 4)–Hamming–Codes und der (8, 4)–Erweiterung

Wir betrachten wie in Aufgabe 1.9

  • den (7, 4, 3)–Hamming–Code und
  • den erweiterten (8, 4, 4)–Hamming–Code.

Die Grafik zeigt die zugehörigen Codetabellen. In der Aufgabe 1.12 wurde schon die Syndromdecodierung dieser beiden Codes behandelt. In dieser Aufgabe sollen die Unterschiede hinsichtlich des Distanzspektrums {$W_{i}$} herausgearbeitet werden. Für die Laufvariable gilt $i = 0, ... , n:$

  • Die Integerzahl $W_{i}$ gibt die Zahl der Codeworte $\underline{x}$ mit dem Hamming–Gewicht $\underline{w}_{\rm H}( \underline{x} ) = i$ an.
  • Bei den hier betrachteten linearen Code bescheibt $W_{i}$ gleichzeitig die Anzahl der Codeworte mit der Hamming–Distanz $i$ vom Nullwort.
  • Häufig weist man der Zahlenmenge { ${W_{i}}$ } einer Pseudo–Funktion zu, die man Gewichtsfunktion (englisch: Weight Enumerator Function, WEF) nennt:
$$\left \{ \hspace{0.05cm} W_i \hspace{0.05cm} \right \} \hspace{0.3cm} \Leftrightarrow \hspace{0.3cm} W(X) = \sum_{i=0 }^{n} W_i \cdot X^{i} = W_0 + W_1 \cdot X + W_2 \cdot X^{2} + ... \hspace{0.05cm} + W_n \cdot X^{n}\hspace{0.05cm}.$$

Bhattacharyya hat die Pseudo–Funktion $W(X;)$ verwendet, um eine kanalunabhängige (obere) Schranke für die Blockfehlerwahrscheinlichkeit anzugeben:

$${\rm Pr(Blockfehler)} \le{\rm Pr(Bhattacharyya)} = W(\beta) -1 \hspace{0.05cm}.$$

Der so genannte Bhattacharyya–Parameter ist dabei wie folgt gegeben:

$$\beta = \left\{ \begin{array}{c} \lambda \\ \\ 2 \cdot \sqrt{\varepsilon \cdot (1- \varepsilon)}\\ \\ {\rm exp}[- R \cdot E_{\rm B}/N_0] \end{array} \right.\quad \begin{array}{*{1}c} {\rm f\ddot{u}r\hspace{0.15cm} das \hspace{0.15cm}BEC-Modell},\\ \\ {\rm f\ddot{u}r\hspace{0.15cm} das \hspace{0.15cm}BSC-Modell}, \\ \\{\rm f\ddot{u}r\hspace{0.15cm} das \hspace{0.15cm}AWGN-Modell}. \end{array}$$

Hinweis:

Die Aufgabe bezieht sich auf Kapitel Schranken für die Blockfehlerwahrscheinlichkeit, ebenso wie Aufgabe 1.14 und Aufgabe 1.16. Als Kanäle sollen betrachtet werden:

Anzumerken ist, dass die Bhattacharyya–Schranke im allgemeinen sehr pessimistisch ist. Die tatsächliche Blockfehlerwahrscheinlichkeit liegt oft deutlich darunter.

Fragebogen

1

Geben Sie das Distanzspektrum des (7, 4, 3)–Hamming–Codes an.

$\ ( 7, 4, 3)–{\rm Code:} W_{0} \ = \ $

$\ W_{3} \ = \ $

$\ W_{4} \ = \ $

$\ W_{7} \ = \ $

2

Wie lautet die Bhattacharyya–Schranke für das BSC–Modell mit $\varepsilon = 0.01?$

$\ (7, 4, 3)–{\rm Code:} \ \ \ {\rm Pr(Bhattacharyya)} \ = \ $

3

Wie lautet bei gleichem Kanal die Schranke des erweiterten Codes?

$\ (8, 4, 4)–{\rm Code:} \ \ \ {\rm Pr(Bhattacharyya)} \ = \ $

4

Mit welchem BEC–Parameter $\lambda$ erhält man die genau gleichen Schranken?

$\lambda \ = \ $

5

Betrachten wir nun das AWGN–Modell. Bestimmen Sie $E_{\rm B} / N_{0}$ in dB derart, dass sich für den (8, 4, 4)–Code die gleiche Bhattacharyya–Schranke ergibt.

$\ (8, 4, 4)–{\rm Code:} \ \ \ \ 10 · \ {\rm lg} \ E_{\rm B}/N_{0} \ = \ $

$ \ \rm dB$

6

Ermitteln Sie nun den AWGN–Parameter für den (7, 4, 3)–Hamming–Code.

$\ (7, 4, 3)–{\rm Code:} \ \ \ \ 10 · \ {\rm lg} \ E_{\rm B}/N_{0} \ = \ $

$ \ \rm dB$


Musterlösung

(1)  Durch die Analyse aller Codeworte des (7, 4, 3)–Hamming–Codes erkennt man, dass

  • $W_{0} \underline{ = \ 1}$ Codewort keine Eins beinhaltet (das Nullwort),
  • $W_{3} \underline{ = \ 7}$ Codeworte drei Einsen beinhalten,
  • $W_{4} \underline{ = \ 7}$ Codeworte vier Einsen beinhalten,
  • $W_{7} \underline{ = \ 1}$ Codewort nur aus Einsen besteht.

$W_{i}$ gibt gleichzeitig die Anzahl der Codeworte an, die sich vom Nullwort in $i \ \rm Bit$ unterscheiden.


(2)  Die Bhattacharyya–Schranke lautet:

$${\rm Pr(Blockfehler)} \le{\rm Pr(Bhattacharyya)} = W(\beta) -1 \hspace{0.05cm}.$$

Die Gewichtsfunktion ist durch die Teilaufgabe 1) festgelegt:

$$W(X) = 1+ 7 \cdot X^{3} + 7 \cdot X^{4} + X^{7}$$
$$\Rightarrow \hspace{0.3cm} {\rm Pr(Bhattacharyya)} = 7 \cdot \beta^{3} + 7 \cdot \beta^{4} + \beta^{7} \hspace{0.05cm}.$$

Für den Bhattacharyya–Parameter des BSC–Modells gilt:

$$\beta = 2 \cdot \sqrt{\varepsilon \cdot (1- \varepsilon)} = 2 \cdot \sqrt{0.01 \cdot 0.99} = 0.199$$
$$ \Rightarrow \hspace{0.3cm} {\rm Pr(Bhattacharyya)} = 7 \cdot 0.199^{3} + 7 \cdot 0.199^{4} + 0.199^{7} \hspace{0.15cm} \underline{ \approx 0.066} \hspace{0.05cm}.$$

Ein Vergleich mit der tatsächlichen Blockfehlerwahrscheinlichkeit, wie in Aufgabe 1.12 berechnet:

$$W(X) = 1+ 14 \cdot X^{4} + X^{8}$$
$$\Rightarrow \hspace{0.3cm} {\rm Pr(Bhattacharyya)} = 14 \cdot \beta^{4} + \beta^{8} = 14 \cdot 0.199^{4} + 0.199^{8} \hspace{0.15cm} \underline{ \approx 0.022} \hspace{0.05cm}.$$

zeigt, dass Bhattacharyya nur eine äußerst grobe Schranke bereitstellt. Im vorliegenden Fall liegt diese Schranke um mehr als den Faktor 30 über dem tatsächlichen Wert.


(3)  Aus der Codetabelle des (8, 4, 4)–Codes erhält man folgende Ergebnisse:

$${\rm Pr(Blockfehler)} \approx 21 \cdot \varepsilon^2 = 2.1 \cdot 10^{-3} \hspace{0.05cm},$$

(4)  Die Gleichung für den Bhattacharyya–Parameter lautet:

$$\beta = \left\{ \begin{array}{c} \lambda \\ \\ 2 \cdot \sqrt{ \varepsilon \cdot (1- \varepsilon)}\\ \\ {\rm exp}[- R \cdot E_{\rm B}/N_0] \end{array} \right.\quad \begin{array}{*{1}c} {\rm f\ddot{u}r\hspace{0.15cm} das \hspace{0.15cm}BEC-Modell},\\ \\ {\rm f\ddot{u}r\hspace{0.15cm} das \hspace{0.15cm}BSC-Modell}, \\ \\{\rm f\ddot{u}r\hspace{0.15cm} das \hspace{0.15cm}AWGN-Modell}. \end{array}$$

Mit dem BEC–Modell ergibt sich genau die gleiche Schranke, wenn die Auslöschungswahrscheinlichkeit $\lambda = \beta \underline{= 0.199}$ beträgt.


(5)  Entsprechend obiger Gleichung muss gelten:

$$\beta = {\rm exp}[- R \cdot E_{\rm B}/N_0] = 0.199 \hspace{0.3cm} \Rightarrow \hspace{0.3cm} R \cdot E_{\rm B}/N_0 = 10^{0.199} = 1.58 \hspace{0.05cm}.$$

Die Coderate des (8, 4, 4)–Codes ist $R = 0.5:$

$$E_{\rm B}/N_0 = 3.16 \hspace{0.3cm} \Rightarrow \hspace{0.3cm} 10 \cdot {\rm lg} \hspace{0.1cm} E_{\rm B}/N_0 \hspace{0.15cm} \underline{\approx 5\,{\rm dB}} \hspace{0.05cm}.$$


(6)  Mit der Coderate $R = 4/7$ erhält man:

$$E_{\rm B}/N_0 = 7/4 \cdot 1.58 = 2.765 \hspace{0.3cm} \Rightarrow \hspace{0.3cm} 10 \cdot {\rm lg} \hspace{0.1cm} E_{\rm B}/N_0 \hspace{0.15cm} \underline{\approx 4.417\,{\rm dB}} \hspace{0.05cm}.$$