Aufgaben:Exercise 2.09: Reed–Solomon Parameters

• Return to book

Some Reed-Solomon codes

Adjacent is an incomplete list of possible Reed–Solomon codes known to be based on a Galois field  ${\rm GF}(q) = {\rm GF}(2^m)$. 

The parameter  $m$  specifies with how many bits a Reed–Solomon code symbol is represented.  It is valid:

• $m = 4$  (red font),

• $m = 5$  (blue font),

• $m = 6$  (green font).

A Reed–Solomon code is generally denoted as follows:   ${\rm RSC}\ (n, \ k, \ d_{\rm min})_q$.

The parameters have the following meaning:

1. The parameter  $n$  specifies the number of symbols of a code word  $\underline{c}$    ⇒   length of the code.
2. Tthe parameter  $k$  specifies the number of symbols of an information block  $\underline{u}$    ⇒   dimension  of the code.
3. The parameter  $d_{\rm min}$  denotes the  minimum distance   between two code words
   $($for all Reed–Solomon codes equal  $n-k+1)$.
4. The parameter  $q$  gives an indication of the use of the Galois field  ${\rm GF}(q)$.

To the right,  there is the binary representation of the same code:

1. In this realization of a Reed–Solomon code,  each information and code symbol is represented by  $m$  bits.
2. For example,  it can be seen from the first row that the minimum distance in terms of bits is also  $d_{\rm min} = 5$  if in  ${\rm GF}(2^m)$  the minimum distance is  $d_{\rm min} = 5$.
3. This code can correct up to   $t = 2$   bit errors  $($or symbol errors$)$  and detect up to   $e = 4$   bit errors  $($or symbol errors$)$.

Hints:

• This exercise belongs to the chapter  "Definition and Properties of Reed-Solomon Codes".

• However,  reference is also made to the chapter  "Extension Field".

Questions

1

It holds  $c_i ∈ {\rm GF}(2^m)$.  Which Reed-Solomon code parameters  $n$  result?

$m = 4 \text{:} \hspace{0.4cm} n \ = \ $

$m = 5 \text{:} \hspace{0.4cm} n \ = \ $

$m = 6 \text{:} \hspace{0.4cm} n \ = \ $

2

Two specific Reed-Solomon codes   ${\rm RSC} \ 1 \ (m = 4, \ t = 4)$   and   ${\rm RSC} \ 2 \ (m = 5, \ t = 8)$   are considered below.
Which parameter  $k$  can be used to correct exactly  $t$  symbol errors?

${\rm RSC} \ 1 \text{:} \hspace{0.4cm} k \ = \ $

${\rm RSC} \ 2 \text{:} \hspace{0.4cm} k \ = \ $

3

Which designations are correct for   $\rm RSC \ 1$   resp.   $\rm RSC \ 2$?

	$\rm RSC \ 1$  is also called  $\rm RSC \, (15, \, 7, \, 9)_{16}$.
	$\rm RSC \ 1$  is also called  $\rm RSC \, (15, \, 7, \, 4)_4$.
	$\rm RSC \ 2$  is also called  $\rm RSC \, (31, \, 17, \, 15)_{32}$.
	$\rm RSC \ 2$  is also called  $\rm RSC \, (31, \, 15, \, 17)_{32}$.

4

How many symbol errors  $(e)$  can be detected at most?

${\rm RSC} \ 1 \text{:} \hspace{0.4cm} e \ = \ $

${\rm RSC} \ 2 \text{:} \hspace{0.4cm}e \ = \ $

5

What are the codes under consideration in binary notation?

	$\rm RSC \ 1$  corresponds to the code  $\rm RSC \, (60, \, 28, \, 36)_2$.
	$\rm RSC \ 1$  corresponds to the code  $\rm RSC \, (60, \, 28, \, 9)_2$.
	$\rm RSC \ 2$  corresponds to the code  $\rm RSC \, (155, \, 75, \, 17)_2$.
	$\rm RSC \ 2$  corresponds to the code  $\rm RSC \, (124, \, 60, \, 17)_2$.

Solution

Solution

(1)  For the code length of Reed–Solomon codes,  the following applies in general:

$$n = q -1 = 2^m -1 \hspace{0.3cm}\Rightarrow \hspace{0.3cm} m = 4 {\rm :}\hspace{0.2cm} n \hspace{0.15cm}\underline {= 15} \hspace{0.05cm}, \hspace{0.4cm}m = 5 {\rm :}\hspace{0.2cm} n \hspace{0.15cm}\underline {= 31} \hspace{0.05cm},\hspace{0.4cm} m = 6 {\rm :}\hspace{0.2cm} n \hspace{0.15cm}\underline {= 63} \hspace{0.05cm}.$$

(2)  To be able to correct  $t$  symbol errors,  the minimum distance must be  $d_{\rm min} = 2t + 1$.

• The Reed–Solomon code is a so-called  "Maximum Distance Separable  $\rm (MDS)$  code".

• For this applies:

$$d_{\rm min} = n-k+1 = 2t+1 \hspace{0.3cm} \Rightarrow \hspace{0.3cm}k = n -2t = 2^m - ( 2t+1) \hspace{0.05cm}.$$

• This gives for the
  • $\rm RSC \ 1$  $($with  $m = 4, \ t = 4) \text{:} \hspace{0.2cm} k = 2^4 - (2 \cdot 4 + 1) \ \underline{= 7}$,
  • $\rm RSC \ 2$  $($with  $m = 5, \ t = 8) \text{:} \hspace{0.2cm} k = 2^5 - (2 \cdot 8 + 1) \ \underline{= 15}$.

(3)  The denotation of a Reed–Solomon code is  ${\rm RSC} \, (n, \, k, \, d_{\rm min})_q$  with  $q = 2^m = n + 1$.

• Correct are the  solutions 1 and 4:
  • $\rm RSC \ 1 \Rightarrow RSC \, (15, \, 7, \, 9)_{16}$,
  • $\rm RSC \ 2 \Rightarrow RSC \, (31, \, 15, \, 17)_{32}$.

(4)  If  $d_{\rm min}$  denotes the minimum distance of a block code,  it can be used to detect  $e = d_{\rm min} - 1$  symbol errors and to correct  $t = e/2$  symbol errors:

• ${\rm RSC} \ 1 \text{:} \hspace{0.2cm} d_{\rm min} = \ \ 9, \ t = 4, \ \underline{e = 8}$,
• ${\rm RSC} \ 2 \text{:} \hspace{0.2cm} d_{\rm min} = 17, \ t = 8, \ \underline{e = 16}$.

(5)  Correct are the two middle  solutions 2 and 3:

• For  ${\rm RSC} \ 1 \, (m = 4)$:   $n = 15$  code symbols from  $\rm GF(2^5)$  correspond to  $60$  bits and  $k = 7$  information symbols are exactly  $28$  bits:
  • $\rm RSC \ 1 \Rightarrow RSC \, (15, \, 7, \, 9)_{16} \Rightarrow RSC \, (60, \, 28, \, 9)_2$,
  • $\rm RSC \ 2 \Rightarrow RSC \, (31, \, 15, \, 17)_{32} \Rightarrow RSC \, (155, \, 75, \, 17)_2$.
• For the minimum distance on bit level   ⇒   $\rm GF(2)$,  $d_{\rm min} = 9$  resp.  $d_{\rm min} = 17$  result in the same values as on symbol level   $($see "theory section"$)$.