A general \(\mathrm{BCH}(n, k)\) code over \(\mathrm{GF}(q)\).

A \(\mathrm{BCH}(n, k)\) code is a cyclic \([n, k, d]_q\) linear block code of length \(n\), dimension \(k\), and minimum distance \(d\), whose symbols lie in the finite field \(\mathrm{GF}(q)\). BCH codes form a broad, algebraically structured family of codes constructed by prescribing a consecutive run of powers of a primitive \(n\)-th root of unity as roots of the generator polynomial.

The classical narrow-sense BCH construction begins with the following setup. Let \(n \mid (q^m - 1)\) for some positive integer \(m\), so that the multiplicative group of \(\mathrm{GF}(q^m)\) contains a primitive \(n\)-th root of unity. Let \(\alpha \in \mathrm{GF}(q^m)\) be such a primitive \(n\)-th root of unity.

A BCH code of designed distance \(\delta\) and starting exponent \(c\) is defined by specifying that its generator polynomial \(g(x)\) has, as zeros in the extension field \(\mathrm{GF}(q^m)\), the consecutive powers

Since the code is cyclic over \(\mathrm{GF}(q)\), its generator polynomial must itself lie in \(\mathrm{GF}(q)[x]\). Therefore, for each prescribed root \(\alpha^i\), we include its minimal polynomial over the base field. The generator polynomial is the least common multiple of these minimal polynomials:

where \(m_{\beta}(x)\) denotes the minimal polynomial of \(\beta \in \mathrm{GF}(q^m)\) over \(\mathrm{GF}(q)\).

The resulting cyclic code has length \(n\), generator degree \(\deg g(x)\), and therefore dimension \(k = n - \deg g(x)\). The actual minimum distance \(d\) satisfies \(d \ge \delta\) by the BCH bound. Narrow-sense BCH codes correspond to the choice \(c = 1\), i.e., roots \(\alpha, \alpha^2, \ldots, \alpha^{\delta-1}\).

This implementation supports general (not necessarily narrow-sense) BCH codes over any prime-power field \(\mathrm{GF}(q)\), provided that \(n \mid (q^m - 1)\) for the chosen extension degree \(m\).

Examples¶

Construct a binary \(\textrm{BCH}(15, 7)\) code.

In [1]: bch = galois.BCH(15, 7); bch
Out[1]: <BCH Code: [15, 7, 5] over GF(2)>

In [2]: GF = bch.field; GF
Out[2]: <class 'galois.GF(2, primitive_element='1', irreducible_poly='x + 1')'>

Encode a message.

In [3]: m = GF.Random(bch.k); m
Out[3]: GF([1, 0, 1, 0, 0, 1, 1], order=2)

In [4]: c = bch.encode(m); c
Out[4]: GF([1, 0, 1, 0, 0, 1, 1, 0, 1, 1, 1, 0, 0, 0, 0], order=2)

Corrupt the codeword and decode the message.

# Corrupt the first symbol in the codeword
In [5]: c[0] ^= 1; c
Out[5]: GF([0, 0, 1, 0, 0, 1, 1, 0, 1, 1, 1, 0, 0, 0, 0], order=2)

In [6]: dec_m = bch.decode(c); dec_m
Out[6]: GF([1, 0, 1, 0, 0, 1, 1], order=2)

In [7]: assert np.array_equal(dec_m, m)

Instruct the decoder to return the number of corrected symbol errors.

In [8]: dec_m, N = bch.decode(c, errors=True); dec_m, N
Out[8]: (GF([1, 0, 1, 0, 0, 1, 1], order=2), 1)

In [9]: assert np.array_equal(dec_m, m)

Constructors¶

BCH(n: int, k: int | None = None, d: int | None = None, ...)

Constructs a general \(\textrm{BCH}(n, k)\) code over \(\mathrm{GF}(q)\).

String representation¶

__repr__() → str

A terse representation of the BCH code.

__str__() → str

A formatted string with relevant properties of the BCH code.

Methods¶

decode(codeword: ArrayLike, ...) → FieldArray

decode(codeword: ArrayLike, ...) → tuple[FieldArray, int | ndarray]

Decodes the codeword \(\mathbf{c}\) into the message \(\mathbf{m}\).

detect(codeword: ArrayLike) → bool | ndarray

Detects if errors are present in the codeword \(\mathbf{c}\).

encode(message: ArrayLike, ...) → FieldArray

Encodes the message \(\mathbf{m}\) into the codeword \(\mathbf{c}\).

Properties¶

property d : int

The minimum distance \(d\) of the \([n, k, d]_q\) code.

property extension_field : type[FieldArray]

The Galois field \(\mathrm{GF}(q^m)\) that defines the BCH syndrome arithmetic.

property field : type[FieldArray]

The Galois field \(\mathrm{GF}(q)\) that defines the codeword alphabet.

property k : int

The message size \(k\) of the \([n, k, d]_q\) code. This is also called the code dimension.

property n : int

The codeword size \(n\) of the \([n, k, d]_q\) code. This is also called the code length.

property t : int

The error-correcting capability \(t\) of the code.

Attributes¶

property is_narrow_sense : bool

Indicates if the BCH code is narrow-sense, meaning the roots of the generator polynomial are consecutive powers of \(\alpha\) starting at 1, that is \(\alpha, \dots, \alpha^{d-1}\).

property is_primitive : bool

Indicates if the BCH code is primitive, meaning \(n = q^m - 1\).

property is_systematic : bool

Indicates if the code is systematic, meaning the codewords have parity appended to the message.

Matrices¶

property G : FieldArray

The generator matrix \(\mathbf{G}\) with shape \((k, n)\).

property H : FieldArray

The parity-check matrix \(\mathbf{H}\) with shape \((n - k, n)\).

Polynomials¶

property alpha : FieldArray

A primitive \(n\)-th root of unity \(\alpha\) in \(\mathrm{GF}(q^m)\) whose consecutive powers \(\alpha^c, \dots, \alpha^{c+d-2}\) are roots of the generator polynomial \(g(x)\) in \(\mathrm{GF}(q^m)\).

property c : int

The first consecutive power \(c\) of \(\alpha\) that defines the roots \(\alpha^c, \dots, \alpha^{c+d-2}\) of the generator polynomial \(g(x)\).

property generator_poly : Poly

The generator polynomial \(g(x)\) over \(\mathrm{GF}(q)\).

property parity_check_poly : Poly

The parity-check polynomial \(h(x)\).

property roots : FieldArray

The \(d - 1\) roots of the generator polynomial \(g(x)\).