Error Correction According to Reed-Solomon Coding

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).