galois.BCH¶
- class galois.BCH(n, k, primitive_poly=None, primitive_element=None, systematic=True)¶
Constructs 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.
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 intodecode()
. Shortened codes are only applicable for systematic codes.- Parameters
n (int) – The codeword size \(n\), must be \(n = 2^m - 1\).
k (int) – The message size \(k\).
primitive_poly (galois.Poly, optional) – Optionally specify the primitive polynomial that defines the extension field \(\mathrm{GF}(2^m)\). The default is
None
which uses Matlab’s default, seegalois.matlab_primitive_poly()
. Matlab tends to use the lexicographically-minimal primitive polynomial as a default instead of the Conway polynomial.primitive_element (int, galois.Poly, optional) – 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)\), i.e.galois.primitive_element(2, m)
.systematic (bool, optional) – Optionally specify if the encoding should be systematic, meaning the codeword is the message with parity appended. The default is
True
.
Examples
In [1]: galois.bch_valid_codes(15) Out[1]: [(15, 11, 1), (15, 7, 2), (15, 5, 3)] In [2]: bch = galois.BCH(15, 7) In [3]: m = galois.GF2.Random(bch.k); m Out[3]: GF([0, 1, 0, 0, 1, 0, 0], order=2) In [4]: c = bch.encode(m); c Out[4]: GF([0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0], order=2) # Corrupt the first bit in the codeword In [5]: c[0] ^= 1 In [6]: dec_m = bch.decode(c); dec_m Out[6]: GF([0, 1, 0, 0, 1, 0, 0], 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([0, 1, 0, 0, 1, 0, 0], order=2), 1) In [9]: np.array_equal(dec_m, m) Out[9]: True
Constructors
Methods
decode
(codeword[, errors])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
The generator matrix \(\mathbf{G}\) with shape \((k, n)\).
The parity-check matrix \(\mathbf{H}\) with shape \((2t, n)\).
The design distance \(d\) of the \([n, k, d]_2\) code.
The Galois field \(\mathrm{GF}(2^m)\) that defines the BCH code.
The generator polynomial \(g(x)\) whose roots are
BCH.roots
.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 - 1}\).
Indicates if the BCH code is primitive, meaning \(n = 2^m - 1\).
The message size \(k\) of the \([n, k, d]_2\) code
The codeword size \(n\) of the \([n, k, d]_2\) code
The \(2t\) roots of the generator polynomial.
Indicates if the code is configured to return codewords in systematic form.
The error-correcting capability of the code.
- decode(codeword, errors=False)[source]¶
Decodes the BCH codeword \(\mathbf{c}\) into the message \(\mathbf{m}\).
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.- Parameters
codeword (numpy.ndarray, galois.FieldArray) – 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 (bool, optional) – Optionally specify whether to return the nubmer of corrected errors.
- Returns
numpy.ndarray, galois.FieldArray – The decoded message as either a \(k\)-length vector or \((N, k)\) matrix.
int, np.ndarray – 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.
Examples
Decode a single codeword.
In [1]: bch = galois.BCH(15, 7) In [2]: m = galois.GF2.Random(bch.k); m Out[2]: GF([0, 1, 1, 1, 0, 1, 1], order=2) In [3]: c = bch.encode(m); c Out[3]: GF([0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 1], order=2) # Corrupt the first bit in the codeword In [4]: c[0] ^= 1 In [5]: dec_m = bch.decode(c); dec_m Out[5]: GF([0, 1, 1, 1, 0, 1, 1], order=2) In [6]: np.array_equal(dec_m, m) Out[6]: True # Instruct the decoder to return the number of corrected bit errors In [7]: dec_m, N = bch.decode(c, errors=True); dec_m, N Out[7]: (GF([0, 1, 1, 1, 0, 1, 1], order=2), 1) In [8]: np.array_equal(dec_m, m) Out[8]: True
Decode a single, shortened codeword.
In [9]: m = galois.GF2.Random(bch.k - 3); m Out[9]: GF([0, 0, 0, 1], order=2) In [10]: c = bch.encode(m); c Out[10]: GF([0, 0, 0, 1, 1, 1, 0, 1, 0, 0, 0, 1], order=2) # Corrupt the first bit in the codeword In [11]: c[0] ^= 1 In [12]: dec_m = bch.decode(c); dec_m Out[12]: GF([0, 0, 0, 1], order=2) In [13]: np.array_equal(dec_m, m) Out[13]: True
Decode a matrix of codewords.
In [14]: m = galois.GF2.Random((5, bch.k)); m Out[14]: GF([[1, 1, 1, 0, 1, 0, 1], [1, 1, 0, 0, 0, 0, 1], [0, 0, 1, 1, 1, 0, 1], [1, 0, 1, 0, 0, 1, 0], [1, 1, 1, 0, 0, 0, 1]], order=2) In [15]: c = bch.encode(m); c Out[15]: GF([[1, 1, 1, 0, 1, 0, 1, 1, 0, 0, 1, 0, 0, 0, 1], [1, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 1, 1, 0, 1], [0, 0, 1, 1, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0], [1, 0, 1, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0, 0, 1], [1, 1, 1, 0, 0, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1]], order=2) # Corrupt the first bit in each codeword In [16]: c[:,0] ^= 1 In [17]: dec_m = bch.decode(c); dec_m Out[17]: GF([[1, 1, 1, 0, 1, 0, 1], [1, 1, 0, 0, 0, 0, 1], [0, 0, 1, 1, 1, 0, 1], [1, 0, 1, 0, 0, 1, 0], [1, 1, 1, 0, 0, 0, 1]], order=2) In [18]: np.array_equal(dec_m, m) Out[18]: True # Instruct the decoder to return the number of corrected bit errors In [19]: dec_m, N = bch.decode(c, errors=True); dec_m, N Out[19]: (GF([[1, 1, 1, 0, 1, 0, 1], [1, 1, 0, 0, 0, 0, 1], [0, 0, 1, 1, 1, 0, 1], [1, 0, 1, 0, 0, 1, 0], [1, 1, 1, 0, 0, 0, 1]], order=2), array([1, 1, 1, 1, 1])) In [20]: np.array_equal(dec_m, m) Out[20]: True
- detect(codeword)[source]¶
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 (numpy.ndarray, galois.FieldArray) – 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 notFalse
.- Return type
Examples
Detect errors in a valid codeword.
In [1]: bch = galois.BCH(15, 7) # The minimum distance of the code In [2]: bch.d Out[2]: 5 In [3]: m = galois.GF2.Random(bch.k); m Out[3]: GF([0, 1, 0, 0, 1, 0, 1], order=2) In [4]: c = bch.encode(m); c Out[4]: GF([0, 1, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0, 0, 1, 1], order=2) In [5]: bch.detect(c) Out[5]: False
Detect \(d_{min}-1\) errors in a received codeword.
# Corrupt the first `d - 1` bits in the codeword In [6]: c[0:bch.d - 1] ^= 1 In [7]: bch.detect(c) Out[7]: True
- encode(message, parity_only=False)[source]¶
Encodes the message \(\mathbf{m}\) into the BCH codeword \(\mathbf{c}\).
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.- Parameters
message (numpy.ndarray, galois.FieldArray) – 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 (bool, optional) – 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.- Return type
Examples
Encode a single codeword.
In [1]: bch = galois.BCH(15, 7) In [2]: m = galois.GF2.Random(bch.k); m Out[2]: GF([0, 0, 0, 0, 0, 0, 0], order=2) In [3]: c = bch.encode(m); c Out[3]: GF([0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], order=2) In [4]: p = bch.encode(m, parity_only=True); p Out[4]: GF([0, 0, 0, 0, 0, 0, 0, 0], order=2)
Encode a single, shortened codeword.
In [5]: m = galois.GF2.Random(bch.k - 3); m Out[5]: GF([0, 0, 0, 1], order=2) In [6]: c = bch.encode(m); c Out[6]: GF([0, 0, 0, 1, 1, 1, 0, 1, 0, 0, 0, 1], order=2)
Encode a matrix of codewords.
In [7]: m = galois.GF2.Random((5, bch.k)); m Out[7]: GF([[1, 1, 1, 1, 0, 1, 0], [1, 1, 0, 0, 0, 0, 0], [0, 1, 0, 0, 0, 0, 1], [0, 0, 1, 0, 0, 1, 0], [0, 0, 0, 1, 0, 0, 0]], order=2) In [8]: c = bch.encode(m); c Out[8]: GF([[1, 1, 1, 1, 0, 1, 0, 1, 1, 0, 0, 1, 0, 0, 0], [1, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 1, 1, 0, 0], [0, 1, 0, 0, 0, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1], [0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1], [0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 1]], order=2) In [9]: p = bch.encode(m, parity_only=True); p Out[9]: GF([[1, 1, 0, 0, 1, 0, 0, 0], [1, 0, 0, 1, 1, 1, 0, 0], [1, 0, 1, 0, 0, 1, 0, 1], [0, 1, 0, 0, 1, 0, 0, 1], [0, 0, 0, 1, 1, 1, 0, 1]], order=2)
- property G¶
The generator matrix \(\mathbf{G}\) with shape \((k, n)\).
- Type
- property H¶
The parity-check matrix \(\mathbf{H}\) with shape \((2t, n)\).
- Type
- property d¶
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\).
- Type
- property field¶
The Galois field \(\mathrm{GF}(2^m)\) that defines the BCH code.
- Type
- property 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 - 1}\).
- Type
- property roots¶
The \(2t\) roots of the generator polynomial. These are consecutive powers of \(\alpha\).
- Type
- property systematic¶
Indicates if the code is configured to return codewords in systematic form.
- Type