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 .