Kanalcodierung/Definition und Eigenschaften von Reed–Solomon–Codes: Unterschied zwischen den Versionen

Aus LNTwww
Wechseln zu:Navigation, Suche
 
(9 dazwischenliegende Versionen desselben Benutzers werden nicht angezeigt)
Zeile 8: Zeile 8:
 
== Codierprinzip und Codeparameter ==
 
== Codierprinzip und Codeparameter ==
 
<br>
 
<br>
Ein <i>Reed&ndash;Solomon&ndash;Code</i>&nbsp; &ndash; im Folgenden manchmal auch verkürzt  als&nbsp; '''RS&ndash;Code'''&nbsp; bezeichnet &ndash; ist ein&nbsp; [[Kanalcodierung/Allgemeine_Beschreibung_linearer_Blockcodes#Lineare_Codes_und_zyklische_Codes| linearer Blockcode]], der
+
Ein&nbsp; "Reed&ndash;Solomon&ndash;Code"&nbsp; &ndash; im Folgenden manchmal auch verkürzt  als&nbsp; "RS&ndash;Code"&nbsp; bezeichnet &ndash; ist ein&nbsp; [[Kanalcodierung/Allgemeine_Beschreibung_linearer_Blockcodes#Lineare_Codes_und_zyklische_Codes| "linearer Blockcode"]],&nbsp; der
 
[[Datei:P ID2515 KC T 2 3 S1 v2.png|right|frame|Linearer $(n, \, k)$–Blockcode|class=fit]]  
 
[[Datei:P ID2515 KC T 2 3 S1 v2.png|right|frame|Linearer $(n, \, k)$–Blockcode|class=fit]]  
*einem Informationsblock&nbsp; $\underline{u}$&nbsp; mit&nbsp; $k$&nbsp; Symbolen  
+
*einem Informationsblock&nbsp; $\underline{u}$&nbsp; mit&nbsp; $k$&nbsp; Symbolen
*ein entsprechendes Codewort&nbsp; $\underline{c}$&nbsp; mit&nbsp; $n > k$  
+
 +
*ein entsprechendes Codewort&nbsp; $\underline{c}$&nbsp; mit&nbsp; $n > k$&nbsp; Symbolen zuordnet.
  
  
Symbolen zuordnet. Diese noch heute vielfach eingesetzten Codes wurden bereits Anfang der 1960er Jahre von&nbsp; [https://de.wikipedia.org/wiki/Irving_Stoy_Reed Irving Stoy Reed]&nbsp; und&nbsp; [https://de.wikipedia.org/wiki/Gustave_Solomon Gustave Solomon]&nbsp; erfunden.<br>
+
Diese noch heute vielfach eingesetzten Codes wurden bereits Anfang der 1960er Jahre  
 +
*von&nbsp; [https://de.wikipedia.org/wiki/Irving_Stoy_Reed Irving Stoy Reed]&nbsp;  
 +
 
 +
*und&nbsp; [https://de.wikipedia.org/wiki/Gustave_Solomon Gustave Solomon]&nbsp; erfunden.<br>
 +
 
  
 
Im Kapitel&nbsp; [[Kanalcodierung/Zielsetzung_der_Kanalcodierung#Blockschaltbild_und_Voraussetzungen|Zielsetzung der Kanalcodierung]]&nbsp; wurde der Informationsblock mit&nbsp; $\underline{u}= (u_1,$ ... , $u_k)$&nbsp; und das Codewort mit&nbsp; $\underline{x}= (x_1,$ ... , $x_n)$&nbsp; bezeichnet.  
 
Im Kapitel&nbsp; [[Kanalcodierung/Zielsetzung_der_Kanalcodierung#Blockschaltbild_und_Voraussetzungen|Zielsetzung der Kanalcodierung]]&nbsp; wurde der Informationsblock mit&nbsp; $\underline{u}= (u_1,$ ... , $u_k)$&nbsp; und das Codewort mit&nbsp; $\underline{x}= (x_1,$ ... , $x_n)$&nbsp; bezeichnet.  
  
Die Nomenklaturänderung&nbsp; $\underline{x} \to \underline{c}$&nbsp; (siehe Grafik) wurde vorgenommen, um Verwechslungen mit dem Argument von Polynomen auszuschließen und die Beschreibung der RS&ndash;Codes zu vereinfachen.
+
Die Nomenklaturänderung &nbsp; $\underline{x} \to \underline{c}$ &nbsp; (siehe Grafik) wurde vorgenommen,&nbsp; um Verwechslungen mit dem Argument von Polynomen auszuschließen und die Beschreibung der RS&ndash;Codes zu vereinfachen.
  
  
Alle im Abschnitt&nbsp; [[Kanalcodierung/Allgemeine_Beschreibung_linearer_Blockcodes#Lineare_Codes_und_zyklische_Codes|Lineare Codes und zyklische Codes]]&nbsp; genannten Eigenschaften linearer zyklischer Blockcodes gelten auch für einen Reed&ndash;Solomon&ndash;Code. Zusätzlich gilt:  
+
Alle im Abschnitt&nbsp; [[Kanalcodierung/Allgemeine_Beschreibung_linearer_Blockcodes#Lineare_Codes_und_zyklische_Codes|"Lineare Codes und zyklische Codes"]]&nbsp; genannten Eigenschaften linearer zyklischer Blockcodes gelten auch für einen Reed&ndash;Solomon&ndash;Code.&nbsp; Zusätzlich gilt:  
  
*Konstruktion und Decodierung von Reed&ndash;Solomon&ndash;Codes basieren auf der Arithmetik eines Galoisfeldes&nbsp; ${\rm GF}(q)$, wobei wir uns hier auf binäre Erweiterungskörper mit&nbsp; $q=2^m$ Elementen&nbsp; beschränken:
+
*Konstruktion und Decodierung von Reed&ndash;Solomon&ndash;Codes basieren auf der Arithmetik eines Galoisfeldes&nbsp; ${\rm GF}(q)$,&nbsp; wobei wir uns hier auf binäre Erweiterungskörper mit&nbsp; $q=2^m$&nbsp; Elementen&nbsp; beschränken:
  
 
::<math>{\rm GF}(2^m) = \big \{\hspace{0.05cm}0\hspace{0.05cm},\hspace{0.1cm} \alpha^{0}  ,\hspace{0.05cm}\hspace{0.1cm}
 
::<math>{\rm GF}(2^m) = \big \{\hspace{0.05cm}0\hspace{0.05cm},\hspace{0.1cm} \alpha^{0}  ,\hspace{0.05cm}\hspace{0.1cm}
 
\alpha^{1}\hspace{0.05cm},\hspace{0.1cm} \alpha^{2}\hspace{0.05cm},\hspace{0.1cm}\text{...}\hspace{0.1cm},  \alpha^{q-2}\hspace{0.05cm} \big \}\hspace{0.05cm}. </math>
 
\alpha^{1}\hspace{0.05cm},\hspace{0.1cm} \alpha^{2}\hspace{0.05cm},\hspace{0.1cm}\text{...}\hspace{0.1cm},  \alpha^{q-2}\hspace{0.05cm} \big \}\hspace{0.05cm}. </math>
  
*Prinzipiell unterschiedlich zum ersten Kapitel ist, dass die Koeffizienten&nbsp; $u_0$,&nbsp; $u_1$, ... ,&nbsp; $u_{k-1}$&nbsp; nun nicht mehr einzelne Informationsbits&nbsp; $(0$ oder $1)$&nbsp; angeben, sondern ebenfalls Elemente aus&nbsp; ${\rm GF}(2^m)$&nbsp; sind. Jedes der&nbsp; $n$&nbsp; Symbole steht für&nbsp; $m$&nbsp; Bit.<br>
+
*Prinzipiell unterschiedlich zum ersten Kapitel ist,&nbsp; dass die Koeffizienten&nbsp; $u_0$,&nbsp; $u_1$, ... ,&nbsp; $u_{k-1}$&nbsp; nun nicht mehr einzelne Informationsbits&nbsp; $(0$&nbsp; oder&nbsp; $1)$&nbsp; angeben,&nbsp; sondern ebenfalls Elemente aus&nbsp; ${\rm GF}(2^m)$&nbsp; sind.&nbsp; Jedes der&nbsp; $n$&nbsp; Symbole steht für&nbsp; $m$&nbsp; Bit.<br>
  
*Bei den Reed&ndash;Solomon&ndash;Codes ist der Parameter&nbsp; $n$&nbsp; (Codelänge) stets gleich der Anzahl der Elemente des Galoisfeldes ohne das Nullwort: &nbsp; $n= q-1$. <br>Wir verwenden hierzu folgende Nomenklatur:
+
*Bei den Reed&ndash;Solomon&ndash;Codes ist der Parameter&nbsp; $n$&nbsp; $($Codelänge$)$&nbsp; stets gleich der Anzahl der Elemente des Galoisfeldes ohne das Nullwort: &nbsp; $n= q-1$. <br>Wir verwenden hierzu folgende Nomenklatur:
  
 
::<math>{\rm GF}(2^m) \hspace{-0.05cm}\setminus \hspace{-0.05cm} \{0\} = \big \{\hspace{0.05cm} \alpha^{0}  ,\hspace{0.05cm}\hspace{0.1cm}
 
::<math>{\rm GF}(2^m) \hspace{-0.05cm}\setminus \hspace{-0.05cm} \{0\} = \big \{\hspace{0.05cm} \alpha^{0}  ,\hspace{0.05cm}\hspace{0.1cm}
 
\alpha^{1}\hspace{0.05cm},\hspace{0.1cm} \alpha^{2}\hspace{0.05cm},\hspace{0.1cm}...\hspace{0.1cm},  \alpha^{n-1}\hspace{0.05cm} \big \}\hspace{0.05cm}. </math>
 
\alpha^{1}\hspace{0.05cm},\hspace{0.1cm} \alpha^{2}\hspace{0.05cm},\hspace{0.1cm}...\hspace{0.1cm},  \alpha^{n-1}\hspace{0.05cm} \big \}\hspace{0.05cm}. </math>
  
*Die&nbsp; $k$&nbsp; Koeffizienten&nbsp; $u_i \in {\rm GF}(2^m)$&nbsp; des Informationsblocks&nbsp; $\underline{u}$, wobei für den Index&nbsp; $ 0 \le i < k$&nbsp; gilt,  kann man formal auch durch ein Polynom&nbsp; $u(x)$&nbsp; ausdrücken. Der Grad des Polynoms ist dabei&nbsp; $k-1$:
+
*Die&nbsp; $k$&nbsp; Koeffizienten&nbsp; $u_i \in {\rm GF}(2^m)$&nbsp; des Informationsblocks&nbsp; $\underline{u}$,&nbsp; wobei für den Index&nbsp; $ 0 \le i < k$&nbsp; gilt,&nbsp; kann man formal auch durch ein Polynom&nbsp; $u(x)$&nbsp; ausdrücken.&nbsp; Der Grad des Polynoms ist dabei&nbsp; $k-1$:
  
 
::<math>u(x) = \sum_{i = 0}^{k-1} u_i \cdot x^{i}  = u_0 + u_1 \cdot x + u_2 \cdot x^2 + \hspace{0.1cm}\text{...}\hspace{0.1cm}+ u_{k-1} \cdot x^{k-1}  \hspace{0.05cm},\hspace{0.4cm} u_i \in {\rm GF}(2^m)
 
::<math>u(x) = \sum_{i = 0}^{k-1} u_i \cdot x^{i}  = u_0 + u_1 \cdot x + u_2 \cdot x^2 + \hspace{0.1cm}\text{...}\hspace{0.1cm}+ u_{k-1} \cdot x^{k-1}  \hspace{0.05cm},\hspace{0.4cm} u_i \in {\rm GF}(2^m)
Zeile 44: Zeile 49:
 
::<math>c_0 = u(\alpha^{0}) \hspace{0.05cm},\hspace{0.3cm} c_1 = u(\alpha^{1})\hspace{0.05cm},\hspace{0.1cm}...\hspace{0.1cm},\hspace{0.3cm} c_{n-1}= u(\alpha^{n-1}) \hspace{0.05cm}.</math>
 
::<math>c_0 = u(\alpha^{0}) \hspace{0.05cm},\hspace{0.3cm} c_1 = u(\alpha^{1})\hspace{0.05cm},\hspace{0.1cm}...\hspace{0.1cm},\hspace{0.3cm} c_{n-1}= u(\alpha^{n-1}) \hspace{0.05cm}.</math>
  
*Meist werden die Codesymbole&nbsp; $c_i \in {\rm GF}(2^m)$&nbsp; vor der Übertragung wieder in Binärform &nbsp; &#8658; &nbsp; ${\rm GF}(2)$&nbsp; gebracht, wobei dann jedes Symbol durch &nbsp;$m$&nbsp; Bit dargestellt wird.<br>
+
*Meist werden die Codesymbole&nbsp; $c_i \in {\rm GF}(2^m)$&nbsp; vor der Übertragung wieder in Binärform &nbsp; &#8658; &nbsp; ${\rm GF}(2)$&nbsp; gebracht,&nbsp; wobei dann jedes Symbol durch &nbsp;$m$&nbsp; Bit dargestellt wird.<br>
  
  
Zeile 50: Zeile 55:
  
 
{{BlaueBox|TEXT=   
 
{{BlaueBox|TEXT=   
$\text{Definition:}$&nbsp;  Ein&nbsp; $(n, k)$'''&ndash;Reed&ndash;Solomon&ndash;Code'''&nbsp; für das Galoisfeld&nbsp; ${\rm GF}(2^m)$&nbsp; wird festgelegt durch
+
$\text{Definition:}$&nbsp;  Ein&nbsp; $(n,\ k)$'''&ndash;Reed&ndash;Solomon&ndash;Code'''&nbsp; für das Galoisfeld&nbsp; ${\rm GF}(2^m)$&nbsp; wird festgelegt durch
*die&nbsp; $n= 2^{m-1}$&nbsp; Elemente von&nbsp; ${\rm GF}(2^m) \hspace{-0.05cm}\setminus \hspace{-0.05cm} \{0\} =\{ \alpha^0, \alpha^1, \, \text{...} \, ,  \alpha^{n-1}\}$, wobei&nbsp; $\alpha$&nbsp; ein&nbsp; [[Kanalcodierung/Erweiterungskörper#Bin.C3.A4re_Erweiterungsk.C3.B6rper_.E2.80.93_Primitive_Polynome|primitives Element]]&nbsp; von&nbsp; ${\rm GF}(2^m)$&nbsp; bezeichnet,
+
*die&nbsp; $n= 2^{m-1}$&nbsp; Elemente von&nbsp; ${\rm GF}(2^m) \hspace{-0.05cm}\setminus \hspace{-0.05cm} \{0\} =\{ \alpha^0, \alpha^1, \, \text{...} \, ,  \alpha^{n-1}\}$,&nbsp; wobei&nbsp; $\alpha$&nbsp; ein&nbsp; [[Kanalcodierung/Erweiterungskörper#Bin.C3.A4re_Erweiterungsk.C3.B6rper_.E2.80.93_Primitive_Polynome|"primitives Element"]]&nbsp; von&nbsp; ${\rm GF}(2^m)$&nbsp; bezeichnet,
  
*ein an den Informationsblockt&nbsp; $\underline{u}$&nbsp; angepasstes&nbsp; [[Kanalcodierung/Erweiterungskörper#Verallgemeinerte_Definition_eines_Erweiterungsk.C3.B6rpers|Polynom]]&nbsp; vom Grad&nbsp; $k-1$&nbsp; der Form
+
*ein an den Informationsblockt&nbsp; $\underline{u}$&nbsp; angepasstes&nbsp; [[Kanalcodierung/Erweiterungskörper#Verallgemeinerte_Definition_eines_Erweiterungsk.C3.B6rpers|"Polynom"]]&nbsp; vom Grad&nbsp; $k-1$&nbsp; der Form
  
 
::<math>u(x) = \sum_{i = 0}^{k-1} u_i \cdot x^{i}  = u_0 + u_1 \cdot x + u_2 \cdot x^2 + \hspace{0.1cm}... \hspace{0.1cm}+ u_{k-1} \cdot x^{k-1}  \hspace{0.05cm},\hspace{0.4cm} u_i \in {\rm GF}(2^m)
 
::<math>u(x) = \sum_{i = 0}^{k-1} u_i \cdot x^{i}  = u_0 + u_1 \cdot x + u_2 \cdot x^2 + \hspace{0.1cm}... \hspace{0.1cm}+ u_{k-1} \cdot x^{k-1}  \hspace{0.05cm},\hspace{0.4cm} u_i \in {\rm GF}(2^m)
 
\hspace{0.05cm}.</math>
 
\hspace{0.05cm}.</math>
  
Damit lässt sich der&nbsp; $(n, k)$&ndash;Reed&ndash;Solomon&ndash;Code  beschreiben als
+
&rArr; &nbsp; Damit lässt sich der&nbsp; $(n,\ k)$&ndash;Reed&ndash;Solomon&ndash;Code  beschreiben als
  
 
::<math>C_{\rm RS} = \Big \{ \underline {c} =  \big ( u(\alpha^{0}) \hspace{0.05cm},\hspace{0.1cm} u(\alpha^{1})\hspace{0.05cm},\hspace{0.1cm}...\hspace{0.1cm},  u(\alpha^{n-1})\hspace{0.1cm}  \big )
 
::<math>C_{\rm RS} = \Big \{ \underline {c} =  \big ( u(\alpha^{0}) \hspace{0.05cm},\hspace{0.1cm} u(\alpha^{1})\hspace{0.05cm},\hspace{0.1cm}...\hspace{0.1cm},  u(\alpha^{n-1})\hspace{0.1cm}  \big )
Zeile 66: Zeile 71:
 
Die bisherigen Angaben sollen nun an zwei einfachen Beispielen verdeutlicht werden.
 
Die bisherigen Angaben sollen nun an zwei einfachen Beispielen verdeutlicht werden.
  
[[Datei:P ID2517 KC T 2 3 S1b v3.png|right|frame|$\rm GF(2^2)$&nbsp; in drei verschiedenwn Darstellungen: <br>Exponenten–, Polynom– und Koeffizientenform |class=fit]]
 
 
{{GraueBox|TEXT=   
 
{{GraueBox|TEXT=   
 
$\text{Beispiel 1:}$&nbsp;  Wir betrachten die folgenden Codeparametern:
 
$\text{Beispiel 1:}$&nbsp;  Wir betrachten die folgenden Codeparametern:
 
+
[[Datei:P ID2517 KC T 2 3 S1b v3.png|right|frame|$\rm GF(2^2)$&nbsp; in drei verschiedenwn Darstellungen: <br>Exponenten–, Polynom– und Koeffizientenform |class=fit]]
 
::<math>k = 2 \hspace{0.05cm},\hspace{0.15cm}n = 3 \hspace{0.5cm} \Rightarrow  \hspace{0.5cm} \underline {u} = (u_0, u_1)\hspace{0.05cm},\hspace{0.15cm}  
 
::<math>k = 2 \hspace{0.05cm},\hspace{0.15cm}n = 3 \hspace{0.5cm} \Rightarrow  \hspace{0.5cm} \underline {u} = (u_0, u_1)\hspace{0.05cm},\hspace{0.15cm}  
 
\underline {c} = (c_0, c_1, c_2)\hspace{0.05cm},</math>
 
\underline {c} = (c_0, c_1, c_2)\hspace{0.05cm},</math>
Zeile 76: Zeile 80:
 
\hspace{0.5cm} \Rightarrow  \hspace{0.5cm} m = 2\hspace{0.05cm}.</math>
 
\hspace{0.5cm} \Rightarrow  \hspace{0.5cm} m = 2\hspace{0.05cm}.</math>
  
Ausgehend von der Bedingungsgleichung&nbsp; $p(\alpha) =  \alpha^2 + \alpha + 1 = 0$  &nbsp; &#8658; &nbsp; $\alpha^2 = \alpha + 1$&nbsp; erhält man die Zuordnungen zwischen  
+
Ausgehend von der Bedingungsgleichung &nbsp; $p(\alpha) =  \alpha^2 + \alpha + 1 = 0$  &nbsp; &#8658; &nbsp; $\alpha^2 = \alpha + 1$&nbsp; erhält man die Zuordnungen zwischen  
*der Exponentendarstellung,  
+
*der Exponentendarstellung,
*der Polynomdarstellung und  
+
 +
*der Polynomdarstellung und
 +
 
*der Koeffizientendarstellung  
 
*der Koeffizientendarstellung  
  
  
von&nbsp; ${\rm GF}(2^2)$&nbsp; gemäß obiger Tabelle. Daraus ist ersichtlich:
+
von&nbsp; ${\rm GF}(2^2)$&nbsp; gemäß obiger Tabelle.&nbsp; Daraus ist ersichtlich:
  
*Der Koeffizientenvektor wird durch das Polynom&nbsp; $u(x) = u_0 + u_1 \cdot x$&nbsp;  ausgedrückt. Der Polynomgrad ist&nbsp; $k- 1 = 1$.  
+
# Der Koeffizientenvektor wird durch das Polynom&nbsp; $u(x) = u_0 + u_1 \cdot x$&nbsp;  ausgedrückt.&nbsp; Der Polynomgrad ist&nbsp; $k- 1 = 1$.  
*Für&nbsp; $u_0 = \alpha^1$&nbsp; und&nbsp; $u_1 = \alpha^2$&nbsp; erhält man beispielsweise das Polynom&nbsp; $u(x) = \alpha + \alpha^2 \cdot x$&nbsp; und damit
+
# Für&nbsp; $u_0 = \alpha^1$&nbsp; und&nbsp; $u_1 = \alpha^2$&nbsp; erhält man beispielsweise das Polynom&nbsp; $u(x) = \alpha + \alpha^2 \cdot x$&nbsp; und damit
  
 
::<math>c_0 = u (x = \alpha^0) = u (x = 1) =  \alpha + \alpha^2 \cdot 1 = \alpha + (\alpha + 1) =1 \hspace{0.05cm},</math>
 
::<math>c_0 = u (x = \alpha^0) = u (x = 1) =  \alpha + \alpha^2 \cdot 1 = \alpha + (\alpha + 1) =1 \hspace{0.05cm},</math>
Zeile 91: Zeile 97:
 
::<math>c_2 =u (x = \alpha^2) =  \alpha + \alpha^2 \cdot \alpha^2 = \alpha + \alpha^4 =  \alpha + \alpha^1 = 0 \hspace{0.05cm}.</math>
 
::<math>c_2 =u (x = \alpha^2) =  \alpha + \alpha^2 \cdot \alpha^2 = \alpha + \alpha^4 =  \alpha + \alpha^1 = 0 \hspace{0.05cm}.</math>
  
Daraus ergeben sich folgende Zuordnungen auf Symbol&ndash; bzw. Bitebene:
+
&rArr; &nbsp; Daraus ergeben sich folgende Zuordnungen auf Symbol&ndash; bzw. Bitebene:
  
 
::<math>\underline {u} =(\alpha^1, \ \alpha^2)\hspace{0.57cm}\leftrightarrow\hspace{0.3cm}  
 
::<math>\underline {u} =(\alpha^1, \ \alpha^2)\hspace{0.57cm}\leftrightarrow\hspace{0.3cm}  
Zeile 101: Zeile 107:
 
$\text{Beispiel 2:}$&nbsp;   
 
$\text{Beispiel 2:}$&nbsp;   
 
Rechts ist die Codetabelle des&nbsp; $\text{RSC (3, 2, 2)}_4$&nbsp; genannten Reed&ndash;Solomon&ndash;Codes angegeben.  
 
Rechts ist die Codetabelle des&nbsp; $\text{RSC (3, 2, 2)}_4$&nbsp; genannten Reed&ndash;Solomon&ndash;Codes angegeben.  
*Die Bezeichnung bezieht sich auf die Parameter&nbsp; $n=3$,&nbsp; $k=2$,&nbsp; $d_{\rm min}=2$&nbsp; und&nbsp;  $q = 4$.  
+
*Die Bezeichnung bezieht sich auf die Parameter&nbsp; $n=3$,&nbsp; $k=2$,&nbsp; $d_{\rm min}=2$&nbsp; und&nbsp;  $q = 4$.
 +
 
*In den Spalten 1 bis 3 erkennt man den Zusammenhang &nbsp;$\underline {u} \  &#8594; \ u(x) \ &#8594; \ \underline {c}$.
 
*In den Spalten 1 bis 3 erkennt man den Zusammenhang &nbsp;$\underline {u} \  &#8594; \ u(x) \ &#8594; \ \underline {c}$.
 +
 
*In den beiden letzten Spalten ist die Codiervorschrift &nbsp;$\underline {u}_{\rm bin} \  &#8596; \ \underline {c}_{\rm bin}$ angegeben.<br>
 
*In den beiden letzten Spalten ist die Codiervorschrift &nbsp;$\underline {u}_{\rm bin} \  &#8596; \ \underline {c}_{\rm bin}$ angegeben.<br>
  
  
Zur Verdeutlichung nochmals der Eintrag für $(\alpha^0, \ \alpha^2)$:
+
Zur Verdeutlichung nochmals der Eintrag für&nbsp;  $(\alpha^0, \ \alpha^2)$&nbsp; (siehe rote Markierung):
  
 
::<math>u(x) = u_0 + u_1 \cdot x = \alpha^0 +  \alpha^2 \cdot x. </math>
 
::<math>u(x) = u_0 + u_1 \cdot x = \alpha^0 +  \alpha^2 \cdot x. </math>
Zeile 116: Zeile 124:
 
::<math>c_2 =u (x = \alpha^2) =  1 + \alpha^2 \cdot \alpha^2 = 1 + \alpha =  \alpha^2  \hspace{0.05cm}.</math>
 
::<math>c_2 =u (x = \alpha^2) =  1 + \alpha^2 \cdot \alpha^2 = 1 + \alpha =  \alpha^2  \hspace{0.05cm}.</math>
  
<i>Hinweise:</i>  
+
<u>Hinweise:</u>  
*Aus der Elementenmenge $\{0, \ \alpha^0 = 1, \ \alpha^1 = \alpha, \ \alpha^2\}$ sollte nicht geschlossen werden, dass für diesen Code die 3D&ndash;Darstellung  mit den Achsen&nbsp; $\alpha^0 = 1$,&nbsp; $\alpha^1 = \alpha$,&nbsp; $\alpha^2$&nbsp; zutrifft. Siehe Abschnitt &nbsp; [[Kanalcodierung/Erweiterungskörper#Bin.C3.A4re_Erweiterungsk.C3.B6rper_.E2.80.93_Primitive_Polynome|Primitive Polynome]]&nbsp;&ndash; Beispiel 5.
+
*Aus der Elementenmenge&nbsp; $\{0, \ \alpha^0 = 1, \ \alpha^1 = \alpha, \ \alpha^2\}$&nbsp; sollte nicht geschlossen werden,&nbsp; dass für diesen Code die 3D&ndash;Darstellung  mit den Achsen&nbsp; $\alpha^0 = 1$,&nbsp; $\alpha^1 = \alpha$,&nbsp; $\alpha^2$&nbsp; zutrifft.&nbsp; Siehe Abschnitt &nbsp; [[Kanalcodierung/Erweiterungskörper#Bin.C3.A4re_Erweiterungsk.C3.B6rper_.E2.80.93_Primitive_Polynome|"Primitive Polynome"]]&nbsp;&ndash; Beispiel 5.
*Aus der Koeffizientendarstellung im&nbsp; $\text{Beispiel 1}$&nbsp; geht vielmehr eindeutig hervor, dass &nbsp; ${\rm GF} (2^2)$&nbsp; zweidimensional ist, wobei die Achsen der 2D&ndash;Darstellung mit&nbsp; $\alpha^0 = 1$&nbsp; und&nbsp; $\alpha^1 = \alpha$&nbsp; zu beschriften sind.
+
 
 +
*Aus der Koeffizientendarstellung im&nbsp; $\text{Beispiel 1}$&nbsp; geht vielmehr eindeutig hervor,&nbsp; dass &nbsp; ${\rm GF} (2^2)$&nbsp; zweidimensional ist,&nbsp; wobei die Achsen der zweidimensionalen Darstellung mit&nbsp; $\alpha^0 = 1$&nbsp; und&nbsp; $\alpha^1 = \alpha$&nbsp; zu beschriften sind.
 
}}<br>
 
}}<br>
  
 
== Generatormatrix  der Reed–Solomon–Codes ==
 
== Generatormatrix  der Reed–Solomon–Codes ==
 
<br>
 
<br>
Da es sich beim Reed&ndash;Solomon&ndash;Code um einen linearen Blockcode handelt, ist der Zusammenhang zwischen Informationswort&nbsp; $\underline {u}$&nbsp; und Codewort&nbsp; $\underline {c}$&nbsp; durch die&nbsp; [[Kanalcodierung/Allgemeine_Beschreibung_linearer_Blockcodes#Codefestlegung_durch_die_Generatormatrix| Generatormatrix]]&nbsp; $\boldsymbol{\rm G}$&nbsp; gegeben:
+
Da es sich beim Reed&ndash;Solomon&ndash;Code um einen linearen Blockcode handelt,&nbsp; ist der Zusammenhang zwischen dem Informationswort&nbsp; $\underline {u}$&nbsp; und dem Codewort&nbsp; $\underline {c}$&nbsp; durch die&nbsp; [[Kanalcodierung/Allgemeine_Beschreibung_linearer_Blockcodes#Codefestlegung_durch_die_Generatormatrix| "Generatormatrix"]]&nbsp; $\boldsymbol{\rm G}$&nbsp; gegeben:
  
 
::<math>\underline {c} = \underline {u} \cdot { \boldsymbol{\rm G}}
 
::<math>\underline {c} = \underline {u} \cdot { \boldsymbol{\rm G}}
 
\hspace{0.05cm}.</math>
 
\hspace{0.05cm}.</math>
  
Wie bei jedem linearen&nbsp; $(n, k)$&ndash;Blockcode besteht die Generatormatrix aus&nbsp; $k$&nbsp; Zeilen und&nbsp; $n$&nbsp; Spalten. Im Gegensatz zum Kapitel&nbsp; [[Kanalcodierung/Allgemeine_Beschreibung_linearer_Blockcodes#Lineare_Codes_und_zyklische_Codes|Allgemeine Beschreibung linearer Blockcodes]]&nbsp; sind nun aber die Elemente der Generatormatrix nicht mehr binär&nbsp; $(0$ oder $1)$, sondern entstammen dem Galoisfeld&nbsp; ${\rm GF}(2^m) \hspace{-0.05cm}\setminus \hspace{-0.05cm} \{0\} $.<br>
+
Wie bei jedem linearen&nbsp; $(n,\ k)$&ndash;Blockcode besteht die Generatormatrix  
 +
*aus&nbsp; $k$&nbsp; Zeilen
 +
 +
*und&nbsp; $n$&nbsp; Spalten.  
 +
 
 +
 
 +
Im Gegensatz zum Kapitel&nbsp; [[Kanalcodierung/Allgemeine_Beschreibung_linearer_Blockcodes#Lineare_Codes_und_zyklische_Codes|"Allgemeine Beschreibung linearer Blockcodes"]]&nbsp;  
 +
*sind nun aber die Elemente der Generatormatrix nicht mehr binär&nbsp; $(0$&nbsp; oder&nbsp; $1)$,  
 +
 
 +
*sondern entstammen dem Galoisfeld&nbsp; ${\rm GF}(2^m) \hspace{-0.05cm}\setminus \hspace{-0.05cm} \{0\} $.<br>
 +
 
  
 
{{GraueBox|TEXT=   
 
{{GraueBox|TEXT=   
$\text{Beispiel 3:}$&nbsp; Wir betrachten wie im&nbsp; $\text{Beispiel 2}$&nbsp; (vorherige Seite) den&nbsp; $\text{RSC (3, 2, 2)}_4$, dessen Generatormatrix folgende Form hat:
+
$\text{Beispiel 3:}$&nbsp; Wir betrachten wie im&nbsp; [[Kanalcodierung/Definition_und_Eigenschaften_von_Reed–Solomon–Codes#Codierprinzip_und_Codeparameter|$\text{Beispiel 2}$]]&nbsp; (vorherige Seite)&nbsp; den&nbsp; $\text{RSC (3, 2, 2)}_4$, dessen Generatormatrix folgende Form hat:
  
 
:<math> { \boldsymbol{\rm G} } =  
 
:<math> { \boldsymbol{\rm G} } =  
Zeile 142: Zeile 161:
  
 
Daneben gilt:
 
Daneben gilt:
*Die erste Zeile von&nbsp; $\boldsymbol{\rm G}$&nbsp; gibt das Codewort für das Informationswort&nbsp; $\underline {u}_1 = (1,  0)$&nbsp; an bzw. für die Polynomfunktion $u_1(x) = 1$. Damit erhält man die Matrixelemente der ersten Zeile zu
+
*Die erste Zeile von&nbsp; $\boldsymbol{\rm G}$&nbsp; gibt das Codewort für das Informationswort&nbsp; $\underline {u}_1 = (1,  0)$&nbsp; an bzw. für die Polynomfunktion&nbsp; $u_1(x) = 1$.&nbsp; Damit erhält man die Matrixelemente der ersten Zeile zu
  
::<math>g_{00} = u_{1}(\alpha^{0}) = 1\hspace{0.05cm},\hspace{0.3cm}
+
:$$g_{00} = u_{1}(\alpha^{0}) = 1\hspace{0.05cm},$$
g_{01} = u_{1}(\alpha^{1}) = 1\hspace{0.05cm},\hspace{0.3cm}
+
:$$g_{01} = u_{1}(\alpha^{1}) = 1\hspace{0.05cm},$$
g_{02} = u_{1}(\alpha^{2}) = 1\hspace{0.05cm}.</math>
+
:$$g_{02} = u_{1}(\alpha^{2}) = 1\hspace{0.05cm}.$$
  
*Die zweite Zeile ist gleich dem Codewort für das Informationswort $\underline {u}_2 = (0,  1)$ &nbsp; &#8658; &nbsp; $u_2(x) = x$. Die Matrixelemente der zweiten Zeile lauten somit:
+
*Die zweite Zeile ist gleich dem Codewort für das Informationswort&nbsp; $\underline {u}_2 = (0,\ 1)$ &nbsp; &#8658; &nbsp; $u_2(x) = x$.&nbsp; Die Matrixelemente der zweiten Zeile lauten somit:
  
::<math>g_{10} = u_{2}(\alpha^{0}) = \alpha^{0} = 1\hspace{0.05cm},\hspace{0.3cm}
+
:$$g_{10} = u_{2}(\alpha^{0}) = \alpha^{0} = 1\hspace{0.05cm},$$
g_{11} = u_{2}(\alpha^{1}) =  \alpha \hspace{0.05cm},\hspace{0.3cm}
+
:$$g_{11} = u_{2}(\alpha^{1}) =  \alpha \hspace{0.05cm},$$
g_{12} = u_{2}(\alpha^{2}) = \alpha^{2}\hspace{0.05cm}.</math>
+
:$$g_{12} = u_{2}(\alpha^{2}) = \alpha^{2}\hspace{0.05cm}.$$
  
::<math>\Rightarrow\hspace{0.3cm} { \boldsymbol{\rm G} } =  
+
* Somit lautet die komplette Generatormatrix:
 +
::<math>{ \boldsymbol{\rm G} } =  
 
\begin{pmatrix}
 
\begin{pmatrix}
 
1 & 1 & 1\\
 
1 & 1 & 1\\
Zeile 160: Zeile 180:
 
\end{pmatrix}\hspace{0.05cm}.</math>
 
\end{pmatrix}\hspace{0.05cm}.</math>
  
Für das Informationswort $\underline {u}= (u_0, \ u_1)$ mit den Symbolen $u_0, \ u_1 &#8712; \{0, \ \alpha^0, \ \alpha^1 = \alpha, \ \alpha^2\}$&nbsp; erhält man unter Berücksichtigung der beiden Gleichungen&nbsp; $\alpha^2 = \alpha + 1$&nbsp; sowie&nbsp; $\alpha^3 = \alpha^0 = 1$&nbsp; wiederum die Codetabelle des&nbsp; $\text{RSC (3, 2, 2)}_4$&nbsp; auf Symbolebene.<br>
+
[[Datei:P ID2519 KC T 2 3 S2a v1.png|right|frame|Codetabelle des&nbsp; $\text{RSC (3, 2, 2)}_4$&nbsp; auf Symbolebene|class=fit]]
 +
*Für das Informationswort&nbsp; $\underline {u}= (u_0, \ u_1)$&nbsp; mit den Symbolen  
 +
:$$u_0, \ u_1 &#8712; \{0, \ \alpha^0, \ \alpha^1 = \alpha, \ \alpha^2\}$$
 +
erhält man unter Berücksichtigung der beiden Gleichungen &nbsp; $\alpha^2 = \alpha + 1$ &nbsp; sowie &nbsp; $\alpha^3 = \alpha^0 = 1$ &nbsp; wiederum die Codetabelle des&nbsp; $\text{RSC (3, 2, 2)}_4$&nbsp; auf Symbolebene.<br>
  
[[Datei:P ID2519 KC T 2 3 S2a v1.png|center|frame|Codetabelle des&nbsp; $\text{RSC (3, 2, 2)}_4$&nbsp; auf Symbolebene|class=fit]]
+
# Man erhält natürlich mit der gleichen Generatormatrix genau die gleiche Codetabelle&nbsp; $\underline {u} &nbsp; &#8596; &nbsp; \underline {c}$&nbsp; wie nach der Berechnung über die Funktion&nbsp; $u(x)$.  
 
+
# Die entsprechende Codetabelle auf Bitebene&nbsp; $($siehe&nbsp; $\text{Beispiel 2}$&nbsp; auf der vorherigen Seite$)$&nbsp; ergibt sich wieder,&nbsp; wenn man die Elemente nicht in Exponentendarstellung angibt,&nbsp; sondern in Koeffizientenform:
*Man erhält natürlich mit der Generatormatrix genau die gleiche Codetabelle&nbsp; $\underline {u} &nbsp; &#8596; &nbsp; \underline {c}$&nbsp; wie nach der Berechnung über die Funktion&nbsp; $u(x)$.  
 
*Die entsprechende Codetabelle auf Bitebene (siehe&nbsp; $\text{Beispiel 2}$&nbsp; auf der vorherigen Seite) ergibt sich wieder, wenn man die Elemente nicht in Exponentendarstellung angibt, sondern in Koeffizientenform:
 
  
 
::<math>(0, \hspace{0.1cm}\alpha^{0}, \hspace{0.1cm}\alpha^{1}, \hspace{0.1cm}\alpha^{2}) \hspace{0.3cm}\Leftrightarrow\hspace{0.3cm}(00, \hspace{0.1cm}01, \hspace{0.1cm}10, \hspace{0.1cm}11)  
 
::<math>(0, \hspace{0.1cm}\alpha^{0}, \hspace{0.1cm}\alpha^{1}, \hspace{0.1cm}\alpha^{2}) \hspace{0.3cm}\Leftrightarrow\hspace{0.3cm}(00, \hspace{0.1cm}01, \hspace{0.1cm}10, \hspace{0.1cm}11)  
Zeile 177: Zeile 198:
 
*der Codewortlänge&nbsp; $n$&nbsp; (Symbolanzahl pro Codewort).<br><br>
 
*der Codewortlänge&nbsp; $n$&nbsp; (Symbolanzahl pro Codewort).<br><br>
  
[[Kanalcodierung/Allgemeine_Beschreibung_linearer_Blockcodes#Codefestlegung_durch_die_Generatormatrix| Generatormatrix]]&nbsp; $\boldsymbol{\rm G}$&nbsp; $(k$ Zeilen,&nbsp; $n$ Spalten$)$&nbsp; und&nbsp;  [[Kanalcodierung/Allgemeine_Beschreibung_linearer_Blockcodes#Codefestlegung_durch_die_Pr.C3.BCfmatrix| Prüfmatrix]]&nbsp; $\boldsymbol{\rm H}$&nbsp; $(n-k$ Zeilen,&nbsp; $n$&nbsp; Spalten$)$ müssen gemeinsam folgende Gleichung erfüllen:
+
{{BlaueBox|TEXT=
 +
&rArr; &nbsp; Diee&nbsp;[[Kanalcodierung/Allgemeine_Beschreibung_linearer_Blockcodes#Codefestlegung_durch_die_Generatormatrix| "Generatormatrix"]]&nbsp; $\boldsymbol{\rm G}$&nbsp; $(k$ Zeilen,&nbsp; $n$ Spalten$)$&nbsp; und&nbsp;  [[Kanalcodierung/Allgemeine_Beschreibung_linearer_Blockcodes#Codefestlegung_durch_die_Pr.C3.BCfmatrix| "Prüfmatrix"]]&nbsp; $\boldsymbol{\rm H}$&nbsp; $(n-k$ Zeilen,&nbsp; $n$&nbsp; Spalten$)$ müssen gemeinsam folgende Gleichung erfüllen:
  
::<math>{ \boldsymbol{\rm G}} \cdot { \boldsymbol{\rm H }}^{\rm T}= { \boldsymbol{\rm 0}}\hspace{0.05cm}.</math>
+
:$${\boldsymbol{\rm G} } \cdot { \boldsymbol{\rm H } }^{\rm T}= { \boldsymbol{\rm 0} }\hspace{0.05cm}.$$
  
Hierbei bezeichnet&nbsp; $\boldsymbol{\rm 0}$&nbsp; eine Nullmatrix $($alle Elemente gleich $0)$&nbsp; mit&nbsp; $k$&nbsp; Zeilen und&nbsp; $n-k$&nbsp; Spalten.<br>
+
*Hierbei bezeichnet&nbsp; "$\boldsymbol{\rm 0}$"&nbsp; eine Nullmatrix:&nbsp; $($alle Elemente gleich $0)$&nbsp; mit&nbsp; $k$&nbsp; Zeilen und&nbsp; $n-k$&nbsp; Spalten.}}<br>
  
 
{{GraueBox|TEXT=   
 
{{GraueBox|TEXT=   
$\text{Beispiel 4:}$&nbsp; Wir betrachten den&nbsp; $\text{RSC (7, 3, 5)}_8$ &nbsp; &#8658; &nbsp; Codeparameter&nbsp; $n= 7$,&nbsp; $k= 3$, basierend auf dem Galoisfeld&nbsp; $\rm GF(2^3 = 8)$&nbsp; mit der Nebenbedingung&nbsp; $\alpha^3 =\alpha + 1$. Beachten Sie hinsichtlich der Codebezeichnung:
+
$\text{Beispiel 4:}$&nbsp; Wir betrachten den&nbsp; $\text{RSC (7, 3, 5)}_8$.
*Der dritte Parameter der für Blockcodes üblichen Nomenklatur nennt die freie Distanz&nbsp; $d_{\rm min}= 5$.<br>
+
*odeparameter&nbsp; $n= 7$,&nbsp; $k= 3$,  
 +
 
 +
*basierend auf dem Galoisfeld&nbsp; $\rm GF(2^3 = 8)$&nbsp;  
 +
 
 +
*mit der Nebenbedingung&nbsp; $\alpha^3 =\alpha + 1$.  
 +
 
 +
 
 +
Beachten Sie hinsichtlich der Codebezeichnung:
  
*Anders als bei den im Kapitel&nbsp; [[Kanalcodierung/Beispiele_binärer_Blockcodes|Beispiele binärer Blockcodes]]&nbsp; behandelten binären Codes (Single Parity–check Code, Repetition Code, Hamming Code) wird bei den Reed&ndash;Solomon&ndash;Codes noch der Hinweis&nbsp; $q$&nbsp; zum Galoisfeld hinzugefügt&nbsp; $($hier: &nbsp; $q = 8)$.<br><br>
+
# Der dritte Parameter der für Blockcodes üblichen Nomenklatur nennt die freie Distanz&nbsp; $d_{\rm min}= 5$.<br>
 +
# Anders als bei den im Kapitel&nbsp; [[Kanalcodierung/Beispiele_binärer_Blockcodes|"Beispiele binärer Blockcodes"]]&nbsp; behandelten binären Codes&nbsp; $($Single Parity–check Code,&nbsp; Repetition Code,&nbsp; Hamming Code$)$&nbsp; wird bei den Reed&ndash;Solomon&ndash;Codes noch der Hinweis&nbsp; $q$&nbsp; zum Galoisfeld hinzugefügt&nbsp; $($hier: &nbsp; $q = 8)$.<br><br>
  
 
Alle Elemente der Generatormatrix und der Prüfmatrix,
 
Alle Elemente der Generatormatrix und der Prüfmatrix,
Zeile 229: Zeile 259:
  
 
Dies soll hier nur für zwei Elemente nachgewiesen werden:
 
Dies soll hier nur für zwei Elemente nachgewiesen werden:
*Erste Zeile, erste Spalte:
+
*Erste Zeile,&nbsp; erste Spalte:
  
 
::<math>1 \hspace{0.1cm}  \cdot  \hspace{0.1cm} \big [1 + \alpha^1 + \alpha^2 + \alpha^3 + \alpha^4 + \alpha^5 + \alpha^6 \big ] =  1 + \alpha + \alpha^2 + (\alpha + 1) + (\alpha^2 + \alpha)+ (\alpha^2 + \alpha +1)+ (\alpha^2 + 1) = 0 \hspace{0.05cm}; </math>
 
::<math>1 \hspace{0.1cm}  \cdot  \hspace{0.1cm} \big [1 + \alpha^1 + \alpha^2 + \alpha^3 + \alpha^4 + \alpha^5 + \alpha^6 \big ] =  1 + \alpha + \alpha^2 + (\alpha + 1) + (\alpha^2 + \alpha)+ (\alpha^2 + \alpha +1)+ (\alpha^2 + 1) = 0 \hspace{0.05cm}; </math>
  
*Letzte Zeile, letzte Spalte:
+
*Letzte Zeile,&nbsp; letzte Spalte:
  
 
::<math>1 \hspace{0.1cm}  \cdot  \hspace{0.1cm} 1 + \alpha^2 \cdot \alpha^4 + \alpha^4 \cdot \alpha^1
 
::<math>1 \hspace{0.1cm}  \cdot  \hspace{0.1cm} 1 + \alpha^2 \cdot \alpha^4 + \alpha^4 \cdot \alpha^1
Zeile 241: Zeile 271:
 
== Singleton–Schranke und minimale Distanz ==
 
== Singleton–Schranke und minimale Distanz ==
 
<br>
 
<br>
Eine wichtige Kenngröße eines jeden Blockcodes ist die&nbsp; [[Kanalcodierung/Zielsetzung_der_Kanalcodierung#Einige_wichtige_Definitionen_zur_Blockcodierung| minimale  Distanz]]&nbsp; zwischen zwei beliebigen Codeworten&nbsp; $\underline {c}_i$&nbsp; und&nbsp; $\underline {c}_j$.  
+
Eine wichtige Kenngröße eines jeden Blockcodes ist die&nbsp; [[Kanalcodierung/Zielsetzung_der_Kanalcodierung#Einige_wichtige_Definitionen_zur_Blockcodierung| "minimale  Distanz"]]&nbsp; zwischen zwei beliebigen Codeworten&nbsp; $\underline {c}_i$&nbsp; und&nbsp; $\underline {c}_j$.  
*Die Reed&ndash;Solomon&ndash;Codes gehören zur Klasse der&nbsp; <i>linearen</i>&nbsp; und&nbsp; <i>zyklischen</i>&nbsp; Codes. Bei diesen kann man vom Nullwort&nbsp; $\underline {c}_0 = (0,  0, \hspace{0.05cm} \text{...} \hspace{0.05cm},  0)$&nbsp; als Bezugsgröße ausgehen.  
+
*Die Reed&ndash;Solomon&ndash;Codes gehören zur Klasse der&nbsp; '''linearen</i> und&nbsp; zyklischen'''&nbsp; Codes.&nbsp; Bei diesen kann man vom Nullwort&nbsp; $\underline {c}_0 = (0,  0, \hspace{0.05cm} \text{...} \hspace{0.05cm},  0)$&nbsp; als Bezugsgröße ausgehen.  
*Aus der Anzahl der Nullen in den anderen Codeworten&nbsp; $\underline {c}_j &ne; \underline {c}_0$&nbsp; lässt sich das [[Kanalcodierung/Schranken_f%C3%BCr_die_Blockfehlerwahrscheinlichkeit#Distanzspektrum_eines_linearen_Codes_.282.29| Distanzspektrum]]&nbsp; $\{ \hspace{0.05cm}W_j\hspace{0.05cm}\}$&nbsp; angeben.<br>
+
 
 +
*Aus der Anzahl der Nullen in den anderen Codeworten&nbsp; $\underline {c}_j &ne; \underline {c}_0$&nbsp; lässt sich das&nbsp; [[Kanalcodierung/Schranken_f%C3%BCr_die_Blockfehlerwahrscheinlichkeit#Distanzspektrum_eines_linearen_Codes_.282.29| "Distanzspektrum"]]&nbsp; $\{ \hspace{0.05cm}W_j\hspace{0.05cm}\}$&nbsp; angeben.<br>
  
  
Zeile 249: Zeile 280:
 
$\text{Beispiel 5:}$&nbsp; Die Tabelle verdeutlicht die Bestimmung des Distanzspektrums für den&nbsp; $\text{RSC (3, 2, 2)}_4$.  
 
$\text{Beispiel 5:}$&nbsp; Die Tabelle verdeutlicht die Bestimmung des Distanzspektrums für den&nbsp; $\text{RSC (3, 2, 2)}_4$.  
 
*Gegenüber den bisherigen Grafiken wird  die Symbolmenge vereinfachend mit&nbsp; $\{0,\ 1,\ 2,\ 3\}$&nbsp; anstelle von $\{0,\ \alpha^0,\ \alpha^1,\ \alpha^2\}$&nbsp; bezeichnet.  
 
*Gegenüber den bisherigen Grafiken wird  die Symbolmenge vereinfachend mit&nbsp; $\{0,\ 1,\ 2,\ 3\}$&nbsp; anstelle von $\{0,\ \alpha^0,\ \alpha^1,\ \alpha^2\}$&nbsp; bezeichnet.  
*Die Distanz&nbsp; $d$&nbsp;  zwischen&nbsp; $\underline {c}_j$&nbsp; und dem Nullwort&nbsp;  $\underline {c}_0$&nbsp; ist identisch dem&nbsp; [[Kanalcodierung/Zielsetzung_der_Kanalcodierung#Einige_wichtige_Definitionen_zur_Blockcodierung|Hamming&ndash;Gewicht]]&nbsp; $w_{\rm H}(\underline {c}_j)$.<br>
+
*Die Distanz&nbsp; $d$&nbsp;  zwischen&nbsp; $\underline {c}_j$&nbsp; und dem Nullwort&nbsp;  $\underline {c}_0$&nbsp; ist identisch dem&nbsp; [[Kanalcodierung/Zielsetzung_der_Kanalcodierung#Einige_wichtige_Definitionen_zur_Blockcodierung|"Hamming&ndash;Gewicht"]]&nbsp; $w_{\rm H}(\underline {c}_j)$.<br>
 
 
[[Datei:P ID2520 KC T 2 3 S3 v1.png|center|frame|Zur Herleitung des Distanzspektrums für den&nbsp; $\text{RSC (3, 2, 2)}_4$|class=fit]]
 
  
Aus der oberen Tabelle kann unter anderem abgelesen werden:
+
[[Datei:P ID2520 KC T 2 3 S3 v1.png|right|frame|Zur Herleitung des Distanzspektrums für den&nbsp; $\text{RSC (3, 2, 2)}_4$|class=fit]]
*Neun Codeworte unterscheiden sich vom Nullwort in zwei Symbolen und sechs Codeworte in drei Symbolen: &nbsp; $W_2 = 9$,&nbsp; $W_3 = 6$.
 
*Es gibt kein einziges Codewort mit nur einer Null. Das heißt: &nbsp; Die minimale Distanz beträgt hier&nbsp; $d_{\rm min} = 2$. <br>
 
  
 +
&rArr; &nbsp; Aus der oberen Tabelle kann unter anderem abgelesen werden:
 +
*Neun Codeworte unterscheiden sich vom Nullwort in zwei Symbolen und sechs Codeworte in drei Symbolen: &nbsp;
 +
:$$W_2 = 9,\ \ W_3 = 6.$$
 +
*Es gibt kein einziges Codewort mit nur einer Null. Das heißt: &nbsp; Die minimale Distanz beträgt hier&nbsp;
 +
:$$d_{\rm min} = 2.$$
  
Aus der unteren Tabelle erkennt man, dass auch für die Binärdarstellung&nbsp; $d_{\rm min} = 2$&nbsp; gilt.}}<br>
+
&rArr; &nbsp; Aus der unteren Tabelle erkennt man, dass auch für die Binärdarstellung&nbsp; $d_{\rm min} = 2$&nbsp; gilt.}}<br>
  
 
Dieses empirische Ergebnis soll nun verallgemeinert werden:
 
Dieses empirische Ergebnis soll nun verallgemeinert werden:
Zeile 264: Zeile 296:
 
{{BlaueBox|TEXT=   
 
{{BlaueBox|TEXT=   
 
$\text{Ohne Beweis:}$&nbsp;  
 
$\text{Ohne Beweis:}$&nbsp;  
*Die&nbsp; <i>minimale Distanz</i>&nbsp; eines jeden&nbsp; $(n, k)$&ndash;Reed&ndash;Solomon&ndash;Codes ist&nbsp; $d_{\rm min} =n-k+1$ &nbsp; &rArr; &nbsp; es lassen sich&nbsp; $e = d_{\rm min} -1 =n-k$&nbsp; Symbolfehler erkennen.<br>
+
# Die&nbsp; "minimale Distanz"&nbsp; eines jeden&nbsp; $(n, k)$&ndash;Reed&ndash;Solomon&ndash;Codes ist &nbsp; $d_{\rm min} =n-k+1$ &nbsp; &rArr; &nbsp; es lassen sich &nbsp; $e = d_{\rm min} -1 =n-k$ &nbsp; Symbolfehler erkennen.<br>
 
+
# Bei&nbsp; "fehlerkorrigierenden Codes"&nbsp; wählt man meist&nbsp; $d_{\rm min} $&nbsp; ungeradzahlig &nbsp; &#8658; &nbsp; $n-k$&nbsp; geradzahlig.
*Bei&nbsp; <i>fehlerkorrigierenden Codes</i>&nbsp; wählt man meist&nbsp; $d_{\rm min} $&nbsp; ungeradzahlig &nbsp; &#8658; &nbsp; $n-k$&nbsp; geradzahlig. Bei RS&ndash;Codes können dann bis zu&nbsp; $t =(n-k)/2$&nbsp; Symbolfehler korrigiert werden.<br>
+
# Bei Reed&ndash;Solomon&ndash;Codes können dann bis zu &nbsp; $t =(n-k)/2$&nbsp; Symbolfehler korrigiert werden.<br>
 
+
# Die&nbsp; [https://de.wikipedia.org/wiki/Singleton-Schranke "Singleton&ndash;Schranke"]&nbsp; besagt,&nbsp; dass für alle linearen Codes&nbsp; $d_{\rm min} \le n-k+1$&nbsp; gilt.  
*Die&nbsp; [https://de.wikipedia.org/wiki/Singleton-Schranke Singleton&ndash;Schranke]&nbsp; besagt, dass für alle linearen Codes&nbsp; $d_{\rm min} \le n-k+1$&nbsp; gilt. RS&ndash;Codes erreichen diese Schranke mit Gleichheit; sie sind so genannte&nbsp; [https://de.wikipedia.org/wiki/MDS-Code MDS&ndash;Codes]&nbsp; (<i>Maximum Distance Separable</i>&nbsp;).
+
# Reed&ndash;Solomon&ndash;Codes erreichen diese Schranke mit Gleichheit;&nbsp; sie sind so genannte&nbsp; [https://de.wikipedia.org/wiki/MDS-Code "MDS&ndash;Codes"]&nbsp; ("Maximum Distance Separable").
 
+
# Das&nbsp; [[Kanalcodierung/Schranken_f%C3%BCr_die_Blockfehlerwahrscheinlichkeit#Distanzspektrum_eines_linearen_Codes| "Distanzspektrum"]]&nbsp; setzt sich zusammen aus&nbsp; $W_0 = 1$&nbsp; sowie weiteren Gewichtsfaktoren&nbsp; $W_i$&nbsp; mit&nbsp; $d &#8804; i &#8804; n$,&nbsp; wobei in der folgenden Gleichung&nbsp; $d_{\rm min}$&nbsp; mit&nbsp; $d$&nbsp; abgekürzt ist:
*Das&nbsp; [[Kanalcodierung/Schranken_f%C3%BCr_die_Blockfehlerwahrscheinlichkeit#Distanzspektrum_eines_linearen_Codes| Distanzspektrum]]&nbsp; setzt sich zusammen aus&nbsp; $W_0 = 1$&nbsp; sowie weiteren Gewichtsfaktoren&nbsp; $W_i$&nbsp; mit&nbsp; $d &#8804; i &#8804; n$, wobei in der folgenden Gleichung&nbsp; $d_{\rm min}$&nbsp; mit&nbsp; $d$&nbsp; abgekürzt ist:
 
  
::<math>W_i =  {n \choose i} \cdot \sum_{j = 0}^{i-d}\hspace{0.15cm}(-1)^j \cdot {i \choose j} \cdot \bigg  [\hspace{0.03cm}q^{i\hspace{0.03cm}-\hspace{0.03cm}j\hspace{0.03cm}-\hspace{0.03cm}d\hspace{0.03cm}+\hspace{0.03cm}1}-1 \hspace{0.03cm} \bigg ]\hspace{0.05cm}.</math>}}
+
:::<math>W_i =  {n \choose i} \cdot \sum_{j = 0}^{i-d}\hspace{0.15cm}(-1)^j \cdot {i \choose j} \cdot \bigg  [\hspace{0.03cm}q^{i\hspace{0.03cm}-\hspace{0.03cm}j\hspace{0.03cm}-\hspace{0.03cm}d\hspace{0.03cm}+\hspace{0.03cm}1}-1 \hspace{0.03cm} \bigg ]\hspace{0.05cm}.</math>}}
  
 
== Codebezeichnung und Coderate ==
 
== Codebezeichnung und Coderate ==
 
<br>
 
<br>
 
Die übliche Bezeichnung für die Reed&ndash;Solomon&ndash;Codes ist &nbsp;${\rm RSC} \ \ (n,\ k, \ d_{\rm min})_q$&nbsp; mit
 
Die übliche Bezeichnung für die Reed&ndash;Solomon&ndash;Codes ist &nbsp;${\rm RSC} \ \ (n,\ k, \ d_{\rm min})_q$&nbsp; mit
*der Länge&nbsp; $n$&nbsp; des Codes (Symbolanzahl eines Codewortes),<br>
+
*der Länge&nbsp; $n$&nbsp; des Codes&nbsp; $($Symbolanzahl eines Codewortes$)$,<br>
  
*der Dimension&nbsp; $k$&nbsp; des Codes (Symbolanzahl eines Informationswortes),<br>
+
*der Dimension&nbsp; $k$&nbsp; des Codes&nbsp; $($Symbolanzahl eines Informationswortes$)$,<br>
  
*der minimalen Distanz&nbsp; $d_{\rm min} = n-k+1$, maximal entsprechend der&nbsp; ''Singleton&ndash;Schranke'', und<br>
+
*der minimalen Distanz&nbsp; $d_{\rm min} = n-k+1$,&nbsp; maximal entsprechend der&nbsp; "Singleton&ndash;Schranke",&nbsp; und<br>
  
 
*der Größe&nbsp; $q = 2^m$&nbsp; des Galoisfeldes&nbsp; ${\rm GF}(q)$.<br><br>
 
*der Größe&nbsp; $q = 2^m$&nbsp; des Galoisfeldes&nbsp; ${\rm GF}(q)$.<br><br>
  
Alle Elemente&nbsp; $u_i$&nbsp; des Informationswortes&nbsp; $\underline{u}= (u_0, \hspace{0.05cm}\text{...} \hspace{0.05cm}, u_i,  \hspace{0.05cm}\text{...} \hspace{0.05cm}, u_{k-1})$ und alle Elemente <i>c<sub>i</sub></i> des Codewortes $\underline{c}= (c_0, \hspace{0.05cm}\text{...} \hspace{0.05cm}, c_i,  \hspace{0.05cm}\text{...} \hspace{0.05cm}, c_{n-1})$&nbsp; sind nicht binäre Symbole und entstammen dem Galoisfeld&nbsp; ${\rm GF}(q)$.<br>
+
&rArr; &nbsp; Alle Elemente&nbsp; $u_i$&nbsp; des Informationswortes &nbsp; $\underline{u}= (u_0, \hspace{0.05cm}\text{...} \hspace{0.05cm}, u_i,  \hspace{0.05cm}\text{...} \hspace{0.05cm}, u_{k-1})$ &nbsp; und alle Elemente&nbsp; $c_i$&nbsp; des Codewortes &nbsp; $\underline{c}= (c_0, \hspace{0.05cm}\text{...} \hspace{0.05cm}, c_i,  \hspace{0.05cm}\text{...} \hspace{0.05cm}, c_{n-1})$ &nbsp; sind nicht binäre Symbole und entstammen dem Galoisfeld&nbsp; ${\rm GF}(q)$.<br>
  
Für die Realisierung werden diese Symbole stets auch binär dargestellt und man kommt zum äquivalenten binären Reed&ndash;Solomon&ndash;Code &nbsp;${\rm RSC} \ \ (n_{\rm bin},\ k_{\rm bin}, \ d_{\rm min})_2$&nbsp; mit
+
&rArr; &nbsp; Für die Realisierung werden diese Symbole stets auch binär dargestellt und man kommt zum äquivalenten binären Reed&ndash;Solomon&ndash;Code &nbsp;${\rm RSC} \ \ (n_{\rm bin},\ k_{\rm bin}, \ d_{\rm min})_2$&nbsp; mit
 
*$n_{\rm bin} = n \cdot m$ &nbsp; Bit eines Codewortes,<br>
 
*$n_{\rm bin} = n \cdot m$ &nbsp; Bit eines Codewortes,<br>
  
 
*$k_{\rm bin} = k \cdot m$  &nbsp; Bit eines Informationswortes.<br><br>
 
*$k_{\rm bin} = k \cdot m$  &nbsp; Bit eines Informationswortes.<br><br>
  
Die Coderate wird durch diese Maßnahme nicht verändert:
+
&rArr; &nbsp; Die Coderate wird durch diese Maßnahme nicht verändert:
  
 
::<math>R_{\rm bin} =  \frac{k_{\rm bin}}{n_{\rm bin}} = \frac{k \cdot m}{n \cdot m} = \frac{k}{n} = R
 
::<math>R_{\rm bin} =  \frac{k_{\rm bin}}{n_{\rm bin}} = \frac{k \cdot m}{n \cdot m} = \frac{k}{n} = R
 
\hspace{0.05cm}.</math>
 
\hspace{0.05cm}.</math>
  
Ebenso ändert sich durch den Übergang von&nbsp; ${\rm GF}(q)$&nbsp; auf&nbsp; ${\rm GF}(2)$&nbsp; nichts an der minimalen Distanz&nbsp; $d_{\rm min}$.<br>
+
&rArr; &nbsp; Ebenso ändert sich durch den Übergang von&nbsp; ${\rm GF}(q)$&nbsp; auf&nbsp; ${\rm GF}(2)$&nbsp; nichts an der minimalen Distanz&nbsp; $d_{\rm min}$.<br>
  
 
{{GraueBox|TEXT=   
 
{{GraueBox|TEXT=   
$\text{Beispiel 6:}$&nbsp; Wie im&nbsp; $\text{Beispiel 5}$&nbsp; (vorherige Seite) betrachten wir wieder den&nbsp; $\text{RSC (3, 2, 2)}_4$&nbsp; und geben dessen&nbsp; <i>Distanzspektrum</i>&nbsp; $\{ \hspace{0.05cm}W_j\hspace{0.05cm}\}$&nbsp; nochmals an (obere Tabelle). Die untere Tabelle gilt für den äquivalenten binären Reed&ndash;Solomon&ndash;Code&nbsp; $\text{RSC (6, 4, 2)}_2$.
+
$\text{Beispiel 6:}$&nbsp; Wie im&nbsp; $\text{Beispiel 5}$&nbsp; (vorherige Seite)&nbsp; betrachten wir wieder den&nbsp; $\text{RSC (3, 2, 2)}_4$.&nbsp;
 +
[[Datei:P ID2521 KC T 2 3 S3 v1.png|right|frame|Herleitung der Distanzspektren von&nbsp; $\text{RSC (3, 2, 2)}_4$&nbsp; und &nbsp;$\text{RSC (6, 4, 2)}_2$|class=fit]]
 +
# Wir geben dessen&nbsp; "Distanzspektrum"&nbsp; $\{ \hspace{0.05cm}W_j\hspace{0.05cm}\}$&nbsp; nochmals an&nbsp; (obere Tabelle).  
 +
# Die untere Tabelle gilt für den äquivalenten binären Reed&ndash;Solomon&ndash;Code&nbsp; $\text{RSC (6, 4, 2)}_2$.
  
[[Datei:P ID2521 KC T 2 3 S3 v1.png|center|frame|Herleitung der Distanzspektren von&nbsp; $\text{RSC (3, 2, 2)}_4$&nbsp; und &nbsp;$\text{RSC (6, 4, 2)}_2$|class=fit]]
 
  
*Beide Codes haben die gleiche Coderate &nbsp;$R = k/n =2/3$&nbsp; und auch die gleiche minimale Distanz &nbsp;$d_{\rm min} = 2$.
+
 
 +
<u> Man erkennt aus diesen Zahlenwerten:</u>
 +
 
 +
*Beide Codes haben die gleiche Coderate &nbsp;$R = k/n =2/3$&nbsp;  
 +
 
 +
*Beide Codes auch die gleiche minimale Distanz &nbsp;$d_{\rm min} = 2$.
 +
 
 
*Die beiden Codes unterscheiden sich jedoch hinsichtlich des Distanzspektrums &nbsp;$\{ \hspace{0.05cm}W_j\hspace{0.05cm}\}$&nbsp; und der&nbsp; [[Kanalcodierung/Schranken_f%C3%BCr_die_Blockfehlerwahrscheinlichkeit#Distanzspektrum_eines_linearen_Codes|Gewichtsfunktion]]&nbsp; $W(X)$:
 
*Die beiden Codes unterscheiden sich jedoch hinsichtlich des Distanzspektrums &nbsp;$\{ \hspace{0.05cm}W_j\hspace{0.05cm}\}$&nbsp; und der&nbsp; [[Kanalcodierung/Schranken_f%C3%BCr_die_Blockfehlerwahrscheinlichkeit#Distanzspektrum_eines_linearen_Codes|Gewichtsfunktion]]&nbsp; $W(X)$:
  
:$$\text{RSC (3, 2, 2)}_4\text{:} \hspace{0.3cm} W_0 =  1\hspace{0.05cm}, \hspace{0.2cm}W_2 =  9\hspace{0.05cm}, \hspace{0.2cm}W_3 =  6\hspace{0.3cm}\Rightarrow\hspace{0.3cm}W(X) = 1 + 9 \cdot X^2 + 6 \cdot X^3\hspace{0.05cm}.$$
+
:$$\text{RSC (3, 2, 2)}_4\text{:} \hspace{0.3cm} W_0 =  1\hspace{0.05cm}, \hspace{0.2cm}W_2 =  9\hspace{0.05cm}, \hspace{0.2cm}W_3 =  6$$
 +
:$$\Rightarrow\hspace{0.3cm}W(X) = 1 + 9 \cdot X^2 + 6 \cdot X^3\hspace{0.05cm}.$$
  
 
:$$\text{RSC (6, 4, 2)}_2\text{:} \hspace{0.3cm} W_0 =  1\hspace{0.05cm}, \hspace{0.2cm}W_2 =  3\hspace{0.05cm}, \hspace{0.2cm}W_3 =  8
 
:$$\text{RSC (6, 4, 2)}_2\text{:} \hspace{0.3cm} W_0 =  1\hspace{0.05cm}, \hspace{0.2cm}W_2 =  3\hspace{0.05cm}, \hspace{0.2cm}W_3 =  8
Zeile 317: Zeile 357:
 
== Bedeutung der Reed–Solomon–Codes ==
 
== Bedeutung der Reed–Solomon–Codes ==
 
<br>
 
<br>
Anhand des hier oft beispielhaft betrachteten&nbsp; $\text{RSC (3, 2, 2)}_4$&nbsp; konnten wir viele Eigenschaften der Reed&ndash;Solomon&ndash;Codes in überschaubarem Rahmen kennenlernen. Praxisrelevant ist dieser Code allerdings nicht, da wegen&nbsp; $d_{\rm min} = 2$&nbsp; kein einziger Fehler korrigiert und auch nur ein einziger Fehler erkannt werden kann. Schon der nächstgrößere Code&nbsp; $\text{RSC (7, 3, 5)}_8$, der bis zu&nbsp; $t = 2$&nbsp; Fehler korrigieren kann, weist bereits eine Codetabelle mit&nbsp;  $8^3 = 512$&nbsp; Einträgen auf und ist zu Demonstrationszwecken ungeeignet.<br>
+
Anhand des hier oft beispielhaft betrachteten&nbsp; $\text{RSC (3, 2, 2)}_4$&nbsp; konnten wir viele Eigenschaften der Reed&ndash;Solomon&ndash;Codes in überschaubarem Rahmen kennenlernen.  
 
+
*Praxisrelevant ist dieser Code allerdings nicht,&nbsp; da wegen&nbsp; $d_{\rm min} = 2$&nbsp; kein einziger Fehler korrigiert und auch nur ein einziger Fehler erkannt werden kann.  
In der Praxis werden meist sehr große RS&ndash;Codes eingesetzt, zum Beispiel der&nbsp; $\text{RSC (255, 223, 33)}_{256}$&nbsp; mit folgenden Eigenschaften:
 
*Der Code basiert auf dem Galoisfeld&nbsp; $\rm GF(2^8)$. Jedes Symbol entspricht somit einem Byte. Die Coderate ist mit&nbsp; $R = 0.8745$&nbsp; relativ groß.<br>
 
 
 
*Trotz dieser großen Coderate (also geringe Redundanz) können mit diesem Code bis zu&nbsp; $e = 32$&nbsp; Fehler innerhalb eines Blocks aus&nbsp; $255$&nbsp; Symbolen erkannt und&nbsp; $t = 16$&nbsp; Fehler korrigiert werden.<br>
 
 
 
*Die Codetabelle würde allerdings&nbsp; $2^{8 \hspace{0.05cm}\cdot \hspace{0.05cm} 223}= 2^{ \hspace{0.05cm} 1784} &asymp; 10^{537}$&nbsp; Einträge aufweisen und wird deshalb wahrscheinlich auch von niemanden tatsächlich erstellt.<br><br>
 
 
 
Der große Vorteil der Reed&ndash;Solomon&ndash;Codes (und einer ganzen Reihe davon abgeleiteter weiterer Codes) ist zum einen, dass sie analytisch geschlossen konstruiert werden können, zum anderen ihre große Flexibilität hinsichtlich der Codeparameter. Meist geht man wie folgt vor:
 
*Man gibt die Korrekturfähigkeit in Form des Parameters&nbsp; $t$&nbsp; vor. Daraus ergibt sich die minimale Distanz&nbsp; $d_{\rm min} = 2t + 1$&nbsp; und die Differenz&nbsp; $n-k = 2t$&nbsp; entsprechend der Singleton&ndash;Schranke. Einen besseren Wert gibt es nicht.<br>
 
  
*Ein weiterer Entwurfsparameter ist die Coderate&nbsp; $R=k/n$, wobei die Codewortlänge&nbsp; $n = 2^m -1$&nbsp; nicht völlig frei wählbar ist. Durch Erweiterung, Verkürzung und Punktierung &ndash; siehe&nbsp; [[Aufgaben:Aufgabe_1.09Z:_Erweiterung_und/oder_Punktierung|Aufgabe 1.9Z]]&nbsp; &ndash; kann die Vielzahl an möglichen Codes weiter vergrößert werden.<br>
+
*Schon der nächstgrößere Code&nbsp; $\text{RSC (7, 3, 5)}_8$,&nbsp; der bis zu&nbsp; $t = 2$&nbsp; Fehler korrigieren kann,&nbsp; weist bereits eine Codetabelle mit &nbsp; $8^3 = 512$ &nbsp; Einträgen auf und ist zu Demonstrationszwecken ungeeignet.<br>
  
*Bei Reed&ndash;Solomon&ndash;Codes ist die Gewichtsverteilung exakt bekannt und es ist eine Anpassung an die Fehlerstruktur des Kanals möglich. Diese Codes sind insbesondere für Bündelfehlerkanäle gut geeignet, die bei mobilen Funksystemen aufgrund von temporären Abschattungen häufig vorliegen.<br>
 
  
*Im Falle statistisch unabhängiger Fehler sind&nbsp; [https://de.wikipedia.org/wiki/BCH-Code BCH&ndash;Codes]&nbsp; (von $\rm B$ose&ndash;$\rm C$haudhuri&ndash;$\rm H$ocquenghem) besser geeignet. Diese sind mit den RS&ndash;Codes eng verwandt, allerdings erfüllen sie nicht immer das Singleton&ndash;Kriterium. Eine ausführliche Beschreibung finden Sie in [Fri96]<ref name='Fri96'>Friedrichs, B.: ''Kanalcodierung – Grundlagen und Anwendungen in modernen Kommunikations- systemen.'' Berlin – Heidelberg: Springer, 1996.</ref>.<br>
+
In der Praxis werden meist sehr große Reed–Solomon&ndash;Codes eingesetzt,&nbsp; zum Beispiel der&nbsp; $\text{RSC (255, 223, 33)}_{256}$&nbsp; mit folgenden Eigenschaften:
 +
# Der Code basiert auf dem Galoisfeld&nbsp; $\rm GF(2^8)$.&nbsp; Jedes Symbol entspricht somit einem Byte.&nbsp; Die Coderate ist mit&nbsp; $R = 0.8745$&nbsp; relativ groß.<br>
 +
# Trotz dieser großen Coderate&nbsp; $($also geringe Redundanz$)$&nbsp; können mit diesem Code bis zu&nbsp; $e = 32$&nbsp; Fehler innerhalb eines Blocks aus&nbsp; $255$&nbsp; Symbolen erkannt und&nbsp; $t = 16$&nbsp; Fehler korrigiert werden.<br>
 +
# Die Codetabelle würde allerdings &nbsp; $2^{8 \hspace{0.05cm}\cdot \hspace{0.05cm} 223}= 2^{ \hspace{0.05cm} 1784} &asymp; 10^{537}$ &nbsp; Einträge aufweisen und wird deshalb wahrscheinlich auch von niemanden tatsächlich erstellt.<br><br>
  
*Die Decodierung nach dem&nbsp; [https://en.wikipedia.org/wiki/Lattice_problem BDD&ndash;Prinzip]&nbsp; (<i>Bounded Distance Decoding</i>&nbsp;) kann rechentechnisch sehr einfach erfolgen, zum Beispiel mit dem&nbsp; [https://de.wikipedia.org/wiki/Berlekamp-Massey-Algorithmus Berlekamp&ndash;Massey&ndash;Algorithmus]. Zudem kann der Decoder ohne großen Mehraufwand auch&nbsp; [https://en.wikipedia.org/wiki/Soft-decision_decoder ''Soft Decision Information'']&nbsp; verarbeiten.<br>
+
Der große Vorteil der Reed&ndash;Solomon&ndash;Codes&nbsp; $($und einer ganzen Reihe davon abgeleiteter weiterer Codes$)$&nbsp; ist zum einen,&nbsp; dass sie analytisch geschlossen konstruiert werden können,&nbsp; zum anderen ihre große Flexibilität hinsichtlich der Codeparameter.&nbsp; Meist geht man wie folgt vor:
 +
# Man gibt die Korrekturfähigkeit in Form des Parameters&nbsp; $t$&nbsp; vor.&nbsp; Daraus ergibt sich die minimale Distanz &nbsp; $d_{\rm min} = 2t + 1$ &nbsp; und die Differenz &nbsp; $n-k = 2t$ &nbsp; entsprechend der Singleton&ndash;Schranke.&nbsp; Einen besseren Wert gibt es nicht.<br>
 +
# Ein weiterer Entwurfsparameter ist die Coderate&nbsp; $R=k/n$,&nbsp; wobei die Codewortlänge&nbsp; $n = 2^m -1$&nbsp; nicht völlig frei wählbar ist.&nbsp; Durch Erweiterung,&nbsp; Verkürzung und Punktierung &ndash; siehe&nbsp; [[Aufgaben:Aufgabe_1.09Z:_Erweiterung_und/oder_Punktierung|"Aufgabe 1.9Z"]]&nbsp; &ndash; kann die Vielzahl an möglichen Codes weiter vergrößert werden.<br>
 +
# Bei Reed&ndash;Solomon&ndash;Codes ist die Gewichtsverteilung exakt bekannt und es ist eine Anpassung an die Fehlerstruktur des Kanals möglich.&nbsp; Diese Codes sind insbesondere für Bündelfehlerkanäle gut geeignet,&nbsp; die bei mobilen Funksystemen aufgrund temporärer Abschattungen häufig vorliegen.<br>
 +
# Im Falle statistisch unabhängiger Fehler sind so genannte &nbsp; [https://de.wikipedia.org/wiki/BCH-Code "BCH&ndash;Codes"]&nbsp; $($von $\rm B$ose&ndash;$\rm C$haudhuri&ndash;$\rm H$ocquenghem$)$&nbsp; besser geeignet.&nbsp; Diese sind mit den Reed&ndash;Solomon&ndash;Codes eng verwandt,&nbsp; allerdings erfüllen sie nicht immer das Singleton&ndash;Kriterium.&nbsp; Eine ausführliche Beschreibung finden Sie in&nbsp; [Fri96]<ref name='Fri96'>Friedrichs, B.:&nbsp; Kanalcodierung – Grundlagen und Anwendungen in modernen Kommunikations- systemen.&nbsp; Berlin – Heidelberg: Springer, 1996.</ref>.<br>
 +
# Die Decodierung nach dem&nbsp; [https://en.wikipedia.org/wiki/Lattice_problem "BDD&ndash;Prinzip"]&nbsp; ("Bounded Distance Decoding")&nbsp; kann rechentechnisch sehr einfach erfolgen,&nbsp; zum Beispiel mit dem&nbsp; [https://de.wikipedia.org/wiki/Berlekamp-Massey-Algorithmus "Berlekamp&ndash;Massey&ndash;Algorithmus"].&nbsp; Zudem kann der Decoder ohne großen Mehraufwand auch&nbsp; [https://en.wikipedia.org/wiki/Soft-decision_decoder "Soft Decision Information"]&nbsp; verarbeiten.<br>
  
 
== Aufgaben zum Kapitel==
 
== Aufgaben zum Kapitel==

Aktuelle Version vom 7. Oktober 2022, 17:11 Uhr

Codierprinzip und Codeparameter


Ein  "Reed–Solomon–Code"  – im Folgenden manchmal auch verkürzt als  "RS–Code"  bezeichnet – ist ein  "linearer Blockcode",  der

Linearer $(n, \, k)$–Blockcode
  • einem Informationsblock  $\underline{u}$  mit  $k$  Symbolen
  • ein entsprechendes Codewort  $\underline{c}$  mit  $n > k$  Symbolen zuordnet.


Diese noch heute vielfach eingesetzten Codes wurden bereits Anfang der 1960er Jahre


Im Kapitel  Zielsetzung der Kanalcodierung  wurde der Informationsblock mit  $\underline{u}= (u_1,$ ... , $u_k)$  und das Codewort mit  $\underline{x}= (x_1,$ ... , $x_n)$  bezeichnet.

Die Nomenklaturänderung   $\underline{x} \to \underline{c}$   (siehe Grafik) wurde vorgenommen,  um Verwechslungen mit dem Argument von Polynomen auszuschließen und die Beschreibung der RS–Codes zu vereinfachen.


Alle im Abschnitt  "Lineare Codes und zyklische Codes"  genannten Eigenschaften linearer zyklischer Blockcodes gelten auch für einen Reed–Solomon–Code.  Zusätzlich gilt:

  • Konstruktion und Decodierung von Reed–Solomon–Codes basieren auf der Arithmetik eines Galoisfeldes  ${\rm GF}(q)$,  wobei wir uns hier auf binäre Erweiterungskörper mit  $q=2^m$  Elementen  beschränken:
\[{\rm GF}(2^m) = \big \{\hspace{0.05cm}0\hspace{0.05cm},\hspace{0.1cm} \alpha^{0} ,\hspace{0.05cm}\hspace{0.1cm} \alpha^{1}\hspace{0.05cm},\hspace{0.1cm} \alpha^{2}\hspace{0.05cm},\hspace{0.1cm}\text{...}\hspace{0.1cm}, \alpha^{q-2}\hspace{0.05cm} \big \}\hspace{0.05cm}. \]
  • Prinzipiell unterschiedlich zum ersten Kapitel ist,  dass die Koeffizienten  $u_0$,  $u_1$, ... ,  $u_{k-1}$  nun nicht mehr einzelne Informationsbits  $(0$  oder  $1)$  angeben,  sondern ebenfalls Elemente aus  ${\rm GF}(2^m)$  sind.  Jedes der  $n$  Symbole steht für  $m$  Bit.
  • Bei den Reed–Solomon–Codes ist der Parameter  $n$  $($Codelänge$)$  stets gleich der Anzahl der Elemente des Galoisfeldes ohne das Nullwort:   $n= q-1$.
    Wir verwenden hierzu folgende Nomenklatur:
\[{\rm GF}(2^m) \hspace{-0.05cm}\setminus \hspace{-0.05cm} \{0\} = \big \{\hspace{0.05cm} \alpha^{0} ,\hspace{0.05cm}\hspace{0.1cm} \alpha^{1}\hspace{0.05cm},\hspace{0.1cm} \alpha^{2}\hspace{0.05cm},\hspace{0.1cm}...\hspace{0.1cm}, \alpha^{n-1}\hspace{0.05cm} \big \}\hspace{0.05cm}. \]
  • Die  $k$  Koeffizienten  $u_i \in {\rm GF}(2^m)$  des Informationsblocks  $\underline{u}$,  wobei für den Index  $ 0 \le i < k$  gilt,  kann man formal auch durch ein Polynom  $u(x)$  ausdrücken.  Der Grad des Polynoms ist dabei  $k-1$:
\[u(x) = \sum_{i = 0}^{k-1} u_i \cdot x^{i} = u_0 + u_1 \cdot x + u_2 \cdot x^2 + \hspace{0.1cm}\text{...}\hspace{0.1cm}+ u_{k-1} \cdot x^{k-1} \hspace{0.05cm},\hspace{0.4cm} u_i \in {\rm GF}(2^m) \hspace{0.05cm}.\]
  • Die  $n$  Symbole des zugehörigen Codewortes  $\underline{c}= (c_0, c_1,$ ... , $c_{n-1})$  ergeben sich mit diesem Polynom  $u(x)$  zu
\[c_0 = u(\alpha^{0}) \hspace{0.05cm},\hspace{0.3cm} c_1 = u(\alpha^{1})\hspace{0.05cm},\hspace{0.1cm}...\hspace{0.1cm},\hspace{0.3cm} c_{n-1}= u(\alpha^{n-1}) \hspace{0.05cm}.\]
  • Meist werden die Codesymbole  $c_i \in {\rm GF}(2^m)$  vor der Übertragung wieder in Binärform   ⇒   ${\rm GF}(2)$  gebracht,  wobei dann jedes Symbol durch  $m$  Bit dargestellt wird.


Wir fassen diese Aussagen kurz zusammen:

$\text{Definition:}$  Ein  $(n,\ k)$–Reed–Solomon–Code  für das Galoisfeld  ${\rm GF}(2^m)$  wird festgelegt durch

  • die  $n= 2^{m-1}$  Elemente von  ${\rm GF}(2^m) \hspace{-0.05cm}\setminus \hspace{-0.05cm} \{0\} =\{ \alpha^0, \alpha^1, \, \text{...} \, , \alpha^{n-1}\}$,  wobei  $\alpha$  ein  "primitives Element"  von  ${\rm GF}(2^m)$  bezeichnet,
  • ein an den Informationsblockt  $\underline{u}$  angepasstes  "Polynom"  vom Grad  $k-1$  der Form
\[u(x) = \sum_{i = 0}^{k-1} u_i \cdot x^{i} = u_0 + u_1 \cdot x + u_2 \cdot x^2 + \hspace{0.1cm}... \hspace{0.1cm}+ u_{k-1} \cdot x^{k-1} \hspace{0.05cm},\hspace{0.4cm} u_i \in {\rm GF}(2^m) \hspace{0.05cm}.\]

⇒   Damit lässt sich der  $(n,\ k)$–Reed–Solomon–Code beschreiben als

\[C_{\rm RS} = \Big \{ \underline {c} = \big ( u(\alpha^{0}) \hspace{0.05cm},\hspace{0.1cm} u(\alpha^{1})\hspace{0.05cm},\hspace{0.1cm}...\hspace{0.1cm}, u(\alpha^{n-1})\hspace{0.1cm} \big ) \hspace{0.1cm} \big \vert \hspace{0.2cm} u(x) = \sum_{i = 0}^{k-1} u_i \cdot x^{i}\hspace{0.05cm},\hspace{0.2cm} u_i \in {\rm GF}(2^m) \Big \} \hspace{0.05cm}.\]


Die bisherigen Angaben sollen nun an zwei einfachen Beispielen verdeutlicht werden.

$\text{Beispiel 1:}$  Wir betrachten die folgenden Codeparametern:

$\rm GF(2^2)$  in drei verschiedenwn Darstellungen:
Exponenten–, Polynom– und Koeffizientenform
\[k = 2 \hspace{0.05cm},\hspace{0.15cm}n = 3 \hspace{0.5cm} \Rightarrow \hspace{0.5cm} \underline {u} = (u_0, u_1)\hspace{0.05cm},\hspace{0.15cm} \underline {c} = (c_0, c_1, c_2)\hspace{0.05cm},\]
\[q = n+1 = 4 \hspace{0.45cm} \Rightarrow \hspace{0.5cm} {\rm GF} (q) = {\rm GF} (2^m) \hspace{0.5cm} \Rightarrow \hspace{0.5cm} m = 2\hspace{0.05cm}.\]

Ausgehend von der Bedingungsgleichung   $p(\alpha) = \alpha^2 + \alpha + 1 = 0$   ⇒   $\alpha^2 = \alpha + 1$  erhält man die Zuordnungen zwischen

  • der Exponentendarstellung,
  • der Polynomdarstellung und
  • der Koeffizientendarstellung


von  ${\rm GF}(2^2)$  gemäß obiger Tabelle.  Daraus ist ersichtlich:

  1. Der Koeffizientenvektor wird durch das Polynom  $u(x) = u_0 + u_1 \cdot x$  ausgedrückt.  Der Polynomgrad ist  $k- 1 = 1$.
  2. Für  $u_0 = \alpha^1$  und  $u_1 = \alpha^2$  erhält man beispielsweise das Polynom  $u(x) = \alpha + \alpha^2 \cdot x$  und damit
\[c_0 = u (x = \alpha^0) = u (x = 1) = \alpha + \alpha^2 \cdot 1 = \alpha + (\alpha + 1) =1 \hspace{0.05cm},\]
\[c_1 =u (x = \alpha^1) = \alpha + \alpha^2 \cdot \alpha = \alpha + \alpha^3 = \alpha + \alpha^0 = \alpha + 1 = \alpha^2 \hspace{0.05cm},\]
\[c_2 =u (x = \alpha^2) = \alpha + \alpha^2 \cdot \alpha^2 = \alpha + \alpha^4 = \alpha + \alpha^1 = 0 \hspace{0.05cm}.\]

⇒   Daraus ergeben sich folgende Zuordnungen auf Symbol– bzw. Bitebene:

\[\underline {u} =(\alpha^1, \ \alpha^2)\hspace{0.57cm}\leftrightarrow\hspace{0.3cm} \underline {c} = (1, \ \alpha^2, \ 0)\hspace{0.05cm},\hspace{1cm}\underline {u}_{\rm bin} =(1,\ 0,\ 1,\ 1)\hspace{0.3cm}\leftrightarrow\hspace{0.3cm} \underline {c}_{\rm bin} = (0,\ 1,\ 1,\ 1,\ 0,\ 0)\hspace{0.05cm}.\]


Codetabelle des  $\text{RSC (3, 2, 2)}_4$

$\text{Beispiel 2:}$  Rechts ist die Codetabelle des  $\text{RSC (3, 2, 2)}_4$  genannten Reed–Solomon–Codes angegeben.

  • Die Bezeichnung bezieht sich auf die Parameter  $n=3$,  $k=2$,  $d_{\rm min}=2$  und  $q = 4$.
  • In den Spalten 1 bis 3 erkennt man den Zusammenhang  $\underline {u} \ → \ u(x) \ → \ \underline {c}$.
  • In den beiden letzten Spalten ist die Codiervorschrift  $\underline {u}_{\rm bin} \ ↔ \ \underline {c}_{\rm bin}$ angegeben.


Zur Verdeutlichung nochmals der Eintrag für  $(\alpha^0, \ \alpha^2)$  (siehe rote Markierung):

\[u(x) = u_0 + u_1 \cdot x = \alpha^0 + \alpha^2 \cdot x. \]

Daraus ergeben sich folgende Codesymbole:

\[c_0 = u (x = \alpha^0) = 1 + \alpha^2 \cdot 1 = 1 + (1+\alpha ) =\alpha \hspace{0.05cm},\]
\[c_1 = u (x = \alpha^1) = 1 + \alpha^2 \cdot \alpha = 1 + (1+\alpha ) \cdot \alpha = 1 + \alpha + \alpha^2 = 0 \hspace{0.05cm},\]
\[c_2 =u (x = \alpha^2) = 1 + \alpha^2 \cdot \alpha^2 = 1 + \alpha = \alpha^2 \hspace{0.05cm}.\]

Hinweise:

  • Aus der Elementenmenge  $\{0, \ \alpha^0 = 1, \ \alpha^1 = \alpha, \ \alpha^2\}$  sollte nicht geschlossen werden,  dass für diesen Code die 3D–Darstellung mit den Achsen  $\alpha^0 = 1$,  $\alpha^1 = \alpha$,  $\alpha^2$  zutrifft.  Siehe Abschnitt   "Primitive Polynome" – Beispiel 5.
  • Aus der Koeffizientendarstellung im  $\text{Beispiel 1}$  geht vielmehr eindeutig hervor,  dass   ${\rm GF} (2^2)$  zweidimensional ist,  wobei die Achsen der zweidimensionalen Darstellung mit  $\alpha^0 = 1$  und  $\alpha^1 = \alpha$  zu beschriften sind.


Generatormatrix der Reed–Solomon–Codes


Da es sich beim Reed–Solomon–Code um einen linearen Blockcode handelt,  ist der Zusammenhang zwischen dem Informationswort  $\underline {u}$  und dem Codewort  $\underline {c}$  durch die  "Generatormatrix"  $\boldsymbol{\rm G}$  gegeben:

\[\underline {c} = \underline {u} \cdot { \boldsymbol{\rm G}} \hspace{0.05cm}.\]

Wie bei jedem linearen  $(n,\ k)$–Blockcode besteht die Generatormatrix

  • aus  $k$  Zeilen
  • und  $n$  Spalten.


Im Gegensatz zum Kapitel  "Allgemeine Beschreibung linearer Blockcodes" 

  • sind nun aber die Elemente der Generatormatrix nicht mehr binär  $(0$  oder  $1)$,
  • sondern entstammen dem Galoisfeld  ${\rm GF}(2^m) \hspace{-0.05cm}\setminus \hspace{-0.05cm} \{0\} $.


$\text{Beispiel 3:}$  Wir betrachten wie im  $\text{Beispiel 2}$  (vorherige Seite)  den  $\text{RSC (3, 2, 2)}_4$, dessen Generatormatrix folgende Form hat:

\[ { \boldsymbol{\rm G} } = \begin{pmatrix} g_{00} & g_{01} & g_{02}\\ g_{10} & g_{11} & g_{12} \end{pmatrix}\hspace{0.05cm},\hspace{0.3cm} g_{ij} \in {\rm GF}(2^2) \hspace{-0.01cm}\setminus \hspace{-0.01cm} \{0\} = \big \{\hspace{0.05cm} \alpha^{0} \hspace{0.05cm},\hspace{0.1cm} \alpha^{1}\hspace{0.05cm},\hspace{0.1cm} \alpha^{2} \hspace{0.05cm}\big \}\hspace{0.05cm}. \]

Daneben gilt:

  • Die erste Zeile von  $\boldsymbol{\rm G}$  gibt das Codewort für das Informationswort  $\underline {u}_1 = (1, 0)$  an bzw. für die Polynomfunktion  $u_1(x) = 1$.  Damit erhält man die Matrixelemente der ersten Zeile zu
$$g_{00} = u_{1}(\alpha^{0}) = 1\hspace{0.05cm},$$
$$g_{01} = u_{1}(\alpha^{1}) = 1\hspace{0.05cm},$$
$$g_{02} = u_{1}(\alpha^{2}) = 1\hspace{0.05cm}.$$
  • Die zweite Zeile ist gleich dem Codewort für das Informationswort  $\underline {u}_2 = (0,\ 1)$   ⇒   $u_2(x) = x$.  Die Matrixelemente der zweiten Zeile lauten somit:
$$g_{10} = u_{2}(\alpha^{0}) = \alpha^{0} = 1\hspace{0.05cm},$$
$$g_{11} = u_{2}(\alpha^{1}) = \alpha \hspace{0.05cm},$$
$$g_{12} = u_{2}(\alpha^{2}) = \alpha^{2}\hspace{0.05cm}.$$
  • Somit lautet die komplette Generatormatrix:
\[{ \boldsymbol{\rm G} } = \begin{pmatrix} 1 & 1 & 1\\ 1 & \alpha & \alpha^2 \end{pmatrix}\hspace{0.05cm}.\]
Codetabelle des  $\text{RSC (3, 2, 2)}_4$  auf Symbolebene
  • Für das Informationswort  $\underline {u}= (u_0, \ u_1)$  mit den Symbolen
$$u_0, \ u_1 ∈ \{0, \ \alpha^0, \ \alpha^1 = \alpha, \ \alpha^2\}$$

erhält man unter Berücksichtigung der beiden Gleichungen   $\alpha^2 = \alpha + 1$   sowie   $\alpha^3 = \alpha^0 = 1$   wiederum die Codetabelle des  $\text{RSC (3, 2, 2)}_4$  auf Symbolebene.

  1. Man erhält natürlich mit der gleichen Generatormatrix genau die gleiche Codetabelle  $\underline {u}   ↔   \underline {c}$  wie nach der Berechnung über die Funktion  $u(x)$.
  2. Die entsprechende Codetabelle auf Bitebene  $($siehe  $\text{Beispiel 2}$  auf der vorherigen Seite$)$  ergibt sich wieder,  wenn man die Elemente nicht in Exponentendarstellung angibt,  sondern in Koeffizientenform:
\[(0, \hspace{0.1cm}\alpha^{0}, \hspace{0.1cm}\alpha^{1}, \hspace{0.1cm}\alpha^{2}) \hspace{0.3cm}\Leftrightarrow\hspace{0.3cm}(00, \hspace{0.1cm}01, \hspace{0.1cm}10, \hspace{0.1cm}11) \hspace{0.05cm}. \]


Generatormatrix und Prüfmatrix


Wir verallgemeinern nun das Ergebnis der letzten Seite für einen Reed–Solomon–Code mit

  • der Dimension  $k$  (Symbolanzahl pro Informationsblock),
  • der Codewortlänge  $n$  (Symbolanzahl pro Codewort).

⇒   Diee  "Generatormatrix"  $\boldsymbol{\rm G}$  $(k$ Zeilen,  $n$ Spalten$)$  und  "Prüfmatrix"  $\boldsymbol{\rm H}$  $(n-k$ Zeilen,  $n$  Spalten$)$ müssen gemeinsam folgende Gleichung erfüllen:

$${\boldsymbol{\rm G} } \cdot { \boldsymbol{\rm H } }^{\rm T}= { \boldsymbol{\rm 0} }\hspace{0.05cm}.$$
  • Hierbei bezeichnet  "$\boldsymbol{\rm 0}$"  eine Nullmatrix:  $($alle Elemente gleich $0)$  mit  $k$  Zeilen und  $n-k$  Spalten.


$\text{Beispiel 4:}$  Wir betrachten den  $\text{RSC (7, 3, 5)}_8$.

  • odeparameter  $n= 7$,  $k= 3$,
  • basierend auf dem Galoisfeld  $\rm GF(2^3 = 8)$ 
  • mit der Nebenbedingung  $\alpha^3 =\alpha + 1$.


Beachten Sie hinsichtlich der Codebezeichnung:

  1. Der dritte Parameter der für Blockcodes üblichen Nomenklatur nennt die freie Distanz  $d_{\rm min}= 5$.
  2. Anders als bei den im Kapitel  "Beispiele binärer Blockcodes"  behandelten binären Codes  $($Single Parity–check Code,  Repetition Code,  Hamming Code$)$  wird bei den Reed–Solomon–Codes noch der Hinweis  $q$  zum Galoisfeld hinzugefügt  $($hier:   $q = 8)$.

Alle Elemente der Generatormatrix und der Prüfmatrix,

\[{ \boldsymbol{\rm G} } = \begin{pmatrix} 1 & 1 & 1 & 1 & 1 & 1 & 1\\ 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} \end{pmatrix}\hspace{0.05cm},\hspace{0.4cm} { \boldsymbol{\rm H} } = \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^2 & \alpha^{5} & \alpha^{1} & \alpha^{4}\\ 1 & \alpha^4 & \alpha^1 & \alpha^{5} & \alpha^{2} & \alpha^{6} & \alpha^{3} \end{pmatrix}\hspace{0.05cm}, \]

entstammen dem Galoisfeld  ${\rm GF}(2^3) \hspace{-0.01cm}\setminus \hspace{-0.01cm} \{0\} = \big \{\hspace{0.05cm} \alpha^{0} \hspace{0.05cm},\hspace{0.1cm}\alpha^{1}\hspace{0.05cm},\hspace{0.1cm} \alpha^{2} \hspace{0.05cm},\hspace{0.1cm} \alpha^{3} \hspace{0.05cm},\hspace{0.1cm}\alpha^{4}\hspace{0.05cm},\hspace{0.1cm} \alpha^{5} \hspace{0.05cm},\hspace{0.1cm} \alpha^{6} \hspace{0.05cm}\big \}$. Für das Matrixprodukt gilt:

\[{ \boldsymbol{\rm G} } \cdot { \boldsymbol{\rm H } }^{\rm T}= \begin{pmatrix} 1 & 1 & 1 & 1 & 1 & 1 & 1\\ 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} \end{pmatrix} \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} = \begin{pmatrix} 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \end{pmatrix} \hspace{0.05cm}.\]

Dies soll hier nur für zwei Elemente nachgewiesen werden:

  • Erste Zeile,  erste Spalte:
\[1 \hspace{0.1cm} \cdot \hspace{0.1cm} \big [1 + \alpha^1 + \alpha^2 + \alpha^3 + \alpha^4 + \alpha^5 + \alpha^6 \big ] = 1 + \alpha + \alpha^2 + (\alpha + 1) + (\alpha^2 + \alpha)+ (\alpha^2 + \alpha +1)+ (\alpha^2 + 1) = 0 \hspace{0.05cm}; \]
  • Letzte Zeile,  letzte Spalte:
\[1 \hspace{0.1cm} \cdot \hspace{0.1cm} 1 + \alpha^2 \cdot \alpha^4 + \alpha^4 \cdot \alpha^1 + \alpha^6 \cdot \alpha^5+ \alpha^1 \cdot \alpha^2+ \alpha^3 \cdot \alpha^6+ \alpha^5 \cdot \alpha^3= 1 + \alpha^6 + \alpha^5 + \alpha^{11} + \alpha^{3}+ \alpha^{9}+ \alpha^{8} =\]
\[ \hspace{1.5cm} = \hspace{0.15cm} 1 + \alpha^6 + \alpha^5 + \alpha^{4} + \alpha^{3}+ \alpha^{2}+ \alpha^{1} =0 \hspace{0.05cm}.\]


Singleton–Schranke und minimale Distanz


Eine wichtige Kenngröße eines jeden Blockcodes ist die  "minimale Distanz"  zwischen zwei beliebigen Codeworten  $\underline {c}_i$  und  $\underline {c}_j$.

  • Die Reed–Solomon–Codes gehören zur Klasse der  linearen und  zyklischen  Codes.  Bei diesen kann man vom Nullwort  $\underline {c}_0 = (0, 0, \hspace{0.05cm} \text{...} \hspace{0.05cm}, 0)$  als Bezugsgröße ausgehen.
  • Aus der Anzahl der Nullen in den anderen Codeworten  $\underline {c}_j ≠ \underline {c}_0$  lässt sich das  "Distanzspektrum"  $\{ \hspace{0.05cm}W_j\hspace{0.05cm}\}$  angeben.


$\text{Beispiel 5:}$  Die Tabelle verdeutlicht die Bestimmung des Distanzspektrums für den  $\text{RSC (3, 2, 2)}_4$.

  • Gegenüber den bisherigen Grafiken wird die Symbolmenge vereinfachend mit  $\{0,\ 1,\ 2,\ 3\}$  anstelle von $\{0,\ \alpha^0,\ \alpha^1,\ \alpha^2\}$  bezeichnet.
  • Die Distanz  $d$  zwischen  $\underline {c}_j$  und dem Nullwort  $\underline {c}_0$  ist identisch dem  "Hamming–Gewicht"  $w_{\rm H}(\underline {c}_j)$.
Zur Herleitung des Distanzspektrums für den  $\text{RSC (3, 2, 2)}_4$

⇒   Aus der oberen Tabelle kann unter anderem abgelesen werden:

  • Neun Codeworte unterscheiden sich vom Nullwort in zwei Symbolen und sechs Codeworte in drei Symbolen:  
$$W_2 = 9,\ \ W_3 = 6.$$
  • Es gibt kein einziges Codewort mit nur einer Null. Das heißt:   Die minimale Distanz beträgt hier 
$$d_{\rm min} = 2.$$

⇒   Aus der unteren Tabelle erkennt man, dass auch für die Binärdarstellung  $d_{\rm min} = 2$  gilt.


Dieses empirische Ergebnis soll nun verallgemeinert werden:

$\text{Ohne Beweis:}$ 

  1. Die  "minimale Distanz"  eines jeden  $(n, k)$–Reed–Solomon–Codes ist   $d_{\rm min} =n-k+1$   ⇒   es lassen sich   $e = d_{\rm min} -1 =n-k$   Symbolfehler erkennen.
  2. Bei  "fehlerkorrigierenden Codes"  wählt man meist  $d_{\rm min} $  ungeradzahlig   ⇒   $n-k$  geradzahlig.
  3. Bei Reed–Solomon–Codes können dann bis zu   $t =(n-k)/2$  Symbolfehler korrigiert werden.
  4. Die  "Singleton–Schranke"  besagt,  dass für alle linearen Codes  $d_{\rm min} \le n-k+1$  gilt.
  5. Reed–Solomon–Codes erreichen diese Schranke mit Gleichheit;  sie sind so genannte  "MDS–Codes"  ("Maximum Distance Separable").
  6. Das  "Distanzspektrum"  setzt sich zusammen aus  $W_0 = 1$  sowie weiteren Gewichtsfaktoren  $W_i$  mit  $d ≤ i ≤ n$,  wobei in der folgenden Gleichung  $d_{\rm min}$  mit  $d$  abgekürzt ist:
\[W_i = {n \choose i} \cdot \sum_{j = 0}^{i-d}\hspace{0.15cm}(-1)^j \cdot {i \choose j} \cdot \bigg [\hspace{0.03cm}q^{i\hspace{0.03cm}-\hspace{0.03cm}j\hspace{0.03cm}-\hspace{0.03cm}d\hspace{0.03cm}+\hspace{0.03cm}1}-1 \hspace{0.03cm} \bigg ]\hspace{0.05cm}.\]

Codebezeichnung und Coderate


Die übliche Bezeichnung für die Reed–Solomon–Codes ist  ${\rm RSC} \ \ (n,\ k, \ d_{\rm min})_q$  mit

  • der Länge  $n$  des Codes  $($Symbolanzahl eines Codewortes$)$,
  • der Dimension  $k$  des Codes  $($Symbolanzahl eines Informationswortes$)$,
  • der minimalen Distanz  $d_{\rm min} = n-k+1$,  maximal entsprechend der  "Singleton–Schranke",  und
  • der Größe  $q = 2^m$  des Galoisfeldes  ${\rm GF}(q)$.

⇒   Alle Elemente  $u_i$  des Informationswortes   $\underline{u}= (u_0, \hspace{0.05cm}\text{...} \hspace{0.05cm}, u_i, \hspace{0.05cm}\text{...} \hspace{0.05cm}, u_{k-1})$   und alle Elemente  $c_i$  des Codewortes   $\underline{c}= (c_0, \hspace{0.05cm}\text{...} \hspace{0.05cm}, c_i, \hspace{0.05cm}\text{...} \hspace{0.05cm}, c_{n-1})$   sind nicht binäre Symbole und entstammen dem Galoisfeld  ${\rm GF}(q)$.

⇒   Für die Realisierung werden diese Symbole stets auch binär dargestellt und man kommt zum äquivalenten binären Reed–Solomon–Code  ${\rm RSC} \ \ (n_{\rm bin},\ k_{\rm bin}, \ d_{\rm min})_2$  mit

  • $n_{\rm bin} = n \cdot m$   Bit eines Codewortes,
  • $k_{\rm bin} = k \cdot m$   Bit eines Informationswortes.

⇒   Die Coderate wird durch diese Maßnahme nicht verändert:

\[R_{\rm bin} = \frac{k_{\rm bin}}{n_{\rm bin}} = \frac{k \cdot m}{n \cdot m} = \frac{k}{n} = R \hspace{0.05cm}.\]

⇒   Ebenso ändert sich durch den Übergang von  ${\rm GF}(q)$  auf  ${\rm GF}(2)$  nichts an der minimalen Distanz  $d_{\rm min}$.

$\text{Beispiel 6:}$  Wie im  $\text{Beispiel 5}$  (vorherige Seite)  betrachten wir wieder den  $\text{RSC (3, 2, 2)}_4$. 

Herleitung der Distanzspektren von  $\text{RSC (3, 2, 2)}_4$  und  $\text{RSC (6, 4, 2)}_2$
  1. Wir geben dessen  "Distanzspektrum"  $\{ \hspace{0.05cm}W_j\hspace{0.05cm}\}$  nochmals an  (obere Tabelle).
  2. Die untere Tabelle gilt für den äquivalenten binären Reed–Solomon–Code  $\text{RSC (6, 4, 2)}_2$.


Man erkennt aus diesen Zahlenwerten:

  • Beide Codes haben die gleiche Coderate  $R = k/n =2/3$ 
  • Beide Codes auch die gleiche minimale Distanz  $d_{\rm min} = 2$.
  • Die beiden Codes unterscheiden sich jedoch hinsichtlich des Distanzspektrums  $\{ \hspace{0.05cm}W_j\hspace{0.05cm}\}$  und der  Gewichtsfunktion  $W(X)$:
$$\text{RSC (3, 2, 2)}_4\text{:} \hspace{0.3cm} W_0 = 1\hspace{0.05cm}, \hspace{0.2cm}W_2 = 9\hspace{0.05cm}, \hspace{0.2cm}W_3 = 6$$
$$\Rightarrow\hspace{0.3cm}W(X) = 1 + 9 \cdot X^2 + 6 \cdot X^3\hspace{0.05cm}.$$
$$\text{RSC (6, 4, 2)}_2\text{:} \hspace{0.3cm} W_0 = 1\hspace{0.05cm}, \hspace{0.2cm}W_2 = 3\hspace{0.05cm}, \hspace{0.2cm}W_3 = 8 \hspace{0.05cm}, \hspace{0.2cm}W_4 = 3\hspace{0.05cm}, \hspace{0.2cm}W_6 = 1 \hspace{0.3cm}\Rightarrow\hspace{0.3cm}W(X) = 1 + 3 \cdot X^2 + 8 \cdot X^3 + 4 \cdot X^4 + X^6 \hspace{0.05cm}.$$


Bedeutung der Reed–Solomon–Codes


Anhand des hier oft beispielhaft betrachteten  $\text{RSC (3, 2, 2)}_4$  konnten wir viele Eigenschaften der Reed–Solomon–Codes in überschaubarem Rahmen kennenlernen.

  • Praxisrelevant ist dieser Code allerdings nicht,  da wegen  $d_{\rm min} = 2$  kein einziger Fehler korrigiert und auch nur ein einziger Fehler erkannt werden kann.
  • Schon der nächstgrößere Code  $\text{RSC (7, 3, 5)}_8$,  der bis zu  $t = 2$  Fehler korrigieren kann,  weist bereits eine Codetabelle mit   $8^3 = 512$   Einträgen auf und ist zu Demonstrationszwecken ungeeignet.


In der Praxis werden meist sehr große Reed–Solomon–Codes eingesetzt,  zum Beispiel der  $\text{RSC (255, 223, 33)}_{256}$  mit folgenden Eigenschaften:

  1. Der Code basiert auf dem Galoisfeld  $\rm GF(2^8)$.  Jedes Symbol entspricht somit einem Byte.  Die Coderate ist mit  $R = 0.8745$  relativ groß.
  2. Trotz dieser großen Coderate  $($also geringe Redundanz$)$  können mit diesem Code bis zu  $e = 32$  Fehler innerhalb eines Blocks aus  $255$  Symbolen erkannt und  $t = 16$  Fehler korrigiert werden.
  3. Die Codetabelle würde allerdings   $2^{8 \hspace{0.05cm}\cdot \hspace{0.05cm} 223}= 2^{ \hspace{0.05cm} 1784} ≈ 10^{537}$   Einträge aufweisen und wird deshalb wahrscheinlich auch von niemanden tatsächlich erstellt.

Der große Vorteil der Reed–Solomon–Codes  $($und einer ganzen Reihe davon abgeleiteter weiterer Codes$)$  ist zum einen,  dass sie analytisch geschlossen konstruiert werden können,  zum anderen ihre große Flexibilität hinsichtlich der Codeparameter.  Meist geht man wie folgt vor:

  1. Man gibt die Korrekturfähigkeit in Form des Parameters  $t$  vor.  Daraus ergibt sich die minimale Distanz   $d_{\rm min} = 2t + 1$   und die Differenz   $n-k = 2t$   entsprechend der Singleton–Schranke.  Einen besseren Wert gibt es nicht.
  2. Ein weiterer Entwurfsparameter ist die Coderate  $R=k/n$,  wobei die Codewortlänge  $n = 2^m -1$  nicht völlig frei wählbar ist.  Durch Erweiterung,  Verkürzung und Punktierung – siehe  "Aufgabe 1.9Z"  – kann die Vielzahl an möglichen Codes weiter vergrößert werden.
  3. Bei Reed–Solomon–Codes ist die Gewichtsverteilung exakt bekannt und es ist eine Anpassung an die Fehlerstruktur des Kanals möglich.  Diese Codes sind insbesondere für Bündelfehlerkanäle gut geeignet,  die bei mobilen Funksystemen aufgrund temporärer Abschattungen häufig vorliegen.
  4. Im Falle statistisch unabhängiger Fehler sind so genannte   "BCH–Codes"  $($von $\rm B$ose–$\rm C$haudhuri–$\rm H$ocquenghem$)$  besser geeignet.  Diese sind mit den Reed–Solomon–Codes eng verwandt,  allerdings erfüllen sie nicht immer das Singleton–Kriterium.  Eine ausführliche Beschreibung finden Sie in  [Fri96][1].
  5. Die Decodierung nach dem  "BDD–Prinzip"  ("Bounded Distance Decoding")  kann rechentechnisch sehr einfach erfolgen,  zum Beispiel mit dem  "Berlekamp–Massey–Algorithmus".  Zudem kann der Decoder ohne großen Mehraufwand auch  "Soft Decision Information"  verarbeiten.

Aufgaben zum Kapitel


Aufgabe 2.7: Reed–Solomon–Code (7, 3, 5) zur Basis 8

Aufgabe 2.7Z: Reed–Solomon–Code (15, 5, 11) zur Basis 16

Aufgabe 2.8: Generatorpolynome für Reed-Solomon

Aufgabe 2.8Z: „Plus” und „Mal” in GF(2 hoch 3)

Aufgabe 2.9: Reed–Solomon–Parameter

Aufgabe 2.10: Fehlererkennung bei Reed–Solomon

Aufgabe 2.10Z: Coderate und minimale Distanz

Quellenverzeichnis

  1. Friedrichs, B.:  Kanalcodierung – Grundlagen und Anwendungen in modernen Kommunikations- systemen.  Berlin – Heidelberg: Springer, 1996.