Exercise 2.10Z: Code Rate and Minimum Distance

• Return to book

The 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 code words. 

• 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} \, (255, \, 223, \, d_{\rm min})_{256}$  discussed in  (1) 

• 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 falsified 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 Reed–Solomon decoder can correct  $16$  falsified code symbols.

• It does not matter whether in a code symbol only one bit or all  $m = 8$  bits have been falsified.

• Therefore,  with the most favorable error distribution,  up to  $N_4 = 8 \cdot 16 \ \underline{= 128}$  bits can be falsified without the code word being incorrectly decoded.