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

Aus LNTwww
(Weitergeleitet von Aufgabe 1.15: Distanzspektren)
Wechseln zu:Navigation, Suche

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

Wir betrachten wie in der  "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, \ \text{...} \ , 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 e}^{- R \hspace{0.05cm}\cdot \hspace{0.05cm}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}$$

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




Hinweise:

  • Als Kanäle sollen betrachtet werden:




Fragebogen

1

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

$W_{0} \ = \ $

$W_{3} \ = \ $

$W_{4} \ = \ $

$W_{7} \ = \ $

2

Wie lautet die Bhattacharyya–Schranke für den  $(7, 4, 3)$–Hamming–Code und das BSC–Modell mit  $\varepsilon = 0.01$?

${\rm Pr(Bhattacharyya)} \ = \ $

$\ \%$

3

Wie lautet bei gleichem Kanal die Schranke des erweiterten  $(8, 4, 4)$–Hamming–Codes?

${\rm Pr(Bhattacharyya)} \ = \ $

$\ \%$

4

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

$\lambda \ = \ $

5

Wir betrachten weiterhin den erweiterten  $(8, 4, 4)$–Hamming–Code,  aber nun das AWGN–Modell.
Bestimmen Sie  $E_{\rm B} / N_{0}$  (in dB)  derart,  dass sich die gleiche Bhattacharyya–Schranke ergibt.

$10 · \lg {E_{\rm B}/N_0} \ = \ $

$ \ \rm dB$

6

Ermitteln Sie nun den AWGN–Parameter   $(10 · \lg {E_{\rm B}/N_0})$   für den  $(7, 4, 3)$–Hamming–Code.

$10 · \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 beinhaltet keine Eins   ⇒   das Nullwort,
  • $W_{3} \ \underline{ = \ 7}$   ⇒   Codeworte beinhalten drei Einsen,
  • $W_{4} \ \underline{ = \ 7}$   ⇒   Codeworte beinhalten vier Einsen,
  • $W_{7} \ \underline{ = \ 1}$   ⇒   Codewort besteht nur aus Einsen.


$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}\hspace{0.3cm} \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\hspace{0.3cm} \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 6.6\%} \hspace{0.05cm}.$$
  • Ein Vergleich mit der tatsächlichen Blockfehlerwahrscheinlichkeit,  wie in "Aufgabe 1.12" berechnet,
$${\rm Pr(Blockfehler)} \approx 21 \cdot \varepsilon^2 = 2.1 \cdot 10^{-3} \hspace{0.05cm},$$
zeigt,  dass Bhattacharyya nur eine 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:

$$W(X) = 1+ 14 \cdot X^{4} + X^{8}\hspace{0.3cm} \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 2.2\%} \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 e}^{- 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 e}^{- R \hspace{0.05cm}\cdot \hspace{0.05cm} 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 erweiterten  $(8, 4, 4)$–Hamming–Codes beträgt  $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$  des  $(7, 4, 3)$–Hamming–Codes 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}.$$