Kanalcodierung/Fehlerkorrektur nach Reed–Solomon–Codierung

1. Kanalcodierung
2. Reed–Solomon–Codes und deren Decodierung
3. Fehlerkorrektur nach Reed–Solomon–Codierung

• Vorherige Seite
• Nächste Seite

• Vorherige Seite
• Nächste Seite

Blockschaltbild und Voraussetzungen zu Kapitel 2.5

Wie im Kapitel 2.4 betrachten wir ein Übertragungssystem mit Reed–Solomon–Codierung, das durch die beiden Codeparameter n = 2^m – 1 und k gekennzeichnet ist. Mit der Generatormatrix G lautet der Zusammenhang zwischen dem Informationswort u und dem Codewort c:

\[\underline {c} = {\rm enc}(\underline {u}) = \underline {u} \cdot { \boldsymbol{\rm G}} \hspace{0.3cm} {\rm mit} \hspace{0.3cm}\underline {u} = (u_0, u_1, ... \hspace{0.05cm}, u_i, ...\hspace{0.05cm}, u_{k-1})\hspace{0.05cm}, \hspace{0.2cm} \underline {c} = (c_0, c_1, ... \hspace{0.05cm}, c_i, ...\hspace{0.05cm}, c_{n-1}) \hspace{0.05cm}.\]

Sowohl die Informationssymbole u_i als auch die Codesymbole c_i entstammen dem Körper GF(q) mit q = n + 1 = 2^m, und sind somit durch m Binärsymbole (Bit) darstellbar.

Ein Vergleich dieses Blockschaltbildes mit dem entsprechenden Modell zu Kapitel 2.4 zeigt:

• Der wesentliche Unterschied liegt im verwendeten diskreten Kanalmodell (grün hinterlegt). Anstelle des Auslöschungskanals („m–BEC”) wird nun der m–BSC betrachtet. Für jedes einzelne Bit des Codesymbols c_i wird der Binary Symmetric Channel (BSC) angewandt. Ist auch nur ein Bit innerhalb des Codesymbols verfälscht, so ist y_i ≠ c_i.
  

• Im Kapitel 2.4 sind unsichere Bit bereits durch Auslöschungen E (Erasures) markiert. Aufgabe des Codewortfinders (CWF) ist es deshalb, aus dem verstümmelten Empfangswort y das Decodierergebnis z zu rekonstruieren. Ist die Anzahl e der Auslöschungen kleiner als die minimale Distanz d_min, so gelingt dies und man erhält z = c. Andernfalls meldet der CWF, dass er das aktuelle Empfangswort y nicht decodieren kann. Eine Fehlentscheidung (z ≠ c) ist ausgeschlossen.
  

• In diesem Kapitel wird nun der erste Decoderblock als Codewortschätzer (CWS) bezeichnet. Die Namensgebung soll deutlich machen, dass aufgrund des m–BSC–Modells Fehlentscheidungen (z ≠ c) unvermeidlich sind, nämlich dann, wenn durch mehrere Symbolfehler das Empfangswort y zu einem gültigen Codewort verfälscht wurde.
  
  

Aufgabe des Decoders ist es, seinen Ausgangsvektor υ so zu bestimmen, dass er „möglichst gut” mit dem Informationswort u übereinstimmt. Oder etwas genauer formuliert:

\[{ \rm Pr(Blockfehler)} = { \rm Pr}( \underline{\upsilon} \ne \underline{u}) \stackrel{!}{=} { \rm Minimum}\hspace{0.05cm}.\]

Aufgrund des deterministischen Mappings c = enc(u) und υ = enc^–1(z) gilt in gleicher Weise:

\[{ \rm Pr(Blockfehler)} = { \rm Pr}( \underline{z} \ne \underline{c}) \stackrel{!}{=} { \rm Minimum}\hspace{0.05cm}.\]

Deshalb werden im Folgenden die zwei gelb hinterlegten Blöcke nicht weiter betrachtet. Im Mittelpunkt der Betrachtungen steht vielmehr der rot hinterlegte Codewortschätzer (CWS).

Mögliche Codewortschätzer: HD–MLD bzw. BDD (1)

Die rechte Skizze der nachfolgenden Grafik verdeutlicht nochmals die Aufgabenstellung, wobei hier das Kanalmodell „m–BSC” durch den additiven Fehlervektor e = y – c ersetzt ist. Die linke Skizze verdeutlicht den Zusammenhang zwischen diesen drei Vektoren.

Diese Aufgabenstellung soll durch ein Beispiel verdeutlicht werden.

:

Alle nachfolgend genannten Symbole sind Elemente von GF(2³) = {0, 1, α¹, α², α³, α⁴, α⁵, α⁶}. Zur Umrechnung zwischen der Koeffizientendarstellung (mit der Reihenfolge k₂, k₁, k₀) und der Exponentendarstellung (als Potenzen des primitiven Elements α) kann die nebenstehende Tabelle verwendet werden.

Codewort und Empfangswort lauten in Koeffizientendarstellung:

\[\underline{c} \hspace{-0.15cm} = \hspace{-0.15cm} \Big ( (010), (001), (100),(010),(100),(111),(111)\Big )\hspace{0.05cm},\] \[\underline{y} \hspace{-0.15cm} = \hspace{-0.15cm} \Big ( (011), (001), (000),(010),(100),(111),(111)\Big )\hspace{0.05cm}.\]

Damit ergibt sich für den Fehlervektor e = y – c:

\[\underline{e} \hspace{0.05cm} = \hspace{0.05cm} \Big ( (001), (000), (100), (000),(000),(000),(000)\Big )\hspace{0.05cm}.\]

Umgewandelt in die Exponentendarstellung erhält man:

\[\underline{c} \hspace{-0.15cm} = \hspace{-0.15cm} \Big ( \alpha^1, 1, \alpha^2,\alpha^1,\alpha^2,\alpha^5,\alpha^5\Big )\hspace{0.05cm},\]

\[\underline{y} \hspace{-0.15cm} = \hspace{-0.15cm} \Big ( \alpha^3, 1, \hspace{0.09cm}0\hspace{0.09cm},\alpha^1,\alpha^2,\alpha^5,\alpha^5\Big ) \hspace{0.3cm} \Rightarrow \hspace{0.3cm}\underline{e} = \Big ( \hspace{0.05cm}1, \hspace{0.05cm}0, \hspace{0.05cm}\alpha^2,\hspace{0.05cm}0,\hspace{0.05cm}0,\hspace{0.05cm}0,\hspace{0.05cm}0\hspace{0.05cm}\Big )\hspace{0.05cm}.\]

Aufgabe des Codewortschätzers (CWS) ist es, das zu y wahrscheinlichste Codewort c_i zu finden und sein Ergebnis z = c_i an das nachfolgende Mapping weiterzugeben. Es gibt verschiedene Möglichkeiten:

• Hard Decision Maximum Likelihood Decoding (HD–MLD),
  

• Bounded Distance Decoding (BDD),
  

• Decodierung über die halbe Mindestdistanz.
  
  

Diese Decodierprinzipien werden auf der nächsten Seite ausführlicher behandelt.

Mögliche Codewortschätzer: HD–MLD bzw. BDD (2)

Aufgabe des Codewortschätzers (CWS) ist es, das zu y wahrscheinlichste Codewort c_i zu finden und sein Ergebnis z = c_i weiterzugeben. Hierfür gibt es mehrere Möglichkeiten:

Hard Decision Maximum Likelihood Decoding (HD–MLD):

Man wählt von allen möglichen Reed–Solomon–Codeworten c_i (hiervon gibt es insgesamt q^k) dasjenige mit der geringsten Hamming–Distanz zum Empfangswort y aus. Somit lautet das Ergebnis:

\[\underline{z} = {\rm arg} \min_{\underline{x}_{\hspace{0.03cm}i} \hspace{0.05cm} \in \hspace{0.05cm} \mathcal{C}_{\rm RS}} \hspace{0.1cm} d_{\rm H}(\underline{y} \hspace{0.05cm}, \hspace{0.1cm}\underline{c}_{\hspace{0.03cm}i})\hspace{0.05cm}.\]

Die Entscheidung passiert hier auf der maximalen Rückschlusswahrscheinlichkeit Pr(c_i | y) und führt zum bestmöglichen Ergebnis. Näheres siehe Kapitel 1.2. Es wird stets entschieden, selbst wenn die Anzahl r der Symbolfehler größer ist als die Korrekturfähigkeit t des Codes. In einem solchen Fall ist allerdings das Decodierergebnis sehr unsicher.

Es sei nochmals erwähnt, dass bei ML–Decodierung immer entschieden wird. Ein Decodierversagen ist ausgeschlossen. Aber natürlich gibt es auch falsche Entscheidungen.

Bounded Distance Decoding (BDD):

Falls die Anzahl r der Symbolfehler im Empfangswort y nicht größer ist als die Korrekturfähigkeit t = ⌊(d_min – 1)/2⌋ des Codes, kann man die r Symbolfehler vollständig korrigieren. Der Fall r > t führt zu einem Abbruch des Decodiervorgangs ohne Ergebnis. Anders ausgedrückt: Es werden nur diejenigen Empfangsworte zum Kugelmittelpunkt decodiert, die in einer Kugel um diesen mit Radius t liegen. Andere werden als undecodierbar markiert, zum Beispiel als Erasure.

Decodierung über die halbe Mindestdistanz:

Hier wird auch im Fall r > t versucht, das Codewort zu decodieren. Im Gegensatz zu HD–MLD, das ebenfalls über die halbe Mindestdistanz hinaus decodiert, ist hier aber ein Decodierversagen nicht per se ausgeschlossen.

Für den Rest dieses Kapitels beschäftigen wir uns ausschließlich mit Bounded Distance Decoding. Der Grund hierfür ist die enorme Komplexität der Maximum Likelihood Detection proportional zu q^n–k.

Vorgehensweise beim „Bounded Distance Decoding”

Im Folgenden werden die einzelnen Schritte des BDD–Algorithmuses kurz und rezeptartig beschrieben. Auf den nächsten Seiten werden dann die einzelnen Punkte genauer behandelt und die Vorgehensweise an typischen Beispielen verdeutlicht.

(A) Berechne das Syndrom s = y · H^T:

• Ergibt sich aus dem Empfangswort y und der Prüfmatrix H des Codes das Syndrom s = 0, so setze den BDD–Ausgang z = y und beende den Decodiervorgang für dieses Empfangswort.
  

• Andernfalls setze den Parameter r = 1 und mache mit Schritt (B) weiter.
  
  

(B) Bestimme die tatsächliche Symbolfehleranzahl r:

• Erstelle und überprüfe die Gleichungen Λ_l · s^T = 0 für l = 1, ..., 2t–r unter der Annahme, dass das Empfangswort genau r Symbolfehler beinhaltet.
  

• Λ_l bezeichnet die verallgemeinerten ELP–Koeffizientenvektoren und t die Korrekturfähigkeit des Codes. Für die Reed–Solomon–Codes gilt einheitlich t = ⌊(n – k)/2⌋.
  

• Gibt es eine eindeutige Lösung, dann mache mit Schritt (C) weiter. Im Empfangsvektor y sind dann tatsächlich genau r Symbole verfälscht und im Fehlervektor e gibt es r Einträge ungleich 0.
  

• Andernfalls erhöhe r um 1. Falls r ≤ t, dann wiederhole Schritt (B) von Beginn an: Das bisher angenommene r war offensichtlich zu klein. Deshalb nun ein neuer Versuch mit größerem r.
  

• Ist das neue r größer als die Korrekturfähigkeit t des Codes, so kann das aktuelle Empfangswort nicht decodiert werden. Beende den Decodierversuch mit einer Fehlermeldung.
  
  

(C) Lokalisiere die r Fehlerpositionen:

• Erstelle das Error Locator Polynom Λ(x) und finde dessen r Nullstellen in GF(q) \ {0}.
  

• Ein Fehler an der Stelle i liegt immer dann vor, wenn Λ(αⁱ) = 0 ist.
  
  

(D) Bestimme die r Fehlerwerte e_i ≠ 0:

• Bekannt sind die r Fehlerstellen. Ersetzt man im Empfangsvektor y die falschen Symbole durch Auslöschungen  ⇒  y_i = E, falls e_i ≠ 0, so findet man das Ergebnis z entsprechend Kapitel 2.4.
  

• Eine Alternative: Aus der Gleichung e · H^T = s kommt man unter Ausnutzung der fehlerfreien Stellen (e_i = 0) zu einem linearen Gleichungssystem für die fehlerhaften Symbole (e_i ≠ 0).