Reed-Solomon Code calculation

I have a Reed-Solomon Code which can correct t=2 errors. The generator polynomial is $p(X) = X^3 + X + 1$ and $p(a) = a^3 + a + 1 = 0$ this means $a^3 = a + 1$

1. What is the degree of generator polynomial of this code?
2. Are the following code words valid, why or why not?

$(1, a+1, 1, 0, 0, a+1, a)$

$(a^2+a+1, a+1, a^2, a^2+a+1, a^2, 0, 0)$

The first question is easy to answer I think; the degree of the generator polynomial is 3.

However, the second question is way more challenging. I assume that the finite field $\operatorname{GF}(2^3)$ is used and therefore a code word consists of $n = 2^3 - 1 = 7$ symbols. This criteria is met by both code words mentioned in the second question.

How can I determine the validity of the 2 code words?

Probably I have to use the Discrete Fourier Transform (DFT) but because of $n=7$ this would generate a $7\times 7$ matrix which is to costly to do it by hand.

Is there a simple way to calculate all valid code words?

-

migrated from crypto.stackexchange.comAug 27 '12 at 1:20

This question came from our site for software developers, mathematicians and others interested in cryptography.

1 Answer

OK, now that I have read your questions more carefully, here is some more preliminary information. Your Reed-Solomon code has a generator polynomial of degree $4$ which is not the same as what you call the generator polynomial, viz., $p(x) = x^3 + x + 1$. In coding theory $p(x)$ would be called the irreducible polynomial used to construct the field. In this instance, it would more likely be called the primitive polynomial since its root $a$ is a primitive element of the field, meaning that all $7$ nonzero elements of the field can be represented as powers of $a$.

So, what is this generator polynomial (call it $g(x)$) of the Reed-Solomon code? You might have been given this information as part of the problem, so look for it. The generator polynomial of a $t$-error-correcting Reed-Solomon code has the property that $2t$ successive powers of $a$ are roots of the polynomial. Thus, we have

\begin{align*} g(x) &= (x-a^i)(x-a^{i+1})(x-a^{i+2}\cdots(x-a^{i+2t-1})\\ &= g_{2t}x^{2t} + g_{2t-1}x^{2t-1} + \cdots + g_1 x + g_0 \end{align*} where all the coefficients $g_j$ are necessarily nonzero. Popular choices for $i$ are $0$ and $1$, but unless you know $g(x)$, it is not possible to answer the question about which vectors are valid codewords, except possibly in the general form "This vector is not a valid codeword for any choice of $i$, $0 \leq i \leq 6$" which would require a lot more calculation of the form given below.

Valid codeword polynomials are divisible by the generator polynomial $g(x)$. So, if you are given the second form of $g(x)$ as described above, then divide the alleged codeword polynomial $c(x)$ (which, for the vector $(c_0, c_1, \ldots, c_6)$, could be $c(x) = c_0 + c_1x + \cdots + c_6x^6$ or $c(x) = c_0x^6 + c_1x^5 + \cdots + c_5x + c_6$ depending on the convention used in the document you are reading) by the generator polynomial $g(x)$ which is given to you. This is plain polynomial long division as you would have learned in secondary school except that you are working over a finite field instead of real numbers. If the remainder is zero, the vector is indeed a codeword; if the remainder is nonzero, it is not a codeword.

On the other hand, if you are given the $4$ roots of $g(x)$ but not the coefficients $g_j$, then rather than multiplying out the four factors to get the $g_j$ and then doing the polynomial division, it is easier to simply evaluate the alleged codeword polynomial $c(x)$ at the four roots of the generator polynomial (this is called computing the syndrome in coding theory). If all four evaluations $c(a^i)$, $c(a^{i+1})$, $c(a^{i+2})$, $c(a^{i+3})$ result in $0$, $c(x)$ is indeed a valid codeword polynomial; if at at least one evaluation gives a nonzero result, $c(x)$ is not a valid codeword polynomial. This way of checking can be adapted to determine whether the vector in question is a codeword in any double-error-correcting Reed-Solomon code. Evaluate the codeword polynomial at $a^i$ for all $i, 0 \leq i \leq 6$. This is computing the finite-field discrete Fourier transform which you mentioned. Then look for $4$ consecutive $0$ values in the sequence $$c(1), c(a), c(a^2), c(a^3), c(a^4), c(a^5), c(a^6), c(1), c(a), c(a^2).$$ If there are $4$ consecutive $0$ values beginning with $c(a^i), 0 \leq i \leq 6$, then $c(x)$ is a valid codeword polynomial in the double-error-correcting Reed-Solomon code with generator polynomial $$g(x) = (x-a^i)(x-a^{i+1})(x-a^{i+2})(x-a^{i+3}).$$ There may be more than one choice of $i$ for which this holds. On the other hand, there might not be $4$ consecutive zeroes in which case you have shown that

$c(x)$ is not a valid codeword polynomial in any double-error-correcting Reed-Solomon code of length $7$ over the finite field of $8$ elements.

Finally, your question about creating a list of codewords has the following answer. The codewords are all the multiples of $g(x)$. So, write out all the $8^3$ polynomials $b(x)$ of degree $2$ or less (remember that polynomials of degree $2$ have $3$ coefficients, and we have $8$ choices for each coefficient. The codewords then are the $8^3$ polynomials $b(x)g(x)$. An easier way is to create three vectors of length $7$ corresponding to $g(x)$, $xg(x)$ and $x^2g(x)$ respectively, and then take all possible linear combinations $b_2(x^2g(x)) + b_1 (xg(x)) + b_0g(x)$.

-
+1 A very good effort in guessing and explaining what the question really was about! –  Jyrki Lahtonen Aug 27 '12 at 11:41