###### 1

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

\(\newcommand{\identity}{\mathrm{id}}
\newcommand{\notdivide}{\nmid}
\newcommand{\notsubset}{\not\subset}
\newcommand{\lcm}{\operatorname{lcm}}
\newcommand{\gf}{\operatorname{GF}}
\newcommand{\inn}{\operatorname{Inn}}
\newcommand{\aut}{\operatorname{Aut}}
\newcommand{\Hom}{\operatorname{Hom}}
\newcommand{\cis}{\operatorname{cis}}
\newcommand{\chr}{\operatorname{char}}
\newcommand{\Null}{\operatorname{Null}}
\newcommand{\transpose}{\text{t}}
\newcommand{\lt}{<}
\newcommand{\gt}{>}
\newcommand{\amp}{&}
\)

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{.}\)

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

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

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

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.