Kanalcodierung/Fehlerkorrektur nach Reed–Solomon–Codierung - Versionsgeschichte

Guenter am 21. Oktober 2022 um 15:15 Uhr

2022-10-21T15:15:32Z

Guenter am 29. Mai 2019 um 10:01 Uhr

2019-05-29T10:01:42Z

Änderungen zeigen

Guenter am 24. Mai 2019 um 16:17 Uhr

2019-05-24T16:17:17Z

Änderungen zeigen

Guenter am 24. Mai 2019 um 14:45 Uhr

2019-05-24T14:45:14Z

Änderungen zeigen

Guenter am 24. Mai 2019 um 14:06 Uhr

2019-05-24T14:06:50Z

Guenter am 24. Mai 2019 um 13:59 Uhr

2019-05-24T13:59:52Z

Guenter am 10. Juli 2018 um 12:13 Uhr

2018-07-10T12:13:01Z

Guenter am 10. Juli 2018 um 12:09 Uhr

2018-07-10T12:09:52Z

Guenter am 10. Juli 2018 um 12:08 Uhr

2018-07-10T12:08:47Z

Guenter am 10. Juli 2018 um 12:04 Uhr

2018-07-10T12:04:01Z

@@ Zeile 20: / Zeile 20: @@
 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&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;Bits  ergibt&nbsp; $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&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.

← Nächstältere Version		Version vom 24. Mai 2019, 14:06 Uhr
Zeile 38:		Zeile 38:


−	Die zwei gelb hinterlegten Blöcke werden im Folgenden nicht weiter betrachtet. Im Mittelpunkt der Betrachtungen steht der rot hinterlegte <i>Codewortschätzer</i>  $\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>  $\rm (CWS)$.<br>

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

@@ Zeile 8: / Zeile 8: @@
 == Blockschaltbild und Voraussetzungen zur RS&ndash;Fehlerkorrektur ==
 <br>
-Wie im Kapitel [[Kanalcodierung/Reed–Solomon–Decodierung_beim_Auslöschungskanal#Blockschaltbild_und_Voraussetzungen_zur_RS.E2.80.93Fehlererkennung|Decodierung beim Auslöschungskanal]] betrachten wir ein Übertragungssystem mit Reed&ndash;Solomon&ndash;Codierung, das durch die beiden Codeparameter $n=2^m-1$ und $k$ gekennzeichnet  ist. Mit der Generatormatrix $\boldsymbol{\rm G}$ lautet der Zusammenhang zwischen dem Informationswort $\underline {u}$ und dem Codewort  $\underline {c}$:
+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}}
@@ Zeile 15: / Zeile 15: @@
 \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;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.
-*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=
-$\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;
-::<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>}}
-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 der rot hinterlegte <i>Codewortschätzer</i>&nbsp; $\rm (CWS)$.<br>
 == Mögliche Codewortschätzer für die RS&ndash;Decodierung ==

@@ Zeile 537: / Zeile 537: @@
 *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 $\rm (BMA)$. Genauere Informationen finden Sie wieder in [Bos98]<ref name ='Bos98'></ref> und [Fri96]<ref name ='Fri96'></ref>.<br>
-*Weitere effiziente Decodiermethoden 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> unter Verwendung der [[Signaldarstellung/Diskrete_Fouriertransformation_(DFT)#Argumente_f.C3.BCr_die_diskrete_Realisierung_der_FT| Diskreten Fouriertransformation]] $\rm (DFT)$ im Körper ${\rm GF}(n)$.<br><br>
 Die Grundzüge der Reed&ndash;Solomon&ndash;Fehlerkorrektur wurden bereits in den 1960er Jahren entwickelt. Aber bis in die heutige Zeit (2013) ist die (möglichst schnelle) algebraische Decodierung dieser Codes ein hochaktuelles Forschungsgebiet.

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

@@ Zeile 416: / Zeile 416: @@
 *Die Annahme, dass tatsächlich $r = 2$&nbsp; Positionen des Empfangsvektors $\underline {y}$&nbsp; verfälscht wurden, ist richtig.<br>
 *Man weiß aber noch nicht, welche Positionen verfälscht wurden. Soviel vorneweg:
-*Es sind nicht die Symbolpositionen 2 und 6, sondern die Positionen 0 und 2, wie im folgenden $\text{Beispiel 5}$ gezeigt wird.}}<br>
+*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.}}<br>

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