Exercise 2.10Z: Code Rate and Minimum Distance

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

$q \hspace{0.2cm} = \ $

$e \hspace{0.2cm} = \ $

$t \hspace{0.2cm} = \ $

$R \hspace{0.2cm} = \ $

$d_{\rm min} \ = \ $

$R \hspace{0.2cm} = \ $

$d_{\rm min} \ = \ $

$N_{3} \ = \ $

$N_{4} \ = \ $

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

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.