Kanalcodierung/Fehlerkorrektur nach Reed–Solomon–Codierung: Unterschied zwischen den Versionen

Aus LNTwww
Wechseln zu:Navigation, Suche
 
(10 dazwischenliegende Versionen desselben Benutzers werden nicht angezeigt)
Zeile 8: Zeile 8:
 
== Blockschaltbild und Voraussetzungen zur RS–Fehlerkorrektur ==
 
== Blockschaltbild und Voraussetzungen zur RS–Fehlerkorrektur ==
 
<br>
 
<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}$:
+
Wie im Kapitel&nbsp; [[Kanalcodierung/Reed–Solomon–Decodierung_beim_Auslöschungskanal#Blockschaltbild_und_Voraussetzungen_zur_RS.E2.80.93Fehlererkennung|Decodierung beim Auslöschungskanal]]&nbsp; betrachten wir ein Übertragungssystem mit Reed&ndash;Solomon&ndash;Codierung, das durch die beiden Codeparameter&nbsp; $n=2^m-1$&nbsp; und&nbsp; $k$&nbsp; gekennzeichnet  ist. Mit der Generatormatrix&nbsp; $\boldsymbol{\rm G}$&nbsp; lautet der Zusammenhang zwischen dem Informationswort&nbsp; $\underline {u}$&nbsp; und dem Codewort&nbsp; $\underline {c}$:
  
 
::<math>\underline {c} = {\rm enc}(\underline {u}) = \underline {u} \cdot { \boldsymbol{\rm G}}
 
::<math>\underline {c} = {\rm enc}(\underline {u}) = \underline {u} \cdot { \boldsymbol{\rm G}}
Zeile 15: Zeile 15:
 
\hspace{0.05cm}.</math>
 
\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>
+
Die Informationssymbole&nbsp; $u_i$&nbsp; und auch die Codesymbole&nbsp; $C_i$&nbsp; entstammen dem Körper&nbsp; ${\rm GF}(q)$&nbsp; mit&nbsp; $q=n+1=2^m$; sie sind durch&nbsp; $m$&nbsp; 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]]
+
[[Datei:P ID2545 KC T 2 5 S1 v2.png|center|frame|Übertragungssystem mit Reed–Solomon–Codierung/Decodierung und&nbsp; $m$–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:
+
Ein Vergleich dieses Blockschaltbildes mit dem entsprechenden&nbsp; [[Kanalcodierung/Reed–Solomon–Decodierung_beim_Auslöschungskanal#Blockschaltbild_und_Voraussetzungen_zur_RS.E2.80.93Fehlererkennung|Blockschaltbild zur RS&ndash;Fehlererkennung]]&nbsp; 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>
+
*Der wesentliche Unterschied liegt im verwendeten diskreten Kanalmodell (grün hinterlegt). Anstelle des Auslöschungskanals&nbsp; (&bdquo;$m$&ndash;BEC&rdquo;)&nbsp; wird nun der&nbsp; $m$&ndash;BSC&nbsp; betrachtet. Für jedes einzelne Bit des Codesymbols&nbsp; $c_i$&nbsp; wird der&nbsp; [[Kanalcodierung/Kanalmodelle_und_Entscheiderstrukturen#Binary_Symmetric_Channel_.E2.80.93_BSC| ''Binary Symmetric Channel'']]&nbsp; (BSC) angewandt. Ein Bitfehler bezüglich des $i$&ndash;ten Bits  ergibt&nbsp; $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>
+
*Im&nbsp; [[Kanalcodierung/Reed–Solomon–Decodierung_beim_Auslöschungskanal|letzten Kapitel]]&nbsp; waren unsichere Bits bereits durch Auslöschungen&nbsp; $\rm E$&nbsp; (<i>Erasures</i>&nbsp;) markiert. Aufgabe des&nbsp; <i>Codewortfinders</i>&nbsp; $\rm (CWF)$ war es, aus dem verstümmelten Empfangswort&nbsp; $\underline {y}$&nbsp; das Decodierergebnis&nbsp; $\underline {z}$&nbsp; zu rekonstruieren.  
 +
*Ist dabei die Anzahl&nbsp; $e$&nbsp; der Auslöschungen kleiner als die minimale Distanz&nbsp; $d_{\rm min}$, so gelingt dies und man erhält&nbsp; $\underline {z} = \underline {c}$. Andernfalls meldet der Codewortfinder, dass er das aktuelle Empfangswort&nbsp; $\underline {y}$&nbsp; nicht decodieren kann. &nbsp; Eine Fehlentscheidung&nbsp; $(\underline {z} \ne \underline {c})$&nbsp; war beim BEC 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>
+
*In diesem Kapitel wird nun der erste Decoderblock als&nbsp; <i>Codewortschätzer</i>&nbsp; $\rm (CWS)$ bezeichnet. Die Namensgebung soll deutlich machen, dass aufgrund des&nbsp; $m$&ndash;BSC&ndash;Modells Fehlentscheidungen&nbsp; $(\underline {z} \ne \underline {c})$&nbsp; unvermeidlich sind, nämlich dann, wenn mehrere Symbolfehler das Empfangswort&nbsp; $\underline {y}$&nbsp; zu einem gültigen Codewort verfälschen.<br><br>
  
 
{{BlaueBox|TEXT=   
 
{{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:
+
$\text{Fazit:}$&nbsp;   
 +
*Aufgabe des Decoders ist es, seinen Ausgangsvektor&nbsp; $\underline {v}$&nbsp; so zu bestimmen, dass er &bdquo;möglichst gut&rdquo; mit dem Informationswort&nbsp; $\underline {u}$&nbsp; übereinstimmt. Exakter formuliert:
  
::<math>{ \rm Pr(Blockfehler)} = { \rm Pr}( \underline{\upsilon} \ne \underline{u}) \stackrel{!}{=} { \rm Minimum}\hspace{0.05cm}.</math>
+
::<math>{ \rm Pr(Blockfehler)} = { \rm Pr}( \underline{v} \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:
+
*Aufgrund des deterministischen Mappings&nbsp; $\underline{c} = {\rm enc}(\underline{u})$&nbsp; und&nbsp; $\underline{v} = {\rm enc}^{-1}(\underline{z})$&nbsp; gilt in gleicher Weise:
  
 
::<math>{ \rm Pr(Blockfehler)} = { \rm Pr}( \underline{z} \ne \underline{c}) \stackrel{!}{=} { \rm Minimum}\hspace{0.05cm}.</math>}}
 
::<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>
+
Die zwei gelb hinterlegten Blöcke werden im Folgenden nicht weiter betrachtet.  Im Mittelpunkt der Betrachtungen steht nun der rot hinterlegte <i>Codewortschätzer</i>&nbsp; $\rm (CWS)$.<br>
  
 
== Mögliche Codewortschätzer für die RS&ndash;Decodierung ==
 
== Mögliche Codewortschätzer für die RS&ndash;Decodierung ==
 
<br>
 
<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>
+
Die rechte Skizze der nachfolgenden Grafik verdeutlicht nochmals die Aufgabenstellung, wobei hier das Kanalmodell &bdquo;$m$&ndash;BSC&rdquo; durch den additiven&nbsp;  '''Fehlervektor'''&nbsp; $\underline{e} = \underline{y} - \underline{c}$&nbsp; 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]]
+
[[Datei:P ID2546 KC T 2 5 S2 v2.png|center|frame|Zur Definition des Fehlervektors&nbsp; $\underline{e}$|class=fit]]
  
 
Diese Aufgabenstellung soll durch ein Beispiel verdeutlicht werden.<br>
 
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)$]]  
+
[[Datei:P ID2547 KC T 2 5 Darstellung v1.png|right|frame|Drei Darstellungsformen für&nbsp; $\rm GF(2^3)$]]  
 
{{GraueBox|TEXT=   
 
{{GraueBox|TEXT=   
 
$\text{Beispiel 1:}$&nbsp;   
 
$\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   
+
Alle Symbole seien Elemente von&nbsp; $\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$)
+
*zwischen der Koeffizientendarstellung $($mit der Reihenfolge&nbsp; $k_2$,&nbsp; $k_1$,&nbsp; $k_0)$  
* und der Exponentendarstellung (als Potenzen des primitiven Elements $\alpha$)
+
* und der Exponentendarstellung $($als Potenzen des primitiven Elements&nbsp; $\alpha)$  
  
  
Zeile 61: Zeile 63:
 
::<math>\underline{y} =\Big ( (011), (001), (000),(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}$:
+
Damit ergibt sich für den Fehlervektor&nbsp; $\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>
 
::<math>\underline{e} \hspace{0.05cm} = \hspace{0.05cm} \Big ( (001), (000), (100), (000),(000),(000),(000)\Big )\hspace{0.05cm}.</math>
Zeile 71: Zeile 73:
 
::<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>
 
::<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:
+
Aufgabe des Codewortschätzers&nbsp; $\rm (CWS)$&nbsp; ist es, das zu&nbsp; $\underline{y}$&nbsp; wahrscheinlichste Codewort&nbsp; $\underline{c}_i$&nbsp; zu finden und sein Ergebnis&nbsp; $\underline{z} = \underline{c}_i$&nbsp; an das nachfolgende Mapping weiterzugeben. Hierzu gibt es verschiedene Möglichkeiten:
 
*<i>Hard Decision Maximum Likelihood Decoding</i>&nbsp;  $\text{(HD&ndash;MLD)}$,<br>
 
*<i>Hard Decision Maximum Likelihood Decoding</i>&nbsp;  $\text{(HD&ndash;MLD)}$,<br>
  
Zeile 81: Zeile 83:
  
  
<b>Hard Decision Maximum Likelihood Decoding (HD&ndash;MLD):</b><br>
+
<b>Hard Decision Maximum Likelihood Decoding&nbsp; $\text{(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:
+
Man wählt von allen möglichen Reed&ndash;Solomon&ndash;Codeworten&nbsp; $\underline{c}_i$&nbsp; $($hiervon gibt es insgesamt&nbsp; $q^k)$&nbsp; dasjenige mit der geringsten&nbsp; [[Kanalcodierung/Zielsetzung_der_Kanalcodierung#Einige_wichtige_Definitionen_zur_Blockcodierung| Hamming&ndash;Distanz]]&nbsp; zum Empfangswort&nbsp; $\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}
+
::<math>\underline{z} = {\rm arg} \min_{\underline{c}_{\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>
 
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>
+
Die Entscheidung passiert hier auf der maximalen Rückschlusswahrscheinlichkeit&nbsp; ${\rm Pr}(\underline{c}_i\hspace{0.05cm}|\hspace{0.05cm}\underline{y})$&nbsp; und führt zum bestmöglichen Ergebnis. Näheres siehe&nbsp; [[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&nbsp; $r$&nbsp; der Symbolfehler größer ist als die Korrekturfähigkeit&nbsp; $t$&nbsp; 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.  
 
*Es sei nochmals erwähnt, dass bei Maximum&ndash;Likelihood&ndash;Decodierung immer entschieden wird.  
Zeile 95: Zeile 97:
  
  
<b>Bounded Distance Decoding (BDD):</b><br>
+
<b>Bounded Distance Decoding&nbsp; $\text{(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:
+
Falls die Anzahl&nbsp; $r$&nbsp; der Symbolfehler im Empfangswort&nbsp; $\underline{y}$&nbsp; nicht größer ist als die Korrekturfähigkeit&nbsp; $t = &lfloor;(d_{\rm min}- 1)/2&rfloor;$&nbsp; des Codes, kann man die&nbsp; $r$&nbsp; Symbolfehler vollständig korrigieren. Allerdings gilt auch:
*Der Fall $r > t$ führt zu einem Abbruch des Decodiervorgangs ohne Ergebnis. Anders ausgedrückt:   
+
*Der Fall&nbsp; $r > t$&nbsp; führt zu einem Abbruch des Decodiervorgangs ohne Ergebnis. &nbsp; Anders ausgedrückt:   
*Es werden nur diejenigen Empfangsworte zum Kugelmittelpunkt hin decodiert, die in einer Kugel um diesen mit Radius $t$ liegen.  
+
*Es werden nur diejenigen Empfangsworte zum Kugelmittelpunkt hin decodiert, die in einer Kugel um diesen mit Radius&nbsp; $t$&nbsp; liegen.  
 
*Andere  Empfangsworte werden als undecodierbar markiert, zum Beispiel als <i>Erasure</i>.<br><br>
 
*Andere  Empfangsworte werden als undecodierbar markiert, zum Beispiel als <i>Erasure</i>.<br><br>
  
Zeile 105: Zeile 107:
 
<b>Decodierung über die halbe Mindestdistanz</b>:<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>
+
Hier wird auch im Fall&nbsp; $r > t$&nbsp; versucht, das Codewort zu decodieren. Im Gegensatz zu&nbsp; $\text{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>
+
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>&nbsp; proportional zu&nbsp; $q^{n-k}$.<br>
  
 
== Vorgehensweise beim „Bounded Distance Decoding” ==
 
== Vorgehensweise beim „Bounded Distance Decoding” ==
Zeile 114: Zeile 116:
  
  
$\rm (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]]
+
$\rm (A)$&nbsp; &nbsp;$\text{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}$.  
+
*Berechne aus dem Empfangswort&nbsp; $\underline{y}$&nbsp; und der Prüfmatrix&nbsp; $\boldsymbol{\rm H }$&nbsp; des Codes das Syndrom&nbsp; $\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>
+
*Ergibt sich&nbsp; $\underline {s} =\underline {0}$, so setze den BDD&ndash;Ausgang&nbsp; $\underline {z} =\underline {y}$&nbsp; und beende den Decodiervorgang für dieses Empfangswort.<br>
*Andernfalls setze den Parameter $r = 1$ und mache mit Schritt $\rm (B)$ weiter.<br><br>
+
*Andernfalls setze den Parameter&nbsp; $r = 1$&nbsp; und mache mit Schritt&nbsp; $\rm (B)$&nbsp; weiter.<br><br>
  
  
$\rm (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]]
+
$\rm (B)$&nbsp; &nbsp;$\text{Bestimmung der tatsächlichen Symbolfehleranzahl } r$&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>
+
*Erstelle und überprüfe die Gleichungen&nbsp; $\underline {\it \Lambda} _l \cdot\underline {s}^{\rm T} = 0$ &nbsp; für &nbsp; $l = 1,$ ... , $2 \cdot t -r$&nbsp; unter der Annahme, dass das Empfangswort genau &nbsp; $r$ &nbsp; 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>
+
*$\underline {\it \Lambda} _l $&nbsp; bezeichnet die verallgemeinerten &nbsp;$\text{ELP}$&ndash;Koeffizientenvektoren, wobei &bdquo;$\text{ELP}$&rdquo; für&nbsp; [[Kanalcodierung/Fehlerkorrektur_nach_Reed–Solomon–Codierung#Error_Locator_Polynom_.E2.80.93_Definition_und_Eigenschaften|Error Locator Polynom]]&nbsp; steht, und&nbsp; $t$&nbsp; die Korrekturfähigkeit des Codes angibt. <br>Für die Reed&ndash;Solomon&ndash;Codes gilt einheitlich&nbsp; $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>
+
*Gibt es eine eindeutige Lösung, dann mache mit Schritt&nbsp; $\rm (C)$&nbsp; weiter. &nbsp;Im Empfangsvektor&nbsp; $\underline{y}$&nbsp; sind dann tatsächlich genau&nbsp; $r$&nbsp; Symbole verfälscht und im Fehlervektor&nbsp; $\underline{e}$&nbsp; gibt es&nbsp; $r$&nbsp; Einträge ungleich $0$.<br>
  
*Andernfalls erhöhe $r$ um $1$. Falls $r &#8804; t$, dann wiederhole Schritt $\rm (B)$ von Beginn an: &nbsp;Das bisher angenommene $r$ war offensichtlich zu klein. Deshalb nun ein neuer Versuch mit größerem $r$.<br>
+
*Andernfalls erhöhe&nbsp; $r$&nbsp; um&nbsp; $1$. &nbsp; Falls&nbsp; $r &#8804; t$, dann wiederhole Schritt&nbsp; $\rm (B)$&nbsp; von Beginn an: &nbsp; Das bisher angenommene&nbsp; $r$&nbsp; war offensichtlich zu klein. Deshalb nun ein neuer Versuch mit größerem&nbsp; $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>
+
*Ist das neue&nbsp; $r$&nbsp; größer als die Korrekturfähigkeit&nbsp; $t$&nbsp; des Codes, so kann das aktuelle Empfangswort nicht decodiert werden. Beende den Decodierversuch mit einer&nbsp; ''Fehlermeldung''.<br><br>
  
  
$\rm (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]]
+
$\rm (C)$&nbsp; &nbsp;$\text{Lokalisierung der }r \text{  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>
+
*Erstelle das&nbsp; <i>Error Locator Polynom</i>&nbsp; ${\it \Lambda}(x)$&nbsp; und finde dessen&nbsp; $r$&nbsp; Nullstellen in&nbsp; ${\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>
+
*Ein Fehler an der Stelle&nbsp; $i$&nbsp; liegt immer dann vor, wenn&nbsp; ${\it \Lambda}(\alpha^{i}) = 0$&nbsp; ist.<br><br>
  
  
$\rm (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]]
+
$\rm (D)$&nbsp; &nbsp;$\text{Bestimmung der   }r \text{ 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>
+
*Bekannt sind nun die&nbsp; $r$&nbsp; Fehlerstellen. Ersetzt man im Empfangsvektor&nbsp; $\underline{y}$&nbsp; die falschen Symbole durch Auslöschungen &nbsp; &#8658; &nbsp; $y_i = \rm E$, falls&nbsp; $e_i &ne; 0$, so findet man das Ergebnis&nbsp; $\underline{y}$&nbsp; entsprechend dem Kapitel&nbsp; [[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>
+
*Eine Alternative: &nbsp; Aus der Gleichung&nbsp; $\underline {e}  \cdot  \boldsymbol{\rm H }^{\rm T} = \underline {s}$&nbsp; kommt man unter Ausnutzung der fehlerfreien Stellen&nbsp; $(e_i = 0)$&nbsp; zu einem linearen Gleichungssystem für die fehlerhaften Symbole&nbsp; $(e_i \ne 0)$.<br><br>
  
 
== Schritt (A): Auswertung des Syndroms beim BDD ==
 
== Schritt (A): Auswertung des Syndroms beim BDD ==
 
<br>
 
<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}$&nbsp; herangezogen werden. Mit dem Empfangswort $\underline{y}$&nbsp; gleich Codewort $\underline{c}$&nbsp;  plus Fehlervektor $\underline{e}$&nbsp; gilt:
+
Wie im Abschnitt&nbsp; [[Kanalcodierung/Decodierung_linearer_Blockcodes#Prinzip_der_Syndromdecodierung|Prinzip der Syndromdecodierung]]&nbsp; gezeigt wurde, kann zur Decodierung eines linearen Codes das Syndrom&nbsp; $\underline{s}$&nbsp; herangezogen werden.  
 +
 
 +
Mit dem Empfangswort&nbsp; $\underline{y}$&nbsp; gleich Codewort&nbsp; $\underline{c}$&nbsp;  plus Fehlervektor&nbsp; $\underline{e}$&nbsp; gilt:
  
 
::<math>\underline {s} = \underline {y}  \cdot { \boldsymbol{\rm H }}^{\rm T}=  
 
::<math>\underline {s} = \underline {y}  \cdot { \boldsymbol{\rm H }}^{\rm T}=  
Zeile 152: Zeile 156:
 
\hspace{0.05cm}.</math>
 
\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:
+
Da stets&nbsp; $\underline {c}  \cdot { \boldsymbol{\rm H }}^{\rm T} =\underline {0}$&nbsp; gilt, folgt aus&nbsp; $\underline{s}= \underline{0}$&nbsp; auch&nbsp; $\underline {e}  \cdot { \boldsymbol{\rm H }}^{\rm T} =\underline {0}$. &nbsp; Das heißt:
*Mit sehr großer Wahrscheinlichkeit kann aus $\underline{s}= \underline{0}$&nbsp; auch auf $\underline{e}= \underline{0}$&nbsp; und damit auch auf das richtige Decodierergebnis $\underline{z}= \underline{y}$&nbsp; geschlossen werden. Der Decodiervorgang wäre damit abgeschlossen.<br>
+
*Mit sehr großer Wahrscheinlichkeit kann aus&nbsp; $\underline{s}= \underline{0}$&nbsp; auch auf&nbsp; $\underline{e}= \underline{0}$&nbsp; und damit auch auf das richtige Decodierergebnis&nbsp; $\underline{z}= \underline{y}$&nbsp; 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}$&nbsp; 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>
+
*Es gibt aber auch Fehlermuster&nbsp; $\underline{e} \ne \underline{0}$, die zum Syndrom&nbsp; $\underline{s}= \underline{0}$&nbsp; führen. Solche Muster beinhalten sicher mehr als&nbsp; $t$&nbsp; 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|$\rm GF(2^3)$&ndash;Darstellungen]]  
 
[[Datei:P ID2548 KC T 2 5 Darstellung v1.png|right|frame|$\rm GF(2^3)$&ndash;Darstellungen]]  
 
{{GraueBox|TEXT=   
 
{{GraueBox|TEXT=   
 
$\text{Beispiel 2:}$&nbsp;   
 
$\text{Beispiel 2:}$&nbsp;   
Diesem und den folgenden Beispielen auf den nächsten Seiten liegt stets der Reed&ndash;Solomon&ndash;Code $\text{RSC (7, 3, 5)}_8$ zugrunde, so dass die in der Grafik angegebenen Umrechnungen in $\rm GF(2^3)$ genutzt werden können. Das Empfangswort lautet:
+
Diesem und den folgenden Beispielen auf den nächsten Seiten liegt stets der Reed&ndash;Solomon&ndash;Code&nbsp; $\text{RSC (7, 3, 5)}_8$&nbsp; zugrunde, so dass die in der Grafik angegebenen Umrechnungen in&nbsp; $\rm GF(2^3)$&nbsp; 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>
 
::<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:
+
Mit der&nbsp; [[Kanalcodierung/Definition_und_Eigenschaften_von_Reed%E2%80%93Solomon%E2%80%93Codes#Generatormatrix_und_Pr.C3.BCfmatrix_.282.29| Prüfmatrix]]&nbsp; $\boldsymbol{\rm H }$&nbsp; ergibt sich für das Syndrom:
  
 
::<math>\underline {s} = \underline {y}  \cdot { \boldsymbol{\rm H } }^{\rm T}=  
 
::<math>\underline {s} = \underline {y}  \cdot { \boldsymbol{\rm H } }^{\rm T}=  
Zeile 184: Zeile 188:
 
(\alpha^5,\alpha^2,\alpha^3,\alpha^1)  \hspace{0.05cm}.</math>
 
(\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>
+
Das Empfangswort wurde also verfälscht. &nbsp; Andernfalls hätte sich&nbsp; $\underline{e}= \underline{0} = (0, 0, 0, 0)$&nbsp; ergeben müssen.<br>
  
Die Beschreibung des Decodiervorgangs beim $\text{RSC (7, 3, 5)}_8$ wird im [[Kanalcodierung/Fehlerkorrektur_nach_Reed–Solomon–Codierung#Schritt_.28B.29:_Aufstellen.2FAuswerten_des_ELP.E2.80.93Koeffizientenvektors|$\text{Beispiel 4}$]] fortgesetzt.}}<br>
+
Die Beschreibung des Decodiervorgangs beim&nbsp; $\text{RSC (7, 3, 5)}_8$&nbsp; wird im&nbsp; [[Kanalcodierung/Fehlerkorrektur_nach_Reed–Solomon–Codierung#Schritt_.28B.29:_Aufstellen.2FAuswerten_des_ELP.E2.80.93Koeffizientenvektors|$\text{Beispiel 4}$]]&nbsp; fortgesetzt.}}<br>
  
 
== Error Locator Polynom – Definition und Eigenschaften ==
 
== Error Locator Polynom – Definition und Eigenschaften ==
 
<br>
 
<br>
Nach der Syndromberechnung im Schritt $\rm (A)$ mit dem Ergebnis $\underline{s} \ne \underline{0}$ wissen wir,
+
Nach der Syndromberechnung im Schritt&nbsp; $\rm (A)$&nbsp; mit dem Ergebnis&nbsp; $\underline{s} \ne \underline{0}$&nbsp; wissen wir,
*dass das Empfangswort $\underline{y}$&nbsp; nicht mit dem Codewort $\underline{c}$&nbsp; übereinstimmt, bzw.<br>
+
*dass das Empfangswort&nbsp; $\underline{y}$&nbsp; nicht mit dem Codewort&nbsp; $\underline{c}$&nbsp; ü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>
+
*dass der Fehlervektor&nbsp; $\underline{e}  = (e_0, \hspace{0.05cm}e_1, \hspace{0.05cm}\text{ ...}\hspace{0.05cm} , e_{n-1})$&nbsp; mit Sicherheit auch Elemente ungleich&nbsp; $0$&nbsp; 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}$&nbsp; benennen.<br>
+
Wir wissen allerdings nicht, wie viele Symbole verfälscht wurden&nbsp; $(0 < r &#8804; n)$&nbsp; und wir können auch nicht die Positionen der Fehlerstellen&nbsp; $(e_i &ne; 0)$&nbsp; im Fehlervektor&nbsp; $\underline{c}$&nbsp; 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>
+
Einen Lösungsansatz für diese Aufgabe bietet das so genannte&nbsp; <i>Error Locator Polynom</i>, das von&nbsp; [https://de.wikipedia.org/wiki/W._Wesley_Peterson William Wesley Peterson]&nbsp; eingeführt wurde &nbsp; &rArr; &nbsp; 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 &bdquo;Schlüsselgleichung&rdquo; üblich.<br>
  
 
{{BlaueBox|TEXT=   
 
{{BlaueBox|TEXT=   
$\text{Definition:}$&nbsp; Es sei bekannt, dass genau $r$ Elemente des Fehlervektors $\underline{e}$&nbsp; 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:
+
$\text{Definition:}$&nbsp; Es sei bekannt, dass genau&nbsp; $r$&nbsp; Elemente des Fehlervektors&nbsp; $\underline{e}$&nbsp; ungleich Null sind, erkennbar am&nbsp; [[Kanalcodierung/Zielsetzung_der_Kanalcodierung#Einige_wichtige_Definitionen_zur_Blockcodierung|Hamming&ndash;Gewicht]]&nbsp; $w_{\rm H}(\underline{e}) = r$.  
 +
*Ebenfalls bekannt sei die Menge&nbsp; ${I}_{\rm FP}$&nbsp; 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>
 
::<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):
+
*Dann gilt für das&nbsp; '''Error Locator Polynom''' &nbsp;$\rm (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>
 
::<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:
+
Vom <i>Error Locator Polynom</i>&nbsp; wissen wir aufgrund der Definition:
*Wegen des Faktors $x$ vor dem Produktzeichen ist ${\it \Lambda}(x= 0) = 0$.<br>
+
*Wegen des Faktors&nbsp; $x$&nbsp; vor dem Produktzeichen ist&nbsp; ${\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>
+
*Weitere&nbsp; $r$&nbsp; Nullstellen ergeben sich für&nbsp; $x =  \alpha^{i}$&nbsp; mit&nbsp; $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>
+
*Dagegen ergibt das&nbsp; <i>Error Locator Polynom</i>&nbsp; für&nbsp; $i &#8713; I_{\rm FP}$ &nbsp; &#8658; &nbsp; $e_i = 0$&nbsp; 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>
+
Wir suchen also die&nbsp; $r$&nbsp; nichttrivialen Nullstellen von&nbsp; ${\it \Lambda}(x)$&nbsp; mit dem Argument&nbsp; $x &#8712; {\rm GF}(q) \hspace{-0.05cm}\setminus \hspace{-0.05cm} \{0\}$. Gelingt uns dies, so kennen wir die&nbsp; $r$&nbsp; Fehlerpositionen, jedoch noch nicht die tatsächlichen Fehlerwerte&nbsp; $e_i &#8712; {\rm GF}(q)$.<br>
  
 
[[Datei:P ID2549 KC T 2 5 Darstellung v1.png|right|frame|$\rm GF(2^3)$&ndash;Darstellungen]]  
 
[[Datei:P ID2549 KC T 2 5 Darstellung v1.png|right|frame|$\rm GF(2^3)$&ndash;Darstellungen]]  
 
{{GraueBox|TEXT=   
 
{{GraueBox|TEXT=   
 
$\text{Beispiel 3:}$&nbsp;  
 
$\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>
+
Es gelte $n=7$ &nbsp; &#8658; &nbsp; $q=8$,&nbsp; $r=2$&nbsp; und&nbsp; $I_{\rm FP}  = \{2, \hspace{0.05cm}4\}$:  &nbsp; &nbsp; &nbsp; &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)$:
+
Damit erhält man für das&nbsp; <i>Error Locator Poynom</i>&nbsp; aus&nbsp; ${\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>{\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>
 
::<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:
+
Die weiteren Nullstellen $($außer bei&nbsp; $x = 0)$&nbsp; ergeben sich hier natürlich für&nbsp; $x = \alpha^2$&nbsp; und&nbsp; $x = \alpha^4$, wie eine 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^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>
 
::<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&nbsp; $\text{RSC (7, 3, 5)}_8$&nbsp; mit den folgenden Parameterwerten aus:  
Für die weitere Herleitung gehen wir stets vom $\text{RSC (7, 3, 5)}_8$ 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.$$
+
:$$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})$:
+
Die Anzahl der Symbolfehler sei&nbsp; $r = t = 2$. Damit lautet das zu lösende Gleichungssystem mit den Hilfsgrößen&nbsp; $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_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>
Zeile 244: Zeile 248:
 
::<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>
 
::<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)$:
+
In Vektorform lautet dieses Gleichungssystem mit dem Hilfsvektor&nbsp; $\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}
 
::<math>\underline {L}^{\rm T}=\begin{pmatrix}
Zeile 272: Zeile 276:
 
\hspace{0.05cm}.</math>
 
\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:
+
Wir erweitern nun den ELP&ndash;Koeffizientenvektor&nbsp; $\underline {\it \Lambda }$&nbsp; durch Anhängen von Nullen auf die Länge&nbsp; $n-k$.  
 +
 
 +
Im betrachteten Beispiel erhält man somit&nbsp; ${\it \Lambda } = ( \lambda_0,\hspace{0.05cm}\lambda_1,\hspace{0.05cm}1, \hspace{0.05cm}0)$&nbsp; und folgende Vektorgleichung:
  
 
::<math>\underline {L}^{\rm T}
 
::<math>\underline {L}^{\rm T}
Zeile 294: Zeile 300:
  
 
Damit haben wir erreicht:
 
Damit haben wir erreicht:
*Aus der $7&times 3$&ndash;Matrix wurde nun eine $7&times 4$&ndash;Matrix.  
+
*Aus der&nbsp; $7&times 3$&ndash;Matrix wurde nun eine&nbsp; $7&times 4$&ndash;Matrix.  
 
*Die vierte Spalte kann eigentlich beliebig gefüllt werden, da alle Elemente mit Nullen multipliziert werden.  
 
*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 $\text{RSC (7, 3, 5)}_8$.
+
*Durch die hier gewählte Ergänzung erhält man die transponierte&nbsp; [[Kanalcodierung/Definition_und_Eigenschaften_von_Reed%E2%80%93Solomon%E2%80%93Codes#Generatormatrix_und_Pr.C3.BCfmatrix| Prüfmatrix]]&nbsp; des&nbsp; $\text{RSC (7, 3, 5)}_8$.
 
* Somit kann man für die letzte Vektorgleichung schreiben:
 
* Somit kann man für die letzte Vektorgleichung schreiben:
  
Zeile 303: Zeile 309:
 
\hspace{0.05cm}.</math>
 
\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>:
+
Da aber für die Fehlerstellen&nbsp; $(e_i &ne; 0)$&nbsp; stets&nbsp; $L_i = {\it \Lambda}(\alpha^{i}) = 0$&nbsp; gilt, ist das Produkt&nbsp; $L_i \cdot e_i \equiv 0$&nbsp; 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}
 
::<math>\underline {L}^{\rm T}  \cdot \underline {e}^{\rm T} = 0  \hspace{0.3cm} \Rightarrow  \hspace{0.3cm}
Zeile 313: Zeile 319:
 
$\text{Wichtiges Zwischenergebnis:}$&nbsp;  
 
$\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.
+
Die ''nichttrivialen Nullstellen'' &nbsp;$($ungleich $0)$&nbsp; $\lambda_0$, $\lambda_1$,  ... des ''Error Locator Polynoms''&nbsp; ${\it \Lambda}(x)$&nbsp; müssen stets der Vektorgleichung&nbsp; $\underline {\it \Lambda }  \cdot \underline {s}^{\rm T} = 0 $&nbsp; genügen.
*Hierbei bezeichnet  $\underline {\it \Lambda }$ den ''ELP&ndash;Koeffizientenvektor''.
+
*Hierbei bezeichnet&nbsp; $\underline {\it \Lambda }$&nbsp; den &nbsp;$\rm ELP-Koeffizientenvektor$.
* $\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>
+
* $\underline {s }  = \underline {y }\cdot  \boldsymbol{\rm H }^{\rm T} $&nbsp; gibt das&nbsp; [[Kanalcodierung/Fehlerkorrektur_nach_Reed%E2%80%93Solomon%E2%80%93Codierung#Schritt_.28A.29:_Auswertung_des_Syndroms_beim_BDD| Syndrom]]&nbsp; an.}}<br>
  
 
== Schritt (B): Aufstellen/Auswerten des ELP–Koeffizientenvektors ==
 
== Schritt (B): Aufstellen/Auswerten des ELP–Koeffizientenvektors ==
 
<br>
 
<br>
Bevor wir dieses Zwischenergebnis  für den Schritt $\rm (B)$ berücksichtigen können, müssen noch einige Verallgemeinerungen vorgenommen werden. Der Grund hierfür ist:
+
Bevor wir dieses Zwischenergebnis  für den Schritt&nbsp; $\rm (B)$&nbsp; 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>
+
*Die Gleichung&nbsp; $\underline {\it \Lambda }  \cdot \underline {s}^{\rm T} = 0 $&nbsp; liefert nur eine einzige Bestimmungsgleichung. Damit kann das Problem für&nbsp; $r = 1$&nbsp; gelöst werden, wenn man sicher ist, dass tatsächlich nur ein einziges 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>
+
*Ist man sich dessen nicht sicher, führt aber die Berechnung trotzdem für&nbsp; $r = 1$&nbsp; 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>
+
Die Eigenschaft des&nbsp; [[Kanalcodierung/Fehlerkorrektur_nach_Reed–Solomon–Codierung#Error_Locator_Polynom_.E2.80.93_Definition_und_Eigenschaften|''Error Locator Polynoms'']], dass&nbsp; ${\it \Lambda}(\alpha^{i})$&nbsp; nur für&nbsp; $e_i &ne; 0$&nbsp; $(i$&ndash;tes Symbol verfälscht$)$ gleich Null ist, bleibt erhalten, wenn man&nbsp; ${\it \Lambda}(x)$&nbsp; mit beliebigen Potenzen von&nbsp; $x$&nbsp; multipliziert. Jede Multiplikation mit&nbsp; $x$&nbsp; 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]]
 
[[Datei:P ID2550 KC T 2 5 S3 v1.png|center|frame|Verschobene ELP–Koeffizientenvektoren|class=fit]]
Zeile 330: Zeile 336:
 
{{BlaueBox|TEXT=   
 
{{BlaueBox|TEXT=   
 
$\text{Definition:}$&nbsp;  
 
$\text{Definition:}$&nbsp;  
Die '''verallgemeinerten ELP&ndash;Koeffizientenvektoren''' $\underline {\it \Lambda }_l$ ergeben sich durch sukzessive Verschiebungen gegenüber $\underline {\it \Lambda }_l$:
+
Die &nbsp;$\text{verallgemeinerten ELP&ndash;Koeffizientenvektoren}$&nbsp; $\underline {\it \Lambda }_l$&nbsp; ergeben sich durch sukzessive Verschiebungen gegenüber&nbsp; $\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>
 
::<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 }$.}}
+
In dieser Definitionsgleichung  entspricht&nbsp; $\underline {\it \Lambda }_1$&nbsp; dem bisherigen&nbsp; $\underline {\it \Lambda }$.}}
  
  
Die Grafik zeigt die Belegung unter der Annahme von $r$ Fehlerstellen im Fehlervektor$\underline {e}$ für
+
Die Grafik zeigt die Belegung unter der Annahme von&nbsp; $r$&nbsp; Fehlerstellen im Fehlervektor &nbsp;$\underline {e}$&nbsp; für
 
*$r=1$ &nbsp; im linken Bereich (mit blauer Hinterlegung),
 
*$r=1$ &nbsp; im linken Bereich (mit blauer Hinterlegung),
 
*$r=2$ &nbsp; im mittleren Bereich (mit roter Hinterlegung),
 
*$r=2$ &nbsp; im mittleren Bereich (mit roter Hinterlegung),
Zeile 344: Zeile 350:
  
 
Man erkennt:
 
Man erkennt:
*Die Länge aller $\underline {\it \Lambda }_l$&nbsp; 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>
+
*Die Länge aller&nbsp; $\underline {\it \Lambda }_l$&nbsp; ist stets&nbsp; $n-k$. Jeder Vektor beinhaltet jeweils&nbsp; $r$&nbsp; Koeffizienten&nbsp; $\lambda_0$,&nbsp; $\lambda_1$, ... ,&nbsp; $\lambda_{r-1}$ &nbsp; &rArr; &nbsp; $0 &#8804; i < r$&nbsp; und eine Eins. Der Rest eines jeden Vektors ist mit Nullen aufgefüllt.<br>
  
*Für jedes $r$&nbsp; gibt es genau $n-k-r$&nbsp; 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>
+
*Für jedes&nbsp; $r$&nbsp; gibt es genau&nbsp; $n-k-r$&nbsp; Koeffizientenvektoren&nbsp; $\underline {\it \Lambda }_l$, wobei sich&nbsp; $\underline {\it \Lambda }_l$&nbsp; aus&nbsp; $\underline {\it \Lambda }_{l-1}$&nbsp; stets durch Rechtsverschiebung um eine Position ergibt. Der Vektor&nbsp; $\underline {\it \Lambda }_{n-k-r}$&nbsp; endet immer mit einer&nbsp; $1$.<br>
  
*Das Gleichungssystem  $\underline {\it \Lambda }_l  \cdot \underline {s}^{\rm T} = 0 $ führt deshalb zu $n-k-r$&nbsp; Gleichungen. Der gewählte Ansatz für $r$&nbsp; ist nur dann richtig, wenn alle Gleichungen zu den gleichen Ergebnissen für $\lambda_0$,  ... , $\lambda_{r-1}$ führen.<br>
+
*Das Gleichungssystem&nbsp; $\underline {\it \Lambda }_l  \cdot \underline {s}^{\rm T} = 0 $&nbsp; führt deshalb zu&nbsp; $n-k-r$&nbsp; Gleichungen. Der gewählte Ansatz für&nbsp; $r$&nbsp; ist nur dann richtig, wenn alle Gleichungen zu den gleichen Ergebnissen für&nbsp; $\lambda_0$,  ... , $\lambda_{r-1}$&nbsp; führen.<br>
  
*Ist dies nicht der Fall, so muss man $r$&nbsp; erhöhen und damit ein neues Gleichungssystem bearbeiten, und zwar solange, bis sich aus allen Gleichungen für das aktuelle $r$&nbsp; eine eindeutige Lösung ergibt.<br>
+
*Ist dies nicht der Fall, so muss man&nbsp; $r$&nbsp; erhöhen und damit ein neues Gleichungssystem bearbeiten, und zwar solange, bis sich aus allen Gleichungen für das aktuelle&nbsp; $r$&nbsp; eine eindeutige Lösung ergibt.<br>
  
*Ist schließlich $r$&nbsp; größer als die Korrekturfähigkeit $t$ des Codes, so kann die Berechnung beendet werden. Das anstehende Empfangswort $\underline {y}$&nbsp; ist dann nicht decodierbar.<br>
+
*Ist schließlich&nbsp; $r$&nbsp; größer als die Korrekturfähigkeit&nbsp; $t$&nbsp; des Codes, so kann die Berechnung beendet werden. Das anstehende Empfangswort&nbsp; $\underline {y}$&nbsp; ist dann nicht decodierbar.<br>
  
  
 
{{GraueBox|TEXT=   
 
{{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:  
+
$\text{Beispiel 4:}$&nbsp; Es gelten weiterhin die im&nbsp; [[Kanalcodierung/Fehlerkorrektur_nach_Reed%E2%80%93Solomon%E2%80%93Codierung#Schritt_.28A.29:_Auswertung_des_Syndroms_beim_BDD| $\text{Beispiel 2}$]]&nbsp; 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}$.  
+
*Dort wurde aufgrund des Syndroms&nbsp; $\underline {s} = (\alpha^5,\alpha^2,\alpha^3,\alpha^1)  &ne; \underline {0}$&nbsp; auch nachgewiesen, dass der Empfangsvektor&nbsp; $\underline {y}$&nbsp; verfälscht wurde &nbsp; &rArr; &nbsp;  Fehlervektor&nbsp; $\underline {e} \ne \underline {0}$.  
*Nicht bekannt ist allerdings die tatsächliche Symbolfehleranzahl $r$.<br>
+
*Nicht bekannt ist allerdings die tatsächliche Symbolfehleranzahl&nbsp; $r$.<br>
  
  
Unter der Annahme eines einzigen falschen Symbols $(r= 1)$ erhält man folgendes Gleichungssystem (hier in Matrixform geschrieben):
+
Unter der Annahme eines einzigen falschen Symbols&nbsp; $(r= 1)$&nbsp; erhält man folgendes Gleichungssystem (hier in Matrixform geschrieben):
 
[[Datei:P ID2556 KC T 2 5 Darstellung v1.png|right|frame|$\rm GF(2^3)$&ndash;Darstellungen]]
 
[[Datei:P ID2556 KC T 2 5 Darstellung v1.png|right|frame|$\rm GF(2^3)$&ndash;Darstellungen]]
  
Zeile 383: Zeile 389:
 
\hspace{0.05cm}.</math>
 
\hspace{0.05cm}.</math>
  
Dieses Gleichungssystem liefert drei unterschiedliche Lösungen für $\lambda_0$, was nicht zielführend ist:<br>
+
Dieses Gleichungssystem liefert drei unterschiedliche Lösungen für&nbsp; $\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}
 
::<math>\text{Zeile 1:}\hspace{0.5cm}\alpha^5 \cdot \lambda_0 + \alpha^2 = 0 \hspace{0.3cm} \Rightarrow  \hspace{0.3cm}
Zeile 392: Zeile 398:
 
\lambda_0 = \alpha^{1-3}=  \alpha^{-2} = \alpha^{5} \hspace{0.05cm}.</math>
 
\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$:
+
Deshalb stellen wir nun ein weiteres Gleichungssystem auf, und zwar unter der Annahme&nbsp; $r = 2$:
  
 
::<math>\big ({ \boldsymbol{\it \Lambda } }_l \big) \cdot \underline {s} ^{\rm T}=  
 
::<math>\big ({ \boldsymbol{\it \Lambda } }_l \big) \cdot \underline {s} ^{\rm T}=  
Zeile 408: Zeile 414:
 
0\\  
 
0\\  
 
0
 
0
\end{pmatrix} </math>
+
\end{pmatrix}\hspace{0.05cm}. </math>
  
Dies führt zu zwei Gleichungen für $\lambda_0$ und $\lambda_1$:
+
Dies führt zu zwei Gleichungen für&nbsp; $\lambda_0$&nbsp; und&nbsp; $\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>
+
::<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 = 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:  
+
Dieses Gleichungssystem ist nun eindeutig lösbar. Man erhält&nbsp; $\lambda_0 = \alpha^2$&nbsp; und&nbsp; $\lambda_1 = \alpha^6$. Das bedeutet:  
*Die Annahme, dass tatsächlich $r = 2$ Positionen des Empfangsvektors $\underline {y}$ verfälscht wurden, ist richtig.<br>
+
*Die Annahme, dass tatsächlich&nbsp; $r = 2$&nbsp; Positionen des Empfangsvektors&nbsp; $\underline {y}$&nbsp; verfälscht wurden, ist richtig.<br>
*Man weiß aber noch nicht, welche Positionen verfälscht wurden. Soviel vorneweg:  
+
*Man weiß aber noch nicht, welche Positionen verfälscht wurden. &nbsp; Soviel vorneweg:  
*Es sind nicht die Symbolpositionen 2 und 6, sondern die Positionen 0 und 2, wie im folgenden Beispiel 5 gezeigt wird.}}<br>  
+
*Es sind nicht die Symbolpositionen 2 und 6, sondern die Positionen 0 und 2, wie im folgenden&nbsp; $\text{Beispiel 5}$&nbsp; (nächste Seite) gezeigt wird.}}<br>  
  
  
 
== Schritt (C): Lokalisierung der Fehlerstellen ==
 
== Schritt (C): Lokalisierung der Fehlerstellen ==
 
<br>
 
<br>
Nach Abarbeitung von Schritt '''(B)''' sind bekannt:
+
Nach Abarbeitung von Schritt&nbsp; $\rm(B)$&nbsp; 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 Anzahl&nbsp; $r$&nbsp; der Fehlerstellen&nbsp; $e_i &ne; 0$&nbsp; im Vektor&nbsp; $\underline {e} = (e_0, \hspace{0.05cm}\text{... }\hspace{0.05cm}, e_i, \hspace{0.05cm}\text{... }\hspace{0.05cm}, e_{n-1})$,<br>
  
*die Koeffizienten $\lambda_0, \text{... } , \lambda_{r-1}$ des <i>Error Locator Polynoms</i>.<br><br>
+
*die Koeffizienten&nbsp; $\lambda_0, \hspace{0.05cm}\text{... }\hspace{0.05cm} , \lambda_{r-1}$&nbsp; 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}.$
 
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.):
+
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 so genannte <i>Chien&ndash;Suche</i>, in dem man durch Einsetzen der möglichen Codesymbole außer dem Nullsymbol &nbsp; &rArr; &nbsp; $(\alpha^0, \text{... }, \alpha^i, \text{... },\alpha^{n-1})$&nbsp; in das <i>Error Locator Polynom</i>&nbsp; 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>
+
*die Auswertung der Gleichung&nbsp; $\underline {L} = (L_0, \text{... }, L_i, \text{... },L_{n-1} ) = \underline {\it \Lambda } \cdot { \boldsymbol{\rm H }}$&nbsp; mit der Abkürzung&nbsp; $L_i = {\it \Lambda}(\alpha^i)$.<br><br>
  
 +
[[Datei:P ID2557 KC T 2 5 Darstellung v1.png|right|frame|$\rm GF(2^3)$&ndash;Darstellungen]]
 
{{GraueBox|TEXT=   
 
{{GraueBox|TEXT=   
 
$\text{Beispiel 5:}$&nbsp;  
 
$\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
+
Im&nbsp; [[Kanalcodierung/Fehlerkorrektur_nach_Reed%E2%80%93Solomon%E2%80%93Codierung#Schritt_.28B.29:_Aufstellen.2FAuswerten_des_ELP.E2.80.93Koeffizientenvektors| $\text{Beispiel 4}$]]&nbsp; wurde entsprechend den in&nbsp; [[Kanalcodierung/Fehlerkorrektur_nach_Reed%E2%80%93Solomon%E2%80%93Codierung#Schritt_.28A.29:_Auswertung_des_Syndroms_beim_BDD| $\text{Beispiel 2}$]]&nbsp; genannten Randbedingungen ermittelt, dass
*$r= 2$ Symbolfehler vorliegen, und  
+
*$r= 2$&nbsp; 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>:
+
*die ELP&ndash;Koeffizienten&nbsp; $\lambda_0 = \alpha^2$&nbsp; und&nbsp; $\lambda_1 = \alpha^6$&nbsp; lauten.  
 +
 
 +
 
 +
Damit ergibt sich folgendes <i>Error Locator Polynom</i>:
  
 
::<math>{\it \Lambda}(x)=x \cdot \big [{\it \lambda}_0 + \lambda_1 \cdot x+x^2 \big ]
 
::<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>
 
=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
 
Entsprechend der Chien&ndash;Suche erhält man
  
Zeile 451: Zeile 460:
 
  \hspace{0.3cm} \Rightarrow  \hspace{0.3cm}{ \boldsymbol{\rm Nullstelle} }\hspace{0.05cm}.</math>
 
  \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>
+
Damit sind die beiden Fehlerpositionen mit&nbsp; $i = 0$&nbsp; und&nbsp; $i = 2$&nbsp; gefunden &nbsp; &rArr; &nbsp; der Fehlervektor lautet: &nbsp; $\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:
+
Die Vektorgleichung&nbsp; $\underline {L} = \underline {\it \Lambda } \cdot { \boldsymbol{\rm H } }$&nbsp; liefert das gleiche Ergebnis in kompakterer Form:
  
 
::<math>\underline {L} = \underline{\it \Lambda} \cdot  { \boldsymbol{\rm H } }  = (\alpha^2, \alpha^6, 1, 0) \cdot
 
::<math>\underline {L} = \underline{\it \Lambda} \cdot  { \boldsymbol{\rm H } }  = (\alpha^2, \alpha^6, 1, 0) \cdot
Zeile 469: Zeile 477:
 
\underline {e} = (e_0, 0, e_2, 0, 0, 0, 0)\hspace{0.05cm}.</math>
 
\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>
+
Das Beispiel wird mit dem&nbsp; $\text{Beispiel 6}$&nbsp; auf der nächsten Seite fortgesetzt.}}<br>
  
 
== Schritt (D): Abschließende Fehlerkorrektur ==
 
== Schritt (D): Abschließende Fehlerkorrektur ==
 
<br>
 
<br>
Im letzten Schritt müssen nun nur noch die $r$ Symbolfehler korrigiert werden, deren Positionen nach Beendigung von Schritt '''(C)''' bekannt sind:
+
Im letzten Schritt müssen nun nur noch die&nbsp; $r$&nbsp; Symbolfehler korrigiert werden, deren Positionen nach Beendigung von Schritt&nbsp; $\rm (C)$&nbsp; 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>
+
*Markiert man die Fehlerpositionen im Empfangswort&nbsp; $\underline {y}$&nbsp; als Auslöschungen&nbsp; $\rm E$&nbsp; (<i>Erasures</i>&nbsp;), so kann das zugehörige Codewort&nbsp; $\underline {z}$&nbsp; entsprechend der Beschreibung im Kapitel&nbsp; [[Kanalcodierung/Reed–Solomon–Decodierung_beim_Auslöschungskanal|Reed–Solomon–Decodierung beim Auslöschungskanal]]&nbsp; 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>
+
*Eine zweite Möglichkeit bietet die Bestimmung des Fehlervektors&nbsp; $\underline {e}$&nbsp; aus der Gleichung&nbsp; $\underline {e}  \cdot  \boldsymbol{\rm H }^{\rm T} = \underline {s}$&nbsp; und die Korrektur entsprechend&nbsp; $\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]]  
+
[[Datei:P ID2558 KC T 2 5 Darstellung v1.png|right|frame|$\rm GF(2^3)$&ndash;Darstellungen]]  
 
{{GraueBox|TEXT=   
 
{{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  
+
$\text{Beispiel 6:}$&nbsp; Wir betrachten wieder den&nbsp; $\text{RSC (7, 3, 5)}_8$. Im&nbsp; [[Kanalcodierung/Fehlerkorrektur_nach_Reed%E2%80%93Solomon%E2%80%93Codierung#Schritt_.28A.29:_Auswertung_des_Syndroms_beim_BDD| $\text{Beispiel 2}$]]&nbsp; 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  
+
*das Empfangswort mit&nbsp; $\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)$&nbsp; 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)$
+
*daraus das Syndrom&nbsp; $\underline{s}=\big (\alpha^5,\hspace{0.05cm}\alpha^2, \hspace{0.05cm} \alpha^3, \hspace{0.05cm} \alpha^1\big)$&nbsp; ermittelt.
  
  
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>
+
Nach den Berechnungen im&nbsp; [[Kanalcodierung/Fehlerkorrektur_nach_Reed%E2%80%93Solomon%E2%80%93Codierung#Schritt_.28C.29:_Lokalisierung_der_Fehlerstellen| $\text{Beispiel 5}$]]&nbsp; lautet der Fehlervektor&nbsp; $\underline {e} = (e_0, 0, e_2, 0, 0, 0, 0)$. <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$:
+
Aus &nbsp;$\underline {e}  \cdot  \boldsymbol{\rm H }^{\rm T} = \underline {s}$&nbsp; erhält man nun folgende Bestimmungsgleichungen für die Fehlerwerte&nbsp; $e_0$&nbsp; und&nbsp; $e_2$:
  
 
::<math>\underline {e}  \cdot \boldsymbol{\rm H }^{\rm T}= \begin{pmatrix}
 
::<math>\underline {e}  \cdot \boldsymbol{\rm H }^{\rm T}= \begin{pmatrix}
Zeile 512: Zeile 520:
 
e_0 + e_2 \cdot \alpha^1 = \alpha^1\hspace{0.05cm}.</math>
 
e_0 + e_2 \cdot \alpha^1 = \alpha^1\hspace{0.05cm}.</math>
  
 +
Alle Gleichungen führen zum Ergebnis &nbsp;$e_0 = 1$&nbsp; und &nbsp;$e_2 =\alpha^2$.
  
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)$:
+
Damit  lautet das korrigierte Codewort mit&nbsp; $\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)$&nbsp; und&nbsp; $\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}=
 
::<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>
 
(\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>
+
Dieses ist ein gültiges Codewort von&nbsp; $\text{RSC (7, 3, 5)}_8$.}}<br>
  
 
== Schnelle Reed–Solomon–Decodierung ==
 
== Schnelle Reed–Solomon–Decodierung ==
 
<br>
 
<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>
+
Die Klasse der Reed&ndash;Solomon&ndash;Codes wurde bereits im Jahre 1960 durch die Veröffentlichung&nbsp; [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>
+
Auf den letzten Seiten haben wir den so genannten Petersen&ndash;Algorithmus inklusive der Chien&ndash;Suche am Beispiel des&nbsp; $\text{RSC (7, 3, 5)}_8$&nbsp; demonstriert, der bis zu&nbsp; $t = 2$&nbsp; Fehler korrigieren kann. Im Mittelpunkt des Decodiervorgangs stand dabei das Aufstellen und Lösen der Schlüsselgleichung (englisch: &nbsp; <i>Error Locator Polynom</i>&nbsp;), wobei die Nullstellen eines Grad&ndash;$2$&ndash;Polynoms im Körper&nbsp; $\rm GF(7)$&nbsp; gefunden werden mussten. Es war zu 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>
+
Bei den in Praxis eingesetzten Codes mit großer Codewortlänge&nbsp; $n$&nbsp; und hoher Korrekturfähigkeit&nbsp; $t$&nbsp; würde der Decodieraufwand explodieren, wenn nicht schnellere Decodieralgorithmen gefunden worden wären. So müssen beim Reed&ndash;Solomon&ndash;Code&nbsp; $\text{RSC (255, 223, 33)}_{256}$, der schon früh im ESA/NASA&ndash;Standard zur Satellitenübertragung genannt wurde, zur Decodierng eines einzigen Codewortes bis zu&nbsp; $t = 16$&nbsp; Nullstellen im Körper&nbsp; $\rm GF(255)$&nbsp; gefunden werden. Und das in Echtzeit!<br>
  
 
Ab Ende der 1960er Jahre haben sich viele Wissenschaftler um schnellere Decodieralgorithmen für  Reed&ndash;Solomon&ndash;Codes bemüht:
 
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>
+
*Beim&nbsp; [https://de.wikipedia.org/wiki/Berlekamp-Massey-Algorithmus Berlekamp&ndash;Massey&ndash;Algorithmus]&nbsp; $\rm (BMA)$&nbsp; wird die Schlüsselgleichung&nbsp; $\underline {\it \Lambda}  \cdot  \underline{s }^{\rm T} = 0$&nbsp; als rückgekoppeltes Schieberegister dargestellt, siehe zum Beispiel&nbsp; [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>,&nbsp; [Fri96]<ref name ='Fri96'>Friedrichs, B.: ''Kanalcodierung – Grundlagen und Anwendungen in modernen Kommunikations- systemen.'' Berlin – Heidelberg: Springer, 1996.</ref> und&nbsp; [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>
+
*Etwas später wurde in&nbsp; [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>&nbsp; ein Decodierverfahren vorgeschlagen, das auf dem&nbsp; [https://de.wikipedia.org/wiki/Euklidischer_Algorithmus Euklidischen Algorithmus]&nbsp; basiert. Dieser liefert den größten gemeinsamen Teiler zweier ganzer Zahlen, was zur Decodierung genutzt wird. Der Euklidische Algorithmus ist vergleichbar schnell wie der&nbsp; $\rm BMA$. Genauere Informationen finden Sie wieder in&nbsp; [Bos98]<ref name ='Bos98'></ref> und&nbsp; [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>
+
*Weitere effiziente Decodiermethoden von Reed&ndash;Solomon&ndash;Codes arbeiten im <i>Frequenzbereich</i>&nbsp; unter Verwendung der&nbsp; [[Signaldarstellung/Diskrete_Fouriertransformation_(DFT)#Argumente_f.C3.BCr_die_diskrete_Realisierung_der_FT| Diskreten Fouriertransformation]]&nbsp; $\rm (DFT)$&nbsp; im Körper&nbsp; ${\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.
 
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.

Aktuelle Version vom 21. Oktober 2022, 16:15 Uhr

Blockschaltbild und Voraussetzungen zur RS–Fehlerkorrektur


Wie im Kapitel  Decodierung beim Auslöschungskanal  betrachten wir ein Übertragungssystem mit Reed–Solomon–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}$:

\[\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}.\]

Die Informationssymbole  $u_i$  und auch die Codesymbole  $C_i$  entstammen dem Körper  ${\rm GF}(q)$  mit  $q=n+1=2^m$; sie sind durch  $m$  Binärsymbole (Bit) darstellbar.

Übertragungssystem mit Reed–Solomon–Codierung/Decodierung und  $m$–BSC

Ein Vergleich dieses Blockschaltbildes mit dem entsprechenden  Blockschaltbild zur RS–Fehlererkennung  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. Ein Bitfehler bezüglich des $i$–ten Bits ergibt  $y_i \ne c_i$.
  • Im  letzten Kapitel  waren unsichere Bits bereits durch Auslöschungen  $\rm E$  (Erasures ) markiert. Aufgabe des  Codewortfinders  $\rm (CWF)$ war es, 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})$  war beim BEC ausgeschlossen.
  • In diesem Kapitel wird nun der erste Decoderblock als  Codewortschätzer  $\rm (CWS)$ bezeichnet. Die Namensgebung soll deutlich machen, dass aufgrund des  $m$–BSC–Modells Fehlentscheidungen  $(\underline {z} \ne \underline {c})$  unvermeidlich sind, nämlich dann, wenn mehrere Symbolfehler das Empfangswort  $\underline {y}$  zu einem gültigen Codewort verfälschen.

$\text{Fazit:}$ 

  • Aufgabe des Decoders ist es, seinen Ausgangsvektor  $\underline {v}$  so zu bestimmen, dass er „möglichst gut” mit dem Informationswort  $\underline {u}$  übereinstimmt. Exakter formuliert:
\[{ \rm Pr(Blockfehler)} = { \rm Pr}( \underline{v} \ne \underline{u}) \stackrel{!}{=} { \rm Minimum}\hspace{0.05cm}.\]
  • Aufgrund des deterministischen Mappings  $\underline{c} = {\rm enc}(\underline{u})$  und  $\underline{v} = {\rm enc}^{-1}(\underline{z})$  gilt in gleicher Weise:
\[{ \rm Pr(Blockfehler)} = { \rm Pr}( \underline{z} \ne \underline{c}) \stackrel{!}{=} { \rm Minimum}\hspace{0.05cm}.\]


Die zwei gelb hinterlegten Blöcke werden im Folgenden nicht weiter betrachtet. Im Mittelpunkt der Betrachtungen steht nun der rot hinterlegte Codewortschätzer  $\rm (CWS)$.

Mögliche Codewortschätzer für die RS–Decodierung


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

Zur Definition des Fehlervektors  $\underline{e}$

Diese Aufgabenstellung soll durch ein Beispiel verdeutlicht werden.

Drei Darstellungsformen für  $\rm GF(2^3)$

$\text{Beispiel 1:}$  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.

Codewort und Empfangswort lauten in diesem Beispiel in Koeffizientendarstellung:

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

Damit ergibt sich für den Fehlervektor  $\underline{e} = \underline{y} - \underline{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} = \Big ( \alpha^1, \hspace{0.09cm}1\hspace{0.09cm}, \alpha^2,\alpha^1,\alpha^2,\alpha^5,\alpha^5\Big )\hspace{0.05cm},\]
\[\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},\]
\[\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}.\]


Aufgabe des Codewortschätzers  $\rm (CWS)$  ist es, das zu  $\underline{y}$  wahrscheinlichste Codewort  $\underline{c}_i$  zu finden und sein Ergebnis  $\underline{z} = \underline{c}_i$  an das nachfolgende Mapping weiterzugeben. Hierzu gibt es verschiedene Möglichkeiten:

  • Hard Decision Maximum Likelihood Decoding  $\text{(HD–MLD)}$,
  • Bounded Distance Decoding  $\text{(BDD)}$,
  • Decodierung über die halbe Mindestdistanz.

Diese Decodierprinzipien werden im Folgenden beschrieben.


Hard Decision Maximum Likelihood Decoding  $\text{(HD–MLD)}$:

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

\[\underline{z} = {\rm arg} \min_{\underline{c}_{\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  ${\rm Pr}(\underline{c}_i\hspace{0.05cm}|\hspace{0.05cm}\underline{y})$  und führt zum bestmöglichen Ergebnis. Näheres siehe  ML–Entscheidung beim BSC–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.

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


Bounded Distance Decoding  $\text{(BDD)}$:

Falls die Anzahl  $r$  der Symbolfehler im Empfangswort  $\underline{y}$  nicht größer ist als die Korrekturfähigkeit  $t = ⌊(d_{\rm min}- 1)/2⌋$  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 Erasure.


Decodierung über die halbe Mindestdistanz:

Hier wird auch im Fall  $r > t$  versucht, das Codewort zu decodieren. Im Gegensatz zu  $\text{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 Decoding  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.


$\rm (A)$   $\text{Berechnung und Auswertung des Syndroms}$   ⇒   Detaillierte Beschreibung

  • Berechne aus dem Empfangswort  $\underline{y}$  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–Ausgang  $\underline {z} =\underline {y}$  und beende den Decodiervorgang für dieses Empfangswort.
  • Andernfalls setze den Parameter  $r = 1$  und mache mit Schritt  $\rm (B)$  weiter.


$\rm (B)$   $\text{Bestimmung der tatsächlichen Symbolfehleranzahl } r$  ⇒   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.
  • $\underline {\it \Lambda} _l $  bezeichnet die verallgemeinerten  $\text{ELP}$–Koeffizientenvektoren, wobei „$\text{ELP}$” für  Error Locator Polynom  steht, und  $t$  die Korrekturfähigkeit des Codes angibt.
    Für die Reed–Solomon–Codes gilt einheitlich  $t = ⌊(n-k)/2 ⌋$.
  • Gibt es eine eindeutige Lösung, dann mache mit Schritt  $\rm (C)$  weiter.  Im Empfangsvektor  $\underline{y}$  sind dann tatsächlich genau  $r$  Symbole verfälscht und im Fehlervektor  $\underline{e}$  gibt es  $r$  Einträge ungleich $0$.
  • Andernfalls erhöhe  $r$  um  $1$.   Falls  $r ≤ t$, dann wiederhole Schritt  $\rm (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.


$\rm (C)$   $\text{Lokalisierung der }r \text{ Fehlerpositionen}$  ⇒   Detaillierte Beschreibung

  • Erstelle das  Error Locator Polynom  ${\it \Lambda}(x)$  und finde dessen  $r$  Nullstellen in  ${\rm GF}(q) \hspace{-0.05cm}\setminus \hspace{-0.05cm} \{0\}$.
  • Ein Fehler an der Stelle  $i$  liegt immer dann vor, wenn  ${\it \Lambda}(\alpha^{i}) = 0$  ist.


$\rm (D)$   $\text{Bestimmung der }r \text{ Fehlerwerte und Korrektur}$  ⇒   Detaillierte Beschreibung

  • Bekannt sind nun die  $r$  Fehlerstellen. Ersetzt man im Empfangsvektor  $\underline{y}$  die falschen Symbole durch Auslöschungen   ⇒   $y_i = \rm E$, falls  $e_i ≠ 0$, so findet man das Ergebnis  $\underline{y}$  entsprechend dem Kapitel  Reed–Solomon–Decodierung beim Auslöschungskanal.
  • 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)$.

Schritt (A): Auswertung des Syndroms beim BDD


Wie im Abschnitt  Prinzip der Syndromdecodierung  gezeigt wurde, 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:

\[\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}.\]

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

$\rm GF(2^3)$–Darstellungen

$\text{Beispiel 2:}$  Diesem und den folgenden Beispielen auf den nächsten Seiten liegt stets der Reed–Solomon–Code  $\text{RSC (7, 3, 5)}_8$  zugrunde, so dass die in der Grafik angegebenen Umrechnungen in  $\rm GF(2^3)$  genutzt werden können. Das Empfangswort lautet:

\[\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).\]

Mit der  Prüfmatrix  $\boldsymbol{\rm H }$  ergibt sich für das Syndrom:

\[\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}. \]

Diese Vektor–Matrix–Multiplikationen liefert das Ergebnis:

\[\underline {s} \hspace{-0.05cm} = \hspace{-0.05cm} (\alpha^3 , \alpha^3 , \alpha^3 , \alpha^3) + (\alpha^1 , \alpha^2 , \alpha^3 , \alpha^4) + (0,0,0,0) \hspace{-0.05cm}+\hspace{-0.05cm} (\alpha^4,1,\alpha^3,\alpha^6)+(\alpha^6,\alpha^3,1,\alpha^4)\hspace{-0.05cm}+\hspace{-0.05cm}(\alpha^3,\alpha^1,\alpha^6,\alpha^4) \hspace{-0.05cm}+\hspace{-0.05cm} (\alpha^4,\alpha^3,\alpha^2,\alpha^1)\]
\[\Rightarrow \hspace{0.3cm} \underline {s} = \text{...} \hspace{0.05cm}= (\alpha^5,\alpha^2,\alpha^3,\alpha^1) \hspace{0.05cm}.\]

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

Die Beschreibung des Decodiervorgangs beim  $\text{RSC (7, 3, 5)}_8$  wird im  $\text{Beispiel 4}$  fortgesetzt.


Error Locator Polynom – Definition und Eigenschaften


Nach der Syndromberechnung im Schritt  $\rm (A)$  mit dem Ergebnis  $\underline{s} \ne \underline{0}$  wissen wir,

  • dass das Empfangswort  $\underline{y}$  nicht mit dem Codewort  $\underline{c}$  übereinstimmt, bzw.
  • 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.

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

Einen Lösungsansatz für diese Aufgabe bietet das so genannte  Error Locator Polynom, das von  William Wesley Peterson  eingeführt wurde   ⇒   siehe [Pet60]Referenzfehler: Ungültige Verwendung von <ref>: Der Parameter „name“ ist ungültig oder zu lang.. Im Deutschen ist hierfür auch der Begriff „Schlüsselgleichung” üblich.

$\text{Definition:}$  Es sei bekannt, dass genau  $r$  Elemente des Fehlervektors  $\underline{e}$  ungleich Null sind, erkennbar am  Hamming–Gewicht  $w_{\rm H}(\underline{e}) = r$.

  • Ebenfalls bekannt sei die Menge  ${I}_{\rm FP}$  der Fehlerpositionen:
\[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}.\]
  • Dann gilt für das  Error Locator Polynom  $\rm (ELP)$:
\[{\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 ].\]


Vom Error Locator Polynom  wissen wir aufgrund der Definition:

  • Wegen des Faktors  $x$  vor dem Produktzeichen ist  ${\it \Lambda}(x= 0) = 0$.
  • Weitere  $r$  Nullstellen ergeben sich für  $x = \alpha^{i}$  mit  $i \in I_{\rm FP}$, das heißt, für alle Fehlerpositionen.
  • Dagegen ergibt das  Error Locator Polynom  für  $i ∉ I_{\rm FP}$   ⇒   $e_i = 0$  keine Nullstelle:   ${\it \Lambda}(x= \alpha^{i}) \ne0$.

Wir suchen also die  $r$  nichttrivialen Nullstellen von  ${\it \Lambda}(x)$  mit dem Argument  $x ∈ {\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 ∈ {\rm GF}(q)$.

$\rm GF(2^3)$–Darstellungen

$\text{Beispiel 3:}$  Es gelte $n=7$   ⇒   $q=8$,  $r=2$  und  $I_{\rm FP} = \{2, \hspace{0.05cm}4\}$:        P ID2551 KC T 2 5 S5a.png

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

\[{\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 ] \]
\[\Rightarrow \hspace{0.3cm} {\it \Lambda}(x)= x \cdot \big [\alpha^6 + \alpha \cdot x + x^2\big ]\hspace{0.05cm}.\]

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

\[{\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},\]
\[ {\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}.\]


Für die weitere Herleitung gehen wir stets vom  $\text{RSC (7, 3, 5)}_8$  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})$:

\[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},\]
\[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},\]
\[...\]
\[ 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}.\]

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)$:

\[\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}.\]

Wir erweitern nun den ELP–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:

\[\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}.\]

Damit haben wir erreicht:

  • Aus der  $7× 3$–Matrix wurde nun eine  $7× 4$–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  Prüfmatrix  des  $\text{RSC (7, 3, 5)}_8$.
  • Somit kann man für die letzte Vektorgleichung schreiben:
\[\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}.\]

Da aber für die Fehlerstellen  $(e_i ≠ 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 Error Locator Polynoms:

\[\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}.\]

$\text{Wichtiges Zwischenergebnis:}$ 

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  $\rm ELP-Koeffizientenvektor$.
  • $\underline {s } = \underline {y }\cdot \boldsymbol{\rm H }^{\rm T} $  gibt das  Syndrom  an.


Schritt (B): Aufstellen/Auswerten des ELP–Koeffizientenvektors


Bevor wir dieses Zwischenergebnis für den Schritt  $\rm (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 einziges Symbol verfälscht wurde.
  • 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.

Die Eigenschaft des  Error Locator Polynoms, dass  ${\it \Lambda}(\alpha^{i})$  nur für  $e_i ≠ 0$  $(i$–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–Koeffizientenvektor eine Verschiebung um eine Stelle nach rechts.

Verschobene ELP–Koeffizientenvektoren

$\text{Definition:}$  Die  $\text{verallgemeinerten ELP–Koeffizientenvektoren}$  $\underline {\it \Lambda }_l$  ergeben sich durch sukzessive Verschiebungen gegenüber  $\underline {\it \Lambda }_l$:

\[{\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}.\]

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}$   ⇒   $0 ≤ i < r$  und eine Eins. Der Rest eines jeden Vektors ist mit Nullen aufgefüllt.
  • 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$.
  • 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.
  • 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.
  • 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.


$\text{Beispiel 4:}$  Es gelten weiterhin die im  $\text{Beispiel 2}$  genannten Voraussetzungen:

  • Dort wurde aufgrund des Syndroms  $\underline {s} = (\alpha^5,\alpha^2,\alpha^3,\alpha^1) ≠ \underline {0}$  auch nachgewiesen, dass der Empfangsvektor  $\underline {y}$  verfälscht wurde   ⇒   Fehlervektor  $\underline {e} \ne \underline {0}$.
  • Nicht bekannt ist allerdings die tatsächliche Symbolfehleranzahl  $r$.


Unter der Annahme eines einzigen falschen Symbols  $(r= 1)$  erhält man folgendes Gleichungssystem (hier in Matrixform geschrieben):

$\rm GF(2^3)$–Darstellungen
\[\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}.\]

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

\[\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},\]
\[\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},\]
\[\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}.\]

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

\[\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}\hspace{0.05cm}. \]

Dies führt zu zwei Gleichungen für  $\lambda_0$  und  $\lambda_1$:

\[\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 = 0 \hspace{0.05cm}.\]

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.
  • 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  $\text{Beispiel 5}$  (nächste Seite) gezeigt wird.



Schritt (C): Lokalisierung der Fehlerstellen


Nach Abarbeitung von Schritt  $\rm(B)$  sind bekannt:

  • die Anzahl  $r$  der Fehlerstellen  $e_i ≠ 0$  im Vektor  $\underline {e} = (e_0, \hspace{0.05cm}\text{... }\hspace{0.05cm}, e_i, \hspace{0.05cm}\text{... }\hspace{0.05cm}, e_{n-1})$,
  • die Koeffizienten  $\lambda_0, \hspace{0.05cm}\text{... }\hspace{0.05cm} , \lambda_{r-1}$  des Error Locator Polynoms.

Zu bestimmen ist nun noch die Menge der Fehlerpositionen:   $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 Chien–Suche, in dem man durch Einsetzen der möglichen Codesymbole außer dem Nullsymbol   ⇒   $(\alpha^0, \text{... }, \alpha^i, \text{... },\alpha^{n-1})$  in das Error Locator Polynom  dessen Nullstellen ermittelt,
  • 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)$.

$\rm GF(2^3)$–Darstellungen

$\text{Beispiel 5:}$  Im  $\text{Beispiel 4}$  wurde entsprechend den in  $\text{Beispiel 2}$  genannten Randbedingungen ermittelt, dass

  • $r= 2$  Symbolfehler vorliegen, und
  • die ELP–Koeffizienten  $\lambda_0 = \alpha^2$  und  $\lambda_1 = \alpha^6$  lauten.


Damit ergibt sich folgendes Error Locator Polynom:

\[{\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}.\]

Entsprechend der Chien–Suche erhält man

\[{\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},\]
\[{\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},\]
\[{\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}.\]

Damit sind die beiden Fehlerpositionen mit  $i = 0$  und  $i = 2$  gefunden   ⇒   der Fehlervektor lautet:   $\underline {e} = (e_0, 0, e_2, 0, 0, 0, 0)$ .

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

\[\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} \]
\[ \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) \]
\[ \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}.\]

Das Beispiel wird mit dem  $\text{Beispiel 6}$  auf der nächsten Seite fortgesetzt.


Schritt (D): Abschließende Fehlerkorrektur


Im letzten Schritt müssen nun nur noch die  $r$  Symbolfehler korrigiert werden, deren Positionen nach Beendigung von Schritt  $\rm (C)$  bekannt sind:

  • Markiert man die Fehlerpositionen im Empfangswort  $\underline {y}$  als Auslöschungen  $\rm E$  (Erasures ), so kann das zugehörige Codewort  $\underline {z}$  entsprechend der Beschreibung im Kapitel  Reed–Solomon–Decodierung beim Auslöschungskanal  gefunden werden.
  • 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.

$\rm GF(2^3)$–Darstellungen

$\text{Beispiel 6:}$  Wir betrachten wieder den  $\text{RSC (7, 3, 5)}_8$. Im  $\text{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  $\text{Beispiel 5}$  lautet der Fehlervektor  $\underline {e} = (e_0, 0, e_2, 0, 0, 0, 0)$.

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$:

\[\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} \]
\[\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)\]
\[\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}.\]

Alle 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)$:

\[\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}. \]

Dieses ist ein gültiges Codewort von  $\text{RSC (7, 3, 5)}_8$.


Schnelle Reed–Solomon–Decodierung


Die Klasse der Reed–Solomon–Codes wurde bereits im Jahre 1960 durch die Veröffentlichung  [RS60][1] eingeführt. Ihre effiziente Decodierung war jedoch erst ein bis zwei Jahrzehnte später möglich.

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

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–Solomon–Code  $\text{RSC (255, 223, 33)}_{256}$, der schon früh im ESA/NASA–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 in Echtzeit!

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

  • Beim  Berlekamp–Massey–Algorithmus  $\rm (BMA)$  wird die Schlüsselgleichung  $\underline {\it \Lambda} \cdot \underline{s }^{\rm T} = 0$  als rückgekoppeltes Schieberegister dargestellt, siehe zum Beispiel  [Mas69][2],  [Fri96][3] und  [Bos98][4]. Das Problem wird damit auf die Synthese eines autoregressiven Filters zurückgeführt. Dieser Algorithmus arbeitet wesentlich schneller als der (leichter durchschaubare) Petersen–Algorithmus.
  • Etwas später wurde in  [SK+75][5]  ein Decodierverfahren vorgeschlagen, das auf dem  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  $\rm BMA$. Genauere Informationen finden Sie wieder in  [Bos98][4] und  [Fri96][3].
  • Weitere effiziente Decodiermethoden von Reed–Solomon–Codes arbeiten im Frequenzbereich  unter Verwendung der  Diskreten Fouriertransformation  $\rm (DFT)$  im Körper  ${\rm GF}(n)$.

Die Grundzüge der Reed–Solomon–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


Aufgabe 2.12: Decodierung beim RSC (7, 4, 4) zur Basis 8

Aufgabe 2.12Z: Reed–Solomon–Syndromberechnung

Aufgabe 2.13: Decodierung beim RSC (7, 3, 5) zur Basis 8

Aufgabe 2.14: Petersen–Algorithmus

Quellenverzeichnis

  1. Reed, I.S.; Solomon, G.: Polynomial Codes over Certain Finite Fields. J. Siam, Vol. 8, pp. 300–304, 1960.
  2. Massey, J.L.: Shift Register Synthesis and BCH Decoding.. IEEE Trans. on Information Theory, vol. IT-15, pp. 122–127, Jan. 1969.
  3. 3,0 3,1 Friedrichs, B.: Kanalcodierung – Grundlagen und Anwendungen in modernen Kommunikations- systemen. Berlin – Heidelberg: Springer, 1996.
  4. 4,0 4,1 Bossert, M.: Kanalcodierung. Stuttgart: B. G. Teubner, 1998.
  5. 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.