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$


*

*What is the degree of generator polynomial of this code?

*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?
 A: 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)$.
