## Exercises22.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 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\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.