Decodierung linearer Blockcodes
Inhaltsverzeichnis
Blockschaltbild und Voraussetzungen
Wir gehen von dem bereits im Kapitel Kanalmodelle und Entscheiderstrukturen gezeigten Blockschaltbild aus, wobei als Kanalmodell meist der Binary Symmetric Channel (BSC) verwendet wird. Zur Codewortschätzung verwenden wir den Maximum–Likelihood–Entscheider (ML), der für binäre Codes ⇒ x_∈GF(2n) auf Blockebene das gleiche Ergebnis liefert wie der MAP–Empfänger.
Die Aufgabe des Kanaldecoders kann wie folgt beschrieben werden:
- Der Vektor v_ nach der Decodierung (an der Sinke) soll möglichst gut mit dem Informationswort u_ übereinstimmen. Das heißt: Die Blockfehlerwahrscheinlichkeit soll möglichst klein sein:
- Pr(Blockfehler)=Pr(v_≠u_)!=Minimum.
- Aufgrund der deterministischen Zuweisungen x_=enc(u_) bzw. v_=enc−1(z_) gilt aber auch:
- Pr(Blockfehler)=Pr(z_≠x_)!=Minimum.
- Gesucht ist somit das zum gegebenen Empfangswort y_=x_+e_ am wahrscheinlichsten gesendete Codewort x_i, das als Ergebnis z_ weiter gegeben wird:
- z_=argmaxx_i∈CPr(x_i|y_).
- Beim BSC–Kanal gilt sowohl x_i∈GF(2n) als auch y_∈GF(2n), so dass die Maximum–Likelihood–Regel auch mit der Hamming–Distanz dH(y_,x_i) geschrieben werden kann:
- z_=argminx_i∈CdH(y_,x_i).
Prinzip der Syndromdecodierung
Vorausgesetzt wird hier ein (n,k)–Blockcode mit der Prüfmatrix H und den systematischen Codeworten
- x_=(x1,x2,...,xi,...,xn)=(u1,u2,...,uk,p1,...,pn−k).
Mit dem Fehlervektor e_ gilt dann für das Empfangswort:
- y_=x_+e_,y_∈GF(2n),x_∈GF(2n),e_∈GF(2n).
Ein Bitfehler an der Position i, das heißt yi≠xi, wird ausgedrückt durch den Fehlerkoeffizienten ei=1.
Definition: Das Syndrom s_=(s0,s1,...,sm−1) berechnet sich (als Zeilen– bzw. Spaltenvektor) aus dem Empfangswort y_ und der Prüfmatrix H in folgender Weise:
- s_=y_⋅HTbzw.s_T=H⋅y_T.
Die Vektorlänge von s_ ist gleich m=n−k (Zeilenzahl von H).
Das Syndrom s_ zeigt folgende Charakteristika:
- Wegen der Gleichung x_⋅HT=0_ hängt das Syndrom s_ nicht vom Codewort x_ ab, sondern allein vom Fehlervektor e_:
- s_=y_⋅HT=x_⋅HT+e_⋅HT=e_⋅HT.
- Bei hinreichend wenig Bitfehlern liefert s_ einen eindeutigen Hinweis auf die Fehlerpositionen und ermöglicht so eine vollständige Fehlerkorrektur.
Beispiel 1: Ausgehend vom systematischen (7, 4, 3)–Hamming–Code erhält man für den Empfangsvektor y_=(0,1,1,1,0,0,1) das folgende Ergebnis:
- H⋅y_T=(111010001110101101001)⋅(0111001)=(011)=s_T.
Vergleicht man das Syndrom mit den Prüfgleichungen des Hamming–Codes, so erkennt man, dass
- am wahrscheinlichsten das vierte Symbol (x4=u4) des Codewortes verfälscht wurde,
- der Codewortschätzer somit das Ergebnis z_=(0,1,1,0,0,0,1) liefern wird.
- die Entscheidung nur dann richtig ist, wenn bei der Übertragung nur ein Bit verfälscht wurde.
Nachfolgend sind die erforderlichen Korrekturen für den (7, 4, 3)–Hamming–Code angegeben, die sich aus dem errechneten Syndrom s_ entsprechend den Spalten der Prüfmatrix ergeben:
- s_=(0,0,0)⇒keineKorrektur;s_=(1,0,0)⇒p1invertieren;
- s_=(0,0,1)⇒p3invertieren;s_=(1,0,1)⇒u1invertieren;
- s_=(0,1,0)⇒p2invertieren;s_=(1,1,0)⇒u3invertieren;
- s_=(0,1,1)⇒u4invertieren;s_=(1,1,1)⇒u2invertieren.
Verallgemeinerung der Syndromdecodierung
Wir fassen die Ergebnisse der letzten Seiten zusammen, wobei wir weiterhin vom BSC–Kanalmodell ausgehen. Das bedeutet: y_ und e_ sind Elemente von GF(2n), während die möglichen Codeworte x_i zum Code C gehören, der einen (n−k)–dimensionalen Untervektorraum von GF(2n) darstellt. Dann gilt:
- Die Syndromdecodierung ist eine Realisierungsmöglichkeit der Maximum–Likelihood–Detektion von Blockcodes. Man entscheidet sich für das Codewort x_i mit der geringsten Hamming–Distanz zum Empfangswort y_:
- z_=argminx_i∈CdH(y_,x_i).
- Die Syndromdecodierung ist aber auch die Suche nach dem wahrscheinlichsten Fehlervektor e_, der die Bedingung e_⋅HT=s_ erfüllt. Das Syndrom liegt dabei durch s_=y_⋅HT fest.
- Mit dem Hamming–Gewicht wH(e_) kann die zweite Interpretation auch wie folgt mathematisch formuliert werden:
- z_=y_+argmine_i∈GF(2n)wH(e_i).
Fazit: Zu beachten ist, dass der Fehlervektor e_ ebenso wie der Empfangsvektor y_ ein Element von GF(2n) ist im Gegensatz zum Syndrom s_∈GF(2m) mit der Anzahl m=n−k der Prüfgleichungen. Das bedeutet,
- dass die Zuordnung zwischen Syndrom s_ und Fehlervektor e_ nicht eindeutig ist, sondern
- dass jeweils 2k Fehlervektoren zum gleichen Syndrom s_ führen, die man zu einer Nebenklasse (englisch: Coset) zusammenfasst.
Beispiel 2: Der Sachverhalt soll hier am Beispiel n=5,k=2 ⇒ m=n−k=3 verdeutlicht werden:
- Die 2n=32 möglichen Fehlervektoren e_ werden in 2m=8 Cosets Ψ0, ... , Ψ7 aufgeteilt. Explizit gezeichnet sind hier nur die Cosets Ψ0 und Ψ5.
- Alle 2k=4 Fehlervektoren des Cosets Ψμ führen zum gleichen Syndrom s_μ.
- Jede Nebenklasse Ψμ hat einen Anführer e_μ, nämlich denjenigen mit dem minimalen Hamming–Gewicht.
Beispiel 3: Ausgehend von einem systematischen (5, 2, 3)–Code C={(0,0,0,0,0),(0,1,0,1,1),(1,0,1,1,0),(1,1,1,0,1)} wird nun die Vorgehensweise bei der Syndromdecodierung im Detail beschrieben.
Generatormatrix und Prüfmatrix lauten:
- G=(1011001011),
- H=(101001101001001).
Die Tabelle fasst das Endergebnis zusammen. Beachten Sie: Der Index μ ist nicht identisch mit dem Binärwert von s_μ:
- Die Reihenfolge ergibt sich vielmehr durch die Anzahl der Einsen im Nebenklassenanführer e_μ.
- Beispielsweise ist das Syndrom s_5=(1,1,0) und das Syndrom s_6=(1,0,1).
Zur Herleitung dieser Tabelle ist anzumerken:
- Die Zeile 1 bezieht sich auf das Syndrom s_0=(0,0,0) und die dazugehörige Nebenklasse Ψ0. Am wahrscheinlichsten ist hier die Fehlerfolge (0,0,0,0,0) ⇒ kein Bitfehler, die wir als Nebenklassenanführer e_0 bezeichnen. Auch die weiteren Einträge in der ersten Zeile, nämlich (1,0,1,1,0), (0,1,0,1,1) und (1,1,1,0,1), liefern jeweils das Syndrom s_0=(0,0,0), ergeben sich aber nur mit mindestens drei Bitfehlern und sind entsprechend unwahrscheinlich.
- In den Zeilen 2 bis 6 beinhaltet der jeweilige Nebenklassenanführer e_μ genau eine einzige Eins (μ=1, ... , 5). e_μ ist stets das wahrscheinlichste Fehlermuster der Klasse Ψμ. Die anderen Gruppenmitglieder ergeben sich erst bei mindestens zwei Bitfehlern.
- Das Syndrom s_6=(1,0,1) ist mit nur einem Bitfehler nicht möglich. Bei der Erstellung der Tabelle wurden daraufhin alle 5 über 2=10 Fehlermuster e_ mit Gewicht wH(e_)=2 betrachtet. Die zuerst gefundene Folge mit Syndrom s_6=(1,0,1) wurde als Nebenklassenanführer e_6=(1,1,0,0,0) ausgewählt. Bei anderer Probierreihenfolge hätte sich auch die Folge (0,0,1,0,1) aus Ψ6 ergeben können.
- Ähnlich wurde bei der Bestimmung des Anführers e_7=(0,1,1,0,0) der Nebenklasse Ψ7 vorgegangen, die durch das einheitliche Syndrom s_7=(1,1,1) gekennzeichnet ist. Auch in der Klasse Ψ7 gibt es eine weitere Folge mit Hamming–Gewicht wH(e_)=2, nämlich (1,0,0,0,1).
Die obige Tabelle muss nur einmal erstellt und kann beliebig oft genutzt werden. Zunächst muss das Syndrom ermittelt werden. Dieses lautet beispielsweise für den Empfangsvektor y_=(0,1,0,0,1): s_=y_⋅HT=(01001)⋅(110011100010001)=(010)=s_2.
Mit dem Nebenklassenanführer e_2=(0,0,0,1,0) aus obiger Tabelle (roter Eintrag für Index 2) gelangt man schließlich zum Decodierergebnis:
- z_=y_+e_2=(0,1,0,0,1)+(0,0,0,1,0)=(0,1,0,1,1).
Fazit: Aus dieser Kurzzusammenfassung geht schon hervor, dass die Syndromdecodierung mit einem enormen Aufwand verbunden ist, wenn man nicht wie bei zyklischen Codes gewisse Eigenschaften nutzen kann:
- Bei großen Blockcodelängen versagt diese Methode vollständig. So müsste man zur Decodierung eines BCH–Codes – die Abkürzung steht für deren Erfinder Bose, Chaudhuri und Hocquenghem – mit den Codeparametern n=511, k=259 unddmin=61 genau 2511−259≈1076 Fehlermuster der Länge 511 auswerten und abspeichern.
- Für diese Codes und auch für andere Codes großer Blocklänge gibt es aber spezielle Decodieralgorithmen, die mit weniger Aufwand zum Erfolg führen.
Codiergewinn – Bitfehlerrate bei AWGN
Wir betrachten nun die Bitfehlerrate (englisch: Bit Error Rate, BER) für folgende Konstellationen:
- Hamming–Code (7, 4, 3),
- AWGN–Kanal, gekennzeichnet durch den Quotienten EB/N0/N0 (in dB),
- Maximum–Likelihood–Detektion (ML) mit Hard Decision bzw. Soft Decision.
Zu dieser Grafik ist anzumerken:
- Die schwarze Vergleichskurve gilt beispielsweise für die binäre Phasenmodulation (BPSK) ohne Codierung. Hierfür benötigt man für die Bitfehlerrate 10−5 etwa 10⋅lgEB/N0≈9.6dB.
- Die roten Kreise gelten für den (7, 4, 3)–Code und harte Entscheidungen des Maximum–Likelihood–Decoders (ML–HD). Die Syndromdecodierung ist hierfür eine mögliche Realisierungsform.
- Diese Systemkonfiguration bringt erst für 10⋅lgEB/N0>6dB eine Verbesserung gegenüber dem Vergleichssystem. Für BER=10−5 benötigt man nur noch 10−5 etwa 10⋅lgEB/N0≈9.2dB.
- Die grünen Kreuze für den Hamming–Code mit Soft–Decision (ML–SD) liegen im gesamten Bereich unterhalb der Vergleichskurve. Für BER=10−5 ergibt sich 10⋅lgEB/N0≈7.8dB..
Definition: Als Codiergewinn einer Systemkonfiguration (gekennzeichnet durch seinen Code und die Art der Decodierung) bezeichnen wir das gegenüber dem Vergleichssystem (ohne Codierung) kleinere 10⋅lgEB/N0, das für eine vorgegebene Bitfehlerrate (BER) erforderlich ist:
- GCode(System|BER)=10⋅lgEB/N0(ohneCodierung|BER)−10⋅lgEB/N0(System|BER).
Angewendet auf obige Grafik erhält man:
GCode(Hamming(7,4,3),ML−HD|BER=10−5)=0.4dB,
GCode(Hamming(7,4,3),ML−SD|BER=10−5)=1.8dB.
Decodierung beim Binary Erasure Channel
Abschließend soll noch gezeigt werden, in wie weit der Decoder zu modifizieren ist, wenn anstelle des BSC–Modells (Binary Symmetrie Channel) das BEC–Kanalmodell (Binary Erasure Channel) zum Einsatz kommt, der keine Fehler produziert, sondern unsichere Bit als Auslöschungen markiert.
Beispiel 4: Ohne Einschränkung der Allgemeingültigkeit betrachten wir wie im Beispiel 3 wieder den systematischen (5, 2, 3)–Blockcode C={(0,0,0,0,0),(0,1,0,1,1),(1,0,1,1,0),(1,1,1,0,1)}
Nebenstehende Grafik zeigt das Systemmodell und gibt beispielhafte Werte für die einzelnen Vektoren wider.
- Der linke Bildteil (blau hinterlegt) gilt für das BSC–Modell mit einem Bitfehler 0→1 beim dritten Bit.
- Der rechte Bildteil (grün hinterlegt) gilt für das BEC–Modell und zeigt zwei Erasures 1→E bei Bit 2 und 4.
Man erkennt:
- Bei BSC kann wegen dmin=3nur ein Bitfehler korrigiert werden (t=1, rot markiert). Beschränkt man sich auf Fehlererkennung, so funktioniert diese bis zu e=dmin−1=2 Bitfehler.
- Bei BEC macht Fehlererkennung keinen Sinn, denn bereits der Kanal lokalisiert ein unsicheres Bit als Erasure E (Auslöschung). Die Nullen und Einsen im BEC–Empfangswort y_ sind sicher. Deshalb funktioniert hier die Fehlerkorrektur bis zu e=2 Auslöschungen mit Sicherheit.
- Auch e=3 Auslöschungen sind manchmal noch korrigierbar. So kann y_=(E,E,E,1,1) zu z_=(0,1,0,1,1) korrigiert werden, da kein zweites Codewort mit zwei Einsen endet. Dagegen ist y_=(0,E,0,E,E) aufgrund des im Code erlaubten Nullwortes nicht korrigierbar.
- Wird sichergestellt, dass in keinem Empfangswort mehr als zwei Auslöschungen vorkommen, so ist die BEC–Blockfehlerwahrscheinlichkeit Pr(z_≠x_)=Pr(v_≠u_)≡0. Dagegen hat die entsprechende Blockfehlerwahrscheinlichkeit beim BSC–Modell stets einen Wert größer als 0.
Da nach dem BEC ein jedes Empfangswort entweder richtig oder gar nicht decodiert wird, nennen wir hier den Block y_→z_ zukünftig „Codewortfinder”. Eine „Schätzung” findet nur beim BSC–Modell statt.
Wie funktioniert aber nun die Decodierung eines Empfangswortes y_ mit Auslöschungen algorithmisch?
Beispiel 5: Ausgehend vom Empfangswort y_=(0,E,0,E,1) im Beispiel 4 setzen wir den Ausgang des Codewortfinders formal zu z_=(0,z2,0,z4,1), wobei die Symbole z2∈{0,1} und z4∈{0,1} entsprechend folgender Gleichung zu bestimmen sind:
- z_⋅HT=0_⇒H⋅z_T=0_T.
Es geht nun darum, diese Bestimmungsgleichung möglichst effizient umzusetzen. Es ergeben sich folgende Rechenschritte:
- Mit der Prüfmatrix H des (5, 2, 3)–Blockcodes und dem Vektor z_=(0,z2,0,z4,1) lautet die obige Bestimmungsgleichung:
- H⋅z_T=(101001101001001)⋅(0z20z41)=(000).
- Wir fassen die sicheren (korrekten) Bit zum Vektor z_K zusammen und die ausgelöschten Bit zum Vektor z_E. Dann teilen wir die Prüfmatrix H in die entsprechenden Teilmatrizen HK und HE auf:
- z_K=(0,0,1),HK=(110100001)⇒Spalten1,3und5derPr¨ufmatrix,
- z_E=(z2,z4),HE=(001110)⇒Spalten2und4derPr¨ufmatrix.
- Unter Berücksichtigung der Tatsache, dass in GF(2) die Subtraktion gleich der Addition ist, lässt sich die obige Gleichung wie folgt darstellen:
- HK⋅z_TK+HE⋅z_TE=0_T⇒HE⋅z_TE=HK⋅z_TK⇒(001110)⋅(z2z4)=(110100001)⋅(001)=(001).
- Dies führt zu einem linearen Gleichungssystem mit zwei Gleichungen für die unbekannten z2 und z4 (jeweils 0 oder 1). Aus der letzten Zeile folgt z2=1 und aus der zweiten Zeile z2+z4=0 ⇒ z4=1. Damit ergibt sich das zulässige Codewort z_=(0,1,0,1,1).
Aufgaben zum Kapitel
Aufgabe 1.11: Syndromdecodierung
Aufgabe 1.11Z: Nochmals Syndromdecodierung
Aufgabe 1.12: Hard Decision vs. Soft_Decision
Aufgabe 1.12Z: Vergleich von HC (7, 4, 3) und HC (8, 4, 4)
Aufgabe 1.13: Decodierung beim binären Auslöschungskanal (BEC)
Aufgabe 1.13Z: Nochmals BEC–Decodierung