Aufgaben:Aufgabe 1.12Z: Vergleich von HC (7, 4, 3) und HC (8, 4, 4)

• Zurück zum Buch

Blockfehlerwahrscheinlichkeiten von  $\rm HC \ (7, 4, 3)$  und  $\rm HC \ (8, 4, 4)$

Nun sollen die Blockfehlerwahrscheinlichkeiten

• des  $(7, 4, 3)$–Hamming–Codes und
• des erweiterten  $(8, 4, 4)$–Hamming–Codes

miteinander verglichen werden.  Zugrunde gelegt werden

• das  "BSC–Kanalmodell"  (Parameter  $\varepsilon$,  insbesondere  $\varepsilon = 0.01$  für numerische Ergebnisse),
• die  "Syndromdecodierung",  mit der bei beiden Codes eine Maximum–Likelihood–Detektion realisiert wird; bei richtiger Belegung der Syndromtabelle ergibt sich jeweils die minimale Blockfehlerwahrscheinlichkeit.

Für den  $(7, 4, 3)$–Code wurde in der  "Aufgabe 1.12"  exakt berechnet:

$${\rm Pr(Blockfehler)} = 1 - (1 - \varepsilon)^7 - 7 \cdot \varepsilon \cdot (1 - \varepsilon)^6 \hspace{0.05cm}.$$

Die Zahlenwerte sind in der zweiten Spalte der obigen Tabelle angegeben.  Es handelt sich um die tatsächlichen Werte,  also nicht um die in  "Aufgabe 1.12"  hergeleitete Näherung   ${\rm Pr(Blockfehler)} \approx 21 \cdot \varepsilon^2$.

Anzumerken ist,  dass aufgrund des BSC–Kanalmodells nur harte Entscheidungen möglich sind.  Mit  "SoftDecision"  ergeben sich etwas kleinere Blockfehlerwahrscheinlichkeiten.

Nun soll die Blockfehlerwahrscheinlichkeit für den erweiterten  $(8, 4, 4)$–Code ermittelt werden:

• Die Berechnung in Teilaufgabe  (4)  erfolgt unter der Maßgabe,  dass wie beim  $(7, 4, 3)$–Code nur solche Fehlermuster mit einer einzigen  „$1$”  korrigiert werden.  In der rechten Spalte obiger Tabelle sind die Ergebnisse eingetragen,  bis auf den Wert für  $\varepsilon = 0.01$,  der explizit berechnet werden soll.

• In der Teilaufgabe  (5)  soll dagegen berücksichtigt werden,  dass beim erweitereten  $(8, 4, 4)$–Code Teile der Syndromtabelle noch mit Gewicht–2–Fehlermustern aufgefüllt werden können.

Hinweise:

• Die Aufgabe gehört zum Kapitel  "Decodierung linearer Blockcodes".

• Von Interesse für die Lösung dieser Aufgabe ist insbesondere die Seite  "Verallgemeinerung der Syndromdecodierung".

Fragebogen

1

Wieviele Einträge beinhalten die jeweiligen Syndromtabellen insgesamt?

$(7, 4, 3)–{\rm Code} \text{:} \hspace{0.4cm} N_{\rm ges} \ = \ $

$(8, 4, 4)–{\rm Code} \text{:} \hspace{0.4cm} N_{\rm ges} \ = \ $

2

Wieviele Gewicht–2–Fehlermuster  $(N_2')$  gibt es insgesamt?

$(7, 4, 3)–{\rm Code} \text{:} \hspace{0.4cm} N_2' \ = \ $

$(8, 4, 4)–{\rm Code} \text{:} \hspace{0.4cm} N_2' \ = \ $

3

Wieviele Fehlermuster in den Syndromtabellen  $(N_2)$  beinhalten zwei Einsen?

$(7, 4, 3)–{\rm Code} \text{:} \hspace{0.4cm} N_2 \ = \ $

$(8, 4, 4)–{\rm Code} \text{:} \hspace{0.4cm} N_2 \ = \ $

4

Es gelte nun  $\varepsilon = 0.01.$  Welche Blockfehlerwahrscheinlichkeit ergibt sich für den erweiterten  $(8, 4, 4)$–Code  ohne Gewicht–2–Fehlerkorrektur?

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

5

Welches Ergebnis erzielt man demgegenüber  mit Gewicht–2–Fehlerkorrektur?

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

Musterlösung

Musterlösung

(1)  Die Größe der Syndromtabelle ist allgemein $N_{\rm ges} = 2^m$, wobei $m = n - k$ die Anzahl der Prüfbits angibt.

• Beim $(7, 4, 3)$–Hamming–Code ist $m = n - k = 3$  ⇒  die Länge der Tabelle ist $N_{\rm ges} =2^3 \ \underline{= 8}.$
• Die Syndromtabelle des $(8, 4, 4)$–Codes ist doppelt so groß:   $N_{\rm ges} = 2^4 \ \underline{= 16}$.

(2)  Allgemein gilt für die Anzahl der Einträge mit Gewicht–2–Fehlermustern: $N_2' = $„$n {\rm \ über \ } 2$”. Daraus ergeben sich die Zahlenwerte

• $N_2' \ \underline{= 21} \ $ für $n = 7 \ \ ⇒ \ \ (7, 4, 3)$–Code,
• $N_2' \ \underline{= 28} \ $ für $n = 8 \ \ \Rightarrow \ \ (8, 4, 4)$–Code.

(3)  Beim $(7, 4, 3)$–Hamming–Code ist die Syndromtabelle gefüllt mit einem Eintrag für den fehlerfreien Fall $(N_{0}= 1)$ und $n = 7$ Einträge mit Gewicht–1–Fehlermustern $(N_{1} = 7)$. Damit ist die Anzahl der Einträge mit Gewicht–2–Fehlermustern gleich

$$N_2 = N_{\rm ges} - N_0 - N_1 \hspace{0.15cm} \underline{= 0} \hspace{0.05cm}.$$

Dagegen gilt für den erweiterten $(8, 4, 4)$–Hamming–Code:

$$N_0 = 1\hspace{0.05cm},\hspace{0.2cm}N_1 = 8 \hspace{0.3cm} \Rightarrow \hspace{0.3cm} N_2 = N_{\rm ges} - N_0 - N_1 \hspace{0.15cm} \underline{= 7} \hspace{0.05cm}.$$

(4)  Analog zur Musterlösung der ersten beiden Teile der Aufgabe 1.12 erhält man hier:

Blockfehlerwahrscheinlichkeit von $(7, 4, 3)$– und $(8, 4, 4)$–Code

$${\rm Pr(Blockfehler)} = 1 - (1 - \varepsilon)^8 - 8 \cdot \varepsilon \cdot (1 - \varepsilon)^7$$

$$\Rightarrow \hspace{0.3cm}{\rm Pr(Blockfehler)} =1 - 0.922745 - 0.074655\hspace{0.15cm} \underline{= 2.69 \cdot 10^{-3}} \hspace{0.05cm}.$$

• In der Tabelle sind für diesen Fall und für verschiedene BSC–Parameter $ε$ die Ergebnisse in der dritten Spalte   ⇒   ${\rm Pr}(\ge \text{2Fehler)}$ eingetragen.
• Gegenüber dem $(7, 4, 3)$–Code entsprechend der zweiten Spalte ergibt sich stets eine Verschlechterung.

(5)  Bei bestmöglicher Korrektur (gefüllte Syndromtabelle) werden auch sieben Gewicht–2–Fehlermuster korrigiert.

• Damit vermindert sich die Blockfehlerwahrscheinlichkeit um die „Verbesserung” (Spalte 4):

$${\rm Pr(Gewicht\hspace{-0.1cm}-\hspace{-0.1cm}2\hspace{-0.1cm}-\hspace{-0.1cm}Fehlermuster\hspace{0.15cm} wird \hspace{0.15cm} korrigiert)} = 7 \cdot \varepsilon^2 \cdot (1 - \varepsilon)^6 \hspace{0.05cm}.$$

• Für $\varepsilon = 0.01$ macht diese „Verbesserung” etwa $6.59 · 10^{–4}$ aus.
• Die Blockfehlerwahrscheinlichkeit des $(8, 4, 4)$–Codes (letzte Spalte) ergibt sich somit zu

$${\rm Pr(Blockfehler)} = 2.69 \cdot 10^{-3} - 0.66 \cdot 10^{-3} \underline{= 2.03 \cdot 10^{-3}} \hspace{0.05cm}.$$

In der obigen Tabelle ist diese Rechnung für verschiedene BSC–Parameter $\varepsilon$ durchgeführt. Man erkennt:

• Die Blockfehlerwahrscheinlichkeit des erweiterten $(8, 4, 4)$–Hamming–Codes (letzte Spalte) stimmt exakt mit der des $(7, 4, 3)$–Hamming–Codes (Spalte 2) überein.
• Die Korrektur von $25\%$ der Gewicht–2–Fehlermuster gleicht genau die Tatsache aus, dass beim $(8, 4, 4)$–Code Fehlermuster mit mehr als einem Fehler (Spalte 3) wahrscheinlicher sind als beim $(7, 4, 3)$–Code (Spalte 2).