My question: Let $\alpha$ be a root of $1+x+x^4 \in \text{F}_{2}\left[x\right]$ and let C be a narrow-sense BCH code with length 15, and designed distance 5.
Find the generator polynomial of $C$ and determine the error position of $100000111000000$.
My work so far:
If $\alpha$ is a root of $1+x+x^4 \in \text{F}_{2}\left[x\right]$ and $C$ is a narrow-sense BCH code with parameters with length 15 and designed distance 5, then a generator polynomial is
$g\left(x\right)=\text{lcm}\left(1+x+x^4\right)\left(1+x+x^2+x^3+x^4\right)=1+x^4+x^6+x^7+x^8$
and we also noted that this code will be able to correct 2 errors, from the equation for designed distance $d=2\delta +1$, and because the degree of $g\left(x\right)$ is $8$, we will have a $\left[15, 7, 5\right]$ narrow-sense BCH code.
Now in order to decode the received word $w\left(x\right)=\left(w_{0}+w_{1}x+…+w_{n-1}x^{n-1}\right)=100000111000000$, first we check
$w\left(x\right)H^{T}=0$, where $H$ is the parity check matrix given by
\begin{bmatrix}1 & \alpha & \alpha^{2} &. . . & \alpha^{14} \\1 & \alpha^{3} & \alpha^{9}&…&\alpha^{12} \end{bmatrix}
and if $w\left(x\right)H^{T}=0$ we conclude that there is no error. If $w\left(x\right)H^{T} \neq 0$, next we calculate the syndromes $\left(s_{0}, s_{1}, …, s_{\delta-2}\right)=\left(w_{0}, w_{1}, …, w_{n-1}\right)H^{T}$, where $s_{i}=e\left(\alpha^{i+1}\right)$ is the error locator polynomial.
Because we have a two error pattern, we will need to find the error polynomial to decode $c\left(x\right)=w\left(x\right)-e\left(x\right)$.
We do this in the following way.
First we consider the system of equations
\begin{align*}
\alpha_{1} + \alpha_{2} &= \,s_{1} \\
\alpha_{1}^{3}+\alpha_{2}^{3} &= \, s_{2} \\
\end{align*}
and noting $$\alpha_{1}^{3}+\alpha_{2}^{3}=\underbrace{\left(\alpha_{1}+\alpha_{2}\right)}_{s_{1}} \underbrace{\left(\alpha_{1}^{2}+\alpha_{1}\alpha_{2}+\alpha_{2}^{2}\right)}_{s^{2}_{1}+\alpha_{1}\alpha_{2}}$$
Then, rewriting the two equations for $\alpha_{1}$ and $\alpha_{2}$,
\begin{align*}
\alpha_{1} + \alpha_{2} &= \,s_{1} \\
\alpha_{1}^{3} \cdot \alpha_{2}^{3} &= \, s_{2}s_{1}^{-1}+s_{1}^{2}=\frac{s_{2}+s_{1}^{3}}{s_{1}} \\
\end{align*}
and finally we construct a quadratic equation whose roots are $\alpha_{1}$ and $\alpha_{2}$,
$\left(x-\alpha_{1}\right)\left(x-\alpha_{2}\right)=x^2-\left(\alpha_{1}+\alpha_{2}\right)+\alpha_{1}\alpha_{2}=x^2+s_{1}x+\frac{s_{2}+s_{1}^{3}}{s_{1}}$.
What is giving me trouble:
So after all of this my question is really where to go from here. Do I simply solve the quadratic equations for the roots of $x^2+s_{1}x+\frac{s_{2}+s_{1}^{3}}{s_{1}}$, or is there another detail I am missing? As always, thanks for the help.
Best Answer
After taking the comments above into consideration, I believe I have found the solution.
So, using the transpose of $H$,
$$H^{T} = \begin{bmatrix} 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 1 & 0 & 1 & 0 & 1 \\ 1 & 1 & 0 & 0 & 1 & 1 & 1 & 1 \\ 0 & 1 & 1 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 1 & 0 & 0 & 0 & 1 \\ 1 & 1 & 0 & 1 & 0 & 0 & 1 & 1 \\ 1 & 0 & 1 & 0 & 0 & 1 & 0 & 1 \\ 0 & 1 & 0 & 1 & 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 0 & 1 & 0 & 0 & 0 \\ 0 & 1 & 1 & 1 & 0 & 0 & 0 & 1 \\ 1 & 1 & 1 & 1 & 0 & 0 & 1 & 1 \\ 1 & 0 & 1 & 1 & 0 & 1 & 0 & 1 \\ 1 & 0 & 0 & 1 & 1 & 1 & 1 & 1 \end{bmatrix} $$,
and setting $w\left(x\right)=\begin{bmatrix} 1 & 0 & 0 & 0 &0 &0& 1& 1& 1& 0& 0& 0& 0& 0& 0\end{bmatrix}$
then $$w\left(x\right)H^{T}=\begin{bmatrix} 1 & 1 & 0 & 0 & 1 & 1 & 1 & 1 \end{bmatrix}^T=\begin{bmatrix} 1\\ 1\\ 0\\ 0\\ 1\\ 1\\ 1\\ 1 \end{bmatrix}=\begin{bmatrix} \alpha^{4}\\ \alpha^{12}\\ \end{bmatrix}=\begin{bmatrix} s_{1}\\ s_{2}\\ \end{bmatrix}$$
Now solving for $x^2+s_{1}x+\frac{s_{2}+s_{1}^{3}}{{s_{1}}}=0$,
$$x^2+\alpha^{4}x+\frac{\alpha^{12}+\left(\alpha^{4}\right)^{3}}{\alpha^{4}}=0$$
$$\implies x^2+\alpha^{4}+2\alpha^{8}=x^2+\alpha^{4}$$
is the error check polynomial.
We can check this with $$s\left(x\right)=\left(x-\alpha^{2}\right)\left(x-\alpha^{2}\right)=x^2+\alpha^4$$
So taking this into consideration we can conclude that the errors were in the fourth and twelfth positions.