galois.ReedSolomon

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

A general \(\textrm{RS}(n, k)\) code.

A \(\textrm{RS}(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\) (a prime power).

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 into decode(). Shortened codes are only applicable for systematic codes.

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([13, 11, 15,  4, 14,  3, 14,  1,  4], order=2^4)

In [4]: c = rs.encode(m); c
Out[4]: GF([13, 11, 15,  4, 14,  3, 14,  1,  4,  6, 15, 11,  2, 14,  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([13, 11, 15,  4, 14,  3, 14,  1,  4], 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([13, 11, 15,  4, 14,  3, 14,  1,  4], order=2^4), 1)

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

Constructors

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

Constructs a general \(\textrm{RS}(n, k)\) code.

Special Methods

__repr__()

A terse representation of the Reed-Solomon code.

__str__()

A formatted string with relevant properties of the Reed-Solomon code.

Methods

decode()

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

G

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

H

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

c

The degree of the first consecutive root.

d

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

field

The FieldArray subclass for the \(\mathrm{GF}(q)\) field that defines the Reed-Solomon code.

generator_poly

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

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}\).

k

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

n

The codeword size \(n\) of the \([n, k, d]_q\) 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, c: int = 1, primitive_poly: PolyLike | None = None, primitive_element: PolyLike | None = None, systematic: bool = True)

Constructs a general \(\textrm{RS}(n, k)\) code.

Parameters
n

The codeword size \(n\), must be \(n = q - 1\) where \(q\) is a prime power.

k

The message size \(k\). The error-correcting capability \(t\) is defined by \(n - k = 2t\).

c

The first consecutive power of \(\alpha\). The default is 1.

primitive_poly

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

primitive_element

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)\), 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 Reed-Solomon code.

Examples

In [1]: rs = galois.ReedSolomon(15, 9)

In [2]: rs
Out[2]: <Reed-Solomon Code: [15, 9, 7] over GF(2^4)>
__str__() str

A formatted string with relevant properties of the Reed-Solomon code.

Examples

In [1]: rs = galois.ReedSolomon(15, 9)

In [2]: print(rs)
Reed-Solomon Code:
  [n, k, d]: [15, 9, 7]
  field: GF(2^4)
  generator_poly: x^6 + 7x^5 + 9x^4 + 3x^3 + 12x^2 + 10x + 12
  is_narrow_sense: True
  systematic: True
  t: 3
decode(codeword: Union[ndarray, FieldArray], errors: Literal[False] = False) Union[ndarray, FieldArray]
decode(codeword: Union[ndarray, FieldArray], errors: Literal[True]) Tuple[Union[ndarray, FieldArray], Union[integer, ndarray]]

Decodes the Reed-Solomon 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 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 \(\mathbf{s}\) is computed by \(\mathbf{s} = \mathbf{c}\mathbf{H}^T\), where \(\mathbf{H}\) is the parity-check matrix. The equivalent polynomial operation is the codeword polynomial evaluated at each root of the generator polynomial, i.e. \(\mathbf{s} = [c(\alpha^{c}), c(\alpha^{c+1}), \dots, c(\alpha^{c+2t-1})]\). 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

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

In [1]: rs = galois.ReedSolomon(15, 9)

In [2]: GF = rs.field

In [3]: m = GF.Random(rs.k); m
Out[3]: GF([ 5,  7,  8, 14,  5,  7,  6,  1,  6], order=2^4)

In [4]: c = rs.encode(m); c
Out[4]: GF([ 5,  7,  8, 14,  5,  7,  6,  1,  6, 12,  5,  1, 10,  6, 12], order=2^4)

Corrupt \(t\) symbols of the codeword.

In [5]: e = GF.Random(rs.t, low=1); e
Out[5]: GF([12, 15,  4], order=2^4)

In [6]: c[0:rs.t] += e; c
Out[6]: GF([ 9,  8, 12, 14,  5,  7,  6,  1,  6, 12,  5,  1, 10,  6, 12], order=2^4)

Decode the codeword and recover the message.

In [7]: d = rs.decode(c); d
Out[7]: GF([ 5,  7,  8, 14,  5,  7,  6,  1,  6], order=2^4)

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 = rs.decode(c, errors=True); d, e
Out[9]: (GF([ 5,  7,  8, 14,  5,  7,  6,  1,  6], order=2^4), 3)

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

Encode a single message using the shortened \(\textrm{RS}(11, 5)\) code.

In [11]: rs = galois.ReedSolomon(15, 9)

In [12]: GF = rs.field

In [13]: m = GF.Random(rs.k - 4); m
Out[13]: GF([ 0, 14, 15,  6, 10], order=2^4)

In [14]: c = rs.encode(m); c
Out[14]: GF([ 0, 14, 15,  6, 10,  9, 13,  2, 12, 12,  4], order=2^4)

Corrupt \(t\) symbols of the codeword.

In [15]: e = GF.Random(rs.t, low=1); e
Out[15]: GF([ 5, 10,  1], order=2^4)

In [16]: c[0:rs.t] += e; c
Out[16]: GF([ 5,  4, 14,  6, 10,  9, 13,  2, 12, 12,  4], order=2^4)

Decode the codeword and recover the message.

In [17]: d = rs.decode(c); d
Out[17]: GF([ 0, 14, 15,  6, 10], order=2^4)

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 = rs.decode(c, errors=True); d, e
Out[19]: (GF([ 0, 14, 15,  6, 10], order=2^4), 3)

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

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

In [21]: rs = galois.ReedSolomon(15, 9)

In [22]: GF = rs.field

In [23]: m = GF.Random((3, rs.k)); m
Out[23]: 
GF([[12,  7,  3,  2,  7,  8, 11, 10, 12],
    [ 5,  4,  6, 14,  8,  4, 13,  4, 14],
    [12,  4, 12, 14, 15, 14, 15, 14, 12]], order=2^4)

In [24]: c = rs.encode(m); c
Out[24]: 
GF([[12,  7,  3,  2,  7,  8, 11, 10, 12, 14,  4,  4,  8, 14, 10],
    [ 5,  4,  6, 14,  8,  4, 13,  4, 14,  3, 13, 12,  5, 11,  2],
    [12,  4, 12, 14, 15, 14, 15, 14, 12, 15,  7,  0,  8,  9,  2]],
   order=2^4)

Corrupt the codeword. Add one error to the first codeword, two to the second, and three to the third.

In [25]: c[0,0:1] += GF.Random(1, low=1)

In [26]: c[1,0:2] += GF.Random(2, low=1)

In [27]: c[2,0:3] += GF.Random(3, low=1)

In [28]: c
Out[28]: 
GF([[ 1,  7,  3,  2,  7,  8, 11, 10, 12, 14,  4,  4,  8, 14, 10],
    [ 9, 12,  6, 14,  8,  4, 13,  4, 14,  3, 13, 12,  5, 11,  2],
    [14, 14,  4, 14, 15, 14, 15, 14, 12, 15,  7,  0,  8,  9,  2]],
   order=2^4)

Decode the codeword and recover the message.

In [29]: d = rs.decode(c); d
Out[29]: 
GF([[12,  7,  3,  2,  7,  8, 11, 10, 12],
    [ 5,  4,  6, 14,  8,  4, 13,  4, 14],
    [12,  4, 12, 14, 15, 14, 15, 14, 12]], order=2^4)

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

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

In [31]: d, e = rs.decode(c, errors=True); d, e
Out[31]: 
(GF([[12,  7,  3,  2,  7,  8, 11, 10, 12],
     [ 5,  4,  6, 14,  8,  4, 13,  4, 14],
     [12,  4, 12, 14, 15, 14, 15, 14, 12]], order=2^4),
 array([1, 2, 3]))

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

Encode a matrix of three messages using the shortened \(\textrm{RS}(11, 5)\) code.

In [33]: rs = galois.ReedSolomon(15, 9)

In [34]: GF = rs.field

In [35]: m = GF.Random((3, rs.k - 4)); m
Out[35]: 
GF([[ 7, 11,  4,  1, 14],
    [ 0,  0,  2, 13,  2],
    [ 5, 12,  5, 15,  8]], order=2^4)

In [36]: c = rs.encode(m); c
Out[36]: 
GF([[ 7, 11,  4,  1, 14,  3, 14,  2,  3, 12,  3],
    [ 0,  0,  2, 13,  2, 13, 11, 13,  7, 15,  1],
    [ 5, 12,  5, 15,  8, 11,  2,  1,  7,  8, 15]], order=2^4)

Corrupt the codeword. Add one error to the first codeword, two to the second, and three to the third.

In [37]: c[0,0:1] += GF.Random(1, low=1)

In [38]: c[1,0:2] += GF.Random(2, low=1)

In [39]: c[2,0:3] += GF.Random(3, low=1)

In [40]: c
Out[40]: 
GF([[13, 11,  4,  1, 14,  3, 14,  2,  3, 12,  3],
    [ 7, 11,  2, 13,  2, 13, 11, 13,  7, 15,  1],
    [10,  1, 12, 15,  8, 11,  2,  1,  7,  8, 15]], order=2^4)

Decode the codeword and recover the message.

In [41]: d = rs.decode(c); d
Out[41]: 
GF([[ 7, 11,  4,  1, 14],
    [ 0,  0,  2, 13,  2],
    [ 5, 12,  5, 15,  8]], order=2^4)

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

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

In [43]: d, e = rs.decode(c, errors=True); d, e
Out[43]: 
(GF([[ 7, 11,  4,  1, 14],
     [ 0,  0,  2, 13,  2],
     [ 5, 12,  5, 15,  8]], order=2^4),
 array([1, 2, 3]))

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

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

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{RS}(15, 9)\) code.

In [1]: rs = galois.ReedSolomon(15, 9)

In [2]: GF = rs.field

In [3]: m = GF.Random(rs.k); m
Out[3]: GF([ 9,  1,  0, 10,  1,  7,  7, 10,  2], order=2^4)

In [4]: c = rs.encode(m); c
Out[4]: GF([ 9,  1,  0, 10,  1,  7,  7, 10,  2,  0,  0,  7, 11,  1,  6], order=2^4)

Detect no errors in the valid codeword.

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

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

In [6]: rs.d
Out[6]: 7

In [7]: e = GF.Random(rs.d - 1, low=1); e
Out[7]: GF([ 6, 12,  7,  6, 11, 12], order=2^4)

In [8]: c[0:rs.d - 1] += e; c
Out[8]: GF([15, 13,  7, 12, 10, 11,  7, 10,  2,  0,  0,  7, 11,  1,  6], order=2^4)

In [9]: rs.detect(c)
Out[9]: True

Encode a single message using the shortened \(\textrm{RS}(11, 5)\) code.

In [10]: rs = galois.ReedSolomon(15, 9)

In [11]: GF = rs.field

In [12]: m = GF.Random(rs.k - 4); m
Out[12]: GF([ 8,  3,  1,  5, 10], order=2^4)

In [13]: c = rs.encode(m); c
Out[13]: GF([ 8,  3,  1,  5, 10,  3,  4,  9,  2,  3,  9], order=2^4)

Detect no errors in the valid codeword.

In [14]: rs.detect(c)
Out[14]: False

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

In [15]: rs.d
Out[15]: 7

In [16]: e = GF.Random(rs.d - 1, low=1); e
Out[16]: GF([12, 13,  7,  3,  8, 10], order=2^4)

In [17]: c[0:rs.d - 1] += e; c
Out[17]: GF([ 4, 14,  6,  6,  2,  9,  4,  9,  2,  3,  9], order=2^4)

In [18]: rs.detect(c)
Out[18]: True

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

In [19]: rs = galois.ReedSolomon(15, 9)

In [20]: GF = rs.field

In [21]: m = GF.Random((3, rs.k)); m
Out[21]: 
GF([[12,  4,  5, 13, 11, 10,  4,  9,  1],
    [15,  9, 13, 12,  3,  5,  4,  5, 14],
    [ 3, 10,  3,  4, 12,  1, 13,  6, 13]], order=2^4)

In [22]: c = rs.encode(m); c
Out[22]: 
GF([[12,  4,  5, 13, 11, 10,  4,  9,  1,  6,  5, 14, 13,  8,  3],
    [15,  9, 13, 12,  3,  5,  4,  5, 14,  6, 12,  5, 14,  3,  8],
    [ 3, 10,  3,  4, 12,  1, 13,  6, 13,  9,  9, 14, 12, 11,  6]],
   order=2^4)

Detect no errors in the valid codewords.

In [23]: rs.detect(c)
Out[23]: array([False, False, False])

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

In [24]: rs.d
Out[24]: 7

In [25]: c[0,0:1] += GF.Random(1, low=1)

In [26]: c[1,0:2] += GF.Random(2, low=1)

In [27]: c[2, 0:rs.d - 1] += GF.Random(rs.d - 1, low=1)

In [28]: c
Out[28]: 
GF([[ 9,  4,  5, 13, 11, 10,  4,  9,  1,  6,  5, 14, 13,  8,  3],
    [14, 14, 13, 12,  3,  5,  4,  5, 14,  6, 12,  5, 14,  3,  8],
    [ 5,  7,  7, 15,  7,  0, 13,  6, 13,  9,  9, 14, 12, 11,  6]],
   order=2^4)

In [29]: rs.detect(c)
Out[29]: array([ True,  True,  True])

Encode a matrix of three messages using the shortened \(\textrm{RS}(11, 5)\) code.

In [30]: rs = galois.ReedSolomon(15, 9)

In [31]: GF = rs.field

In [32]: m = GF.Random((3, rs.k - 4)); m
Out[32]: 
GF([[ 9,  5, 12, 15, 15],
    [11, 11,  7,  7,  8],
    [ 3,  1, 15,  5, 10]], order=2^4)

In [33]: c = rs.encode(m); c
Out[33]: 
GF([[ 9,  5, 12, 15, 15,  0,  9,  5, 10, 10,  3],
    [11, 11,  7,  7,  8,  7,  1,  9, 15,  8, 12],
    [ 3,  1, 15,  5, 10,  8, 11, 15, 11,  6,  9]], order=2^4)

Detect no errors in the valid codewords.

In [34]: rs.detect(c)
Out[34]: array([False, False, False])

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

In [35]: rs.d
Out[35]: 7

In [36]: c[0,0:1] += GF.Random(1, low=1)

In [37]: c[1,0:2] += GF.Random(2, low=1)

In [38]: c[2, 0:rs.d - 1] += GF.Random(rs.d - 1, low=1)

In [39]: c
Out[39]: 
GF([[ 1,  5, 12, 15, 15,  0,  9,  5, 10, 10,  3],
    [ 4, 14,  7,  7,  8,  7,  1,  9, 15,  8, 12],
    [11, 15, 11, 15, 12,  1, 11, 15, 11,  6,  9]], order=2^4)

In [40]: rs.detect(c)
Out[40]: array([ True,  True,  True])
encode(message: ndarray | FieldArray, parity_only: bool = False) ndarray | FieldArray

Encodes the message \(\mathbf{m}\) into the Reed-Solomon 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 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.

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 message using the \(\textrm{RS}(15, 9)\) code.

In [1]: rs = galois.ReedSolomon(15, 9)

In [2]: GF = rs.field

In [3]: m = GF.Random(rs.k); m
Out[3]: GF([2, 0, 7, 2, 5, 3, 1, 4, 8], order=2^4)

In [4]: c = rs.encode(m); c
Out[4]: GF([ 2,  0,  7,  2,  5,  3,  1,  4,  8,  3,  1,  8, 10,  5,  4], order=2^4)

Compute the parity symbols only.

In [5]: p = rs.encode(m, parity_only=True); p
Out[5]: GF([ 3,  1,  8, 10,  5,  4], order=2^4)

Encode a single message using the shortened \(\textrm{RS}(11, 5)\) code.

In [6]: rs = galois.ReedSolomon(15, 9)

In [7]: GF = rs.field

In [8]: m = GF.Random(rs.k - 4); m
Out[8]: GF([4, 6, 2, 7, 6], order=2^4)

In [9]: c = rs.encode(m); c
Out[9]: GF([ 4,  6,  2,  7,  6, 15, 13, 13, 11,  0, 14], order=2^4)

Compute the parity symbols only.

In [10]: p = rs.encode(m, parity_only=True); p
Out[10]: GF([15, 13, 13, 11,  0, 14], order=2^4)

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

In [11]: rs = galois.ReedSolomon(15, 9)

In [12]: GF = rs.field

In [13]: m = GF.Random((3, rs.k)); m
Out[13]: 
GF([[11,  8, 12,  4,  3, 13, 14,  9,  3],
    [ 6, 14,  4,  2,  9,  8,  4,  3,  8],
    [ 2,  2,  6, 10,  6, 15,  9,  7,  4]], order=2^4)

In [14]: c = rs.encode(m); c
Out[14]: 
GF([[11,  8, 12,  4,  3, 13, 14,  9,  3,  3,  5,  4,  3, 10,  9],
    [ 6, 14,  4,  2,  9,  8,  4,  3,  8,  1, 14,  7,  8, 12, 14],
    [ 2,  2,  6, 10,  6, 15,  9,  7,  4,  1,  2,  1,  1,  3,  7]],
   order=2^4)

Compute the parity symbols only.

In [15]: p = rs.encode(m, parity_only=True); p
Out[15]: 
GF([[ 3,  5,  4,  3, 10,  9],
    [ 1, 14,  7,  8, 12, 14],
    [ 1,  2,  1,  1,  3,  7]], order=2^4)

Encode a matrix of three messages using the shortened \(\textrm{RS}(11, 5)\) code.

In [16]: rs = galois.ReedSolomon(15, 9)

In [17]: GF = rs.field

In [18]: m = GF.Random((3, rs.k - 4)); m
Out[18]: 
GF([[ 8, 14,  7, 12,  6],
    [ 7,  1,  3,  6,  9],
    [ 4,  8,  4,  1,  6]], order=2^4)

In [19]: c = rs.encode(m); c
Out[19]: 
GF([[ 8, 14,  7, 12,  6, 15,  6,  1,  4,  9,  4],
    [ 7,  1,  3,  6,  9,  4,  8, 10, 14,  4,  0],
    [ 4,  8,  4,  1,  6,  4,  9,  7, 12,  3, 15]], order=2^4)

Compute the parity symbols only.

In [20]: p = rs.encode(m, parity_only=True); p
Out[20]: 
GF([[15,  6,  1,  4,  9,  4],
    [ 4,  8, 10, 14,  4,  0],
    [ 4,  9,  7, 12,  3, 15]], order=2^4)
property G : FieldArray

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)
property H : FieldArray

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)
property c : int

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
property d : int

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
property field : Type[FieldArray]

The FieldArray subclass for the \(\mathrm{GF}(q)\) field 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]: galois.GF(2^4)

In [3]: print(rs.field)
<class 'galois.GF(2^4)'>
property generator_poly : 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)
property is_narrow_sense : bool

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)
property k : int

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
property n : int

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
property roots : FieldArray

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)
property systematic : bool

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
property t : int

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

Examples

In [1]: rs = galois.ReedSolomon(15, 9); rs
Out[1]: <Reed-Solomon Code: [15, 9, 7] over GF(2^4)>

In [2]: rs.t
Out[2]: 3

Last update: May 18, 2022