# Generator matrix for Reed-Solomon code

Given $$\,f(t)=t^3+t+1,\,$$ let $$\,\mathbb{F}_{2^3}=\frac{\mathbb{F}_2\left[t\right]}{\langle f\,\rangle}\,$$ be a finite field and $$\,\xi=t\,\left(\textrm{mod}\,f\right).$$ Let also $$\,\mathcal{C}\,$$ be a cyclic code where $$\,g(x)=\left(x-\xi\right)\left(x-\xi^2\right)\left(x-\xi^3\right)\left(x-\xi^4\right)\,$$ is his generator polynomial.

Question: Find a generator matrix of $$\,\mathcal{C}\,$$ in the basis $$\,B=\left\{1,\xi,\xi^2\right\}\,$$ of $$\,\mathbb{F}_{2^3}\,$$ as an $$\,\mathbb{F}_{2}$$- vector space.

The fisrt thing they ask is to prove that $$\,\xi\,$$ is a $$\,7^{\,th}\,$$ primitive root of the unity (quite easy). Then, prove that the length of $$\,\mathcal{C}\,$$ is $$\,n=7$$.

I found out that $$\,\mathcal{C}\,$$ is a Reed-Solomon code, a type of BCH code whose length is always $$\,n=q-1\,$$ over a finite field $$\,\mathbb{F}_q,\,$$ so this question is also easy to answer.

However, I do not know how to proceed to find the generator matrix of $$\,\mathcal{C}.$$ I tried to expand the generator polynomial $$g(x)=g_0+g_1x+\dots+g_4x^4$$

and define the generator matrix as $$G=\begin{pmatrix}g_0&g_1&g_2&g_3&g_4 & 0 & 0\\ 0 & g_0&g_1&g_2&g_3&g_4 & 0\\ 0 & 0 & g_0&g_1&g_2&g_3&g_4\end{pmatrix}$$

in the basis $$\,B=\left\{1,\xi,\xi^2\right\}\,$$ but I guess I failed.

• No, its fine. You need to calculate the coefficients $g_i$. – Wuestenfux Jan 11 at 11:31
• Basic Galois theory tells us that the zeros of $f(t)$ are $\xi,\xi^2$ and $\xi^4$. So $$f(x)=x^3+x+1=(x-\xi)(x-\xi^2)(x-\xi^4).$$ All you need to do is to calculate $$g(x)=f(x)(x-\xi^3).$$ Observe that $\xi^3=\xi+1$ because $\xi$ is a zero of $f$. – Jyrki Lahtonen Jan 11 at 11:41
• @Jyrki Lahtonen: I guess you mean $f(t)$ is the minimal polynomial of $\xi$ over $\mathbb{F}_{2}$. I didn't realize, thank you very much. However, when I calculate the coefficients of $g(x)$ as you said I get $$g(x)=x^4 - \left(\xi +1\right)^3+x^2-\xi x-\left(\xi+1\right)$$ so, I can't express the coefficients of $x^3$ and $1$ in the basis $B$, or maybe I just don't know how. – CarlIO Jan 11 at 17:45
• Given that $f(x)$ has no quadratic term the coefficient of $x^3$ in $g(x)$ should be just $\xi^3=\xi+1$, no? – Jyrki Lahtonen Jan 11 at 17:51
• Effectively you would then replace each entry of the $3\times7$ matrix with a $3\times3$ block. – Jyrki Lahtonen Jan 11 at 18:30
Lots of comments. We have $$g = (x-\xi)(x-\xi^2)(x-\xi^3)(x-\xi^4).$$ If $$\xi$$ is a zero of the primitive polynomial $$f=x^3+x+1$$, then $$f$$ has the zeros $$\xi,\xi^2,(\xi^2)^2=\xi^4$$. Thus $$g = (x^3+x+1)(x+\xi^3) = x^4+x^2+x+\xi^3x^3+\xi^3 x +\xi^3\\ = x^4 + \xi^3 x^3 +x^2+(\xi^3+1)x+\xi^3.$$ Since $$\xi$$ is a zero of $$f$$, $$\xi^3+\xi+1=0$$ and so $$\xi=\xi^3+1$$ Hence,
$$g= = x^4 + \xi^3 x^3 +x^2+\xi x+\xi^3.$$