Definition und Eigenschaften von Reed–Solomon–Codes

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.

In Kapitel 1.1 wurde der Informationsblock mit u = (u₁, ... , u_k) und das Codewort mit x = (x₁, ... , x_n) 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 = 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}...\hspace{0.1cm}, \alpha^{q-2}\hspace{0.05cm} \big \}\hspace{0.05cm}. \]

Prinzipiell unterschiedlich zum ersten Kapitel ist, dass die Koeffizienten u₀, u₁, ... , u_k_–1 nun nicht mehr einzelne Informationsbits (0 oder 1) angeben, sondern ebenfalls Elemente aus GF(2^m) 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 u_i ∈ GF(2^m) 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 c₀, ... , c_n_–1 des zugehörigen Codewortes c = (c₀, c₁, ... , 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 ∈ GF(2^m) vor der Übertragung wieder in Binärform ⇒ GF(2) gebracht, wobei dann jedes Symbol durch m Bit dargestellt wird.