# Constructing generator polynomial for a BCH code

How can I construct a generator polynomial for a BCH code $$(7,3)$$ code over $$GF(2^3)$$ with designed distance $$\delta =5$$.

Observe that $$x^7-1 = (x+1)(x^3+x+1)(x^3+x^2+1)=m_0(x)m_1(x)m_2(x)$$ where $$m_i(x)$$ are the minimal polynomials for $$\alpha^i$$ where $$\alpha$$ is the primitive element of $$GF(2^3)= GF(2)/(y^3+y+1).$$ Also, $$\alpha$$ is the $$7$$-th root of unity and $$m_1(x)=m_2(x)=m_4(x)$$ and $$m_3=m_5=m_6(x)$$.

Note that the cyclotomic sets are $$C_0=\{0\}, \quad C_1= \{1,2,4\}, C_2= \{3,5,6\}.$$ Since the designed distance is $$5$$, I cant pick $$\delta-1=4$$ distinct consecutive elements from $$\alpha^a, \alpha^{a+1}, \cdots, \alpha^{a+\delta-2}$$ for any value of $$a$$ without having an element in the three cosets and that will make the degree of my polynomial to be $$6$$ or $$7$$ and I also want the weight of the generator to be at least $$5$$. The most natural choice would be $$1+x+x^2+x^3+x^4$$ but this can not work because it does not divide $$x^7-1$$. Also, it is not the lcm of any of the minimal polynomial. Please, How can i construct this generator polynomial. Any help will be appreciated.

• You need to work over the field $GF(8)$, not $GF(2)$. Nov 26, 2018 at 7:51
• @Wuestenfux Thank you for pointing that out. I totally forgot and I figured it out. In fact, the cyclotomic sets are singletons and the generator polynomial is trivial. Thanks once again :) Nov 26, 2018 at 8:32

The first thing you have to do is to create a Field with 8 elements and find a primite element of it. For this, it's sufficient to consider $$\mathbb{F}_8 := \mathbb{F}_2/(x^3+x+1)$$. Denote $$\alpha := [x]$$, then $$\alpha^3=\alpha+1$$. Finding a primitive element of the field means find a generator of the multiplicative group $$(\mathbb{F}_8)^* := \mathbb{F}_8$$. Note that $$\vert (\mathbb{F}_8)^* \vert = 7$$ and since every element $$1 \neq \beta \in (\mathbb{F}_8)^*$$ has a period that divide 7, each non trivial element of $$(\mathbb{F}_8)^*$$ is primitive. In conclusion we can take $$\alpha$$ as a primitive element of the field.
Since your code is a Reed Solomon code, the cyclotomic sets are made up by just one element, and you can consider the Defining set $$\{ 1,2,3,4 \}$$, which is also a complete defining set for a suitable polynomial $$g:=(x-\alpha)\cdot (x-\alpha^2) \cdot (x-\alpha^3) \cdot (x-\alpha^4) \in \mathbb{F}_8[x]$$ Computing $$g$$ we obtain $$g = x^4+(\alpha+1)x^3+x^2+\alpha x + \alpha + 1$$