Aufgaben:Aufgabe 1.12Z: Vergleich von HC (7, 4, 3) und HC (8, 4, 4): Unterschied zwischen den Versionen
Zeile 1: | Zeile 1: | ||
{{quiz-Header|Buchseite=Kanalcodierung/Decodierung linearer Blockcodes}} | {{quiz-Header|Buchseite=Kanalcodierung/Decodierung linearer Blockcodes}} | ||
− | [[Datei:P_ID2409__KC_Z_1_12.png|right|frame|Blockfehlerwahrscheinlichkeit von $(7 | + | [[Datei:P_ID2409__KC_Z_1_12.png|right|frame|Blockfehlerwahrscheinlichkeit von $(7, 4, 3)$– und $(8, 4, 4)$–Code]] |
Nun sollen die Blockfehlerwahrscheinlichkeiten | Nun sollen die Blockfehlerwahrscheinlichkeiten | ||
− | *des $(7 | + | *des $(7, 4, 3)$–Hamming–Codes und |
− | *des erweiterten $(8 | + | *des erweiterten $(8, 4, 4)$–Hamming–Codes |
Zeile 13: | Zeile 13: | ||
− | Für den $(7 | + | Für den $(7, 4, 3)$–Code wurde in der [[Aufgaben:1.12_Hard_/_Soft_Decision|Aufgabe 1.12]] berechnet: |
:$${\rm Pr(Blockfehler)} = 1 - (1 - \varepsilon)^7 - 7 \cdot \varepsilon \cdot (1 - \varepsilon)^6 \hspace{0.05cm}.$$ | :$${\rm Pr(Blockfehler)} = 1 - (1 - \varepsilon)^7 - 7 \cdot \varepsilon \cdot (1 - \varepsilon)^6 \hspace{0.05cm}.$$ | ||
Zeile 21: | Zeile 21: | ||
Anzumerken ist, dass aufgrund des BSC–Kanalmodells nur harte Entscheidungen möglich sind. Mit [[Kanalcodierung/Decodierung_linearer_Blockcodes#Codiergewinn_.E2.80.93_Bitfehlerrate_bei_AWGN|Soft–Decision]] ergeben sich etwas kleinere Blockfehlerwahrscheinlichkeiten. | Anzumerken ist, dass aufgrund des BSC–Kanalmodells nur harte Entscheidungen möglich sind. Mit [[Kanalcodierung/Decodierung_linearer_Blockcodes#Codiergewinn_.E2.80.93_Bitfehlerrate_bei_AWGN|Soft–Decision]] ergeben sich etwas kleinere Blockfehlerwahrscheinlichkeiten. | ||
− | Nun soll die Blockfehlerwahrscheinlichkeit für den erweiterten $(8 | + | 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 | + | *Die Berechnung in Teilaufgabe (4) erfolgt unter der Maßgabe, dass wie beim $(7, 4, 3)$–Code nur die 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 | + | *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. |
Zeile 40: | Zeile 40: | ||
|type="{}"} | |type="{}"} | ||
$(7, 4, 3)–{\rm Code} \text{:} \hspace{0.2cm} N_{\rm ges} \ = \ $ { 8 3% } | $(7, 4, 3)–{\rm Code} \text{:} \hspace{0.2cm} N_{\rm ges} \ = \ $ { 8 3% } | ||
− | $(8, 4, 4)–{\rm Code} \text{:} \hspace{0.2cm} N_{\rm ges} \ = \ ${ 16 3% } | + | $(8, 4, 4)–{\rm Code} \text{:} \hspace{0.2cm} N_{\rm ges} \ = \ $ { 16 3% } |
{Wieviele Gewicht–2–Fehlermuster gibt es insgesamt? | {Wieviele Gewicht–2–Fehlermuster gibt es insgesamt? |
Version vom 20. Dezember 2017, 18:27 Uhr
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 berechnet:
- $${\rm Pr(Blockfehler)} = 1 - (1 - \varepsilon)^7 - 7 \cdot \varepsilon \cdot (1 - \varepsilon)^6 \hspace{0.05cm}.$$
Die Zahlenwerte sind in der Spalte 2 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 Soft–Decision 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 die 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 bezieht sich auf Kapitel Decodierung linearer Blockcodes.
- Von Interesse für die Lösung dieser Aufgabe ist insbesondere die Seite Verallgemeinerung der Syndromdecodierung (2).
- Sollte die Eingabe des Zahlenwertes „0” erforderlich sein, so geben Sie bitte „0.” ein.
Fragebogen
Musterlösung
- Beim $(7, 4, 3)$–Hamming–Code ist $m = n - k = 3$ ⇒ die Länge der Tabelle ist $N_{\rm ges} \ \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 Aufgabe 1.12 (1) und (2) erhält man hier:
- $${\rm Pr(Blockfehler)} \hspace{-0.15cm}\ = \ \hspace{-0.15cm} 1 - (1 - \varepsilon)^8 - 8 \cdot \varepsilon \cdot (1 - \varepsilon)^7=$$
- $$\hspace{2.875cm}\ = \ \hspace{-0.15cm} 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 grün hinterlegten Spalte eingetragen. Gegenüber dem $(7, 4, 3)$–Code 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
- $${\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 $0.66 · 10^{–3}$ aus. Die Blockfehlerwahrscheinlichkeit 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 (siehe 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).