BCH Code

Let be odd.
Let be a field extension of containing all roots
of unity (e.g. for )
A BCH code with design distance
is a Cyclic Code with Defining Set

Lemma

The generator for BCH code is

where is the minimal polynomial for over

Theorem

The Minimum distance of a code for BCH code is at least the design distance .

Proof

Consider the matrix:

Taking any columns, gives a Vandermonde matrix,
so any columns of are linearly independent.
But a codeword in is a dependence relation
between the columns of so

Note that is not the Parity Check Matrix
in the usual sense, because

Decoding

Suppose we receive where is the error pattern

Definition

The error locator polynomial of an error pattern is

where .

Theorem

Suppose where .
has constant term and satisfies:

where is a polynomial of degree .
Moreover, is the unique polynomial of least degree
satisfying the above.

Proof

Let

So is a polynomial of degree equal to
We work in the ring of formal power series.
Note:

So:

Thus we find:

By definition, for
so for . So for
Thus

Also

To show uniqueness, note has distinct nonzero roots,
so and are coprime.
Suppose and are another pair of solutions.
WLOG
Then

But all have degree so we actually have equality.
As they don’t share any roots it has to be (and )

Application

Taking coefficients of for
allows us to solve for the coeffs of .
Then

This determines and we decode as .