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.

Somebody please, help me! Thanks in advance.

  • $\begingroup$ No, its fine. You need to calculate the coefficients $g_i$. $\endgroup$ – Wuestenfux Jan 11 at 11:31
  • $\begingroup$ 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$. $\endgroup$ – Jyrki Lahtonen Jan 11 at 11:41
  • $\begingroup$ @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. $\endgroup$ – CarlIO Jan 11 at 17:45
  • $\begingroup$ Given that $f(x)$ has no quadratic term the coefficient of $x^3$ in $g(x)$ should be just $\xi^3=\xi+1$, no? $\endgroup$ – Jyrki Lahtonen Jan 11 at 17:51
  • 1
    $\begingroup$ Effectively you would then replace each entry of the $3\times7$ matrix with a $3\times3$ block. $\endgroup$ – 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.$$

  • $\begingroup$ Sorry for the late reward @Wuestenfux $\endgroup$ – CarlIO Jun 14 at 10:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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