Exercise 2.08: Generator Polynomials for Reed-Solomon

Four generator matrices, three of which describe Reed-Solomon codes

In the "Exercise 2.7" you should determine the code words of the $\rm RSC \, (7, \, 3, \, 5)_8$ via a polynomial. However, you can also determine the code word $\underline{c}$ from the information word $\underline{u}$ and the generator matrix $\mathbf{G}$ according to the following equation:

$\underline {c} = \underline {u} \cdot { \boldsymbol{\rm G}} \hspace{0.05cm}.$

Two of these generator matrices describe the $\rm RSC \, (7, \, 3, \, 5)_8$ . In the subtask (1) is explicitly asked which.

Another generator matrix belongs to $\rm RSC \, (7, \, 5, \, 3)_8$ , which is considered in subtask (3).

Hints:

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

Important information about Reed–Solomon codes can also be found in "Exercise 2.7".

Questions

Solution

(1) Correct are the solutions 2 and 3 ⇒ matrices

$\mathbf{G}_{\rm B}$ and

$\mathbf{G}_{\rm C}$ .

In the matrix $\mathbf{G}_{\rm C}$ the allowed transformations $\alpha^8 = \alpha, \ \alpha^{10} = \alpha^3$ and $\alpha^{12} = \alpha^5$ have already been considered.

The matrix $\mathbf{G}_{\rm A}$ holds for the $(7, \, 5, \, 3)$ Hamming code and $\mathbf{G}_{\rm D}$ belongs to the $\rm RSC \, (7, \, 5, \, 3)_8$ . See subtask (3) for more details.

(2) In the $\rm RSC \, (7, \, 3, \, 5)_8$ , in each coding step are processed $k = 3$ information symbols,
in coding step 1 according to the specification the symbols $\alpha^4, \ 1$ and $\alpha^3$ .

With the generator matrix $\mathbf{G}_{\rm C}$ thus holds:

$\underline {c} = \underline {u} \cdot { \boldsymbol{\rm G}}_{\rm C} = \begin{pmatrix} \alpha^4 & 1 & \alpha^3 \end{pmatrix} \cdot \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} \end{pmatrix}\hspace{0.05cm}.$

$\rm GF(2^3)$ representation as powers, polynomials, vectors

This results according to the adjacent auxiliary table:

$c_0 \hspace{-0.15cm} \ = \ \hspace{-0.15cm} \alpha^{4}\cdot 1 + 1 \cdot 1 + \alpha^{3}\cdot 1 = (110) + (001) + (011)= (100) = \alpha^{2} \hspace{0.05cm},$

$c_1 \hspace{-0.15cm} \ = \ \hspace{-0.15cm} \alpha^{4}\cdot 1 + 1 \cdot \alpha + \alpha^{3}\cdot \alpha^{2}= (110) + (010) + (110) = (011) = \alpha^{3} \hspace{0.05cm},$

$c_2 \hspace{-0.15cm} \ = \ \hspace{-0.15cm} \alpha^{4}\cdot 1 + 1 \cdot \alpha^{2} + \alpha^{3}\cdot \alpha^{4}= (110) + (100) + (001) = (011) = \alpha^{3} \hspace{0.05cm},$

$c_3 \hspace{-0.15cm} \ = \ \hspace{-0.15cm} \alpha^{4}\cdot 1 + 1 \cdot \alpha^{3} + \alpha^{3}\cdot \alpha^{6}=$ (110) + (011) + (100) = (001) = 1 \hspace{0.05cm},$

$c_4 \hspace{-0.15cm} \ = \ \hspace{-0.15cm} \alpha^{4}\cdot 1 + 1 \cdot \alpha^{4} + \alpha^{3}\cdot \alpha^{1} = \alpha^{4} \hspace{0.05cm},$

$c_5 \hspace{-0.15cm} \ = \ \hspace{-0.15cm} \alpha^{4}\cdot 1 + 1 \cdot \alpha^{5} + \alpha^{3}\cdot \alpha^{3}= (110) + (111) + (101) = (100) = \alpha^{2} \hspace{0.05cm},$

$c_6 \hspace{-0.15cm} \ = \ \hspace{-0.15cm} \alpha^{4}\cdot 1 + 1 \cdot \alpha^{6} + \alpha^{3}\cdot \alpha^{5}= (\alpha^{2} + \alpha) + (\alpha^2 +1) + \alpha = 1 \hspace{0.05cm}.$

You get exactly the same result as in subtask (4) of "Exercise 2.7". Correct are the solutions 1 and 2.
So it is not $c_6 = 0$ , but $c_6 = 1$ .

(3) At the $\rm RSC \, (7, \, 5, \, 3)_8$ , the information word $\underline{u} = (u_0, \, u_1, \, u_2, \, u_3, \, u_4)$ must be considered.

With the generator matrix $\mathbf{G}_{\rm D}$ one obtains:

$\underline {c} = \underline {u} \cdot { \boldsymbol{\rm G}}_{\rm D} = \begin{pmatrix} \alpha^4 & 1 & \alpha^3 & 0 & \alpha^6 \end{pmatrix} \cdot \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}\\ 1 & \alpha^4 & \alpha^1 & \alpha^5 & \alpha^2 & \alpha^{6} & \alpha^{3} \end{pmatrix}\hspace{0.05cm}.$

From this it follows:

$c_0 \hspace{-0.15cm} \ = \ \hspace{-0.15cm} \alpha^{4}\cdot 1 + 1 \cdot 1 + \alpha^{3}\cdot 1 + 0 \cdot 1 + \alpha^{6}\cdot 1= (110) + (001) + (011) + (000) + (101) = (001) = 1 \hspace{0.05cm},$

$c_1 \hspace{-0.15cm} \ = \ \hspace{-0.15cm} \left [ \alpha^{4}\cdot 1 + 1 \cdot \alpha + \alpha^{3}\cdot \alpha^{2} \right ] + 0 \cdot \alpha^{3} + \alpha^{6}\cdot \alpha^{4}= \left [ \alpha^{3} \right ] + \alpha^{3} = 0 \hspace{0.05cm}.$

This takes into account that the bracket expression $[ \ \text{...} \ ]$ corresponds exactly to the result $c_1$ of subtask (2).

Corresponding is also considered in the following calculations:

$c_2 \hspace{-0.15cm} \ = \ \hspace{-0.15cm} \left [ \alpha^{3} \right ] + \alpha^{6}\cdot \alpha^{1}= \left [ \alpha^{3} \right ] + \alpha^{7} = (011) + (001) = (010) = \alpha^{1} \hspace{0.05cm},$

$c_3 \hspace{-0.15cm} \ = \ \hspace{-0.15cm} \left [ 1 \right ] + \alpha^{6}\cdot \alpha^{5}= \left [ 1 \right ] + \alpha^{4}= (001) + (110) = (111) = \alpha^{5} \hspace{0.05cm},$

$c_4 \hspace{-0.15cm} \ = \ \hspace{-0.15cm} \left [ \alpha^{4} \right ] + \alpha^{6}\cdot \alpha^{2}= \left [ \alpha^{4} \right ] + \alpha^{1} = (110) + (010) = (100) = \alpha^{2} \hspace{0.05cm},$

$c_5 \hspace{-0.15cm} \ = \ \hspace{-0.15cm} \left [ \alpha^{2} \right ] + \alpha^{6}\cdot \alpha^{6}= \left [ \alpha^{2} \right ] + \alpha^{5} = (100) + (111) = (011) = \alpha^{3} \hspace{0.05cm},$

$c_6 \hspace{-0.15cm} \ = \ \hspace{-0.15cm} \left [ 1 \right ] + \alpha^{6}\cdot \alpha^{3}= \left [ 1 \right ] + \alpha^{2} = (001) + (100) = (101) = \alpha^{6} \hspace{0.05cm}.$

This means: All proposed solutions are correct.

	the matrix $\mathbf{G}_{\rm A}$ ,
	the matrix $\mathbf{G}_{\rm B}$ ,
	the matrix $\mathbf{G}_{\rm C}$ ,
	the matrix $\mathbf{G}_{\rm D}$ .

	It holds $c_0 = \alpha^2$ ,
	It holds $c_1 = \alpha^3$ ,
	It holds $c_6 = 0$ .

	It holds $c_0 = 1$ ,
	It holds $c_1 = 0$ ,
	It holds $c_6 = \alpha^6$ .