## Exercises17.5Additional Exercises: Error Correction for BCH Codes

BCH codes have very attractive error correction algorithms. Let $C$ be a BCH code in $R_n\text{,}$ 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\text{,}$ then $w(t) = c(t) + e(t)\text{,}$ 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\text{,}$ where $\omega$ is a primitive $n$th root of unity over ${\mathbb Z}_2\text{.}$ We say the syndrome of $w(t)$ is $s_1, \ldots, s_{2r}\text{.}$

###### 1.

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

###### 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\text{.}$ 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})\text{.} \end{equation*}
###### 3.

Recall the $(15,7)$-block BCH code in Example 17.19. By Theorem 16.13, this code is capable of correcting two errors. Suppose that these errors occur in bits $a_1$ and $a_2\text{.}$ The error-locator polynomial is $s(x) = (x + \omega^{a_1})(x + \omega^{a_2})\text{.}$ Show that

\begin{equation*} s(x) = x^2 + s_1 x + \left( s_1^2 + \frac{s_3}{s_1} \right)\text{.} \end{equation*}
###### 4.

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