Definition und Eigenschaften von Reed–Solomon–Codes

Aus LNTwww
Wechseln zu:Navigation, Suche

Konstruktion von Reed–Solomon–Codes (1)


Ein Reed–Solomon–Code – im Folgenden manchmal auch verkürzt als RS–Code bezeichnet – ist ein linearer Blockcode, der einem Informationsblock u mit k Symbolen ein entsprechendes Codewort c mit n > k Symbolen zuordnet. Diese noch heute vielfach eingesetzten Codes wurden bereits Anfang der 1960er Jahre von Irving Stoy Reed und Gustave Solomon erfunden.

Linearer (n, k)–Blockcode

In Kapitel 1.1 wurde der Informationsblock mit u = (u1, ... , uk) und das Codewort mit x = (x1, ... , xn) bezeichnet. Die Nomenklaturänderung gemäß obiger Grafik wurde vorgenommen, um Verwechslungen mit dem Argument von Polynomen auszuschließen und die Beschreibung der RS–Codes zu vereinfachen.

Alle in Kapitel 1.4 genannten Eigenschaften linearer zyklischer Blockcodes gelten auch für einen Reed–Solomon–Code. Zusätzlich gilt:

  • Konstruktion und Decodierung von RS–Codes basieren auf der Arithmetik eines Galoisfeldes GF(q), wobei wir uns hier auf binäre Erweiterungskörper mit q = 2m 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}...\hspace{0.1cm}, \alpha^{q-2}\hspace{0.05cm} \big \}\hspace{0.05cm}. \]
  • Prinzipiell unterschiedlich zum ersten Kapitel ist, dass die Koeffizienten u0, u1, ... , uk–1 nun nicht mehr einzelne Informationsbits (0 oder 1) angeben, sondern ebenfalls Elemente aus GF(2m) sind. Jedes der m Symbole steht vielmehr für m Bit.
  • Bei den Reed–Solomon–Codes ist der Parameter n (Codelänge) 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 ui ∈ GF(2m) des Informationsblocks u ( 0 ≤ i < k) 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}... \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 c0, ... , cn–1 des zugehörigen Codewortes c = (c0, c1, ... , cn–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 ci ∈ GF(2m) vor der Übertragung wieder in Binärform ⇒ GF(2) gebracht, wobei dann jedes Symbol durch m Bit dargestellt wird.

Konstruktion von Reed–Solomon–Codes (2)


Fassen wir die Aussagen der letzten Seite kurz zusammen:

: Ein (n, k)–Reed–Solomon–Code für das Galoisfeld GF(2m) wird festgelegt durch
  • die n = 2m–1 Elemente von GF(2m)\{0} = {α0, α1, ... , αn–1}, wobei α ein primitives Element von GF(2m) bezeichnet,
  • ein an den Informationsblockt 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 | \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 einem einfachen Beispiel verdeutlicht werden.

: Wir gehen von den folgenden Codeparametern aus:

\[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(α) = α2 + α + 1 = 0  ⇒  α2 = α + 1 erhält man folgende Zuordnungen zwischen der Exponenten–, der Polynom– und der Koeffizientendarstellung von GF(22):

GF(22) in Exponenten–, Polynom– und Koeffizientenform

Der Koeffizientenvektor wird durch das Polynom u(x) = u0 + ui · x ausgedrückt. Der Polynomgrad ist <nobr>k – 1 = 1.</nobr> Für u0 = α1 und u1 = α2 erhält man beispielsweise das Polynom u(x) = α + α2 · x und damit

\[c_0 \hspace{-0.15cm} = \hspace{-0.15cm} u (x = \alpha^0) = u (x = 1) = \alpha + \alpha^2 \cdot 1 = \alpha + (\alpha + 1) =1 \hspace{0.05cm},\] \[c_1 \hspace{-0.15cm} = \hspace{-0.15cm} u (x = \alpha^1) = \alpha + \alpha^2 \cdot \alpha = \alpha + \alpha^3 = \alpha + \alpha^0 = \alpha + 1 = \alpha^2 \hspace{0.05cm},\] \[c_2 \hspace{-0.15cm} = \hspace{-0.15cm} 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} \hspace{-0.15cm} = \hspace{-0.15cm} (\alpha^1, \alpha^2)\hspace{0.57cm}\leftrightarrow\hspace{0.3cm} \underline {c} = (1, \alpha^2, 0)\hspace{0.05cm},\]

\[\underline {u}_{\rm bin} \hspace{-0.15cm} = \hspace{-0.15cm} (1,0,1,1)\hspace{0.3cm}\leftrightarrow\hspace{0.3cm} \underline {c}_{\rm bin} = (0,1,1,1,0,0)\hspace{0.05cm}.\]


Konstruktion von Reed–Solomon–Codes (3)


Die folgende Grafik zeigt die Codetabelle dieses RSC (3, 2, 2)4 genannten Reed–Solomon–Codes. Die Bezeichnung bezieht sich auf die Parameter n = 3, k = 2, dmin = 2 und q = 4. In den Spalten 1 bis 3 erkennt man den Zusammenhang uu(x) → c, in den beiden letzten die Codiervorschrift ubincbin.

Codetabelle des RSC (3, 2, 2)4




Zur Verdeutlichung nochmals der Eintrag für (α0, α2):

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

Daraus ergeben sich folgende Codesymbole:

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







Hinweis: Aus der Elementenmenge {0, α0 = 1, α1, α2} sollte nicht geschlossen werden, dass für diesen Code die 3D–Darstellung mit den Achsen α0 = 1, α1 und α2 zutrifft. Aus der Koeffizientendarstellung geht vielmehr eindeutig hervor, dass GF(22) ein zweidimensionaler Code ist, wobei die Achsen der 2D–Darstellung mit α0 = 1 und α1 = α zu beschriften sind.

Generatormatrix und Prüfmatrix (1)


Da es sich beim Reed–Solomon–Code um einen linearen Blockcode handelt, ist der Zusammenhang zwischen Informationswort u und Codewort c durch die Generatormatrix 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 1.4 sind nun aber die Elemente der Generatormatrix nicht mehr binär (0 oder 1), sondern entstammen dem Galoisfeld GF(2m) \ {0}.

: Wir betrachten wie auf der letzten Seite wieder den 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 G gibt das Codewort für das Informationswort u1 = (1, 0) an bzw. für die Polynomfunktion u1(x) = 1. Damit erhält man die Matrixelemente der ersten Zeile zu
\[g_{00} = u_{1}(\alpha^{0}) = 1\hspace{0.05cm},\hspace{0.3cm} g_{01} = u_{1}(\alpha^{1}) = 1\hspace{0.05cm},\hspace{0.3cm} g_{02} = u_{1}(\alpha^{2}) = 1\hspace{0.05cm}.\]
  • Die zweite Zeile ist gleich dem Codewort für das Informationswort u2 = (0, 1)  ⇒  u2(x) = x. Die Matrixelemente der zweiten Zeile lauten somit:
\[g_{10} = u_{2}(\alpha^{0}) = \alpha^{0} = 1\hspace{0.05cm},\hspace{0.3cm} g_{11} = u_{2}(\alpha^{1}) = \alpha \hspace{0.05cm},\hspace{0.3cm} g_{12} = u_{2}(\alpha^{2}) = \alpha^{2}\hspace{0.05cm}.\]
\[\Rightarrow\hspace{0.3cm} { \boldsymbol{\rm G}} = \begin{pmatrix} 1 & 1 & 1\\ 1 & \alpha & \alpha^2 \end{pmatrix}\hspace{0.05cm}.\]

Für das Informationswort u = (u0, u1) mit den Symbolen u0, u1 ∈ {0, α0, α1, α2} erhält man unter Berücksichtigung der beiden Gleichungen α2 = α + 1 sowie α3 = α0 = 1 wiederum die Codetabelle des RSC (3, 2, 2)4 auf Symbolebene.

Codetabelle des RSC (3, 2, 2)4 auf Symbolebene

Man erhält natürlich mit der Generatormatrix genau die gleiche Codetabelle uc wie nach der Berechnung über die Funktion u(x). Die entsprechende Codetabelle auf Bitebene 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 (2)


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

Die Generatormatrix G (mit k Zeilen und n Spalten) und die Prüfmatrix H (nk Zeilen, n Spalten) müssen folgende Gleichung erfüllen:

\[{ \boldsymbol{\rm G}} \cdot { \boldsymbol{\rm H }}^{\rm T}= { \boldsymbol{\rm 0}}\hspace{0.05cm}.\]

Hierbei bezeichnet 0 eine Nullmatrix (alle Elemente gleich 0) mit k Zeilen und nk Spalten.

: Wir betrachten den RSC (7, 3, 5)8  ⇒  Codeparameter n = 7, k = 3, basierend auf dem Galoisfeld GF(23 = 8) mit der Nebenbedingung α3 = α + 1. Beachten Sie hinsichtlich der Bezeichnung:
  • Der dritte Parameter der für Blockcodes üblichen Nomenklatur nennt die freie Distanz dmin = 5.
  • Anders als bei den in Kapitel 1.3 behandelten binären Codes (SPC, RC, HC) 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} \]

entstammen dem Galoisfeld GF(23) \ {0} = {α0, α1, α2, α3, α4, α5, α6}. 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.15cm} \cdot \hspace{0.15cm} \big [1 + \alpha^1 + \alpha^2 + \alpha^3 + \alpha^4 + \alpha^5 + \alpha^6 \big ] =\]
\[\hspace{0.15cm} = \hspace{0.15cm} 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.15cm} \cdot \hspace{0.15cm} 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=\]
\[\hspace{0.15cm} = \hspace{0.15cm} 1 + \alpha^6 + \alpha^5 + \alpha^{11} + \alpha^{3}+ \alpha^{9}+ \alpha^{8} =\]
\[ \hspace{0.15cm} = \hspace{0.15cm} 1 + \alpha^6 + \alpha^5 + \alpha^{4} + \alpha^{3}+ \alpha^{2}+ \alpha^{1} =0 \hspace{0.05cm}.\]