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

A $\text{BCH}(n,k)$ code is a $[n,k,d{]}_q$ linear block code with codeword size $n$, message size $k$, minimum distance $d$, and symbols taken from an alphabet of size $q$.

A BCH code is a cyclic code over $\mathrm{GF}(q)$ with generator polynomial $g(x)$. The generator polynomial is over $\mathrm{GF}(q)$ and has $d-1$ roots ${\alpha }^c,\dots ,{\alpha }^{c+d-2}$ when evaluated in $\mathrm{GF}(q^m)$. The element $\alpha$ is a primitive $n$-th root of unity in $\mathrm{GF}(q^m)$.

Examples¶

Construct a binary $\text{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)'>

Encode a message.

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

In [4]: c = bch.encode(m); c
Out[4]: GF([0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 0, 0, 0, 1, 1], 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([1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 0, 0, 0, 1, 1], order=2)

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

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

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([0, 0, 1, 1, 1, 1, 1], order=2), 1)

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

Constructors¶

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

Constructs a general $\text{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, ...) → tuple[FieldArray, int | np.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 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 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 G : FieldArray

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

property generator_poly : Poly

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

property H : FieldArray

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

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.

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 parity_check_poly : Poly

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

property roots : FieldArray

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

property t : int

The error-correcting capability $t$ of the code. The code can correct $t$ symbol errors in a codeword.