BCH codes have very attractive error correction algorithms. Let $C$ be a BCH code in $R_n$, and suppose that a code polynomial $c(t) = c_0 + c_1 t + \cdots + c_{n-1} t^{n-1}$ is transmitted. Let $w(t) = w_0 + w_1 t + \cdots w_{n-1} t^{n-1}$ be the polynomial in $R_n$ that is received. If errors have occurred in bits $a_1, \ldots, a_k$, then $w(t) = c(t) + e(t)$, where $e(t) = t^{a_1} + t^{a_2} + \cdots + t^{a_k}$ is the error polynomial. The decoder must determine the integers $a_i$ and then recover $c(t)$ from $w(t)$ by flipping the $a_i$th bit. From $w(t)$ we can compute $w( \omega^i ) = s_i$ for $i = 1, \ldots, 2r$, where $\omega$ is a primitive $n$th root of unity over ${\mathbb Z}_2$. We say the syndrome of $w(t)$ is $s_1, \ldots, s_{2r}$.

##### 1

Show that $w(t)$ is a code polynomial if and only if $s_i = 0$ for all $i$.

##### 2

Show that \begin{equation*}s_i = w( \omega^i) = e( \omega^i) = \omega^{i a_1} + \omega^{i a_2} + \cdots + \omega^{i a_k}\end{equation*} for $i = 1, \ldots, 2r$. The error-locator polynomial is defined to be \begin{equation*}s(x) = (x + \omega^{a_1})(x + \omega^{a_2}) \cdots (x + \omega^{a_k}).\end{equation*}

##### 3

Recall the $(15,7)$-block BCH code in Example 22.19. By Theorem 8.13, this code is capable of correcting two errors. Suppose that these errors occur in bits $a_1$ and $a_2$. The error-locator polynomial is $s(x) = (x + \omega^{a_1})(x + \omega^{a_2})$. Show that \begin{equation*}s(x) = x^2 + s_1 x + \left( s_1^2 + \frac{s_3}{s_1} \right).\end{equation*}

##### 4

Let $w(t) = 1 + t^2 +t^4 + t^5 + t^7 + t^{12} + t^{13}$. Determine what the originally transmitted code polynomial was.