Construct a Reed Solomon code: find the parity check matrix

Question

I am trying to solve the following exercise, but I need a check/opinion on how to solve it.

Construct a Reed-Solomon code with dimensions $[12,7]$ over $\mathbb{F}_{13}$ and find a parity check matrix for the code $C$. Hint: $2$ is a primitive element of $\mathbb{F}_{13}$.

---

First thing: I have $\delta=12-7+1=6$, so the minimum distance is exactly $6$. Also, I choose to build a narrow-sense code, so the defining set is $T = \mathcal{C}_1 \cup \ldots \cup \mathcal{C}_{5}$.

As $12=n=13-1$, then $\mathcal{C}_i=\{ i \}$, so the generator polynomial is $$g(x)=(x-2)(x-2^2)(x-2^3)(x-2^4)(x-2^5)=(x-2)(x-4)(x-8)(x-3)(x-6)$$

Now, I can work out the computations and find $h(x)$,check polynomial, dividing $x^{12}-1$ by $g(x)$, but it seems a bit heavy to me. Is there any other possibility to compute the check polynomial faster? And so also the parity check matrix.

Answer 1

Why would you need to divide? You already know its structure as well as you know $g$'s:

It's equal to $(x-1)(x-5)(x-7)(x-9)(x-10)(x-11)(x-12)$

After you have this, you can use its corresponding word, then do cyclic shifts to find the rest of the parity matrix.

Answer 2

As an alternative to @rschweib's answer and possibly requiring little computation you have good look-up tables, a cyclic Reed-Solomon code whose generator polynomial has $2, 2^2, 2^3, 2^4, 2^5$ as roots has parity check matrix $$H = \left[\begin{matrix} 1&2&2^2&2^3&\quad \cdots&2^{11}\\ 1&2^2&(2^2)^2&(2^2)^3&\quad \cdots&(2^2)^{11}\\ 1&2^3&(2^3)^2&(2^3)^3&\quad \cdots&(2^3)^{11}\\ 1&2^4&(2^4)^2&(2^4)^3&\quad \cdots&(2^4)^{11}\\ 1&2^5&(2^5)^2&(2^5)^3&\quad \cdots&(2^5)^{11} \end{matrix}\right]$$

Answer 3

Follow up and for others reading this. I have old RS demo code that I used to generate the polynomials and matrices.

The 5 factor generator polynomial:

(x-2)(x-4)(x-8)(x-3)(x-6) = (x+11)(x+9)(x+5)(x+10)(x+7)
                          = x^5 + 3 x^4 + 5 x^3 + 12 x^2 + 11 x + 5

The remaining 7 factor polynomial. The coefficients of this polynomial correspond to the values in the bottom row of the parity generator matrix.

(x−1)(x−5)(x−7)(x−9)(x−10)(x−11)(x−12) = (x+12)(x+8)(x+6)(x+4)(x+3)(x+2)(x+1)
                          = x^7 + 3 x^6 + 4 x^5 + 9 x^4 + 6 x^3 + 6 x^2 + 2 x + 8

All 12 factors result in x^12 - 1:

(x-1)(x-2)...(x-11)(x-12) = (x+12)(x+11) ... (x+2)(x+1)
                          = x^12 + 12 = x^12 - 1

Parity generator matrix (in decimal despite the leading zeroes):

    05 02 07 06 04 04 10
    02 11 10 12 05 03 08
    12 12 07 01 06 12 01
    08 10 05 01 10 02 02
    03 04 09 06 06 02 08

Parity check matrix:

    05 02 07 06 04 04 10 01 00 00 00 00
    02 11 10 12 05 03 08 00 01 00 00 00
    12 12 07 01 06 12 01 00 00 01 00 00
    08 10 05 01 10 02 02 00 00 00 01 00
    03 04 09 06 06 02 08 00 00 00 00 01

Syndrome generator matrix:

    07 10 05 09 11 12 06 03 08 04 02 01
    10 09 12 03 04 01 10 09 12 03 04 01
    05 12 08 01 05 12 08 01 05 12 08 01
    09 03 01 09 03 01 09 03 01 09 03 01
    11 04 05 03 07 12 02 09 08 10 06 01