2
$\begingroup$

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.

$\endgroup$

3 Answers 3

Reset to default
3
$\begingroup$

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.

$\endgroup$
4
  • 1
    $\begingroup$ Yes sure, but in order to write the parity check I need the coefficients, and so to multiply everything. I was wondering if there was a faster way (?) @rschweib $\endgroup$
    – bobinthebox
    Jun 17, 2020 at 14:32
  • $\begingroup$ Hrm, well I don't think you're going to get an explicit matrix without explicitly computing the polynomial for one of them. One you have the parity polynomial, you can just use it as the first row then do cyclic shifts, right? $\endgroup$
    – rschwieb
    Jun 17, 2020 at 14:34
  • $\begingroup$ Multiplying 7 linear polynomials seems like slightly less work than multiplying 5 and dividing $\endgroup$
    – rschwieb
    Jun 17, 2020 at 14:35
  • 1
    $\begingroup$ I totally agree with you now:) Thanks :) $\endgroup$
    – bobinthebox
    Jun 17, 2020 at 14:36
3
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ I found in my book this statement, thanks! But, the matrix you proposed is the transposed one actually. $\endgroup$
    – bobinthebox
    Jun 18, 2020 at 12:13
  • $\begingroup$ @bobinthebox "matrix you proposed is transposed" Well, that is entirely a matter of notational choices. For some such as myself, $H$ is a $(n-k)\times n$ matrix, a codeword $C$ is a row vector ($1\times n$ matrix) and every codeword $C$ satisfies $HC^T=0$ where that $0$ is a $(n-k)\times 1$ matrix or column vector of zeroes. Others write $C\mathcal H=0$ where $\mathcal H = H^T$ is the transpose of what I have called $H$ and that $0$ is a row vector of $(n-k)$ zeroes. To each his own. $\endgroup$
    – Dilip Sarwate
    Jun 18, 2020 at 14:35
  • $\begingroup$ Yes , I was exactly assuming the same notation as you, but looking at the book "site.iugaza.edu.ps/mashker/files/…", pg. 177, it seems the matrix is different, I think I should have the first row made by all $1$'s... $\endgroup$
    – bobinthebox
    Jun 18, 2020 at 15:44
  • $\begingroup$ @DilipSarwate - isn't H the syndrome generation matrix as seen on page 180 of that book: site.iugaza.edu.ps/mashker/files/… ? $\endgroup$
    – rcgldr
    Jun 21, 2020 at 9:58
0
$\begingroup$

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
$\endgroup$
6
  • $\begingroup$ If the parity check poly is what you wrote, then I think that the parity check matrix is wrong... as the first row should be differentt (and hence all the others) $\endgroup$
    – bobinthebox
    Jun 23, 2020 at 17:10
  • $\begingroup$ it should be (1,2,4,9,6,6,2,8) the first row $\endgroup$
    – bobinthebox
    Jun 23, 2020 at 17:12
  • $\begingroup$ @bobinthebox - the message is multiplied by x^5 in order to append 5 zeroes to it, for room to store the parity bytes. The 5 parities (remainder) are calculated and subtracted from those 5 zeroes. Take a look at the last column of the parity generator matrix, {10, 8, 1, 2, 8}, after subtraction, it's {3, 5, 12, 11, 5}, the same as the coefficients to the 5 factor generator polynomial. The bottom row corresponds to the coefficients of the 7 factor polynomial. $\endgroup$
    – rcgldr
    Jun 23, 2020 at 19:10
  • $\begingroup$ @bobinthebox - that parity generator matrix was created from sets of elements where there is only a single 1: {1,0,0,0,0,0,0}, {0,1,0,0,0,0,0}, {0,0,1,0,0,0,0}, ... {0,0,0,0,0,0,1}, with known working RS code. For example, a code word with a single 1 at the end of the message is the generator polynomial: {0,0,0,0,0,0,1,3,5,12,11,5}. $\endgroup$
    – rcgldr
    Jun 23, 2020 at 19:15
  • $\begingroup$ @bobinthebox - if interested, link to example code eccb13.c. It's an interactive demo. Most of the options are obvious, except that 'P', is used to note locations of erasures. Use 'M' to generate matrices, 'X' to do parity check. It includes the 3 types of decoders, PGZ matrix, SugiYama's extended Euclid (hardware like since the original purpose was for hardware team, where I made a smaller version), Berlekamp Massey. It's based on 1990's code, which explains the usage of Hungarian notation. $\endgroup$
    – rcgldr
    Jun 23, 2020 at 19:27

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .