Quelltext der Seite Kanalcodierung/Fehlerkorrektur nach Reed–Solomon–Codierung

 
{{Header
|Untermenü=Reed–Solomon–Codes und deren Decodierung
|Vorherige Seite=Reed–Solomon–Decodierung beim Auslöschungskanal
|Nächste Seite=Fehlerwahrscheinlichkeit und Anwendungsgebiete
}}

== Blockschaltbild und Voraussetzungen zur RS&ndash;Fehlerkorrektur ==
<br>
Wie im Kapitel [[Kanalcodierung/Reed–Solomon–Decodierung_beim_Auslöschungskanal#Blockschaltbild_und_Voraussetzungen_zur_RS.E2.80.93Fehlererkennung|Decodierung beim Auslöschungskanal]] betrachten wir ein Übertragungssystem mit Reed&ndash;Solomon&ndash;Codierung, das durch die beiden Codeparameter $n=2^m-1$ und $k$ gekennzeichnet  ist. Mit der Generatormatrix $\boldsymbol{\rm G}$ lautet der Zusammenhang zwischen dem Informationswort $\underline {u}$ und dem Codewort  $\underline {c}$:

::<math>\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}\text{...} \hspace{0.05cm}, u_i, \hspace{0.05cm}\text{...} \hspace{0.05cm}, u_{k-1})\hspace{0.05cm}, \hspace{0.2cm} 
\underline {c} = (c_0, c_1, \hspace{0.05cm}\text{...}   \hspace{0.05cm}, c_i, \hspace{0.05cm}\text{...} \hspace{0.05cm}, c_{n-1})
\hspace{0.05cm}.</math>

Sowohl die Informationssymbole $u_i$ als auch die Codesymbole $C_i$ entstammen dem Körper ${\rm GF}(q)$ mit $q=n+1=2^m$, und sind somit durch $m$ Binärsymbole (Bit) darstellbar.<br>

[[Datei:P ID2545 KC T 2 5 S1 v2.png|center|frame|Übertragungssystem mit Reed–Solomon–Codierung/Decodierung und <i>m</i>–BSC|class=fit]]

Ein Vergleich dieses Blockschaltbildes mit dem entsprechenden [[Kanalcodierung/Reed–Solomon–Decodierung_beim_Auslöschungskanal#Blockschaltbild_und_Voraussetzungen_zur_RS.E2.80.93Fehlererkennung|Blockschaltbild zur RS&ndash;Fehlererkennung]] zeigt:
*Der wesentliche Unterschied liegt im verwendeten diskreten Kanalmodell (grün hinterlegt). Anstelle des Auslöschungskanals (&bdquo;$m$&ndash;BEC&rdquo;) wird nun der $m$&ndash;BSC betrachtet. Für jedes einzelne Bit des Codesymbols $c_i$ wird der [[Kanalcodierung/Kanalmodelle_und_Entscheiderstrukturen#Binary_Symmetric_Channel_.E2.80.93_BSC| ''Binary Symmetric Channel'']] (BSC) angewandt. Ein Bitfehler bezüglich des $i$&ndash;Bits  ergibt $y_i \ne c_i$.<br>

*Im [[Kanalcodierung/Reed–Solomon–Decodierung_beim_Auslöschungskanal|letzten Kapitel]] waren unsichere Bits bereits durch Auslöschungen $\rm E$ (<i>Erasures</i>) markiert. Aufgabe des <i>Codewortfinders</i> $\rm (CWF)$ war es deshalb, aus dem verstümmelten Empfangswort $\underline {y}$ das Decodierergebnis $\underline {z}$ zu rekonstruieren. Ist dabei die Anzahl $e$ der Auslöschungen kleiner als die minimale Distanz  $d_{\rm min}$, so gelingt dies und man erhält $\underline {z} = \underline {c}$. Andernfalls meldet der Codewortfinder, dass er das aktuelle Empfangswort $\underline {y}$ nicht decodieren kann. Eine Fehlentscheidung $(\underline {z} \ne \underline {c})$ ist ausgeschlossen.<br>

*In diesem Kapitel wird nun der erste Decoderblock als <i>Codewortschätzer</i>&nbsp; $\rm (CWS)$ bezeichnet. Die Namensgebung soll deutlich machen, dass aufgrund des $m$&ndash;BSC&ndash;Modells Fehlentscheidungen $(\underline {z} \ne \underline {c})$ unvermeidlich sind, nämlich dann, wenn durch mehrere Symbolfehler das Empfangswort $\underline {y}$&nbsp; zu einem gültigen Codewort verfälscht wurde.<br><br>

{{BlaueBox|TEXT=  
$\text{Fazit:}$&nbsp;  Aufgabe des Decoders ist es, seinen Ausgangsvektor $\underline {v}$&nbsp; so zu bestimmen, dass er &bdquo;möglichst gut&rdquo; mit dem Informationswort $\underline {u}$&nbsp; übereinstimmt. Oder etwas genauer formuliert:

::<math>{ \rm Pr(Blockfehler)} = { \rm Pr}( \underline{\upsilon} \ne \underline{u}) \stackrel{!}{=} { \rm Minimum}\hspace{0.05cm}.</math>

Aufgrund des deterministischen Mappings $\underline{c} = {\rm enc}(\underline{u})$ und $\underline{v} = {\rm enc}^{-1}(\underline{z})$ gilt in gleicher Weise:

::<math>{ \rm Pr(Blockfehler)} = { \rm Pr}( \underline{z} \ne \underline{c}) \stackrel{!}{=} { \rm Minimum}\hspace{0.05cm}.</math>}}


Deshalb werden im Folgenden die zwei gelb hinterlegten Blöcke nicht weiter betrachtet.  Im Mittelpunkt der Betrachtungen steht vielmehr der rot hinterlegte <i>Codewortschätzer</i>&nbsp; $\rm (CWS)$.<br>

== Mögliche Codewortschätzer für die RS&ndash;Decodierung ==
<br>
Die rechte Skizze der nachfolgenden Grafik verdeutlicht nochmals die Aufgabenstellung, wobei hier das Kanalmodell &bdquo;$m$&ndash;BSC&rdquo; durch den additiven '''Fehlervektor'''  $\underline{e} = \underline{y} - \underline{c}$ ersetzt ist. Die linke Skizze verdeutlicht den Zusammenhang zwischen diesen drei Vektoren.<br>

[[Datei:P ID2546 KC T 2 5 S2 v2.png|center|frame|Zur Definition des Fehlervektors $\underline{e}$|class=fit]]

Diese Aufgabenstellung soll durch ein Beispiel verdeutlicht werden.<br>

[[Datei:P ID2547 KC T 2 5 Darstellung v1.png|right|frame|Drei Darstellungsformen für $\rm GF(2^3)$]] 
{{GraueBox|TEXT=  
$\text{Beispiel 1:}$&nbsp;  
Alle Symbole seien Elemente von $\rm GF(2^3) \in  \{0, 1, \alpha^1, \alpha^2, \alpha^3, \alpha^4, \alpha^5, \alpha^6\}$. Zur Umrechnung  
*zwischen der Koeffizientendarstellung (mit der Reihenfolge $k_2$, $k_1$, $k_0$) 
* und der Exponentendarstellung (als Potenzen des primitiven Elements $\alpha$) 


kann die nebenstehende Tabelle verwendet werden.<br>

Codewort und Empfangswort lauten in diesem Beispiel in Koeffizientendarstellung:

::<math>\underline{c} = \Big ( (010), (001), (100),(010),(100),(111),(111)\Big )\hspace{0.05cm},</math>
::<math>\underline{y} =\Big ( (011), (001), (000),(010),(100),(111),(111)\Big )\hspace{0.05cm}.</math>

Damit ergibt sich für den Fehlervektor $\underline{e} = \underline{y} - \underline{c}$:

::<math>\underline{e} \hspace{0.05cm} = \hspace{0.05cm} \Big ( (001), (000), (100), (000),(000),(000),(000)\Big )\hspace{0.05cm}.</math>

Umgewandelt in die Exponentendarstellung erhält man:

::<math>\underline{c} = \Big ( \alpha^1, \hspace{0.09cm}1\hspace{0.09cm}, \alpha^2,\alpha^1,\alpha^2,\alpha^5,\alpha^5\Big )\hspace{0.05cm},</math>
::<math>\underline{y} =\Big ( \alpha^3, \hspace{0.09cm}1\hspace{0.09cm}, \hspace{0.09cm}0\hspace{0.09cm},\alpha^1,\alpha^2,\alpha^5,\alpha^5\Big )\hspace{0.05cm},</math>
::<math>\underline{e} = \Big ( \hspace{0.09cm}1\hspace{0.09cm}, \hspace{0.09cm}0\hspace{0.09cm}, \hspace{0.05cm}\alpha^2,\hspace{0.12cm}0\hspace{0.12cm},\hspace{0.12cm}0\hspace{0.12cm},\hspace{0.12cm}0\hspace{0.12cm},\hspace{0.12cm}0\hspace{0.12cm}\Big )\hspace{0.05cm}.</math>}}<br>

Aufgabe des Codewortschätzers $\rm (CWS)$ ist es, das zu $\underline{y}$&nbsp; wahrscheinlichste Codewort $\underline{c}_i$ zu finden und sein Ergebnis $\underline{z} = \underline{c}_i$ an das nachfolgende Mapping weiterzugeben. Es gibt verschiedene Möglichkeiten:
*<i>Hard Decision Maximum Likelihood Decoding</i>&nbsp;  $\text{(HD&ndash;MLD)}$,<br>

*<i>Bounded Distance Decoding</i>&nbsp; $\text{(BDD)}$,<br>

*Decodierung ''über die halbe Mindestdistanz''.<br><br>

Diese Decodierprinzipien werden im Folgenden beschrieben.<br>


<b>Hard Decision Maximum Likelihood Decoding (HD&ndash;MLD):</b><br>

Man wählt von allen möglichen Reed&ndash;Solomon&ndash;Codeworten $\underline{c}_i$ (hiervon gibt es insgesamt $q^k$) dasjenige mit der geringsten [[Kanalcodierung/Zielsetzung_der_Kanalcodierung#Einige_wichtige_Definitionen_zur_Blockcodierung| Hamming&ndash;Distanz]] zum Empfangswort $\underline{y}$&nbsp; aus. Somit lautet das Ergebnis:

::<math>\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}.</math>

Die Entscheidung passiert hier auf der maximalen Rückschlusswahrscheinlichkeit ${\rm Pr}(\underline{c}_i\hspace{0.05cm}|\hspace{0.05cm}\underline{y})$ und führt zum bestmöglichen Ergebnis. Näheres siehe [[Kanalcodierung/Klassifizierung_von_Signalen#ML.E2.80.93Entscheidung_beim_BSC.E2.80.93Kanal| ML&ndash;Entscheidung beim BSC&ndash;Kanal]]. 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.<br>

*Es sei nochmals erwähnt, dass bei Maximum&ndash;Likelihood&ndash;Decodierung immer entschieden wird. 
*Ein Decodierversagen ist ausgeschlossen. 
*Aber natürlich gibt es auch falsche Entscheidungen.<br><br>


<b>Bounded Distance Decoding (BDD):</b><br>

Falls die Anzahl $r$ der Symbolfehler im Empfangswort $\underline{y}$&nbsp; nicht größer ist als die Korrekturfähigkeit $t = &lfloor;(d_{\rm min}- 1)/2&rfloor;$ des Codes, kann man die $r$ Symbolfehler vollständig korrigieren. Allerdings gilt auch:
*Der Fall $r > t$ führt zu einem Abbruch des Decodiervorgangs ohne Ergebnis. Anders ausgedrückt:  
*Es werden nur diejenigen Empfangsworte zum Kugelmittelpunkt hin decodiert, die in einer Kugel um diesen mit Radius $t$ liegen. 
*Andere  Empfangsworte werden als undecodierbar markiert, zum Beispiel als <i>Erasure</i>.<br><br>


<b>Decodierung über die halbe Mindestdistanz</b>:<br>

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

Für den Rest dieses Kapitels beschäftigen wir uns ausschließlich mit <i>Bounded Distance Decoding</i>. Der Grund hierfür ist die enorme Komplexität der <i>Maximum Likelihood Decoding</i> proportional zu $q^{n-k}$.<br>

== Vorgehensweise beim „Bounded Distance Decoding” ==
<br>
Im Folgenden werden die einzelnen Schritte des BDD&ndash;Algorithmuses kurz und rezeptartig beschrieben. Auf den nächsten Seiten werden dann die einzelnen Punkte genauer behandelt und die Vorgehensweise an typischen Beispielen verdeutlicht.<br>


'''(A)'''&nbsp; '''Berechnung und Auswertung des Syndroms''' &nbsp; &rArr; &nbsp; [[Kanalcodierung/Fehlerkorrektur_nach_Reed–Solomon–Codierung#Schritt_.28A.29:_Auswertung_des_Syndroms_beim_BDD|Detaillierte Beschreibung]]
*Berechne aus dem Empfangswort $\underline{y}$&nbsp; und der Prüfmatrix $\boldsymbol{\rm H }$ des Codes das Syndrom $\underline {s} = \underline {y}  \cdot  \boldsymbol{\rm H }^{\rm T}$. 
*Ergibt sich $\underline {s} =\underline {0}$, so setze den BDD&ndash;Ausgang $\underline {z} =\underline {y}$&nbsp; und beende den Decodiervorgang für dieses Empfangswort.<br>
*Andernfalls setze den Parameter $r = 1$ und mache mit Schritt '''(B)''' weiter.<br><br>


'''(B)'''&nbsp; '''Bestimmung der tatsächlichen Symbolfehleranzahl <i>r</i>'''&nbsp; &rArr; &nbsp; [[Kanalcodierung/Fehlerkorrektur_nach_Reed–Solomon–Codierung#Schritt_.28B.29:_Aufstellen.2FAuswerten_des_ELP.E2.80.93Koeffizientenvektors|Detaillierte Beschreibung]]
*Erstelle und überprüfe die Gleichungen $\underline {\it \Lambda} _l \cdot\underline {s}^{\rm T} = 0$ für $l = 1,$ ... , $2 \cdot t -r$ unter der Annahme, dass das Empfangswort genau $r$ Symbolfehler beinhaltet.<br>

*$\underline {\it \Lambda} _l $ bezeichnet die verallgemeinerten ELP&ndash;Koeffizientenvektoren, wobei &bdquo;ELP&rdquo; für [[Kanalcodierung/Fehlerkorrektur_nach_Reed–Solomon–Codierung#Error_Locator_Polynom_.E2.80.93_Definition_und_Eigenschaften|Error Locator Polynom]] steht, und $t$ die Korrekturfähigkeit des Codes. Für die Reed&ndash;Solomon&ndash;Codes gilt einheitlich $t = &lfloor;(n-k)/2 &rfloor;$.<br>

*Gibt es eine eindeutige Lösung, dann mache mit Schritt '''(C)''' weiter. Im Empfangsvektor $\underline{y}$&nbsp; sind dann tatsächlich genau $r$ Symbole verfälscht und im Fehlervektor $\underline{e}$ gibt es $r$ Einträge ungleich $0$.<br>

*Andernfalls erhöhe $r$ um $1$. Falls $r &#8804; t$, dann wiederhole Schritt '''(B)''' von Beginn an: &nbsp;Das bisher angenommene $r$ war offensichtlich zu klein. Deshalb nun ein neuer Versuch mit größerem $r$.<br>

*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''.<br><br>


'''(C)'''&nbsp; '''Lokalisierung der <i>r</i>&nbsp; Fehlerpositionen'''&nbsp; &rArr; &nbsp; [[Kanalcodierung/Fehlerkorrektur_nach_Reed–Solomon–Codierung#Schritt_.28C.29:_Lokalisierung_der_Fehlerstellen|Detaillierte Beschreibung]]
*Erstelle das <i>Error Locator Polynom</i> ${\it \Lambda}(x)$ und finde dessen $r$ Nullstellen in ${\rm GF}(q) \hspace{-0.05cm}\setminus \hspace{-0.05cm} \{0\}$.<br>

*Ein Fehler an der Stelle $i$ liegt immer dann vor, wenn ${\it \Lambda}(\alpha^{i}) = 0$ ist.<br><br>


'''(D)'''&nbsp; '''Bestimmung der <i>r</i>&nbsp;  Fehlerwerte und Korrektur'''&nbsp; &rArr; &nbsp; [[Kanalcodierung/Fehlerkorrektur_nach_Reed–Solomon–Codierung#Schritt_.28D.29:_Abschlie.C3.9Fende_Fehlerkorrektur|Detaillierte Beschreibung]]
*Bekannt sind nun die $r$ Fehlerstellen. Ersetzt man im Empfangsvektor $\underline{y}$&nbsp; die falschen Symbole durch Auslöschungen &nbsp; &#8658; &nbsp; $y_i = \rm E$, falls $e_i &ne; 0$, so findet man das Ergebnis $\underline{y}$&nbsp; entsprechend dem Kapitel [[Kanalcodierung/Reed–Solomon–Decodierung_beim_Auslöschungskanal|Reed–Solomon–Decodierung beim Auslöschungskanal]].<br>

*Eine Alternative: Aus der Gleichung $\underline {e}  \cdot  \boldsymbol{\rm H }^{\rm T}  \underline {s}$kommt man unter Ausnutzung der fehlerfreien Stellen $(e_i = 0)$ zu einem linearen Gleichungssystem für die fehlerhaften Symbole $(e_i \ne 0)$.<br><br>

== Schritt (A): Auswertung des Syndroms beim BDD ==
<br>
Wie im Abschnitt [[Kanalcodierung/Decodierung_linearer_Blockcodes#Prinzip_der_Syndromdecodierung|Prinzip der Syndromdecodierung]] gezeigt, kann zur Decodierung eines linearen Codes das Syndrom  $\underline{s}$ herangezogen werden. Mit dem Empfangswort $\underline{y}$ gleich Codewort $\underline{c}$  plus Fehlervektor $\underline{e}$ gilt:

::<math>\underline {s} = \underline {y}  \cdot { \boldsymbol{\rm H }}^{\rm T}= 
\underline {c}  \cdot { \boldsymbol{\rm H }}^{\rm T}+
\underline {e}  \cdot { \boldsymbol{\rm H }}^{\rm T}
\hspace{0.05cm}.</math>

Da stets $\underline {c}  \cdot { \boldsymbol{\rm H }}^{\rm T} =\underline {0}$ gilt, folgt aus $\underline{s}= \underline{0}$ auch $\underline {e}  \cdot { \boldsymbol{\rm H }}^{\rm T} =\underline {0}$. Das heißt:
*Mit sehr großer Wahrscheinlichkeit kann aus $\underline{s}= \underline{0}$ auch auf $\underline{e}= \underline{0}$und damit auch auf das richtige Decodierergebnis $\underline{z}= \underline{y}$ geschlossen werden. Der Decodiervorgang wäre damit abgeschlossen.<br>

*Es gibt aber auch Fehlermuster $\underline{e} \ne \underline{0}$, die zum Syndrom $\underline{s}= \underline{0}$ führen. Solche Muster beinhalten sicher mehr als $t$ Symbolfehler, so dass auch hier der Abbruch des Decodiervorgangs sinnvoll ist. Alle nachfolgenden Berechnungen würden auch nicht zum Erfolg führen.<br><br>

[[Datei:P ID2548 KC T 2 5 Darstellung v1.png|right|frame||Drei Darstellunsformen für $\rm GF(2^3)$]] 
{{GraueBox|TEXT=  
$\text{Beispiel 2:}$&nbsp;   
Diesem und den folgenden Beispielen auf den nächsten Seiten liegt stets der Reed&ndash;Solomon&ndash;Code '''RS (7, 3, 5)<sub>8</sub>''' zugrunde, so dass die in der Grafik angegebenen Umrechnungen in $\rm GF(2^3)$ genutzt werden können. Das Empfangswort lautet:

::<math>\underline{y}=\big (\alpha^3,\hspace{0.05cm} 1,\hspace{0.05cm} 0, \hspace{0.05cm}\alpha^1, \hspace{0.05cm} \alpha^2, \hspace{0.05cm} \alpha^5, \hspace{0.05cm} \alpha^5 \big).</math>

Mit der [[Kanalcodierung/Definition_und_Eigenschaften_von_Reed%E2%80%93Solomon%E2%80%93Codes#Generatormatrix_und_Pr.C3.BCfmatrix_.282.29| Prüfmatrix]] $\boldsymbol{\rm H }$ ergibt sich für das Syndrom:

::<math>\underline {s} = \underline {y}  \cdot { \boldsymbol{\rm H } }^{\rm T}= 
\begin{pmatrix}
		\alpha^3, \hspace{0.05cm}1, \hspace{0.05cm}0, \hspace{0.05cm}\alpha^1, \hspace{0.05cm}\alpha^2, \hspace{0.05cm}\alpha^5, \hspace{0.05cm}\alpha^5
\end{pmatrix}\cdot
\begin{pmatrix}
						1        & 1        & 1        & 1        \\
						\alpha^1 & \alpha^2 & \alpha^3 & \alpha^4 \\
						\alpha^2 & \alpha^4 & \alpha^6 & \alpha^1 \\
						\alpha^3 & \alpha^6 & \alpha^2 & \alpha^5 \\
						\alpha^4 & \alpha^1 & \alpha^5 & \alpha^2 \\
						\alpha^5 & \alpha^3 & \alpha^1 & \alpha^6 \\
						\alpha^6 & \alpha^5 & \alpha^4 & \alpha^3
					\end{pmatrix}  </math>
::<math>\Rightarrow  \hspace{0.3cm} \underline {s} = (\alpha^3 , \alpha^3 , \alpha^3 , \alpha^3) + (\alpha^1 , \alpha^2 , \alpha^3 , \alpha^4) + (0,0,0,0) + (\alpha^4,1,\alpha^3,\alpha^6)+(\alpha^6,\alpha^3,1,\alpha^4)+(\alpha^3,\alpha^1,\alpha^6,\alpha^4) + (\alpha^4,\alpha^3,\alpha^2,\alpha^1)</math>
::<math>\Rightarrow  \hspace{0.3cm} \underline {s} =  \text{...} \hspace{0.05cm}=
					(\alpha^5,\alpha^2,\alpha^3,\alpha^1)  \hspace{0.05cm}.</math>

Das Empfangswort wurde also verfälscht. Andernfalls hätte sich $\underline{e}= \underline{0} = (0, 0, 0, 0)$ ergeben müssen.<br>

Die Beschreibung des Decodiervorgangs beim RSC (7, 3, 5)<sub>8</sub> wird im [[Kanalcodierung/Fehlerkorrektur_nach_Reed–Solomon–Codierung#Schritt_.28B.29:_Aufstellen.2FAuswerten_des_ELP.E2.80.93Koeffizientenvektors|Koeffizientenvektors|Beispiel 4]] fortgesetzt.}}<br>

== Error Locator Polynom – Definition und Eigenschaften ==
<br>
Nach der Syndromberechnung im Schritt '''(A)''' mit dem Ergebnis $\underline{s} \ne \underline{0}$ wissen wir,
*dass das Empfangswort $\underline{y}$ nicht mit dem Codewort $\underline{c}$ übereinstimmt, bzw.<br>

*dass der Fehlervektor $\underline{e}  = (e_0, \hspace{0.05cm}e_1, \hspace{0.05cm}\text{ ...}\hspace{0.05cm} , e_{n-1})$ mit Sicherheit auch Elemente ungleich $0$ beinhaltet.<br><br>

Wir wissen allerdings nicht, wie viele Symbole verfälscht wurden$ (0 < r &#8804; n)$ und wir können auch nicht die Positionen der Fehlerstellen $(e_i &ne; 0)$ im Fehlervektor $\underline{c}$ benennen.<br>

Einen Lösungsansatz für diese Aufgabe bietet das <i>Error Locator Polynom</i>, das von [https://de.wikipedia.org/wiki/W._Wesley_Peterson William Wesley] Peterson eingeführt wurde. Siehe [Pet60]<ref name =''Pet60>Peterson, W.W: ''Encoding and Error-correction Procedures for the Bose-Chaudhuri codes.'' IRE Transactions on Information Theory , IT-6:459{470), 1960.</ref>. Im Deutschen ist hierfür auch der Begriff <i>Schlüsselgleichung</i> üblich.<br>

{{BlaueBox|TEXT=  
$\text{Definition:}$&nbsp;Es sei bekannt, dass genau $r$ Elemente des Fehlervektors $\underline{e}$ ungleich Null sind, erkennbar am [[Kanalcodierung/Zielsetzung_der_Kanalcodierung#Einige_wichtige_Definitionen_zur_Blockcodierung|Hamming&ndash;Gewicht]] $w_{\rm H}\underline{e} = r$ . Ebenfalls bekannt sei die Menge ${I}_{\rm FP}$ der Fehlerpositionen:

::<math>I_{\rm FP} = \{ i \hspace{0.1cm}\vert \hspace{0.1cm} e_i \ne 0,\hspace{0.1cm} 0 \le i < n \}\hspace{0.05cm}.</math>

Dann gilt für das '''Error Locator Polynom''' (ELP):

::<math>{\it \Lambda}(x)=x \cdot \prod_{i\hspace{0.05cm}\in \hspace{0.05cm} I_{\rm FP} }(x-\alpha^i) =x \cdot \big [{\it \lambda}_0 + \lambda_1 \cdot x+\ldots+{\it \lambda}_{r-1} \cdot x^{r-1}+x^r \big ].</math>}}<br>

Vom <i>Error Locator Polynom</i> wissen wir aufgrund der Definition:
*Wegen des Faktors $x$ vor dem Produktzeichen ist ${\it \Lambda}(x= 0) = 0$.<br>

*Weitere $r$ Nullstellen ergeben sich für $x =  \alpha^{i}$ mit $i \in I_{\rm FP}$, das heißt, für alle Fehlerpositionen.<br>

*Dagegen ergibt das <i>Error Locator Polynom</i> für $i &#8713; I_{\rm FP}$ &nbsp; &#8658; &nbsp; $e_i = 0$ keine Nullstelle: &nbsp; ${\it \Lambda}(x= \alpha^{i}) \ne0$.<br><br>

Wir suchen also die $r$ nichttrivialen Nullstellen von ${\it \Lambda}(x)$ mit dem Argument $x &#8712; {\rm GF}(q) \hspace{-0.05cm}\setminus \hspace{-0.05cm} \{0\}$. Gelingt uns dies, so kennen wir die $r$ Fehlerpositionen, jedoch noch nicht die tatsächlichen Fehlerwerte $e_i &#8712; {\rm GF}(q)$.<br>

[[Datei:P ID2549 KC T 2 5 Darstellung v1.png|right|frame||Drei Darstellunsformen für ${\rm GF}(2^3)$]] 
{{GraueBox|TEXT=  
$\text{Beispiel 3:}$&nbsp; 
Es gelte $n=7$ &nbsp; &#8658; &nbsp; $q=8$, $r=2$ und $I_{\rm FP}  = \{2, \hspace{0.05cm}4\}$:  &nbsp;[[Datei:P ID2551 KC T 2 5 S5a.png]]<br>

Damit erhält man für das <i>Error Locator Poynom</i> aus ${\rm GF}(2^3)$:

::<math>{\it \Lambda}(x)=x \cdot (x\hspace{-0.05cm}-\hspace{-0.05cm}\alpha^2) \cdot (x\hspace{-0.05cm}-\hspace{-0.05cm}\alpha^4)=  x \cdot (x\hspace{-0.05cm}+\hspace{-0.05cm}\alpha^2) \cdot (x\hspace{-0.05cm}+\hspace{-0.05cm}\alpha^4) =x \cdot \big [x^2 \hspace{-0.05cm}+ \hspace{-0.05cm}(\alpha^2 + \alpha^4) \cdot x + \alpha^6\big ] </math>
::<math>\Rightarrow	\hspace{0.3cm}  {\it \Lambda}(x)= x \cdot \big [\alpha^6 + \alpha \cdot x + x^2\big ]\hspace{0.05cm}.</math>

Die beiden Nullstellen (außer bei $x = 0$) ergeben sich hier natürlich für $x = \alpha^2$  und $x = \alpha^4$, wie die folgende Kontrollrechnung zeigt:

::<math>{\it \Lambda}(x = \alpha^2)= x \cdot \big [\alpha^6 + \alpha \cdot \alpha^2 + (\alpha^2)^2\big ] = x \cdot \big [\alpha^6 + \alpha^3 + \alpha^4  \big ]= 0\hspace{0.05cm},</math>
::<math>	 {\it \Lambda}(x = \alpha^4)= x \cdot \big [\alpha^6 + \alpha \cdot \alpha^4 + (\alpha^4)^2\big ] =x \cdot \big [\alpha^6 + \alpha^5 + \alpha \big ]= 0\hspace{0.05cm}.</math>}}<br>

<br>
Für die weitere Herleitung gehen wir stets vom <b>RSC (7, 3, 5)<sub>8</sub></b> mit den folgenden Parameterwerten aus: 

:$$n=7, \hspace{0.3cm}k = 3, \hspace{0.3cm}d_{\rm min} = 5 \ \Rightarrow   t = (d_{\rm min} -1/2) = 2.$$

Die Anzahl der Symbolfehler sei $r = t = 2$. Damit lautet das zu lösende Gleichungssystem mit den Hilfsgrößen $L_i = {\it \Lambda}(\alpha^{i})$:

::<math>L_0 = {\it \Lambda }(\alpha^0) = \alpha^0 \cdot \left [ {\it \lambda}_0 + {\it \lambda}_1 \cdot (\alpha^0)^1 + (\alpha^0)^2 \right ] = {\it \lambda}_0  \cdot 1 + {\it \lambda}_1 \cdot   1 + 1 \hspace{0.05cm},</math>
::<math>L_1 = {\it \Lambda }(\alpha^1) =\alpha^1 \cdot \left [ {\it \lambda}_0 + {\it \lambda}_1 \cdot (\alpha^1)^1 + (\alpha^1)^2 \right ] = {\it \lambda}_0 \cdot \alpha^1+ {\it \lambda}_1 \cdot \alpha^2 + \alpha^3 \hspace{0.05cm},</math>
:::::::::<math>...</math>
::<math> L_6 = {\it \Lambda }(\alpha^6) = \alpha^6 \cdot \left [ {\it \lambda}_0 + {\it \lambda}_1 \cdot (\alpha^6)^1 + (\alpha^6)^2 \right ] = {\it \lambda}_0 \cdot \alpha^6 + {\it \lambda}_1 \cdot \alpha^{12} + \alpha^{18} \hspace{0.05cm}.</math>

In Vektorform lautet dieses Gleichungssystem mit dem Hilfsvektor $\underline{L} = (L_0, \hspace{0.05cm}L_1, \hspace{0.05cm}L_2,\hspace{0.05cm}L_3,\hspace{0.05cm}L_4,\hspace{0.05cm}L_5,\hspace{0.05cm}L_6)$:

::<math>\underline {L}^{\rm T}=\begin{pmatrix}
		L_0\\
		L_1\\
		L_2\\
		L_3\\
		L_4\\
		L_5\\
		L_6
\end{pmatrix}
\hspace{0.15cm} = \hspace{0.15cm}
\begin{pmatrix}
		1 & 1 & 1  \\
		\alpha^1 & \alpha^2 & \alpha^3 \\
		\alpha^2 & \alpha^4 & \alpha^6 \\
		\alpha^3 & \alpha^6 & \alpha^9 \\
		\alpha^4 & \alpha^8 & \alpha^{12}\\
		\alpha^5 & \alpha^{10} & \alpha^{15}\\
		\alpha^6 & \alpha^{12} & \alpha^{18} 
\end{pmatrix}  \hspace{0.15cm}\cdot \hspace{0.15cm}
\begin{pmatrix}
		{\lambda}_0\\
		{\lambda}_1\\
		1 
\end{pmatrix} 		
\hspace{0.05cm}.</math>

Wir erweitern nun den ELP&ndash;Koeffizientenvektor $\underline {\it \Lambda }$ durch Anhängen von Nullen auf die Länge $n-k$. Im betrachteten Beispiel erhält man somit ${\it \Lambda } = ( \lambda_0,\hspace{0.05cm}\lambda_1,\hspace{0.05cm}1, \hspace{0.05cm}0)$ und folgende Vektorgleichung:

::<math>\underline {L}^{\rm T}
\hspace{0.15cm} = \hspace{0.15cm}
\begin{pmatrix}
		1 & 1 & 1 & 1 \\
		\alpha^1 & \alpha^2 & \alpha^3 & \alpha^4\\
		\alpha^2 & \alpha^4 & \alpha^6 & \alpha^8\\
		\alpha^3 & \alpha^6 & \alpha^9 & \alpha^{12}\\
		\alpha^4 & \alpha^8 & \alpha^{12} & \alpha^{16}\\
		\alpha^5 & \alpha^{10} & \alpha^{15} & \alpha^{20}\\
		\alpha^6 & \alpha^{12} & \alpha^{18} & \alpha^{24}
\end{pmatrix}  \hspace{0.15cm}\cdot \hspace{0.15cm}
\begin{pmatrix}
		{\lambda}_0\\
		{\lambda}_1\\
		1\\
		0 
\end{pmatrix} 		
\hspace{0.05cm}.</math>

Damit haben wir erreicht:
*Aus der $7&times 3$&ndash;Matrix wurde nun eine $7&times 4$&ndash;Matrix. 
*Die vierte Spalte kann eigentlich beliebig gefüllt werden, da alle Elemente mit Nullen multipliziert werden. 
*Durch die hier gewählte Ergänzung erhält man die transponierte [[Kanalcodierung/Definition_und_Eigenschaften_von_Reed%E2%80%93Solomon%E2%80%93Codes#Generatormatrix_und_Pr.C3.BCfmatrix_.282.29| Prüfmatrix]] des RSC (7, 3, 5)<sub>8</sub>.
* Somit kann man für die letzte Vektorgleichung schreiben:

::<math>\underline {L}^{\rm T} = { \boldsymbol{\rm H }}^{\rm T} \cdot \underline {\it \Lambda }^{\rm T}
 \hspace{0.3cm} \Rightarrow  \hspace{0.3cm}\underline {L} =	\underline {\it \Lambda } \cdot { \boldsymbol{\rm H }}
\hspace{0.05cm}.</math>

Da aber für die Fehlerstellen $(e_i &ne; 0)$ stets $L_i = {\it \Lambda}(\alpha^{i}) = 0$ gilt, ist das Produkt $L_i \cdot e_i \equiv 0$  und man erhält als Bestimmungsgleichung für die Nullstellen des <i>Error Locator Polynoms</i>:

::<math>\underline {L}^{\rm T}  \cdot \underline {e}^{\rm T} = 0  \hspace{0.3cm} \Rightarrow  \hspace{0.3cm}
\underline {\it \Lambda } \cdot { \boldsymbol{\rm H }} \cdot \underline {e}^{\rm T} = 0 \hspace{0.3cm} \Rightarrow  \hspace{0.3cm}
\underline {\it \Lambda }  \cdot \underline {s}^{\rm T} = 0 
\hspace{0.05cm}.</math>

{{BlaueBox|TEXT=  
$\text{Wichtiges Zwischenergebnis:}$&nbsp; 

Die ''nichttrivialen Nullstellen'' (ungleich 0) $\lambda_0$, $\lambda_1$,  ... des ''Error Locator Polynoms'' ${\it \Lambda}(x)$ müssen stets der Vektorgleichung  $\underline {\it \Lambda }  \cdot \underline {s}^{\rm T} = 0 $ genügen.
*Hierbei bezeichnet  $\underline {\it \Lambda }$ den ''ELP&ndash;Koeffizientenvektor'', und
* $\underline {s }  = \underline {y }\cdot  \boldsymbol{\rm H }^{\rm T} $ gibt das [[Kanalcodierung/Fehlerkorrektur_nach_Reed%E2%80%93Solomon%E2%80%93Codierung#Schritt_.28A.29:_Auswertung_des_Syndroms_beim_BDD| Syndrom]] an.}}<br>

== Schritt (B): Aufstellen/Auswerten des ELP–Koeffizientenvektors ==
<br>
Bevor wir dieses Zwischenergebnis  für den Schritt '''(B)''' berücksichtigen können, müssen noch einige Verallgemeinerungen vorgenommen werden. Der Grund hierfür ist:
*Die Gleichung $\underline {\it \Lambda }  \cdot \underline {s}^{\rm T} = 0 $ liefert nur eine einzige Bestimmungsgleichung. Damit kann das Problem für $r = 1$ gelöst werden, wenn man sicher ist, dass tatsächlich nur ein Symbol verfälscht wurde.<br>

*Ist man sich dessen nicht sicher, führt aber die Berechnung trotzdem für $r = 1$ durch, so  braucht man noch eine zweite Gleichung (oder auch mehrere), um die Annahme zu verifizieren.<br><br>

Die Eigenschaft des [[Kanalcodierung/Fehlerkorrektur_nach_Reed–Solomon–Codierung#Error_Locator_Polynom_.E2.80.93_Definition_und_Eigenschaften|''Error Locator Polynoms'']], dass ${\it \Lambda}(\alpha^{i})$ nur für $e_i &ne; 0$ ($i$&ndash;tes Symbol verfälscht) gleich Null ist, bleibt erhalten, wenn man ${\it \Lambda}(x)$mit beliebigen Potenzen von $x$ multipliziert. Jede Multiplikation mit $x$ bedeutet für den ELP&ndash;Koeffizientenvektor eine Verschiebung um eine Stelle nach rechts.<br>

[[Datei:P ID2550 KC T 2 5 S3 v1.png|center|frame|Verschobene ELP–Koeffizientenvektoren|class=fit]]

{{BlaueBox|TEXT=  
$\text{Definition:}$&nbsp; 
Die '''verallgemeinerten ELP&ndash;Koeffizientenvektoren''' $\underline {\it \Lambda }_l$ ergeben sich durch sukzessive Verschiebungen gegenüber $\underline {\it \Lambda }_l$:

::<math>{\it \Lambda}_l(x)=x^l \cdot \prod_{i\hspace{0.05cm}\in \hspace{0.05cm} I_{\rm FP} }(x-\alpha^i) =x^l \cdot \big [{\it \lambda}_0 + \lambda_1 \cdot x+\ldots+{\it \lambda}_{r-1} \cdot x^{r-1}+x^r \big ]\hspace{0.05cm}.</math>

In dieser Definitionsgleichung  entspricht $\underline {\it \Lambda }_1$ dem bisherigen $\underline {\it \Lambda }$.}}


Die Grafik zeigt die Belegung unter der Annahme von $r$ Fehlerstellen im Fehlervektor$\underline {e}$ für
*$r=1$ im linken Bereich (mit blauer Hinterlegung),
*$r=2$ im mittleren Bereich (mit roter Hinterlegung),
*$r=3$ im rechten Bereich (mit grüner Hinterlegung),


Man erkennt:
*Die Länge aller $\underline {\it \Lambda }_l$ ist stets $n-k$. Jeder Vektor beinhaltet jeweils $r$ Koeffizienten $\lambda_0$, $\lambda_1$, ... , $\lambda_{r-1}$ &nbsp; &rArr; &nbsp; $0 &#8804; i < r$  und eine Eins. Der Rest eines jeden Vektors ist mit Nullen aufgefüllt.<br>

*Für jedes $r$ gibt es genau $n-k-r$ Koeffizientenvektoren $\underline {\it \Lambda }_l$, wobei sich $\underline {\it \Lambda }_l$ aus $\underline {\it \Lambda }_{l-1}$ stets durch Rechtsverschiebung um eine Position ergibt. Der Vektor $\underline {\it \Lambda }_{n-k-r}$ endet immer mit einer $1$.<br>

*Das Gleichungssystem  $\underline {\it \Lambda }_l  \cdot \underline {s}^{\rm T} = 0 $ führt deshalb zu $n-k-r$ Gleichungen. Der gewählte Ansatz für $r$ ist nur dann richtig, wenn alle Gleichungen zu den gleichen Ergebnissen für $\lambda_0$,  ... , $\lambda_{r-1}$ führen.<br>

*Ist dies nicht der Fall, so muss man $r$ erhöhen und damit ein neues Gleichungssystem bearbeiten, und zwar solange, bis sich aus allen Gleichungen für das aktuelle $r$ eine eindeutige Lösung ergibt.<br>

*Ist schließlich $r$ größer als die Korrekturfähigkeit $t$ des Codes, so kann die Berechnung beendet werden. Das anstehende Empfangswort $\underline {y}$ ist dann nicht decodierbar.<br>


{{GraueBox|TEXT=  
$\text{Beispiel 4:}$&nbsp; Es gelten weiterhin die im [[Kanalcodierung/Fehlerkorrektur_nach_Reed%E2%80%93Solomon%E2%80%93Codierung#Schritt_.28A.29:_Auswertung_des_Syndroms_beim_BDD| Beispiel 2]] genannten Voraussetzungen: 
*Dort wurde aufgrund des Syndroms $\underline {s} = (\alpha^5,\alpha^2,\alpha^3,\alpha^1)  &ne; \underline {0}$ auch nachgewiesen, dass der Empfangsvektor $\underline {y}$ verfälscht wurde &nbsp; &rArr; &nbsp;  Fehlervektor $\underline {e} \ne \underline {0}$. 
*Nicht bekannt ist allerdings die tatsächliche Symbolfehleranzahl $r$.<br>


Unter der Annahme eines einzigen falschen Symbols $(r= 1)$ erhält man folgendes Gleichungssystem (hier in Matrixform geschrieben):
[[Datei:P ID2556 KC T 2 5 Darstellung v1.png|right|frame|Drei Darstellunsformen für $\rm GF(2^3)$]]

::<math>\big ({ \boldsymbol{\it \Lambda } }_l \big) \cdot \underline {s} ^{\rm T}= 
\begin{pmatrix}
		\lambda_0 & 1 & 0 & 0  \\
		0 & \lambda_0 & 1 & 0  \\
		0 & 0 & \lambda_0 & 1    
\end{pmatrix} \cdot 
\begin{pmatrix}
		\alpha^5\\ 
		\alpha^2\\ 
		\alpha^3\\
		\alpha 
\end{pmatrix} \stackrel{!}{=}
\begin{pmatrix}
		0\\ 
		0\\ 
		0
\end{pmatrix} 
\hspace{0.05cm}.</math>

Dieses Gleichungssystem liefert drei unterschiedliche Lösungen für $\lambda_0$, was nicht zielführend ist:<br>

::<math>\text{Zeile 1:}\hspace{0.5cm}\alpha^5 \cdot \lambda_0 + \alpha^2 = 0 \hspace{0.3cm} \Rightarrow  \hspace{0.3cm}
\lambda_0 = \alpha^{2-5}= \alpha^{-3}= \alpha^{4}\hspace{0.05cm},</math>
::<math>\text{Zeile 2:}\hspace{0.5cm}\alpha^2 \cdot \lambda_0 + \alpha^3 = 0 \hspace{0.3cm} \Rightarrow  \hspace{0.3cm}
\lambda_0 = \alpha^{3-2}=  \alpha\hspace{0.05cm},</math>
::<math>\text{Zeile 3:}\hspace{0.5cm}\alpha^3 \cdot \lambda_0 + \alpha^1 = 0 \hspace{0.3cm} \Rightarrow  \hspace{0.3cm}
\lambda_0 = \alpha^{1-3}=  \alpha^{-2} = \alpha^{5} \hspace{0.05cm}.</math>

Deshalb stellen wir nun ein weiteres Gleichungssystem auf, und zwar unter der Annahme $r = 2$:

::<math>\big ({ \boldsymbol{\it \Lambda } }_l \big) \cdot \underline {s} ^{\rm T}= 
\begin{pmatrix}
		\lambda_0 & \lambda_1 & 1 & 0  \\
		0 & \lambda_0 & \lambda_1 & 1 
\end{pmatrix} \cdot 
\begin{pmatrix}
		\alpha^5\\ 
		\alpha^2\\ 
		\alpha^3\\
		\alpha 
\end{pmatrix} \stackrel{!}{=}
\begin{pmatrix}
		0\\ 
		0
\end{pmatrix} </math>

Dies führt zu zwei Gleichungen für $\lambda_0$ und $\lambda_1$:
::<math>\alpha^5 \cdot \lambda_0 + \alpha^2 \cdot \lambda_1 + \alpha^3 = 0 \hspace{0.05cm},\hspace{0.5cm}\alpha^2 \cdot \lambda_0 + \alpha^3 \cdot \lambda_1 + \alpha^1 \hspace{-0.15cm}  =  \hspace{-0.15cm} 0 \hspace{0.05cm}.</math>

Dieses Gleichungssystem ist nun eindeutig lösbar. Man erhält $\lambda_0 = \alpha^2$ und $\lambda_1 = \alpha^6$. Das bedeutet: 
*Die Annahme, dass tatsächlich $r = 2$ Positionen des Empfangsvektors $\underline {y}$ verfälscht wurden, ist richtig.<br>
*Man weiß aber noch nicht, welche Positionen verfälscht wurden. Soviel vorneweg: 
*Es sind nicht die Symbolpositionen 2 und 6, sondern die Positionen 0 und 2, wie im folgenden Beispiel 5 gezeigt wird.}}<br> 


== Schritt (C): Lokalisierung der Fehlerstellen ==
<br>
Nach Abarbeitung von Schritt '''(B)''' sind bekannt:
*die Anzahl $r$ der Fehlerstellen $e_i &ne; 0$ im Vektor $\underline {e} = (e_0, \text{... }, e_i, \text{... }, e_{n-1})$<br>

*die Koeffizienten $\lambda_0, \text{... } , \lambda_{r-1}$ des <i>Error Locator Polynoms</i>.<br><br>

Zu bestimmen ist nun noch die Menge der Fehlerpositionen: &nbsp; $I_{\rm FP} = \{ i \hspace{0.1cm}| \hspace{0.1cm} e_i \ne 0,\hspace{0.1cm} 0 \le i < n \}\hspace{0.05cm}.$

Hierzu gibt es zwei Möglichkeiten (beide Verfahren werden im folgenden Beispiel angewendet.):
*die so genannte <i>Chien&ndash;Suche</i>, in dem man durch Einsetzen der möglichen Codesymbole außer dem Nullsymbol  $(\alpha^0, \text{... }, \alpha^i, \text{... },\alpha^{n-1})$ in das <i>Error Locator Polynom</i> dessen Nullstellen ermittelt,<br>

*die Auswertung der Gleichung $\underline {L} =	(L_0, \text{... }, L_i, \text{... },L_{n-1} ) = \underline {\it \Lambda } \cdot { \boldsymbol{\rm H }}$ mit der Abkürzung $L_i = {\it \Lambda}(\alpha^i)$.<br><br>

{{GraueBox|TEXT=  
$\text{Beispiel 5:}$&nbsp; 
Im [[Kanalcodierung/Fehlerkorrektur_nach_Reed%E2%80%93Solomon%E2%80%93Codierung#Schritt_.28B.29:_Aufstellen.2FAuswerten_des_ELP.E2.80.93Koeffizientenvektors_.282.29| Beispiel 4]] wurde entsprechend den in [[Kanalcodierung/Fehlerkorrektur_nach_Reed%E2%80%93Solomon%E2%80%93Codierung#Schritt_.28A.29:_Auswertung_des_Syndroms_beim_BDD| Beispiel 2]] genannten Randbedingungen ermittelt, dass
*$r= 2$ Symbolfehler vorliegen, und 
*die ELP&ndash;Koeffizienten $\lambda_0 = \alpha^2$ und $\lambda_1 = \alpha^6$ lauten. Damit ergibt sich das <i>Error Locator Polynom</i>:

::<math>{\it \Lambda}(x)=x \cdot \big [{\it \lambda}_0 + \lambda_1 \cdot x+x^2 \big ]
	=x \cdot \big [\alpha^2 + \alpha^6 \cdot x+x^2 \big ]\hspace{0.05cm}.</math>

[[Datei:P ID2557 KC T 2 5 Darstellung v1.png|right|frame|Drei Darstellunsformen für $\rm GF(2^3)$]] 
Entsprechend der Chien&ndash;Suche erhält man

::<math>{\it \Lambda}(\alpha^0)\hspace{0.15cm}  =  \hspace{0.15cm}\alpha^0 \cdot \big [ \alpha^2 + \alpha^6 \cdot 1 + 1 \big ]	=  \alpha^2 + (\alpha^2 + 1) + 1 = 0 \hspace{0.3cm} \Rightarrow  \hspace{0.3cm}{ \boldsymbol{\rm Nullstelle} }\hspace{0.05cm},</math>
::<math>{\it \Lambda}(\alpha^1)\hspace{0.15cm}  =  \hspace{0.15cm}\alpha^1 \cdot \big [\alpha^2 + \alpha^6 \cdot \alpha^1 + \alpha^2\big ]= \alpha^1 \hspace{0.3cm} \Rightarrow  \hspace{0.3cm}{\rm Keine\hspace{0.15cm} Nullstelle}\hspace{0.05cm},</math>
::<math>{\it \Lambda}(\alpha^2)\hspace{0.15cm}  =  \hspace{0.15cm}\alpha^2 \cdot \big [ \alpha^2 + \alpha^6 \cdot \alpha^2 + \alpha^4 \big ] =\alpha^4 + \alpha^{10} + \alpha^6 = \text{...}
=  \hspace{0.15cm}0 
 \hspace{0.3cm} \Rightarrow  \hspace{0.3cm}{ \boldsymbol{\rm Nullstelle} }\hspace{0.05cm}.</math>

Damit sind die beiden Fehlerpositionen mit $i = 0$ und $i = 2$ gefunden &nbsp; &rArr; &nbsp; der Fehlervektor lautet: $\underline {e} =	(e_0, 0, e_2, 0, 0, 0, 0)$ .<br>


Die Vektorgleichung $\underline {L} =	 \underline {\it \Lambda } \cdot { \boldsymbol{\rm H } }$ liefert das gleiche Ergebnis in kompakterer Form:

::<math>\underline {L} = \underline{\it \Lambda} \cdot  { \boldsymbol{\rm H } }  = (\alpha^2, \alpha^6, 1, 0) \cdot
				\begin{pmatrix}
						1 & \alpha^1 & \alpha^2 & \alpha^3 & \alpha^4 & \alpha^5 & \alpha^6 \\
						1 & \alpha^2 & \alpha^4 & \alpha^6 & \alpha^1 & \alpha^3 & \alpha^5 \\
						1 & \alpha^3 & \alpha^6 & \alpha^3 & \alpha^5 & \alpha^1 & \alpha^4 \\
						1 & \alpha^4 & \alpha^1 & \alpha^5 & \alpha^2 & \alpha^6 & \alpha^3
					\end{pmatrix}		</math>
::<math> \Rightarrow \hspace{0.3cm} \underline {L}   =  (\alpha^2,\alpha^3,\alpha^4,\alpha^5,\alpha^6,1       ,\alpha^1)
				+ (\alpha^6,\alpha^1,\alpha^3,\alpha^5,1       ,\alpha^2,\alpha^4)+(1,       \alpha^3,\alpha^6,\alpha^3,\alpha^5,\alpha^1,\alpha^4) </math>
::<math> \Rightarrow \hspace{0.3cm} \underline {L}   = (0,\alpha^1,0,\alpha^3,\alpha^3,\alpha^5,\alpha^1)\hspace{0.3cm} \Rightarrow  \hspace{0.3cm}
L_0 = L_2 = 0 \hspace{0.3cm} \Rightarrow \hspace{0.3cm} 
\underline {e} =	(e_0, 0, e_2, 0, 0, 0, 0)\hspace{0.05cm}.</math>

Das Beispiel wird mit dem '''Beispiel 6''' auf der nächsten Seite fortgesetzt.}}<br>

== Schritt (D): Abschließende Fehlerkorrektur ==
<br>
Im letzten Schritt müssen nun nur noch die $r$ Symbolfehler korrigiert werden, deren Positionen nach Beendigung von Schritt '''(C)''' bekannt sind:
*Markiert man die Fehlerpositionen im Empfangswort $\underline {y}$  als Auslöschungen $\rm E$ (<i>Erasures</i>), so kann das zugehörige Codewort $\underline {z}$ entsprechend der Beschreibung im Kapitel [[Kanalcodierung/Reed–Solomon–Decodierung_beim_Auslöschungskanal|Reed–Solomon–Decodierung beim Auslöschungskanal]] gefunden werden.<br>

*Eine zweite Möglichkeit bietet die Bestimmung des Fehlervektors $\underline {e}$ aus der Gleichung $\underline {e}  \cdot  \boldsymbol{\rm H }^{\rm T} = \underline {s}$ und die Korrektur entsprechend $\underline {z} = \underline {y}  - \underline {e} $ . Dieses Verfahren liegt dem folgenden Beispiel zugrunde.<br><br>

[[Datei:P ID2558 KC T 2 5 Darstellung v1.png|right|frame|$\rm GF(2^3)$&ndash;Darstellunsformen]] 
{{GraueBox|TEXT=  
$\text{Beispiel 6:}$&nbsp; Im [[Kanalcodierung/Fehlerkorrektur_nach_Reed%E2%80%93Solomon%E2%80%93Codierung#Schritt_.28A.29:_Auswertung_des_Syndroms_beim_BDD| Beispiel 2]] wurde 
*das Empfangswort mit $\underline{y}=\big (\alpha^3,\hspace{0.05cm} 1,\hspace{0.05cm} 0, \hspace{0.05cm}\alpha^1, \hspace{0.05cm} \alpha^2, \hspace{0.05cm} \alpha^5, \hspace{0.05cm} \alpha^5 \big)$ vorgegeben, und 
*daraus das Syndrom $\underline{s}=\big (\alpha^5,\hspace{0.05cm}\alpha^2, \hspace{0.05cm} \alpha^3, \hspace{0.05cm} \alpha^1\big)$


ermittelt. Nach den Berechnungen im [[Kanalcodierung/Fehlerkorrektur_nach_Reed%E2%80%93Solomon%E2%80%93Codierung#Schritt_.28C.29:_Lokalisierung_der_Fehlerstellen| Beispiel 5]] lautet der Fehlervektor $\underline {e} =	(e_0, 0, e_2, 0, 0, 0, 0)$. <br>Diese Angaben gelten für den '''RSC (7, 3, 5)<sub>8</sub>'''.<br>

Aus $\underline {e}  \cdot  \boldsymbol{\rm H }^{\rm T} = \underline {s}$ erhält man nun folgende Bestimmungsgleichungen für die Fehlerwerte $e_0$ und $e_2$:

::<math>\underline {e}  \cdot \boldsymbol{\rm H }^{\rm T}= \begin{pmatrix}
		e_0 & 0 & e_2 & 0 & 0 & 0 & 0
\end{pmatrix}\cdot
\begin{pmatrix}
		1 & 1 & 1 & 1 \\
		\alpha^1 & \alpha^2 & \alpha^3 & \alpha^4\\
		\alpha^2 & \alpha^4 & \alpha^6 & \alpha^1\\
		\alpha^3 & \alpha^6 & \alpha^2 & \alpha^{5}\\
		\alpha^4 & \alpha^1 & \alpha^{5} & \alpha^{2}\\
		\alpha^5 & \alpha^{3} & \alpha^{1} & \alpha^{6}\\
		\alpha^6 & \alpha^{5} & \alpha^{4} & \alpha^{3}
\end{pmatrix} \stackrel{!}{=} \underline {s} = 
\begin{pmatrix}
		\alpha^5 & \alpha^2 & \alpha^3 & \alpha^1 
\end{pmatrix}  </math>
::<math>\Rightarrow  \hspace{0.3cm}e_0 \cdot (1, 1, 1, 1) + e_2 \cdot (		\alpha^2, \alpha^4, \alpha^6, \alpha^1)\stackrel{!}{=}
(		\alpha^5, \alpha^2, \alpha^3, \alpha^1)</math>
::<math>\Rightarrow  \hspace{0.3cm}
e_0 + e_2 \cdot \alpha^2 = \alpha^5\hspace{0.05cm},\hspace{0.2cm}
e_0 + e_2 \cdot \alpha^4 = \alpha^2\hspace{0.05cm},\hspace{0.2cm}
e_0 + e_2 \cdot \alpha^6 = \alpha^3\hspace{0.05cm},\hspace{0.2cm}
e_0 + e_2 \cdot \alpha^1 = \alpha^1\hspace{0.05cm}.</math>


Diese Gleichungen führen zum Ergebnis $e_0 = 1$ und $e_2 =\alpha^2$. Damit  lautet das korrigierte Codewort mit $\underline {y} =  (\alpha^3,\hspace{0.05cm} 1,\hspace{0.05cm} 0,\hspace{0.05cm}  \alpha^1,\hspace{0.05cm} \alpha^2,\hspace{0.05cm} \alpha^5,\hspace{0.05cm} \alpha^5)$ und $\underline {e}=  (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)$:

::<math>\underline {z} = \underline {y} - \underline {e} = \underline {y} + \underline {e}=
(\alpha^1,\hspace{0.03cm} 1,\hspace{0.03cm} \alpha^2,\hspace{0.03cm}  \alpha^1,\hspace{0.03cm} \alpha^2,\hspace{0.03cm} \alpha^5,\hspace{0.03cm} \alpha^5)\hspace{0.05cm}. </math>

Dieses ist ein gültiges Codewort von RSC (7, 3, 5)<sub>8</sub>.}}<br>

== Schnelle Reed–Solomon–Decodierung ==
<br>
Die Klasse der Reed&ndash;Solomon&ndash;Codes wurde bereits im Jahre 1960 durch die Veröffentlichung [RS60]<ref name='RS60'>Reed, I.S.; Solomon, G.: ''Polynomial Codes over Certain Finite Fields.'' J. Siam, Vol. 8, pp. 300–304, 1960.</ref> eingeführt. Ihre effiziente Decodierung war jedoch erst ein bis zwei Jahrzehnte später möglich.<br>

Auf den letzten Seiten haben wir den so genannten Petersen&ndash;Algorithmus inklusive der Chien&ndash;Suche am Beispiel des RSC (7, 3, 5)<sub>8</sub> demonstriert, der bis zu $t = 2$ Fehler korrigieren kann. Im Mittelpunkt des Decodiervorgangs stand dabei das Aufstellen und Lösen der Schlüsselgleichung (englisch: <i>Error Locator Polynom</i>), wobei die Nullstellen eines Grad&ndash;2&ndash;Polynoms im Körper $\rm GF(7)$ gefunden werden mussten. Sie konnten erkennen, dass schon diese algebraische Decodierung mit großem Aufwand verbunden ist.<br>

Bei den in Praxis eingesetzten Codes mit großer Codewortlänge $n$ und hoher Korrekturfähigkeit $t$ würde der Decodieraufwand explodieren, wenn nicht schnellere Decodieralgorithmen gefunden worden wären. So müssen beim Reed&ndash;Solomon&ndash;Code RSC (255, 223, 33)<sub>256</sub>, der schon früh im ESA/NASA&ndash;Standard zur Satellitenübertragung genannt wurde, zur Decodierng eines einzigen Codewortes bis zu $t = 16$ Nullstellen im Körper $\rm GF(255)$ gefunden werden, und das auch noch in Echtzeit.<br>

Ab Ende der 1960er Jahre haben sich viele Wissenschaftler um schnellere Decodieralgorithmen für  Reed&ndash;Solomon&ndash;Codes bemüht:

*Beim [https://de.wikipedia.org/wiki/Berlekamp-Massey-Algorithmus Berlekamp&ndash;Massey&ndash;Algorithmus] (BMA) wird die Schlüsselgleichung $\underline {\it \Lambda}  \cdot  \underline{s }^{\rm T} = 0$ als rückgekoppeltes Schieberegister dargestellt, siehe zum Beispiel [Mas69]<ref name ='Mas69'>Massey, J.L.: ''Shift Register Synthesis and BCH Decoding.''. IEEE Trans. on Information Theory, vol. IT-15, pp. 122–127, Jan. 1969.</ref>, [Fri96]<ref name ='Fri96'>Friedrichs, B.: ''Kanalcodierung – Grundlagen und Anwendungen in modernen Kommunikations- systemen.'' Berlin – Heidelberg: Springer, 1996.</ref> und [Bos98]<ref name ='Bos98'>Bossert, M.: ''Kanalcodierung.'' Stuttgart: B. G. Teubner, 1998.</ref>. Das Problem wird damit auf die Synthese eines autoregressiven Filters zurückgeführt. Dieser Algorithmus arbeitet wesentlich schneller als der (leichter durchschaubare) Petersen&ndash;Algorithmus.<br>

*Etwas später wurde in [SK+75]<ref name='SK+75'>Sugiyama, Y.; Kashara, M.; Hirasawa, S.; Namekawa, T.: ''A Method for Solving Key Equation for Decoding Goppa Codes.'' Information and Control, Vol. 27, pp. 87–99, 1975.</ref> ein Decodierverfahren vorgeschlagen, das auf dem [https://de.wikipedia.org/wiki/Euklidischer_Algorithmus Euklidischen Algorithmus] basiert. Dieser liefert den größten gemeinsamen Teiler zweier ganzer Zahlen, was zur Decodierung genutzt wird. Der Euklidische Algorithmus ist vergleichbar schnell wie der BMA. Genauere Informationen finden Sie wieder in [Bos98]<ref name ='Bos98'></ref> und [Fri96]<ref name ='Fri96'></ref>.<br>

*Weitere effiziente Decodiernethoden von Reed&ndash;Solomon&ndash;Codes arbeiten im <i>Frequenzbereich</i> unter Verwendung der [[Signaldarstellung/Diskrete_Fouriertransformation_(DFT)#Argumente_f.C3.BCr_die_diskrete_Realisierung_der_FT| Diskreten Fouriertransformation]] (DFT) im Körper ${\rm GF}(n)$.<br><br>

Die Grundzüge der Reed&ndash;Solomon&ndash;Fehlerkorrektur wurden bereits in den 1960er Jahren entwickelt. Aber bis in die heutige Zeit (2013) ist die (möglichst schnelle) algebraische Decodierung dieser Codes ein hochaktuelles Forschungsgebiet.

== Aufgaben zum Kapitel==
<br>
[[Aufgaben:Aufgabe_2.12:_Decodierung_beim_RSC_(7,_4,_4)_zur_Basis_8|Aufgabe 2.12: Decodierung beim RSC (7, 4, 4) zur Basis 8]]

[[Aufgaben:Aufgabe_2.12Z:_Reed–Solomon–Syndromberechnung|Aufgabe 2.12Z: Reed–Solomon–Syndromberechnung]]

[[Aufgaben:Aufgabe_2.13:_Decodierung_beim_RSC_(7,_3,_5)_zur_Basis_8|Aufgabe 2.13: Decodierung beim RSC (7, 3, 5) zur Basis 8]]

[[Aufgaben:Aufgabe_2.14:_Petersen–Algorithmus|Aufgabe 2.14: Petersen–Algorithmus]]

==Quellenverzeichnis==
<references/>

{{Display}}