galois.BCH

class galois.BCH(n: int, k: int, primitive_poly: PolyLike | None = None, primitive_element: PolyLike | None = None, systematic: bool = True)

A primitive, narrow-sense binary \(\textrm{BCH}(n, k)\) code.

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

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\) bits into encode() and \(n-s\) bits into decode(). Shortened codes are only applicable for systematic codes.

Examples

Construct the BCH code.

In [1]: galois.bch_valid_codes(15)
Out[1]: [(15, 11, 1), (15, 7, 2), (15, 5, 3), (15, 1, 7)]

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

Encode a message.

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

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

Corrupt the codeword and decode the message.

# Corrupt the first bit in the codeword
In [5]: c[0] ^= 1

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

In [7]: np.array_equal(dec_m, m)
Out[7]: True
# Instruct the decoder to return the number of corrected bit errors
In [8]: dec_m, N = bch.decode(c, errors=True); dec_m, N
Out[8]: (GF([1, 1, 1, 1, 1, 0, 1], order=2), 1)

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

Constructors

__init__(n, k[, primitive_poly, ...])

Constructs a primitive, narrow-sense binary \(\textrm{BCH}(n, k)\) code.

Special Methods

__repr__()

A terse representation of the BCH code.

__str__()

A formatted string with relevant properties of the BCH code.

Methods

decode()

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

detect(codeword)

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

encode(message[, parity_only])

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

Attributes

G

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

H

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

d

The design distance \(d\) of the \([n, k, d]_2\) code.

field

The FieldArray subclass for the \(\mathrm{GF}(2^m)\) field that defines the BCH code.

generator_poly

The generator polynomial \(g(x)\) whose roots are roots.

is_narrow_sense

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

is_primitive

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

k

The message size \(k\) of the \([n, k, d]_2\) code

n

The codeword size \(n\) of the \([n, k, d]_2\) code

roots

The \(2t\) roots of the generator polynomial.

systematic

Indicates if the code is configured to return codewords in systematic form.

t

The error-correcting capability of the code.

__init__(n: int, k: int, primitive_poly: PolyLike | None = None, primitive_element: PolyLike | None = None, systematic: bool = True)

Constructs a primitive, narrow-sense binary \(\textrm{BCH}(n, k)\) code.

Parameters
n

The codeword size \(n\), must be \(n = 2^m - 1\).

k

The message size \(k\).

primitive_poly

Optionally specify the primitive polynomial that defines the extension field \(\mathrm{GF}(2^m)\). The default is None which uses Matlab’s default, see matlab_primitive_poly().

primitive_element

Optionally specify the primitive element \(\alpha\) whose powers are roots of the generator polynomial \(g(x)\). The default is None which uses the lexicographically-minimal primitive element in \(\mathrm{GF}(2^m)\), see primitive_element().

systematic

Optionally specify if the encoding should be systematic, meaning the codeword is the message with parity appended. The default is True.

__repr__() str

A terse representation of the BCH code.

Examples

In [1]: bch = galois.BCH(15, 7)

In [2]: bch
Out[2]: <BCH Code: [15, 7, 5] over GF(2)>
__str__() str

A formatted string with relevant properties of the BCH code.

Examples

In [1]: bch = galois.BCH(15, 7)

In [2]: print(bch)
BCH Code:
  [n, k, d]: [15, 7, 5]
  field: GF(2)
  generator_poly: x^8 + x^7 + x^6 + x^4 + 1
  is_primitive: True
  is_narrow_sense: True
  systematic: True
  t: 2
decode(codeword: Union[ndarray, GF2], errors: Literal[False] = False) Union[ndarray, GF2]
decode(codeword: Union[ndarray, GF2], errors: Literal[True]) Tuple[Union[ndarray, GF2], Union[integer, ndarray]]

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

Parameters
codeword

The codeword as either a \(n\)-length vector or \((N, n)\) matrix, where \(N\) is the number of codewords. For systematic codes, codeword lengths less than \(n\) may be provided for shortened codewords.

errors

Optionally specify whether to return the number of corrected errors. The default is False.

Returns

  • The decoded message as either a \(k\)-length vector or \((N, k)\) matrix.

  • Optional return argument of the number of corrected bit errors as either a scalar or \(n\)-length vector. Valid number of corrections are in \([0, t]\). If a codeword has too many errors and cannot be corrected, -1 will be returned.

Notes

The codeword vector \(\mathbf{c}\) is defined as \(\mathbf{c} = [c_{n-1}, \dots, c_1, c_0] \in \mathrm{GF}(2)^n\), which corresponds to the codeword polynomial \(c(x) = c_{n-1} x^{n-1} + \dots + c_1 x + c_0\). The message vector \(\mathbf{m}\) is defined as \(\mathbf{m} = [m_{k-1}, \dots, m_1, m_0] \in \mathrm{GF}(2)^k\), which corresponds to the message polynomial \(m(x) = m_{k-1} x^{k-1} + \dots + m_1 x + m_0\).

In decoding, the syndrome vector \(s\) is computed by \(\mathbf{s} = \mathbf{c}\mathbf{H}^T\), where \(\mathbf{H}\) is the parity-check matrix. The equivalent polynomial operation is \(s(x) = c(x)\ \textrm{mod}\ g(x)\). A syndrome of zeros indicates the received codeword is a valid codeword and there are no errors. If the syndrome is non-zero, the decoder will find an error-locator polynomial \(\sigma(x)\) and the corresponding error locations and values.

For the shortened \(\textrm{BCH}(n-s, k-s)\) code (only applicable for systematic codes), pass \(n-s\) bits into decode() to return the \(k-s\)-bit message.

Examples

Encode a single message using the \(\textrm{BCH}(15, 7)\) code.

In [1]: bch = galois.BCH(15, 7)

In [2]: GF = galois.GF(2)

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

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

Corrupt \(t\) bits of the codeword.

In [5]: bch.t
Out[5]: 2

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

Decode the codeword and recover the message.

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

In [8]: np.array_equal(d, m)
Out[8]: True

Decode the codeword, specifying the number of corrected errors, and recover the message.

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

In [10]: np.array_equal(d, m)
Out[10]: True

Encode a single message using the shortened \(\textrm{BCH}(12, 4)\) code.

In [11]: bch = galois.BCH(15, 7)

In [12]: GF = galois.GF(2)

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

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

Corrupt \(t\) bits of the codeword.

In [15]: bch.t
Out[15]: 2

In [16]: c[0:bch.t] ^= 1; c
Out[16]: GF([0, 0, 1, 1, 0, 1, 0, 1, 1, 0, 0, 1], order=2)

Decode the codeword and recover the message.

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

In [18]: np.array_equal(d, m)
Out[18]: True

Decode the codeword, specifying the number of corrected errors, and recover the message.

In [19]: d, e = bch.decode(c, errors=True); d, e
Out[19]: (GF([1, 1, 1, 1], order=2), 2)

In [20]: np.array_equal(d, m)
Out[20]: True

Encode a matrix of three messages using the \(\textrm{BCH}(15, 7)\) code.

In [21]: bch = galois.BCH(15, 7)

In [22]: GF = galois.GF(2)

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

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

Corrupt the codeword. Add zero errors to the first codeword, one to the second, and two to the third.

In [25]: c[1,0:1] ^= 1

In [26]: c[2,0:2] ^= 1

In [27]: c
Out[27]: 
GF([[1, 1, 1, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 1, 0],
    [1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 1],
    [0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 1, 1, 0, 0]], order=2)

Decode the codeword and recover the message.

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

In [29]: np.array_equal(d, m)
Out[29]: True

Decode the codeword, specifying the number of corrected errors, and recover the message.

In [30]: d, e = bch.decode(c, errors=True); d, e
Out[30]: 
(GF([[1, 1, 1, 1, 0, 0, 1],
     [0, 1, 0, 0, 0, 1, 0],
     [1, 1, 0, 0, 0, 0, 0]], order=2),
 array([0, 1, 2]))

In [31]: np.array_equal(d, m)
Out[31]: True

Encode a matrix of three messages using the shortened \(\textrm{BCH}(12, 4)\) code.

In [32]: bch = galois.BCH(15, 7)

In [33]: GF = galois.GF(2)

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

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

Corrupt the codeword. Add zero errors to the first codeword, one to the second, and two to the third.

In [36]: c[1,0:1] ^= 1

In [37]: c[2,0:2] ^= 1

In [38]: c
Out[38]: 
GF([[1, 0, 1, 0, 0, 1, 1, 0, 1, 1, 1, 0],
    [1, 1, 0, 0, 1, 1, 1, 0, 0, 1, 1, 0],
    [0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0]], order=2)

Decode the codeword and recover the message.

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

In [40]: np.array_equal(d, m)
Out[40]: True

Decode the codeword, specifying the number of corrected errors, and recover the message.

In [41]: d, e = bch.decode(c, errors=True); d, e
Out[41]: 
(GF([[1, 0, 1, 0],
     [0, 1, 0, 0],
     [1, 1, 1, 0]], order=2),
 array([0, 1, 2]))

In [42]: np.array_equal(d, m)
Out[42]: True
detect(codeword: ndarray | GF2) bool_ | ndarray

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

The \([n, k, d]_2\) BCH code has \(d_{min} \ge d\) minimum distance. It can detect up to \(d_{min}-1\) errors.

Parameters
codeword

The codeword as either a \(n\)-length vector or \((N, n)\) matrix, where \(N\) is the number of codewords. For systematic codes, codeword lengths less than \(n\) may be provided for shortened codewords.

Returns

A boolean scalar or array indicating if errors were detected in the corresponding codeword True or not False.

Examples

Encode a single message using the \(\textrm{BCH}(15, 7)\) code.

In [1]: bch = galois.BCH(15, 7)

In [2]: GF = galois.GF(2)

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

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

Detect no errors in the valid codeword.

In [5]: bch.detect(c)
Out[5]: False

Detect \(d_{min}-1\) errors in the codeword.

In [6]: bch.d
Out[6]: 5

In [7]: c[0:bch.d - 1] ^= 1; c
Out[7]: GF([1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1], order=2)

In [8]: bch.detect(c)
Out[8]: True

Encode a single message using the shortened \(\textrm{BCH}(12, 4)\) code.

In [9]: bch = galois.BCH(15, 7)

In [10]: GF = galois.GF(2)

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

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

Detect no errors in the valid codeword.

In [13]: bch.detect(c)
Out[13]: False

Detect \(d_{min}-1\) errors in the codeword.

In [14]: bch.d
Out[14]: 5

In [15]: c[0:bch.d - 1] ^= 1; c
Out[15]: GF([1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 0, 1], order=2)

In [16]: bch.detect(c)
Out[16]: True

Encode a matrix of three messages using the \(\textrm{BCH}(15, 7)\) code.

In [17]: bch = galois.BCH(15, 7)

In [18]: GF = galois.GF(2)

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

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

Detect no errors in the valid codewords.

In [21]: bch.detect(c)
Out[21]: array([False, False, False])

Detect one, two, and \(d_{min}-1\) errors in the codewords.

In [22]: bch.d
Out[22]: 5

In [23]: c[0,0:1] ^= 1

In [24]: c[1,0:2] ^= 1

In [25]: c[2, 0:bch.d - 1] ^= 1

In [26]: c
Out[26]: 
GF([[0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1],
    [1, 1, 1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 0, 0, 1]], order=2)

In [27]: bch.detect(c)
Out[27]: array([ True,  True,  True])

Encode a matrix of three messages using the shortened \(\textrm{BCH}(12, 4)\) code.

In [28]: bch = galois.BCH(15, 7)

In [29]: GF = galois.GF(2)

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

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

Detect no errors in the valid codewords.

In [32]: bch.detect(c)
Out[32]: array([False, False, False])

Detect one, two, and \(d_{min}-1\) errors in the codewords.

In [33]: bch.d
Out[33]: 5

In [34]: c[0,0:1] ^= 1

In [35]: c[1,0:2] ^= 1

In [36]: c[2, 0:bch.d - 1] ^= 1

In [37]: c
Out[37]: 
GF([[0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 1],
    [0, 0, 1, 1, 0, 1, 0, 1, 1, 0, 0, 1],
    [1, 0, 1, 1, 1, 1, 1, 0, 0, 1, 1, 0]], order=2)

In [38]: bch.detect(c)
Out[38]: array([ True,  True,  True])
encode(message: ndarray | GF2, parity_only: bool = False) ndarray | GF2

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

Parameters
message

The message as either a \(k\)-length vector or \((N, k)\) matrix, where \(N\) is the number of messages. For systematic codes, message lengths less than \(k\) may be provided to produce shortened codewords.

parity_only

Optionally specify whether to return only the parity bits. This only applies to systematic codes. The default is False.

Returns

The codeword as either a \(n\)-length vector or \((N, n)\) matrix. The return type matches the message type. If parity_only=True, the parity bits are returned as either a \(n - k\)-length vector or \((N, n-k)\) matrix.

Notes

The message vector \(\mathbf{m}\) is defined as \(\mathbf{m} = [m_{k-1}, \dots, m_1, m_0] \in \mathrm{GF}(2)^k\), which corresponds to the message polynomial \(m(x) = m_{k-1} x^{k-1} + \dots + m_1 x + m_0\). The codeword vector \(\mathbf{c}\) is defined as \(\mathbf{c} = [c_{n-1}, \dots, c_1, c_0] \in \mathrm{GF}(2)^n\), which corresponds to the codeword polynomial \(c(x) = c_{n-1} x^{n-1} + \dots + c_1 x + c_0\).

The codeword vector is computed from the message vector by \(\mathbf{c} = \mathbf{m}\mathbf{G}\), where \(\mathbf{G}\) is the generator matrix. The equivalent polynomial operation is \(c(x) = m(x)g(x)\). For systematic codes, \(\mathbf{G} = [\mathbf{I}\ |\ \mathbf{P}]\) such that \(\mathbf{c} = [\mathbf{m}\ |\ \mathbf{p}]\). And in polynomial form, \(p(x) = -(m(x) x^{n-k}\ \textrm{mod}\ g(x))\) with \(c(x) = m(x)x^{n-k} + p(x)\). For systematic and non-systematic codes, each codeword is a multiple of the generator polynomial, i.e. \(g(x)\ |\ c(x)\).

For the shortened \(\textrm{BCH}(n-s, k-s)\) code (only applicable for systematic codes), pass \(k-s\) bits into encode() to return the \(n-s\)-bit codeword.

Examples

Encode a single message using the \(\textrm{BCH}(15, 7)\) code.

In [1]: bch = galois.BCH(15, 7)

In [2]: GF = galois.GF(2)

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

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

Compute the parity bits only.

In [5]: p = bch.encode(m, parity_only=True); p
Out[5]: GF([0, 0, 0, 1, 0, 1, 0, 0], order=2)

Encode a single message using the shortened \(\textrm{BCH}(12, 4)\) code.

In [6]: bch = galois.BCH(15, 7)

In [7]: GF = galois.GF(2)

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

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

Compute the parity bits only.

In [10]: p = bch.encode(m, parity_only=True); p
Out[10]: GF([1, 0, 1, 0, 0, 0, 1, 0], order=2)

Encode a matrix of three messages using the \(\textrm{BCH}(15, 7)\) code.

In [11]: bch = galois.BCH(15, 7)

In [12]: GF = galois.GF(2)

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

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

Compute the parity bits only.

In [15]: p = bch.encode(m, parity_only=True); p
Out[15]: 
GF([[0, 0, 1, 1, 1, 0, 0, 1],
    [0, 0, 0, 1, 1, 0, 0, 1],
    [0, 1, 1, 1, 1, 1, 1, 0]], order=2)

Encode a matrix of three messages using the shortened \(\textrm{BCH}(12, 4)\) code.

In [16]: bch = galois.BCH(15, 7)

In [17]: GF = galois.GF(2)

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

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

Compute the parity bits only.

In [20]: p = bch.encode(m, parity_only=True); p
Out[20]: 
GF([[0, 0, 1, 1, 0, 1, 1, 1],
    [1, 1, 1, 0, 0, 1, 1, 0],
    [1, 0, 0, 1, 0, 1, 0, 1]], order=2)
property G : GF2

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

Examples

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

In [2]: bch.G
Out[2]: 
GF([[1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 1, 0, 0, 0],
    [0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 1, 0, 0],
    [0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 1, 0],
    [0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 1],
    [0, 0, 0, 0, 1, 0, 0, 1, 1, 1, 0, 0, 1, 1, 0],
    [0, 0, 0, 0, 0, 1, 0, 0, 1, 1, 1, 0, 0, 1, 1],
    [0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 1, 0, 0, 0, 1]], order=2)
property H : FieldArray

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

Examples

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

In [2]: bch.H
Out[2]: 
GF([[ 9, 13, 15, 14,  7, 10,  5, 11, 12,  6,  3,  8,  4,  2,  1],
    [13, 14, 10, 11,  6,  8,  2,  9, 15,  7,  5, 12,  3,  4,  1],
    [15, 10, 12,  8,  1, 15, 10, 12,  8,  1, 15, 10, 12,  8,  1],
    [14, 11,  8,  9,  7, 12,  4, 13, 10,  6,  2, 15,  5,  3,  1]],
   order=2^4)
property d : int

The design distance \(d\) of the \([n, k, d]_2\) code. The minimum distance of a BCH code may be greater than the design distance, \(d_{min} \ge d\).

Examples

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

In [2]: bch.d
Out[2]: 5
property field : Type[FieldArray]

The FieldArray subclass for the \(\mathrm{GF}(2^m)\) field that defines the BCH code.

Examples

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

In [2]: bch.field
Out[2]: galois.GF(2^4)

In [3]: print(bch.field)
<class 'galois.GF(2^4)'>
property generator_poly : Poly

The generator polynomial \(g(x)\) whose roots are roots.

Examples

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

In [2]: bch.generator_poly
Out[2]: Poly(x^8 + x^7 + x^6 + x^4 + 1, GF(2))

# Evaluate the generator polynomial at its roots in GF(2^m)
In [3]: bch.generator_poly(bch.roots, field=bch.field)
Out[3]: GF([0, 0, 0, 0], order=2^4)
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, i.e. \(\alpha, \alpha^2, \dots, \alpha^{2t}\).

Examples

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

In [2]: bch.is_narrow_sense
Out[2]: True

In [3]: bch.roots
Out[3]: GF([2, 4, 8, 3], order=2^4)

In [4]: bch.field.primitive_element**(np.arange(1, 2*bch.t + 1))
Out[4]: GF([2, 4, 8, 3], order=2^4)
property is_primitive : bool

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

Examples

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

In [2]: bch.is_primitive
Out[2]: True
property k : int

The message size \(k\) of the \([n, k, d]_2\) code

Examples

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

In [2]: bch.k
Out[2]: 7
property n : int

The codeword size \(n\) of the \([n, k, d]_2\) code

Examples

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

In [2]: bch.n
Out[2]: 15
property roots : FieldArray

The \(2t\) roots of the generator polynomial. These are consecutive powers of \(\alpha\), specifically \(\alpha, \alpha^2, \dots, \alpha^{2t}\).

Examples

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

In [2]: bch.roots
Out[2]: GF([2, 4, 8, 3], order=2^4)

# Evaluate the generator polynomial at its roots in GF(2^m)
In [3]: bch.generator_poly(bch.roots, field=bch.field)
Out[3]: GF([0, 0, 0, 0], order=2^4)
property systematic : bool

Indicates if the code is configured to return codewords in systematic form.

Examples

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

In [2]: bch.systematic
Out[2]: True
property t : int

The error-correcting capability of the code. The code can correct \(t\) bit errors in a codeword.

Examples

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

In [2]: bch.t
Out[2]: 2

Last update: May 18, 2022