galois.ReedSolomon¶
- class galois.ReedSolomon(n, k, c=1, primitive_poly=None, primitive_element=None, systematic=True)¶
Constructs a \(\textrm{RS}(n, k)\) code.
A \(\textrm{RS}(n, k)\) code is a \([n, k, d]_q\) linear block code.
To create the shortened \(\textrm{RS}(n-s, k-s)\) code, construct the full-sized \(\textrm{RS}(n, k)\) code and then pass \(k-s\) symbols into
encode()
and \(n-s\) symbols intodecode()
. Shortened codes are only applicable for systematic codes.- Parameters
n (int) – The codeword size \(n\), must be \(n = q - 1\).
k (int) – The message size \(k\). The error-correcting capability \(t\) is defined by \(n - k = 2t\).
c (int, optional) – The first consecutive power of \(\alpha\). The default is 1.
primitive_poly (galois.Poly, optional) – Optionally specify the primitive polynomial that defines the extension field \(\mathrm{GF}(q)\). 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\) of \(\mathrm{GF}(q)\) whose powers are roots of the generator polynomial \(g(x)\). The default is
None
which uses the lexicographically-minimal primitive element in \(\mathrm{GF}(q)\), seegalois.primitive_element()
.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
Construct the Reed-Solomon code.
In [1]: rs = galois.ReedSolomon(15, 9) In [2]: GF = rs.field
Encode a message.
In [3]: m = GF.Random(rs.k); m Out[3]: GF([ 7, 10, 1, 12, 0, 5, 11, 4, 8], order=2^4) In [4]: c = rs.encode(m); c Out[4]: GF([ 7, 10, 1, 12, 0, 5, 11, 4, 8, 0, 13, 2, 5, 4, 7], order=2^4)
Corrupt the codeword and decode the message.
# Corrupt the first symbol in the codeword In [5]: c[0] ^= 13 In [6]: dec_m = rs.decode(c); dec_m Out[6]: GF([ 7, 10, 1, 12, 0, 5, 11, 4, 8], order=2^4) 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 = rs.decode(c, errors=True); dec_m, N Out[8]: (GF([ 7, 10, 1, 12, 0, 5, 11, 4, 8], order=2^4), 1) In [9]: np.array_equal(dec_m, m) Out[9]: True
Methods
decode
(codeword[, errors])Decodes the Reed-Solomon codeword \(\mathbf{c}\) into the message \(\mathbf{m}\).
detect
(codeword)Detects if errors are present in the Reed-Solomon codeword \(\mathbf{c}\).
encode
(message[, parity_only])Encodes the message \(\mathbf{m}\) into the Reed-Solomon codeword \(\mathbf{c}\).
Attributes
The generator matrix \(\mathbf{G}\) with shape \((k, n)\).
The parity-check matrix \(\mathbf{H}\) with shape \((2t, n)\).
The degree of the first consecutive root.
The design distance \(d\) of the \([n, k, d]_q\) code.
The Galois field \(\mathrm{GF}(q)\) that defines the Reed-Solomon code.
The generator polynomial \(g(x)\) whose roots are
roots
.Indicates if the Reed-Solomon 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}\).
The message size \(k\) of the \([n, k, d]_q\) code.
The codeword size \(n\) of the \([n, k, d]_q\) 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)¶
Decodes the Reed-Solomon codeword \(\mathbf{c}\) into the message \(\mathbf{m}\).
- 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 symbol 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}(q)^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}(q)^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{RS}(n-s, k-s)\) code (only applicable for systematic codes), pass \(n-s\) symbols into
decode()
to return the \(k-s\)-symbol message.Examples
Decode a single codeword.
In [1]: rs = galois.ReedSolomon(15, 9) In [2]: GF = rs.field In [3]: m = GF.Random(rs.k); m Out[3]: GF([ 2, 11, 3, 0, 1, 10, 1, 4, 15], order=2^4) In [4]: c = rs.encode(m); c Out[4]: GF([ 2, 11, 3, 0, 1, 10, 1, 4, 15, 13, 12, 7, 3, 6, 15], order=2^4) # Corrupt the first symbol in the codeword In [5]: c[0] += GF(13) In [6]: dec_m = rs.decode(c); dec_m Out[6]: GF([ 2, 11, 3, 0, 1, 10, 1, 4, 15], order=2^4) 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 = rs.decode(c, errors=True); dec_m, N Out[8]: (GF([ 2, 11, 3, 0, 1, 10, 1, 4, 15], order=2^4), 1) In [9]: np.array_equal(dec_m, m) Out[9]: True
Decode a single, shortened codeword.
In [10]: m = GF.Random(rs.k - 4); m Out[10]: GF([ 0, 5, 7, 1, 10], order=2^4) In [11]: c = rs.encode(m); c Out[11]: GF([ 0, 5, 7, 1, 10, 0, 9, 14, 13, 13, 15], order=2^4) # Corrupt the first symbol in the codeword In [12]: c[0] += GF(13) In [13]: dec_m = rs.decode(c); dec_m Out[13]: GF([ 0, 5, 7, 1, 10], order=2^4) In [14]: np.array_equal(dec_m, m) Out[14]: True
Decode a matrix of codewords.
In [15]: m = GF.Random((5, rs.k)); m Out[15]: GF([[ 2, 2, 7, 7, 0, 4, 15, 14, 11], [ 7, 12, 13, 5, 14, 15, 13, 11, 10], [ 8, 1, 5, 3, 0, 3, 7, 1, 1], [ 8, 11, 11, 9, 12, 10, 7, 2, 15], [ 1, 11, 1, 5, 7, 3, 3, 0, 7]], order=2^4) In [16]: c = rs.encode(m); c Out[16]: GF([[ 2, 2, 7, 7, 0, 4, 15, 14, 11, 12, 12, 10, 11, 15, 3], [ 7, 12, 13, 5, 14, 15, 13, 11, 10, 12, 3, 4, 10, 12, 1], [ 8, 1, 5, 3, 0, 3, 7, 1, 1, 13, 7, 12, 12, 14, 13], [ 8, 11, 11, 9, 12, 10, 7, 2, 15, 6, 0, 6, 11, 0, 1], [ 1, 11, 1, 5, 7, 3, 3, 0, 7, 11, 0, 5, 1, 6, 12]], order=2^4) # Corrupt the first symbol in each codeword In [17]: c[:,0] += GF(13) In [18]: dec_m = rs.decode(c); dec_m Out[18]: GF([[ 2, 2, 7, 7, 0, 4, 15, 14, 11], [ 7, 12, 13, 5, 14, 15, 13, 11, 10], [ 8, 1, 5, 3, 0, 3, 7, 1, 1], [ 8, 11, 11, 9, 12, 10, 7, 2, 15], [ 1, 11, 1, 5, 7, 3, 3, 0, 7]], order=2^4) In [19]: np.array_equal(dec_m, m) Out[19]: True # Instruct the decoder to return the number of corrected symbol errors In [20]: dec_m, N = rs.decode(c, errors=True); dec_m, N Out[20]: (GF([[ 2, 2, 7, 7, 0, 4, 15, 14, 11], [ 7, 12, 13, 5, 14, 15, 13, 11, 10], [ 8, 1, 5, 3, 0, 3, 7, 1, 1], [ 8, 11, 11, 9, 12, 10, 7, 2, 15], [ 1, 11, 1, 5, 7, 3, 3, 0, 7]], order=2^4), array([1, 1, 1, 1, 1])) In [21]: np.array_equal(dec_m, m) Out[21]: True
- detect(codeword)¶
Detects if errors are present in the Reed-Solomon codeword \(\mathbf{c}\).
The \([n, k, d]_q\) Reed-Solomon code has \(d_{min} = 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]: rs = galois.ReedSolomon(15, 9) In [2]: GF = rs.field # The minimum distance of the code In [3]: rs.d Out[3]: 7 In [4]: m = GF.Random(rs.k); m Out[4]: GF([0, 9, 2, 4, 4, 7, 3, 8, 3], order=2^4) In [5]: c = rs.encode(m); c Out[5]: GF([ 0, 9, 2, 4, 4, 7, 3, 8, 3, 13, 12, 5, 11, 0, 7], order=2^4) In [6]: rs.detect(c) Out[6]: False
Detect \(d_{min}-1\) errors in a received codeword.
# Corrupt the first `d - 1` symbols in the codeword In [7]: c[0:rs.d - 1] += GF(13) In [8]: rs.detect(c) Out[8]: True
- encode(message, parity_only=False)¶
Encodes the message \(\mathbf{m}\) into the Reed-Solomon codeword \(\mathbf{c}\).
- 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 symbols. 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 symbols are returned as either a \(n - k\)-length vector or \((N, n-k)\) matrix.- Return type
Notes
The message vector \(\mathbf{m}\) is defined as \(\mathbf{m} = [m_{k-1}, \dots, m_1, m_0] \in \mathrm{GF}(q)^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}(q)^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{RS}(n-s, k-s)\) code (only applicable for systematic codes), pass \(k-s\) symbols into
encode()
to return the \(n-s\)-symbol codeword.Examples
Encode a single codeword.
In [1]: rs = galois.ReedSolomon(15, 9) In [2]: GF = rs.field In [3]: m = GF.Random(rs.k); m Out[3]: GF([11, 4, 0, 7, 10, 2, 9, 3, 2], order=2^4) In [4]: c = rs.encode(m); c Out[4]: GF([11, 4, 0, 7, 10, 2, 9, 3, 2, 8, 12, 15, 13, 0, 9], order=2^4) In [5]: p = rs.encode(m, parity_only=True); p Out[5]: GF([ 8, 12, 15, 13, 0, 9], order=2^4)
Encode a single, shortened codeword.
In [6]: m = GF.Random(rs.k - 4); m Out[6]: GF([12, 7, 13, 11, 15], order=2^4) In [7]: c = rs.encode(m); c Out[7]: GF([12, 7, 13, 11, 15, 14, 1, 14, 12, 6, 13], order=2^4)
Encode a matrix of codewords.
In [8]: m = GF.Random((5, rs.k)); m Out[8]: GF([[ 0, 12, 5, 12, 9, 14, 5, 3, 0], [ 2, 8, 3, 11, 8, 15, 14, 11, 11], [ 5, 0, 15, 8, 15, 1, 12, 5, 13], [ 0, 6, 0, 14, 3, 5, 8, 3, 11], [ 9, 11, 0, 14, 2, 8, 7, 6, 15]], order=2^4) In [9]: c = rs.encode(m); c Out[9]: GF([[ 0, 12, 5, 12, 9, 14, 5, 3, 0, 13, 2, 8, 4, 2, 4], [ 2, 8, 3, 11, 8, 15, 14, 11, 11, 3, 1, 11, 3, 10, 10], [ 5, 0, 15, 8, 15, 1, 12, 5, 13, 3, 1, 4, 12, 3, 14], [ 0, 6, 0, 14, 3, 5, 8, 3, 11, 7, 6, 15, 11, 13, 10], [ 9, 11, 0, 14, 2, 8, 7, 6, 15, 14, 5, 15, 11, 13, 1]], order=2^4) In [10]: p = rs.encode(m, parity_only=True); p Out[10]: GF([[13, 2, 8, 4, 2, 4], [ 3, 1, 11, 3, 10, 10], [ 3, 1, 4, 12, 3, 14], [ 7, 6, 15, 11, 13, 10], [14, 5, 15, 11, 13, 1]], order=2^4)
- property G¶
The generator matrix \(\mathbf{G}\) with shape \((k, n)\).
Examples
In [1]: rs = galois.ReedSolomon(15, 9); rs Out[1]: <Reed-Solomon Code: [15, 9, 7] over GF(2^4)> In [2]: rs.G Out[2]: GF([[ 1, 0, 0, 0, 0, 0, 0, 0, 0, 10, 3, 5, 13, 1, 8], [ 0, 1, 0, 0, 0, 0, 0, 0, 0, 15, 1, 13, 7, 5, 13], [ 0, 0, 1, 0, 0, 0, 0, 0, 0, 11, 11, 13, 3, 10, 7], [ 0, 0, 0, 1, 0, 0, 0, 0, 0, 3, 2, 3, 8, 4, 7], [ 0, 0, 0, 0, 1, 0, 0, 0, 0, 3, 10, 10, 6, 15, 9], [ 0, 0, 0, 0, 0, 1, 0, 0, 0, 5, 11, 1, 5, 15, 11], [ 0, 0, 0, 0, 0, 0, 1, 0, 0, 2, 11, 10, 7, 14, 8], [ 0, 0, 0, 0, 0, 0, 0, 1, 0, 15, 9, 5, 8, 15, 2], [ 0, 0, 0, 0, 0, 0, 0, 0, 1, 7, 9, 3, 12, 10, 12]], order=2^4)
- Type
- property H¶
The parity-check matrix \(\mathbf{H}\) with shape \((2t, n)\).
Examples
In [1]: rs = galois.ReedSolomon(15, 9); rs Out[1]: <Reed-Solomon Code: [15, 9, 7] over GF(2^4)> In [2]: rs.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], [ 7, 6, 1, 7, 6, 1, 7, 6, 1, 7, 6, 1, 7, 6, 1], [10, 8, 15, 12, 1, 10, 8, 15, 12, 1, 10, 8, 15, 12, 1]], order=2^4)
- Type
- property c¶
The degree of the first consecutive root.
Examples
In [1]: rs = galois.ReedSolomon(15, 9); rs Out[1]: <Reed-Solomon Code: [15, 9, 7] over GF(2^4)> In [2]: rs.c Out[2]: 1
- Type
- property d¶
The design distance \(d\) of the \([n, k, d]_q\) code. The minimum distance of a Reed-Solomon code is exactly equal to the design distance, \(d_{min} = d\).
Examples
In [1]: rs = galois.ReedSolomon(15, 9); rs Out[1]: <Reed-Solomon Code: [15, 9, 7] over GF(2^4)> In [2]: rs.d Out[2]: 7
- Type
- property field¶
The Galois field \(\mathrm{GF}(q)\) that defines the Reed-Solomon code.
Examples
In [1]: rs = galois.ReedSolomon(15, 9); rs Out[1]: <Reed-Solomon Code: [15, 9, 7] over GF(2^4)> In [2]: rs.field Out[2]: <class 'numpy.ndarray over GF(2^4)'> In [3]: print(rs.field.properties) GF(2^4): characteristic: 2 degree: 4 order: 16 irreducible_poly: x^4 + x + 1 is_primitive_poly: True primitive_element: x
- Type
- property generator_poly¶
The generator polynomial \(g(x)\) whose roots are
roots
.Examples
In [1]: rs = galois.ReedSolomon(15, 9); rs Out[1]: <Reed-Solomon Code: [15, 9, 7] over GF(2^4)> In [2]: rs.generator_poly Out[2]: Poly(x^6 + 7x^5 + 9x^4 + 3x^3 + 12x^2 + 10x + 12, GF(2^4)) # Evaluate the generator polynomial at its roots In [3]: rs.generator_poly(rs.roots) Out[3]: GF([0, 0, 0, 0, 0, 0], order=2^4)
- Type
- property is_narrow_sense¶
Indicates if the Reed-Solomon 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}\).
Examples
In [1]: rs = galois.ReedSolomon(15, 9); rs Out[1]: <Reed-Solomon Code: [15, 9, 7] over GF(2^4)> In [2]: rs.is_narrow_sense Out[2]: True In [3]: rs.roots Out[3]: GF([ 2, 4, 8, 3, 6, 12], order=2^4) In [4]: rs.field.primitive_element**(np.arange(1, 2*rs.t + 1)) Out[4]: GF([ 2, 4, 8, 3, 6, 12], order=2^4)
- Type
- property k¶
The message size \(k\) of the \([n, k, d]_q\) code.
Examples
In [1]: rs = galois.ReedSolomon(15, 9); rs Out[1]: <Reed-Solomon Code: [15, 9, 7] over GF(2^4)> In [2]: rs.k Out[2]: 9
- Type
- property n¶
The codeword size \(n\) of the \([n, k, d]_q\) code.
Examples
In [1]: rs = galois.ReedSolomon(15, 9); rs Out[1]: <Reed-Solomon Code: [15, 9, 7] over GF(2^4)> In [2]: rs.n Out[2]: 15
- Type
- property roots¶
The \(2t\) roots of the generator polynomial. These are consecutive powers of \(\alpha\), specifically \(\alpha^c, \alpha^{c+1}, \dots, \alpha^{c+2t-1}\).
Examples
In [1]: rs = galois.ReedSolomon(15, 9); rs Out[1]: <Reed-Solomon Code: [15, 9, 7] over GF(2^4)> In [2]: rs.roots Out[2]: GF([ 2, 4, 8, 3, 6, 12], order=2^4) # Evaluate the generator polynomial at its roots In [3]: rs.generator_poly(rs.roots) Out[3]: GF([0, 0, 0, 0, 0, 0], order=2^4)
- Type
- property systematic¶
Indicates if the code is configured to return codewords in systematic form.
Examples
In [1]: rs = galois.ReedSolomon(15, 9); rs Out[1]: <Reed-Solomon Code: [15, 9, 7] over GF(2^4)> In [2]: rs.systematic Out[2]: True
- Type