finite-exercises-bch-codes.ipynb

Kernel:

%%html
<link href="http://mathbook.pugetsound.edu/beta/mathbook-content.css" rel="stylesheet" type="text/css" />
<link href="https://aimath.org/mathbook/mathbook-add-on.css" rel="stylesheet" type="text/css" />
<style>.subtitle {font-size:medium; display:block}</style>
<link href="https://fonts.googleapis.com/css?family=Open+Sans:400,400italic,600,600italic" rel="stylesheet" type="text/css" />
<link href="https://fonts.googleapis.com/css?family=Inconsolata:400,700&subset=latin,latin-ext" rel="stylesheet" type="text/css" /><!-- Hide this cell. -->
<script>
var cell = $(".container .cell").eq(0), ia = cell.find(".input_area")
if (cell.find(".toggle-button").length == 0) {
ia.after(
    $('<button class="toggle-button">Toggle hidden code</button>').click(
        function (){ ia.toggle() }
        )
    )
ia.hide()
}
</script>

Important: to view this notebook properly you will need to execute the cell above, which assumes you have an Internet connection. It should already be selected, or place your cursor anywhere above to select. Then press the "Run" button in the menu bar above (the right-pointing arrowhead), or press Shift-Enter on your keyboard.

ParseError: KaTeX parse error: \newcommand{\lt} attempting to redefine \lt; use \renewcommand

Section22.4Additional 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 . 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 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 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\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*}$$

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.