Aufgaben:Exercise 2.10Z: Code Rate and Minimum Distance

• Return to book

The two inventors of the Reed-Solomon codes

The codes developed by  "Irving Stoy Reed"  and  "Gustave Solomon"  in the early 1960s are referred to in this tutorial as follows:

$${\rm RSC} \, (n, \, k, \, d_{\rm min}) _q.$$

The code parameters have the following meanings:

• $q = 2^m$  is an indication of the size of the Galois field   ⇒   ${\rm GF}(q)$,
• $n = q - 1$  is the code length (symbol number of a code word),
• $k$  indicates the dimension (symbol number of an information block),
• $d_{\rm min}$  denotes the minimum distance between two codewords. For any Reed-Solomon code, $d_{\rm min} = n - k + 1$.
• No other code with the same  $k$  and  $n$  yields a larger value.

Hints:

• The exercise belongs to the chapter  "Definition and properties of Reed–Solomon Codes".
• Information relevant to this exercise can be found on the  Code name and code rate page.

Questions

1 Specify the characteristics of the  ${\rm RSC} \, (255, \, 223, \, d_{\rm min})_q$ .

$q \hspace{0.2cm} = \ $

$e \hspace{0.2cm} = \ $

$t \hspace{0.2cm} = \ $

$R \hspace{0.2cm} = \ $

$d_{\rm min} \ = \ $

2 Specify the characteristics of the  $\rm RSC \, (2040, \, 1784, \, d_{\rm min})_2$ .

$R \hspace{0.2cm} = \ $

$d_{\rm min} \ = \ $

3 How many bit errors  $(N_3)$  may a received word  $\underline{y}$  have at most, so that it is certainly decoded correctly?

$N_{3} \ = \ $

4 How many bit errors  $(N_4)$  may a received word  $\underline{y}$  have in the best case so that it could still be correctly decoded?

$N_{4} \ = \ $

Solution

Solution

(1)  From the code length $n = 255$ follows $q \ \underline{= 256}$.

• The code rate is given by $R = {223}/{255} \hspace{0.15cm}\underline {=0.8745}\hspace{0.05cm}.$

• The minimum distance is $d_{\rm min} = n - k +1 = 255 - 223 +1

\hspace{0.15cm}\underline {=33}\hspace{0.05cm}.$

• This allows

• $e = d_{\rm min} - 1 \ \underline{= 32}$ symbol errors can be detected, and.
• $t = e/2$ (rounded down), so $\underline{t = 16}$ symbol errors can be corrected.

(2)  The code $\rm RSC \, (2040, \, 1784, \, d_{\rm min})_2$ is the binary representation of the ${\rm RSC} discussed in (1) \, (255, \, 223, \, 33)_{256}$ with exactly the same code rate $R \ \underline{= 0.8745}$ and also the same minimum distance $d_{\rm min} \ \underline{= 33}$ as this one. Here $8$ bits (1 byte) are used per code symbol.

(3)  From $d_{\rm min} = 33$ follows again $t = 16 \ \Rightarrow \ N_{3} \ \underline{= 16}$.

• If exactly one bit is corrupted in each code symbol, this also means 16 symbol errors.
• This is the maximum value that the Reed–Solomon decoder can still handle.

(4)  The RS decoder can correct 16 corrupted code symbols,

• whereby it does not matter whether in a code symbol only one bit or all $m = 8$ bits have been corrupted.
• Therefore, with the most favorable error distribution, up to $N_4 = 8 \cdot 16 \ \underline{= 128}$ bits can be corrupted without the code word being incorrectly decoded.