I am following an example given by Writi M on a youtube video "an example of construction of BCH codes and encoding using BCH codes"
The example asks us to construct a BCH code that can correct 3 errors with block length 15 ($t=3, n=15)$ I have found a primitive polynomial for $GF(2^{4})$ is $x^{4} + x + 1$.
From this, I have found that the field elements are: $1, \alpha, \alpha^{2}, \alpha^{3}, \alpha^{4}=\alpha+1, \dots, \alpha^{14}=\alpha^{3} + 1$
I understand that the generator matrix of a 3-error error correcting binary BCH is the lowest common multiple of the minimal polynomials of the field elements i.e $$g(x) = LCM[m_{1}(x), m_{2}(x), \dots, m_{2t}(x)]$$
However, the example then asserts that this is equal to: $$g(x) = LCM[m_{1}(x), m_{3}(x), \dots, m_{2t-1}(x)]$$
Where $m_{i}(x) =$ minimal polynomial of field element $\alpha^{i}$
My first question: Can someoene explain why the generators polynomial can be found by looking at the minimal polynomial of just the field elements with odd index?
In our case, $t=3$, and so $2t-1=5$, meaning that our generator polynomial will be $g(x)$=LCM[m_{1}(x), m_{3}(x), m_{5}(x)]$
So now, we are tasked with finding the minimal polynomials of $\alpha$, $\alpha^{3}$ and $\alpha^{5}$ respectively.
The example states that in order to find the minimal polynomial of $\alpha$, we must first find the conjugates of $\alpha$ in $GF[2^{4}]$.
In the example, it is stated that the conjugates of:
- $\alpha$ are $\alpha^{2}, \alpha^{4}, \alpha^{8}$
- $\alpha^{3}$ are $\alpha^{6}, \alpha^{12}, \alpha^{9}$
- $\alpha^{5}$ are $\alpha^{10}, \alpha^{10}$
I can see that these appear to be in the form $\alpha^{2i mod15}$ where i is the index of the field element and it's modulo $15$ because $\alpha^{15}=\alpha^{0}=1$ (because $n=15$). But I don't understand why taking $\alpha^{2i}$ finds the conjugate?
My second question: How do we find the conjugates of a field element over $GF[2^{4}]$?
Any clarification would be appreciated.
The answer to the first question is simple. The reason is that for all $i$ we have $m_{2i}(x)=m_i(x)$. Over $GF(16)$ your polynomial factors as $$m_1(x)=(x-\alpha)(x-\alpha^2)(x-\alpha^4)(x-\alpha^8).$$ Expand the product on the right hand side as an exercise, if you like!
This is actually related to your second question. Whenever $z\in GF(2^n)$, and there is a polynomial $m(x)$ with coefficients in the prime field $GF(2)$ such that $m(z)=0$, then we automatically also have $$ m(z^2)=m(z)^2=0 $$ by quirks of characteristic two arithmetic, most notably the so called Freshman's dream: $$(u+v)^2=u^2+2uv+v^2=u^2+v^2.$$
We can apply this reasoning recursively. If $m(x)$ has coefficients in $GF(2)$, and $m(z)=0$, then also $m(z^2)=0$. Consequently, $m(z^4)=0$ (apply the previous logic to $z^2$ instead of $z$, $m(z^8)=0$, $m(z^{16})=0$ etc. This won't lead to the polynomial $m(x)$ having too many zeros, because repeated squaring cycles back to $z^{2^n}=z$ when $z\in GF(2^n)$. The conjugates of $z$ are exactly $z,z^2, z^4, z^8,\ldots$. Just like the complex numbers have the property that if $m(z)=0$ and $m(x)$ is a polynomial with real coefficients, then also $m(\overline{z})=0$, i.e. the complex conjugate is also a zero. Unlike in the real vs. complex case in the case of finite fields there can be more conjugates! Their number is equal to the degree of the minimal polynomial.
Play with the idea a bit, and you get used to using it. If you want to get to the bottom of it, you need to learn more abstract algebra, Galois theory in particular. That's more for math people. If you are in engineering, you may not need all of it (but it does help you see how the algebra of e.g. BCH-codes works, if you still study it).