class galois.BCH

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

A $$\textrm{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$$.

Shortened codes

To create the shortened $$\textrm{BCH}(n-s, k-s)$$ code, construct the full-sized $$\textrm{BCH}(n, k)$$ code and then pass $$k-s$$ symbols into encode() and $$n-s$$ symbols into decode(). Shortened codes are only applicable for systematic codes.

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)$$.

$g(x) = \textrm{LCM}(m_{\alpha^c}(x), \dots, m_{\alpha^{c+d-2}}(x))$

Examples

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

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

In : GF = bch.field; GF
Out: <class 'galois.GF(2)'>


Encode a message.

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

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


Corrupt the codeword and decode the message.

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

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

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


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

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

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


## Constructors¶

BCH(n: int, k: = None, d: = 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(...)
decode(...) tuple[FieldArray, int | np.ndarray]

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

detect(codeword: ArrayLike)

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

encode(...)

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 :

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

property field :

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)$$.