Fehlerkorrektur nach Reed–Solomon–Codierung

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.