Aufgaben:Exercise 2.11: Reed-Solomon Decoding according to "Erasures"

• Return to book

${\rm GF}(2^3)$, represented as powers, polynomials, coefficient vectors

We consider here an encoding and decoding system corresponding to the  "graph in the theory section for this chapter". 

• The Reed–Solomon code is given by the generator matrix  $\mathbf{G}$  and the parity-check matrix  $\mathbf{H}$  where all elements are from the Galois field  $\rm GF(2^3) \ \backslash \ \{0\}$:

$${ \boldsymbol{\rm G}} \hspace{-0.15cm} \ = \ \hspace{-0.15cm} \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}\\ 1 & \alpha^3 & \alpha^6 & \alpha^2 & \alpha^{5} & \alpha^{1} & \alpha^{4} \end{pmatrix} \hspace{0.05cm},$$

$${ \boldsymbol{\rm H}} \hspace{-0.15cm} \ = \ \hspace{-0.15cm} \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} \end{pmatrix} \hspace{0.05cm}.$$

• All code symbols   $c_i ∈ \{0, \, 1, \, \alpha, \, \alpha^2, \, \alpha^3, \, \alpha^4, \, \alpha^5, \, \alpha^6\}$   are represented by  $m = 3$  bits and transmitted via the erasure channel  $(m–\rm BEC)$.  A code symbol is already marked as an erasure  $\rm E$  if one of the three associated bits is uncertain.

• The  "code word finder"  $\rm (CWF)$  has the task of generating the regenerated code word  $\underline{z}$  from the partially erased received word  $\underline{y}$.  It must be ensured that the result  $\underline{z}$  is indeed a valid Reed–Solomon code word.

• If the received word  $\underline{y}$  contains too many erasures,  the decoder outputs a message of the type  "symbol cannot be decoded".  So no attempt is made to estimate the code word.  If  $\underline{z}$  is output,  this is also correct:  $\underline{z} = \underline{c}$.

• The sought information value  $\underline{v} = \underline{u}$  results from the inverse encoder function   $\underline{v} = {\rm enc}^{-1}(\underline{z})$.  With the generator matrix  $\mathbf{G}$  this can be realized as follows:

$$\underline{c} = {\rm enc}(\underline{u}) \hspace{-0.15cm} \ = \ \hspace{-0.15cm} \underline{u} \cdot {\boldsymbol{\rm G}} \hspace{0.3cm} \Rightarrow \hspace{0.3cm} \underline{z} = {\rm enc}(\underline{v}) = \underline{v} \cdot {\boldsymbol{\rm G}} \hspace{0.3cm} \Rightarrow \hspace{0.3cm} \underline{v} \hspace{-0.15cm} \ = \ \hspace{-0.15cm} {\rm enc}^{-1}(\underline{z}) = \underline{z} \cdot {\boldsymbol{\rm G}}^{\rm T}\hspace{0.05cm}.$$

Hints:

• This exercise refers to the chapter  "Reed–Solomon Decoding for the Erasure Channel".

• Regarding the code word finder,  we refer in particular to the pages 

"Decoding procedure ...",  and 

"Solution of the matrix equations ...".

• All calculations are to be performed in  $\rm GF(2^3)$.  The upper graph describes their  $q = 8$  elements in power, polynomial and coefficient vector representation.

Questions

1

Specify the code parameters of the present Reed–Solomon code.

$n \ = \ $

$k \ = \ $

$d_{\rm min} \ = \ $

2

Can the received vector   $\underline{y} = (0, \, 0, \, 0,\, 0, \, 0, \, 0, \, {\rm E})$   be decoded??

	YES.
	NO.

3

Can the received vector   $\underline{y} = (\rm E, \, E, \, 1, \, 1, \, 1, \, 1, \, 1)$   be decoded?

	YES.
	NO.

4

What is the result of decoding   "$\underline{y} = (\rm E, \, E, \, E, \, 0, \, 1, \, \alpha, \, 0)$"?

	$z_0 = \alpha, \ z_1 = \alpha^3, \ z_2 = 0$.
	$z_0 = \alpha, \ z_1 = \alpha^3, \ z_2 = \alpha^3$.
	$z_0 = 1, \ z_1 = 0, \ z_2 = \alpha^3$.
	The decoding does not lead to any result.

5

What is the result of decoding   "$\underline{y} = (\rm E, \, E, \, E, \, 0, \, 1, \, \alpha, \, E)$"?

	$z_0 = \alpha, \ z_1 = \alpha^3, \ z_2 = 0, \ z_6 = 1$.
	$z_0 = \alpha, \ z_1 = \alpha^3, \ z_2 = \alpha^3, \ z_6 = 1$.
	$z_0 = 1, \ z_1 = 0, \ z_2 = \alpha^3, \ z_6 = 1$.
	The decoding does not lead to any result.

Solution

Solution

(1)  The number of columns of the parity-check matrix  $\mathbf{H}$  indicates the code length: $n \ \underline{= 7}$.

• The same result is obtained if we assume the order  $q = 8$  of the Galois field.  For the Reed–Solomon codes  $n = q - 1$  is valid.

• The number of rows of the parity-check matrix is equal to  $n - k = 3 \ \Rightarrow \ k \ \underline{= 4}$.

• Of all Reed–Solomon codes,  the  "Singleton bound" is satisfied   ⇒   $d_{\rm min} = n - k + 1 \ \underline{= 4}$.

• Thus,  it is the Reed–Solomon code  $(7, \, 4, \, 4)_8$.

(2)  Decoding is certainly possible as long as the number  $e$  of erasures is smaller than the minimum distance  $d_{\rm min}$.  This condition is fulfilled here   ⇒   YES.

• Since the null word is allowed in all Reed–Solomon codes and every other code word contains at least four symbols  "$\ne 0$",  it is already certain without calculation that the null word was sent.

• The formal calculation confirms this result:

$${ \boldsymbol{\rm H}}_{\rm K} \cdot \underline {z}_{\rm K}^{\rm T} = \begin{pmatrix} 0\\ 0\\ 0 \end{pmatrix} \hspace{0.3cm} \Rightarrow \hspace{0.3cm} \begin{pmatrix} \alpha^6\\ \alpha^{5}\\ \alpha^{4} \end{pmatrix} \cdot z_6 = \begin{pmatrix} 0\\ 0\\ 0 \end{pmatrix} \hspace{0.3cm} \Rightarrow \hspace{0.3cm} z_6 = 0 \hspace{0.05cm}. $$

(3)  Again  $e = 2$  is smaller than  $d_{\rm min} = 4$   ⇒   YES.

• Since  $(1, \, 1, \, 1, \, 1, \, 1, \, 1, \, 1)$  is also a valid code word,  we expect  $z_0 = 1$  und  $z_1 = 1$  in the formal verification.

$${ \boldsymbol{\rm H}}_{\rm K} \cdot \underline {z}_{\rm K}^{\rm T} \hspace{-0.15cm} \ = \ \hspace{-0.15cm} \begin{pmatrix} \alpha^2 & \alpha^3 & \alpha^4 & \alpha^5 & \alpha^6\\ \alpha^4 & \alpha^6 & \alpha^1 & \alpha^{3} & \alpha^{5}\\ \alpha^6 & \alpha^2 & \alpha^{5} & \alpha^{1} & \alpha^{4} \end{pmatrix} \cdot\begin{pmatrix} 1\\ 1\\ 1\\ 1\\ 1 \end{pmatrix}= \begin{pmatrix} \alpha^2 + \alpha^3 + \alpha^4 + \alpha^5 + \alpha^6\\ \alpha^4 + \alpha^6 + \alpha^1 + \alpha^{3} + \alpha^{5}\\ \alpha^6 + \alpha^2 + \alpha^{5} + \alpha^{1} + \alpha^{4} \end{pmatrix}$$

$$\Rightarrow \hspace{0.3cm}{ \boldsymbol{\rm H}}_{\rm K} \cdot \underline {z}_{\rm K}^{\rm T} \hspace{-0.15cm} \ = \ \begin{pmatrix} (100) + (011) + (110) + (111) + (101)\\ (110) + (101) + (010) + (011) + (111)\\ (101) + (100) + (111) + (010) + (110) \end{pmatrix} = \begin{pmatrix} (011)\\ (101)\\ (010) \end{pmatrix} = \begin{pmatrix} \alpha^3\\ \alpha^6\\ \alpha^1 \end{pmatrix} \hspace{0.05cm}. $$

• In this calculation,  we varied between the polynomial representation and the coefficient representation on the data side.  Thus the system of equations reads:

$$\begin{pmatrix} (001) + (010) \\ (001) + (100)\\ (001) + (011) \end{pmatrix} \cdot \begin{pmatrix} z_0\\ z_1 \end{pmatrix} = \begin{pmatrix} (011)\\ (101)\\ (010) \end{pmatrix} \hspace{0.25cm} \Rightarrow \hspace{0.25cm} \begin{pmatrix} (001) + (010) \\ (001) + (100)\\ (000) + (111) \end{pmatrix} \cdot \begin{pmatrix} z_0\\ z_1 \end{pmatrix} = \begin{pmatrix} (011)\\ (101)\\ (111) \end{pmatrix}\hspace{0.05cm}.$$

• The second form is obtained by substituting the third row from the modulo-2 sum of rows 2 and 3.

• From the last row now follows  $z_1 = 1$  and the rows 1 and 2 are then:

$$(1)\hspace{0.3cm}z_0 + (010) \cdot 1 \hspace{-0.15cm} \ = \ \hspace{-0.15cm} (011)\hspace{0.3cm} \Rightarrow \hspace{0.3cm}z_0 = (001) = 1\hspace{0.05cm},$$

$$(2)\hspace{0.3cm}z_0 + (100) \cdot 1 \hspace{-0.15cm} \ = \ \hspace{-0.15cm} (101)\hspace{0.3cm} \Rightarrow \hspace{0.3cm}z_0 = (001) = 1\hspace{0.05cm}. $$

• Both equations lead to the same result  $z_0 = 1, \ z_1 = 1$.  The decoding is successful.

(4)  The decoding happens on the following steps:

$${ \boldsymbol{\rm H}}_{\rm K} \cdot \underline {z}_{\rm K}^{\rm T} \hspace{-0.15cm} \ = \ \hspace{-0.15cm} \begin{pmatrix} \alpha^3 & \alpha^4 & \alpha^5 & \alpha^6\\ \alpha^6 & \alpha^1 & \alpha^{3} & \alpha^{5}\\ \alpha^2 & \alpha^{5} & \alpha^{1} & \alpha^{4} \end{pmatrix} \cdot\begin{pmatrix} 0\\ 1\\ \alpha\\ 0 \end{pmatrix}= \begin{pmatrix} \alpha^4 + \alpha^6\\ \alpha^1 + \alpha^{4}\\ \alpha^5 + \alpha^2 \end{pmatrix}= \begin{pmatrix} (110) + (101)\\ (010) + (110)\\ (111) + (100) \end{pmatrix} = \begin{pmatrix} (011)\\ (100)\\ (011) \end{pmatrix} \hspace{0.05cm},$$

$${ \boldsymbol{\rm H}}_{\rm E} \cdot \underline {z}_{\rm E}^{\rm T} \hspace{-0.15cm} \ = \ \hspace{-0.15cm} \begin{pmatrix} 1 & \alpha^1 & \alpha^2\\ 1 & \alpha^2 & \alpha^4\\ 1 & \alpha^3 & \alpha^6 \end{pmatrix} \cdot\begin{pmatrix} z_0\\ z_1\\ z_2 \end{pmatrix}\hspace{0.3cm} \Rightarrow \hspace{0.3cm} \begin{pmatrix} (001) &(010) &(100)\\ (001) &(100) &(110)\\ (001) &(011) &(101) \end{pmatrix} \cdot \begin{pmatrix} z_0\\ z_1\\ z_2 \end{pmatrix}= \begin{pmatrix} (011)\\ (100)\\ (011) \end{pmatrix} \hspace{0.05cm}. $$

• We now replace row 2 with the modulo-2 sum of rows 1 and 2, and row 3 with the modulo-2 sum of rows 1 and 3:

$$\begin{pmatrix} (001) &(010) &(100)\\ (000) &(110) &(010)\\ (000) &(001) &(001) \end{pmatrix} \cdot \begin{pmatrix} z_0\\ z_1\\ z_2 \end{pmatrix}= \begin{pmatrix} (011)\\ (111)\\ (000) \end{pmatrix} \hspace{0.05cm}.$$

• From the last row follows  $z_1 + z_2 = 0 \ \Rightarrow \ z_2 = z_1$.  Substituting into the second row of this matrix equation we get:

$$\big[(110) + (010)\big] \cdot z_1 = (100) \cdot z_1 = (111) \hspace{0.2cm} \Rightarrow \hspace{0.2cm} \alpha^2 \cdot z_1 = \alpha^5\hspace{0.2cm}\Rightarrow \hspace{0.2cm} z_1 \hspace{0.1cm}\underline{= \alpha^3}\hspace{0.05cm},\hspace{0.2cm}z_2 \hspace{0.1cm}\underline{= \alpha^3} \hspace{0.05cm}. $$

• With this result follows from the first matrix row:

$$z_0 + \big[(010) + (100)\big] \cdot z_1 = z_0 + (110) \cdot z_1 = (011) $$

$$\Rightarrow \hspace{0.2cm} z_0 + \alpha^4 \cdot \alpha^3 = z_0 + 1 = \alpha^3 \hspace{0.2cm} \Rightarrow \hspace{0.2cm} z_0 = \alpha^3 + 1 = ( \alpha + 1) +1\hspace{0.15cm} \underline{= \alpha}\hspace{0.05cm}.$$

• The correct solution is therefore  proposed solution 2.

(5)  Correct is the  proposed solution 4.   Reasons:

• Four information symbols cannot be obtained from the three known symbols  $0, \, 1, \, \alpha$.

• The  $\mathbf{H}$  matrix of this  $(7, \, 4, \, 4)_8$  code has exactly  $n - k = 3$  rows.

• This also means that you have only three equations.  But you would need four equations for the unknowns  $z_0, \ z_1, \ z_2$  and  $z_6$.