class galois.ReedSolomon

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$$.

Shortened codes

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.

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)$$.

$g(x) = (x - \alpha^c) \dots (x - \alpha^{c+d-2})$

Examples

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

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

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


Encode a message.

In : m = GF.Random(rs.k); m
Out: GF([ 9,  0, 11,  2, 11,  6,  9, 13,  2], order=2^4)

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


Corrupt the codeword and decode the message.

# Corrupt the first symbol in the codeword
In : c ^= 13; c
Out: GF([ 4,  0, 11,  2, 11,  6,  9, 13,  2,  1, 10,  0,  3,  3, 11], order=2^4)

In : dec_m = rs.decode(c); dec_m
Out: GF([ 9,  0, 11,  2, 11,  6,  9, 13,  2], order=2^4)

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


Instruct the decoder to return the number of corrected symbol errors.

In : dec_m, N = rs.decode(c, errors=True); dec_m, N
Out: (GF([ 9,  0, 11,  2, 11,  6,  9, 13,  2], order=2^4), 1)

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


## Constructors¶

ReedSolomon(n: int, k: = None, d: = 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(...)
decode(...) tuple[FieldArray, int | np.ndarray]

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

detect(codeword: ArrayLike)

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

encode(...)

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

## Properties¶

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 :

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

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

The error-correcting capability $$t$$ of the code.

## Attributes¶

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.

## Matrices¶

property G : FieldArray

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

property H : FieldArray

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

## Polynomials¶

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 generator_poly : Poly

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

property parity_check_poly : Poly

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

property roots : FieldArray

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