Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
add comment

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

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

1 Answer

up vote 3 down vote accepted

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)$.

share|improve this answer
    
+1 A very good effort in guessing and explaining what the question really was about! –  Jyrki Lahtonen Aug 27 '12 at 11:41
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.