1
$\begingroup$

Can someone explain to me how the minimal polynomials in page 4 of this document are obtained? Please help me.

http://web.ntpu.edu.tw/~yshan/BCH_code.pdf

It should be something standard about minimal polynomials you should only check the Field in the example.. I get $a^2$, but I am not sure about the other two.

Alternatively can someone show me how to do exercise 5 in http://www.ms.uky.edu/~corso/teaching/math362/Coding-Theory-3.pdf page 465 ??

$\endgroup$
18
  • $\begingroup$ What does $GF(2^m)$ mean? $\endgroup$ – Gregory Grant May 11 '15 at 16:57
  • $\begingroup$ Do you know anything about cyclotomic polynomials? $\endgroup$ – Git Gud May 11 '15 at 16:57
  • $\begingroup$ Never heard of cyclotomic polynomial... $\endgroup$ – vounoo May 11 '15 at 17:01
  • $\begingroup$ These polynomials are over $\mathbb{Z}_2$. They should be elements of the Ideal $\frac{\mathbb{Z}_2[x]}{x^4+x+1}$ where $a^4+a+1=0$ etc... $\endgroup$ – vounoo May 11 '15 at 17:03
  • $\begingroup$ @GregoryGrant $GF(q)$ is one of the standard notations for the unique (up to isomorphism) field of cardinality $q$. Even our tag wiki explains this ;-) $\endgroup$ – Jyrki Lahtonen May 11 '15 at 17:08
2
$\begingroup$

Those polynomials can be easily explained. The minimal polynomial of $\alpha$ is $$\phi_1(x)=x^4+x+1,$$ because we defined $\alpha$ to be one of the zeros of this polynomial.

Because $\alpha$ is a primitive element, it is of order $15$. Therefore $\beta=\alpha^3$ is of order five - in other words $\beta^5=1$. This implies that $$ 0=\beta^5-1=(\beta-1)(\beta^4+\beta^3+\beta^2+\beta+1). $$ Because $\beta\neq1$ we see that $\beta$ is a zero of $$ \phi_2(x)=x^4+x^3+x^2+x+1. $$ On the other hand $\beta$ generates the field $GF(16)$, so its minimal polynomial has to be of degree four. Therefore $\phi_2(x)$ is the minimal polynomial. Alternatively we can see that $\beta$ has as its conjugates (act on it by the Frobenius automorphism) $\beta^2=\alpha^6$, $\beta^4=\alpha^{12}$ and $\beta^8=\beta^3=\alpha^9$ four distinct elements of $GF(16)$.

On the other hand $\gamma=\alpha^5$ is of order three ($=15/5$) only. Therefore it belongs to the subfield $GF(4)$ (that contains precisely the roots of unity of order $4-1$). Hence its minimal polynomial is the only irreducible quadratic polynomial over $GF(2)$, namely $$ \phi_3(x)=x^2+x+1. $$ We could also argue as above starting from $$ 0=\gamma^3-1=(\gamma-1)(\gamma^2+\gamma+1). $$


If we want to continue and find the minimal polynomial of $\alpha^7$ it is simplest to observe that $\alpha^7$ is a conjugate of $\alpha^{2\cdot7}=\alpha^{14}=\alpha^{-1}$. But obviously $\alpha^{-1}$ is a zero of the polynomial $$ x^4\phi_1(\frac1x)=x^4(\frac1{x^4}+\frac1x+1)=1+x^3+x^4. $$ Admittedly that is not much use for the purposes of constructing larger minimum distance BCH-codes because once we get to $\alpha^7$ we have exhausted all the elements of $GF(16)\setminus GF(2)$ as zeros of the generator polynomial. Thus the resulting code is kinda tiny. It is the repetion code of length 15.

$\endgroup$
4
  • $\begingroup$ You are seriously the best $\endgroup$ – vounoo May 11 '15 at 17:20
  • $\begingroup$ It makes so much sense $\endgroup$ – vounoo May 11 '15 at 17:20
  • $\begingroup$ If you want become fluent with arithmetic in $GF(16)$ take a look at this Q&A pair I prepared for referrals. If that is all clear to you, then you are good to go (for handling BCH codes over GF(16) at least). Do observe that many (most?) mathematicians write $\Bbb{F}_{16}$ instead of $GF(16)$. $\endgroup$ – Jyrki Lahtonen May 11 '15 at 17:36
  • $\begingroup$ Thanks a lot this is helpful $\endgroup$ – vounoo May 11 '15 at 18:11

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.