Channel Coding/Definition and Properties of Reed-Solomon Codes

1. Channel Coding
2. Reed–Solomon–Codes and Their Decoding
3. Definition and Properties of Reed-Solomon Codes

• Previous page
• Next page

• Previous page
• Next page

Coding principle and code parameters

A Reed–Solomon Code  – hereafter sometimes shortened to  RS code  is a  "linear block code" that is

Linear $(n, \, k)$ block code

• an information block  $\underline{u}$  with  $k$  symbols.
• assings a corresponding codeword  $\underline{c}$  with  $n > k$

symbols. These codes, still widely used today, were invented as early as the early 1960s by  "Irving Stoy Reed"  and  "Gustave Solomon" .

In the chapter  "Objective of Channel Coding"  the information block was denoted by  $\underline{u}= (u_1,$ ... , $u_k)$  and the codeword by  $\underline{x}= (x_1,$ ... , $x_n)$ .

The nomenclature change  $\underline{x} \to \underline{c}$  (see graphic) was made to eliminate confusion with the argument of polynomials and to simplify the description of RS codes.

All the properties of linear cyclic block codes mentioned in the section  "linear codes and cyclic codes"  also apply to a Reed–Solomon–code. In addition:

• Construction and decoding of Reed–Solomon codes are based on the arithmetic of a Galois field  ${\rm GF}(q)$, where we restrict ourselves here to binary extension fields with  $q=2^m$ elements :

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

• Principally different from the first chapter is that the coefficients  $u_0$,  $u_1$, ... ,  $u_{k-1}$  now no longer specify individual bits of information  $(0$ or $1)$  but are also elements of  ${\rm GF}(2^m)$ . Each of the  $n$  symbols represents  $m$  bits.
  

• For Reed–Solomon codes, the parameter  $n$  (code length) is always equal to the number of elements of the Galois field excluding the zero word:   $n= q-1$.
  We use the following nomenclature for this purpose:

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

• The  $k$  coefficients  $u_i \in {\rm GF}(2^m)$  of the information block  $\underline{u}$, where for the index  $ 0 \le i < k$  holds, can also be formally expressed by a polynomial  $u(x)$  . The degree of the polynomial is here  $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}.\]

• The  $n$  symbols of the associated codeword  $\underline{c}= (c_0, c_1,$ ... , $c_{n-1})$  result with this polynomial  $u(x)$  to be

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

• Mostly the code symbols  $c_i \in {\rm GF}(2^m)$  are converted back to binary   ⇒   ${\rm GF}(2)$  before transmission, where each symbol is then represented by  $m$  bits.
  

We briefly summarize these statements:

$\text{Definition:}$  A  $(n, k)$–Reed–Solomon code  for the Galois field  ${\rm GF}(2^m)$  is defined by.

• the  $n= 2^{m-1}$  elements of  ${\rm GF}(2^m) \hspace{-0.05cm}\setminus \hspace{-0.05cm} \{0\} =\{ \alpha^0, \alpha^1, \, \text{...} \, , \alpha^{n-1}\}$, where  $\alpha$  denotes a  "primitive element"  of  ${\rm GF}(2^m)$  denotes,

• an information blockt  $\underline{u}$  matched  "polynomial"  of degree  $k-1$  the 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}.\]

Thus, the  $(n, k)$–Reed–Solomon code can be described as.

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

The previous information will now be illustrated by two simple examples.

$\rm GF(2^2)$  in three different representations:
Exponential, polynomial and coefficient form

$\text{Example 1:}$  We consider the following code parameters:

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

Starting from the conditional equation  $p(\alpha) = \alpha^2 + \alpha + 1 = 0$  ⇒   $\alpha^2 = \alpha + 1$  one obtains the assignments between

• the exponential representation,
• the polynomial representation and
• the coefficient representation

of  ${\rm GF}(2^2)$  according to the above table. From this it can be seen:

• The coefficient vector is expressed by the polynomial  $u(x) = u_0 + u_1 \cdot x$ . The polynomial degree is  $k- 1 = 1$.
• For  $u_0 = \alpha^1$  and  $u_1 = \alpha^2$  we obtain, for example, the polynomial  $u(x) = \alpha + \alpha^2 \cdot x$  and thus

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

This results in the following assignments on symbol or bit level:

\[\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{Example 2:}$  On the right is the code table of the  $\text{RSC (3, 2, 2)}_4$  named Reed–Solomon code.

• The label refers to the parameters  $n=3$,  $k=2$,  $d_{\rm min}=2$  and  $q = 4$.
• In columns 1 to 3, one can see the relationship  $\underline {u} \ → \ u(x) \ → \ \underline {c}$.
• In the last two columns, the coding rule  $\underline {u}_{\rm bin} \ ↔ \ \underline {c}_{\rm bin}$ is given.
  

For clarification again the entry for $(\alpha^0, \ \alpha^2)$:

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

This results in the following code symbols:

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

Hints:

• From the element set $\{0, \ \alpha^0 = 1, \ \alpha^1 = \alpha, \ \alpha^2\}$ it should not be concluded that for this code the 3D–representation with axes  $\alpha^0 = 1$,  $\alpha^1 = \alpha$,  $\alpha^2$  applies. See section   "primitive polynomials" – example 5.
• On the contrary, from the coefficient representation in  $\text{Example 1}$  it is clear that   ${\rm GF} (2^2)$  is two-dimensional, where the axes of the two dimensional representation are to be labeled  $\alpha^0 = 1$  and  $\alpha^1 = \alpha$  .

Generator matrix of Reed-Solomon codes

Since the Reed–Solomon code is a linear block code, the relationship between information word  $\underline {u}$  and codeword  $\underline {c}$  given by the  "Generator Matrix"  $\boldsymbol{\rm G}$ :

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

As with any linear  $(n, k)$–block code, the generator matrix consists of  $k$  rows and  $n$  columns. In contrast to the chapter  "General Description of Linear Block Codes"  however, now the elements of the generator matrix are no longer binary  $(0$ or $1)$, but come from the Galois field  ${\rm GF}(2^m) \hspace{-0.05cm}\setminus \hspace{-0.05cm} \{0\} $.

$\text{Example 3:}$  We consider as in  $\text{Example 2}$  (previous page) the  $\text{RSC (3, 2, 2)}_4$ whose generator matrix has the following form:

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

Beside this:

• The first row of  $\boldsymbol{\rm G}$  gives the codeword for the information word  $\underline {u}_1 = (1, 0)$  respectively for the polynomial function $u_1(x) = 1$. Thus one receives the matrix elements of the first row

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

• The second row is equal to the code word for the information word $\underline {u}_2 = (0, 1)$   ⇒   $u_2(x) = x$. Thus, the matrix elements of the second row are:

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

For the information word $\underline {u}= (u_0, \ u_1)$ mit den Symbolen $u_0, \ u_1 ∈ \{0, \ \alpha^0, \ \alpha^1 = \alpha, \ \alpha^2\}$  one obtains, considering the two equations  $\alpha^2 = \alpha + 1$  and  $\alpha^3 = \alpha^0 = 1$  again the code table of the  $\text{RSC (3, 2, 2)}_4$  at symbol level.

Code table of the  $\text{RSC (3, 2, 2)}_4$  at symbol level

• Of course, with the generator matrix you get exactly the same code table  $\underline {u}   ↔   \underline {c}$  as after the calculation via the function  $u(x)$.
• The corresponding code table on bit level (see  $\text{Example 2}$  on the previous page) results again, if the elements are not given in exponent representation, but in coefficient form:

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

Generator matrix and parity-check matrix

We now generalize the result of the last page for a Reed–Solomon code with

• the dimension  $k$  (number of symbols per information block),
  

• the codeword length  $n$  (number of symbols per codeword).
  
  

"generator matrix"  $\boldsymbol{\rm G}$  $(k$ rows,  $n$ columns$)$  and  "parity-check matrix"  $\boldsymbol{\rm H}$  $(n-k$ rows,  $n$  columns$)$ must jointly satisfy the following equation:

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

Here,  $\boldsymbol{\rm 0}$  denotes a zero matrix $($all elements equal $0)$  with  $k$  rows and  $n-k$  columns.

$\text{Example 4:}$  We consider the  $\text{RSC (7, 3, 5)}_8$   ⇒   code parameter  $n= 7$,  $k= 3$, based on the Galois field  $\rm GF(2^3 = 8)$  with the constraint  $\alpha^3 =\alpha + 1$. Note with respect to the code name:

• The third parameter of the nomenclature commonly used for block codes names the free distance  $d_{\rm min}= 5$.
  

• Unlike the binary codes discussed in the chapter  "Examples of binary block codes"  (single parity-check code, repetition code, Hamming code), the Reed–Solomon codes still have the hint  $q$  added to the Galois field  $($here:   $q = 8)$.
  
  

All elements of the generator matrix and the parity-check matrix,

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

originate from the Galois field  ${\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 \}$. For the matrix product holds:

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

This will be demonstrated here for two elements only:

• First row, first column:

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

• Last row, last column:

\[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 bound and minimum distance

An important parameter of any block code is the  "minimum distance"  between any two code words  $\underline {c}_i$  and  $\underline {c}_j$.

• The Reed–Solomon–codes belong to the class of  linear  and  cyclic  codes. For these, one can start from the zero word  $\underline {c}_0 = (0, 0, \hspace{0.05cm} \text{...} \hspace{0.05cm}, 0)$  as the reference.
• From the number of zeros in the other codewords  $\underline {c}_j ≠ \underline {c}_0$  the "distance spectrum"  $\{ \hspace{0.05cm}W_j\hspace{0.05cm}\}$  can be specified.
  

$\text{Example 5:}$  The table illustrates the determination of the distance spectrum for the  $\text{RSC (3, 2, 2)}_4$.

• Compared to the previous graphs, the symbol set is simplified by  $\{0,\ 1,\ 2,\ 3\}$  instead of $\{0,\ \alpha^0,\ \alpha^1,\ \alpha^2\}$ .
• The distance  $d$  between  $\underline {c}_j$  and the null word  $\underline {c}_0$  is identical to  "Hamming weight"  $w_{\rm H}(\underline {c}_j)$.
  

To derive the distance spectrum for the

From the upper table can be read, among others:

• Nine codewords differ from the zero word in two symbols and six codewords differ in three symbols:   $W_2 = 9$,  $W_3 = 6$.
• There is not a single codeword with only one zero. That means:   The minimum distance here is  $d_{\rm min} = 2$.
  

From the table below one can see that also for the binary representation  $d_{\rm min} = 2$  holds.

This empirical result will now be generalized:

$\text{Without proof:}$ 

• The  minimum distance  of each  $(n, k)$–Reed–Solomon codes is  $d_{\rm min} =n-k+1$   ⇒   symbol errors can be detected  $e = d_{\rm min} -1 =n-k$ .
  

• For  error correcting codes  one usually chooses  $d_{\rm min} $  odd   ⇒   $n-k$  even. For RS–codes then up to  $t =(n-k)/2$  symbol errors can be corrected.
  

• The  [en.wikipedia.org/wiki/Singleton_bound "Singleton bound"]  says tat  $d_{\rm min} \le n-k+1$  holds for all linear codes. RS codes reach this bound with equality; they are so-called  "MDS codes"  (Maximum Distance Separable ).

• The  "distance spectrum"  is composed of  $W_0 = 1$  and other weight factors  $W_i$  with  $d ≤ i ≤ n$, where in the following equation  $d_{\rm min}$  is abbreviated as  $d$ :

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

Code name and code rate

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$  und geben dessen  Distanzspektrum  $\{ \hspace{0.05cm}W_j\hspace{0.05cm}\}$  nochmals an (obere Tabelle). Die untere Tabelle gilt für den äquivalenten binären Reed–Solomon–Code  $\text{RSC (6, 4, 2)}_2$.

Herleitung der Distanzspektren von  $\text{RSC (3, 2, 2)}_4$  und  $\text{RSC (6, 4, 2)}_2$

• Beide Codes haben die gleiche Coderate  $R = k/n =2/3$  und 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\hspace{0.3cm}\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 RS–Codes eingesetzt, zum Beispiel der  $\text{RSC (255, 223, 33)}_{256}$  mit folgenden Eigenschaften:

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

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

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

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

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

• 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 von temporären Abschattungen häufig vorliegen.
  

• Im Falle statistisch unabhängiger Fehler sind  BCH–Codes  (von $\rm B$ose–$\rm C$haudhuri–$\rm H$ocquenghem) besser geeignet. Diese sind mit den RS–Codes eng verwandt, allerdings erfüllen sie nicht immer das Singleton–Kriterium. Eine ausführliche Beschreibung finden Sie in [Fri96].
  

• 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