A general \(\textrm{RS}(n, k)\) code over \(\mathrm{GF}(q)\).

A \(\textrm{RS}(n, k)\) code is a \([n, k, n - k + 1]_q\) linear block code with codeword size \(n\), message size \(k\), minimum distance \(d = n - k + 1\), and symbols taken from an alphabet of size \(q\).

A Reed-Solomon code is a cyclic code over \(\mathrm{GF}(q)\) with generator polynomial \(g(x)\). The generator polynomial has \(d-1\) roots \(\alpha^c, \dots, \alpha^{c+d-2}\). The element \(\alpha\) is a primitive \(n\)-th root of unity in \(\mathrm{GF}(q)\).

Examples¶

Construct a \(\textrm{RS}(15, 9)\) code.

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

In [2]: GF = rs.field; GF
Out[2]: <class 'galois.GF(2^4)'>

Encode a message.

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

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

Corrupt the codeword and decode the message.

# Corrupt the first symbol in the codeword
In [5]: c[0] ^= 13; c
Out[5]: GF([ 4, 15, 12,  9, 14,  6,  0,  8,  3, 14, 14, 12,  3,  1,  7], order=2^4)

In [6]: dec_m = rs.decode(c); dec_m
Out[6]: GF([ 9, 15, 12,  9, 14,  6,  0,  8,  3], 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([ 9, 15, 12,  9, 14,  6,  0,  8,  3], order=2^4), 1)

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

Constructors¶

ReedSolomon(n: int, k: int | None = None, d: int | None = None, ...)

Constructs a general \(\textrm{RS}(n, k)\) code over \(\mathrm{GF}(q)\).

String representation¶

__repr__() → str

A terse representation of the Reed-Solomon code.

__str__() → str

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

Methods¶

decode(codeword: ArrayLike, ...) → FieldArray

decode(codeword, ...) → tuple[FieldArray, int | np.ndarray]

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

detect(codeword: ArrayLike) → bool | ndarray

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

encode(message: ArrayLike, ...) → FieldArray

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

Properties¶

property alpha : FieldArray

A primitive \(n\)-th root of unity \(\alpha\) in \(\mathrm{GF}(q)\) whose consecutive powers \(\alpha^c, \dots, \alpha^{c+d-2}\) are roots of the generator polynomial \(g(x)\).

property c : int

The first consecutive power \(c\) of \(\alpha\) that defines the roots \(\alpha^c, \dots, \alpha^{c+d-2}\) of the generator polynomial \(g(x)\).

property d : int

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

property field : type[FieldArray]

The Galois field \(\mathrm{GF}(q)\) that defines the codeword alphabet.

property G : FieldArray

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

property generator_poly : Poly

The generator polynomial \(g(x)\) over \(\mathrm{GF}(q)\).

property H : FieldArray

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

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, that is \(\alpha, \dots, \alpha^{d-1}\).

property is_primitive : bool

Indicates if the Reed-Solomon code is primitive, meaning \(n = q - 1\).

property is_systematic : bool

Indicates if the code is systematic, meaning the codewords have parity appended to the message.

property k : int

The message size \(k\) of the \([n, k, d]_q\) code. This is also called the code dimension.

property n : int

The codeword size \(n\) of the \([n, k, d]_q\) code. This is also called the code length.

property parity_check_poly : Poly

The parity-check polynomial \(h(x)\).

property roots : FieldArray

The \(d - 1\) roots of the generator polynomial \(g(x)\).

property t : int

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