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.
- Parameters
n (int) – The codeword size \(n\), must be \(n = 2^m - 1\).
k (int) – The message size \(k\).
primitive_poly (int, galois.Poly, optional) – Optionally specify the primitive polynomial that defines the extension field \(\mathrm{GF}(2^m)\). The default is
None
which uses the lexicographically-smallest primitive polynomial, i.e.galois.primitive_poly(2, m, method="smallest")
. The use of the lexicographically-smallest primitive polynomial, as opposed to a Conway polynomial, is the default in textbooks, Matlab, and Octave.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-smallest 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, 0, 0, 0, 1, 0, 0], order=2) In [4]: c = bch.encode(m); c Out[4]: GF([0, 0, 0, 0, 1, 0, 0, 1, 1, 1, 0, 0, 1, 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, 0, 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, 0, 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 into its message.
encode
(message[, parity_only])Encodes the message into a BCH codeword.
Attributes
The generator matrix \(G\) with shape \((k, n)\).
The parity-check matrix \(H\) with shape \((n-k, n)\).
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^{2*t - 1}\).
Indicates if the BCH code is primitive, meaning \(n = 2^m - 1\).
The message size \(k\) of the \(\textrm{BCH}(n, k)\) code.
The codeword size \(n\) of the \(\textrm{BCH}(n, k)\) code.
The 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 into its message.
- Parameters
codeword (np.ndarray, galois.FieldArray) – The codeword as either a \(n\)-length vector or \((N, n)\) matrix, where \(N\) is the number of codewords.
errors (bool, optional) – Optionally specify whether to return the nubmer of corrected errors.
- Returns
np.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
In [1]: bch = galois.BCH(15, 7) In [2]: m = galois.GF2.Random(bch.k); m Out[2]: GF([1, 0, 0, 1, 0, 1, 0], order=2) In [3]: c = bch.encode(m); c Out[3]: GF([1, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0, 0, 1, 1, 0], 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([1, 0, 0, 1, 0, 1, 0], 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([1, 0, 0, 1, 0, 1, 0], order=2), 1) In [8]: np.array_equal(dec_m, m) Out[8]: True
In [9]: bch = galois.BCH(15, 7) In [10]: m = galois.GF2.Random((5, bch.k)); m Out[10]: GF([[1, 1, 0, 0, 0, 0, 1], [0, 0, 1, 0, 1, 0, 1], [1, 1, 1, 0, 0, 0, 1], [1, 1, 1, 1, 0, 0, 1], [0, 0, 1, 0, 0, 0, 1]], order=2) In [11]: c = bch.encode(m); c Out[11]: GF([[1, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 1, 1, 0, 1], [0, 0, 1, 0, 1, 0, 1, 0, 0, 0, 0, 1, 1, 0, 1], [1, 1, 1, 0, 0, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1], [1, 1, 1, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 1, 0], [0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 0, 1, 0, 1, 1]], order=2) # Corrupt the first bit in the codeword In [12]: c[:,0] ^= 1 In [13]: dec_m = bch.decode(c); dec_m Out[13]: GF([[1, 1, 0, 0, 0, 0, 1], [0, 0, 1, 0, 1, 0, 1], [1, 1, 1, 0, 0, 0, 1], [1, 1, 1, 1, 0, 0, 1], [0, 0, 1, 0, 0, 0, 1]], order=2) In [14]: np.array_equal(dec_m, m) Out[14]: True # Instruct the decoder to return the number of corrected bit errors In [15]: dec_m, N = bch.decode(c, errors=True); dec_m, N Out[15]: (GF([[1, 1, 0, 0, 0, 0, 1], [0, 0, 1, 0, 1, 0, 1], [1, 1, 1, 0, 0, 0, 1], [1, 1, 1, 1, 0, 0, 1], [0, 0, 1, 0, 0, 0, 1]], order=2), array([1, 1, 1, 1, 1])) In [16]: np.array_equal(dec_m, m) Out[16]: True
- encode(message, parity_only=False)[source]¶
Encodes the message into a BCH codeword.
- Parameters
message (np.ndarray, galois.FieldArray) – The message as either a \(k\)-length vector or \((N, k)\) matrix, where \(N\) is the number of messages.
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 either a \(n - k\)-length vector or \((N, n-k)\) matrix.- Return type
np.ndarray, galois.FieldArray
Examples
In [1]: bch = galois.BCH(15, 7) In [2]: m = galois.GF2.Random(bch.k); m Out[2]: GF([1, 1, 0, 0, 1, 0, 1], order=2) In [3]: c = bch.encode(m); c Out[3]: GF([1, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 1, 0, 1, 1], order=2) In [4]: p = bch.encode(m, parity_only=True); p Out[4]: GF([1, 0, 1, 0, 1, 0, 1, 1], order=2)
In [5]: bch = galois.BCH(15, 7) In [6]: m = galois.GF2.Random((5, bch.k)); m Out[6]: GF([[0, 1, 1, 0, 1, 1, 0], [1, 1, 0, 1, 0, 1, 0], [1, 0, 1, 1, 1, 1, 0], [1, 0, 0, 1, 1, 0, 1], [1, 1, 0, 1, 0, 1, 1]], order=2) In [7]: c = bch.encode(m); c Out[7]: GF([[0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1], [1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 1, 0, 0, 1, 0], [1, 0, 1, 1, 1, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0], [1, 0, 0, 1, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0], [1, 1, 0, 1, 0, 1, 1, 0, 0, 1, 0, 0, 0, 1, 1]], order=2) In [8]: p = bch.encode(m, parity_only=True); p Out[8]: GF([[1, 1, 0, 1, 1, 0, 1, 1], [1, 1, 1, 1, 0, 0, 1, 0], [0, 1, 0, 1, 1, 0, 1, 0], [1, 1, 0, 0, 0, 0, 1, 0], [0, 0, 1, 0, 0, 0, 1, 1]], order=2)
- property G¶
The generator matrix \(G\) with shape \((k, n)\).
- Type
- property H¶
The parity-check matrix \(H\) with shape \((n-k, n)\).
- 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^{2*t - 1}\).
- Type
- property roots¶
The 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