Reed-Solomon codes and Generalized Reed-Solomon codes#

Given \(n\) different evaluation points \(\alpha_1, \dots, \alpha_n\) from some finite field \(F\), the corresponding Reed-Solomon code (RS code) of dimension \(k\) is the set:

\[\{ (f(\alpha_1), \ldots, f(\alpha_n)) \mid f \in F[x], \deg f < k \}\]

An RS code is often called “classical” if \(\alpha_i = \alpha^{i-1}\) and \(\alpha\) is a primitive \(n\)’th root of unity.

More generally, given also \(n\) “column multipliers” \(\beta_1, \dots, \beta_n\), the corresponding Generalized Reed-Solomon code (GRS code) of dimension \(k\) is the set:

\[\{ (\beta_1 f(\alpha_1), \ldots, \beta_n f(\alpha_n)) \mid f \in F[x], \deg f < k \}\]

Here is a list of all content related to GRS codes:

class sage.coding.grs_code.GRSBerlekampWelchDecoder(code)#

Bases: Decoder

Decoder for (Generalized) Reed-Solomon codes which uses Berlekamp-Welch decoding algorithm to correct errors in codewords.

This algorithm recovers the error locator polynomial by solving a linear system. See [HJ2004] pp. 51-52 for details.

INPUT:

  • code – a code associated to this decoder

EXAMPLES:

sage: F = GF(59)
sage: n, k = 40, 12
sage: C = codes.GeneralizedReedSolomonCode(F.list()[:n], k)
sage: D = codes.decoders.GRSBerlekampWelchDecoder(C)
sage: D
Berlekamp-Welch decoder for [40, 12, 29] Reed-Solomon Code over GF(59)

Actually, we can construct the decoder from C directly:

sage: D = C.decoder("BerlekampWelch")
sage: D
Berlekamp-Welch decoder for [40, 12, 29] Reed-Solomon Code over GF(59)
decode_to_code(r)#

Correct the errors in r and returns a codeword.

Note

If the code associated to self has the same length as its dimension, r will be returned as is.

INPUT:

  • r – a vector of the ambient space of self.code()

OUTPUT:

  • a vector of self.code()

EXAMPLES:

sage: F = GF(59)
sage: n, k = 40, 12
sage: C = codes.GeneralizedReedSolomonCode(F.list()[:n], k)
sage: D = codes.decoders.GRSBerlekampWelchDecoder(C)
sage: c = C.random_element()
sage: Chan = channels.StaticErrorRateChannel(C.ambient_space(),
....:                                        D.decoding_radius())
sage: y = Chan(c)
sage: c == D.decode_to_code(y)
True
decode_to_message(r)#

Decode r to an element in message space of self.

Note

If the code associated to self has the same length as its dimension, r will be unencoded as is. In that case, if r is not a codeword, the output is unspecified.

INPUT:

  • r – a codeword of self

OUTPUT:

  • a vector of self message space

EXAMPLES:

sage: F = GF(59)
sage: n, k = 40, 12
sage: C = codes.GeneralizedReedSolomonCode(F.list()[:n], k)
sage: D = codes.decoders.GRSBerlekampWelchDecoder(C)
sage: c = C.random_element()
sage: Chan = channels.StaticErrorRateChannel(C.ambient_space(),
....:                                        D.decoding_radius())
sage: y = Chan(c)
sage: D.connected_encoder().unencode(c) == D.decode_to_message(y)
True
decoding_radius()#

Return maximal number of errors that self can decode.

OUTPUT:

  • the number of errors as an integer

EXAMPLES:

sage: F = GF(59)
sage: n, k = 40, 12
sage: C = codes.GeneralizedReedSolomonCode(F.list()[:n], k)
sage: D = codes.decoders.GRSBerlekampWelchDecoder(C)
sage: D.decoding_radius()
14
class sage.coding.grs_code.GRSErrorErasureDecoder(code)#

Bases: Decoder

Decoder for (Generalized) Reed-Solomon codes which is able to correct both errors and erasures in codewords.

Let \(C\) be a GRS code of length \(n\) and dimension \(k\). Considering \(y\) a codeword with at most \(t\) errors (\(t\) being the \(\left\lfloor \frac{d-1}{2} \right\rfloor\) decoding radius), and \(e\) the erasure vector, this decoder works as follows:

  • Puncture the erased coordinates which are identified in \(e\).

  • Create a new GRS code of length \(n - w(e)\), where \(w\) is the Hamming weight function, and dimension \(k\).

  • Use Gao decoder over this new code one the punctured word built on the first step.

  • Recover the original message from the decoded word computed on the previous step.

  • Encode this message using an encoder over \(C\).

INPUT:

  • code – the associated code of this decoder

EXAMPLES:

sage: F = GF(59)
sage: n, k = 40, 12
sage: C = codes.GeneralizedReedSolomonCode(F.list()[:n], k)
sage: D = codes.decoders.GRSErrorErasureDecoder(C)
sage: D
Error-Erasure decoder for [40, 12, 29] Reed-Solomon Code over GF(59)

Actually, we can construct the decoder from C directly:

sage: D = C.decoder("ErrorErasure")
sage: D
Error-Erasure decoder for [40, 12, 29] Reed-Solomon Code over GF(59)
decode_to_message(word_and_erasure_vector)#

Decode word_and_erasure_vector to an element in message space of self

INPUT:

  • word_and_erasure_vector – a tuple whose:

    • first element is an element of the ambient space of the code

    • second element is a vector over \(\GF{2}\) whose length is the same as the code’s, containing erasure positions

Note

If the code associated to self has the same length as its dimension, r will be unencoded as is. If the number of erasures is exactly \(n - k\), where \(n\) is the length of the code associated to self and \(k\) its dimension, r will be returned as is. In either case, if r is not a codeword, the output is unspecified.

OUTPUT:

  • a vector of self message space

EXAMPLES:

sage: F = GF(59)
sage: n, k = 40, 12
sage: C = codes.GeneralizedReedSolomonCode(F.list()[:n], k)
sage: D = codes.decoders.GRSErrorErasureDecoder(C)
sage: c = C.random_element()
sage: n_era = randint(0, C.minimum_distance() - 2)
sage: Chan = channels.ErrorErasureChannel(C.ambient_space(),
....:                                     D.decoding_radius(n_era), n_era)
sage: y = Chan(c)
sage: D.connected_encoder().unencode(c) == D.decode_to_message(y)
True
decoding_radius(number_erasures)#

Return maximal number of errors that self can decode according to how many erasures it receives.

INPUT:

  • number_erasures – the number of erasures when we try to decode

OUTPUT:

  • the number of errors as an integer

EXAMPLES:

sage: F = GF(59)
sage: n, k = 40, 12
sage: C = codes.GeneralizedReedSolomonCode(F.list()[:n], k)
sage: D = codes.decoders.GRSErrorErasureDecoder(C)
sage: D.decoding_radius(5)
11

If we receive too many erasures, it returns an exception as codeword will be impossible to decode:

sage: D.decoding_radius(30)
Traceback (most recent call last):
...
ValueError: The number of erasures exceed decoding capability
class sage.coding.grs_code.GRSEvaluationPolynomialEncoder(code, polynomial_ring=None)#

Bases: Encoder

Encoder for (Generalized) Reed-Solomon codes which uses evaluation of polynomials to obtain codewords.

Let \(C\) be a GRS code of length \(n\) and dimension \(k\) over some finite field \(F\). We denote by \(\alpha_i\) its evaluations points and by \(\beta_i\) its column multipliers, where \(1 \leq i \leq n\). Let \(p\) be a polynomial of degree at most \(k-1\) in \(F[x]\) be the message.

The encoding of \(m\) will be the following codeword:

\[(\beta_1 p(\alpha_1), \dots, \beta_n p(\alpha_n)).\]

INPUT:

  • code – the associated code of this encoder

  • polynomial_ring – (default: None) a polynomial ring to specify the message space of self, if needed; it is set to \(F[x]\) (where \(F\) is the base field of code) if default value is kept

EXAMPLES:

sage: F = GF(59)
sage: n, k = 40, 12
sage: C = codes.GeneralizedReedSolomonCode(F.list()[:n], k)
sage: E = codes.encoders.GRSEvaluationPolynomialEncoder(C)
sage: E
Evaluation polynomial-style encoder for [40, 12, 29] Reed-Solomon Code over GF(59)
sage: E.message_space()
Univariate Polynomial Ring in x over Finite Field of size 59

Actually, we can construct the encoder from C directly:

sage: E = C.encoder("EvaluationPolynomial")
sage: E
Evaluation polynomial-style encoder for [40, 12, 29] Reed-Solomon Code over GF(59)

We can also specify another polynomial ring:

sage: R = PolynomialRing(F, 'y')
sage: E = C.encoder("EvaluationPolynomial", polynomial_ring=R)
sage: E.message_space()
Univariate Polynomial Ring in y over Finite Field of size 59
encode(p)#

Transform the polynomial p into a codeword of code().

One can use the following shortcut to encode a word with an encoder E:

E(word)

INPUT:

  • p – a polynomial from the message space of self of degree less than self.code().dimension()

OUTPUT:

  • a codeword in associated code of self

EXAMPLES:

sage: F = GF(11)
sage: Fx.<x> = F[]
sage: n, k = 10 , 5
sage: C = codes.GeneralizedReedSolomonCode(F.list()[:n], k)
sage: E = C.encoder("EvaluationPolynomial")
sage: p = x^2 + 3*x + 10
sage: c = E.encode(p); c
(10, 3, 9, 6, 5, 6, 9, 3, 10, 8)
sage: c in C
True

If a polynomial of too high degree is given, an error is raised:

sage: p = x^10
sage: E.encode(p)
Traceback (most recent call last):
...
ValueError: The polynomial to encode must have degree at most 4

If p is not an element of the proper polynomial ring, an error is raised:

sage: Qy.<y> = QQ[]
sage: p = y^2 + 1
sage: E.encode(p)
Traceback (most recent call last):
...
ValueError: The value to encode must be in
Univariate Polynomial Ring in x over Finite Field of size 11
message_space()#

Return the message space of self

EXAMPLES:

sage: F = GF(11)
sage: n, k = 10 , 5
sage: C = codes.GeneralizedReedSolomonCode(F.list()[:n], k)
sage: E = C.encoder("EvaluationPolynomial")
sage: E.message_space()
Univariate Polynomial Ring in x over Finite Field of size 11
polynomial_ring()#

Return the message space of self

EXAMPLES:

sage: F = GF(11)
sage: n, k = 10 , 5
sage: C = codes.GeneralizedReedSolomonCode(F.list()[:n], k)
sage: E = C.encoder("EvaluationPolynomial")
sage: E.message_space()
Univariate Polynomial Ring in x over Finite Field of size 11
unencode_nocheck(c)#

Return the message corresponding to the codeword c.

Use this method with caution: it does not check if c belongs to the code, and if this is not the case, the output is unspecified. Instead, use unencode().

INPUT:

  • c – a codeword of code()

OUTPUT:

  • a polynomial of degree less than self.code().dimension()

EXAMPLES:

sage: F = GF(11)
sage: n, k = 10 , 5
sage: C = codes.GeneralizedReedSolomonCode(F.list()[:n], k)
sage: E = C.encoder("EvaluationPolynomial")
sage: c = vector(F, (10, 3, 9, 6, 5, 6, 9, 3, 10, 8))
sage: c in C
True
sage: p = E.unencode_nocheck(c); p
x^2 + 3*x + 10
sage: E.encode(p) == c
True

Note that no error is thrown if c is not a codeword, and that the result is undefined:

sage: c = vector(F, (11, 3, 9, 6, 5, 6, 9, 3, 10, 8))
sage: c in C
False
sage: p = E.unencode_nocheck(c); p
6*x^4 + 6*x^3 + 2*x^2
sage: E.encode(p) == c
False
class sage.coding.grs_code.GRSEvaluationVectorEncoder(code)#

Bases: Encoder

Encoder for (Generalized) Reed-Solomon codes that encodes vectors into codewords.

Let \(C\) be a GRS code of length \(n\) and dimension \(k\) over some finite field \(F\). We denote by \(\alpha_i\) its evaluations points and by \(\beta_i\) its column multipliers, where \(1 \leq i \leq n\). Let \(m = (m_1, \dots, m_k)\), a vector over \(F\), be the message. We build a polynomial using the coordinates of \(m\) as coefficients:

\[p = \Sigma_{i=1}^{m} m_i x^i.\]

The encoding of \(m\) will be the following codeword:

\[(\beta_1 p(\alpha_1), \dots, \beta_n p(\alpha_n)).\]

INPUT:

  • code – the associated code of this encoder

EXAMPLES:

sage: F = GF(59)
sage: n, k = 40, 12
sage: C = codes.GeneralizedReedSolomonCode(F.list()[:n], k)
sage: E = codes.encoders.GRSEvaluationVectorEncoder(C)
sage: E
Evaluation vector-style encoder for [40, 12, 29] Reed-Solomon Code over GF(59)

Actually, we can construct the encoder from C directly:

sage: E = C.encoder("EvaluationVector")
sage: E
Evaluation vector-style encoder for [40, 12, 29] Reed-Solomon Code over GF(59)
generator_matrix()#

Return a generator matrix of self

Considering a GRS code of length \(n\), dimension \(k\), with evaluation points \((\alpha_1, \dots, \alpha_n)\) and column multipliers \((\beta_1, \dots, \beta_n)\), its generator matrix \(G\) is built using the following formula:

\[G = [g_{i,j}], g_{i,j} = \beta_j \alpha_{j}^{i}.\]

This matrix is a Vandermonde matrix.

EXAMPLES:

sage: F = GF(11)
sage: n, k = 10, 5
sage: C = codes.GeneralizedReedSolomonCode(F.list()[:n], k)
sage: E = codes.encoders.GRSEvaluationVectorEncoder(C)
sage: E.generator_matrix()
[1 1 1 1 1 1 1 1 1 1]
[0 1 2 3 4 5 6 7 8 9]
[0 1 4 9 5 3 3 5 9 4]
[0 1 8 5 9 4 7 2 6 3]
[0 1 5 4 3 9 9 3 4 5]
class sage.coding.grs_code.GRSGaoDecoder(code)#

Bases: Decoder

Decoder for (Generalized) Reed-Solomon codes which uses Gao decoding algorithm to correct errors in codewords.

Gao decoding algorithm uses early terminated extended Euclidean algorithm to find the error locator polynomial. See [Ga02] for details.

INPUT:

  • code – the associated code of this decoder

EXAMPLES:

sage: F = GF(59)
sage: n, k = 40, 12
sage: C = codes.GeneralizedReedSolomonCode(F.list()[:n], k)
sage: D = codes.decoders.GRSGaoDecoder(C)
sage: D
Gao decoder for [40, 12, 29] Reed-Solomon Code over GF(59)

Actually, we can construct the decoder from C directly:

sage: D = C.decoder("Gao")
sage: D
Gao decoder for [40, 12, 29] Reed-Solomon Code over GF(59)
decode_to_code(r)#

Correct the errors in r and returns a codeword.

Note

If the code associated to self has the same length as its dimension, r will be returned as is.

INPUT:

  • r – a vector of the ambient space of self.code()

OUTPUT:

  • a vector of self.code()

EXAMPLES:

sage: F = GF(59)
sage: n, k = 40, 12
sage: C = codes.GeneralizedReedSolomonCode(F.list()[:n], k)
sage: D = codes.decoders.GRSGaoDecoder(C)
sage: c = C.random_element()
sage: Chan = channels.StaticErrorRateChannel(C.ambient_space(),
....:                                        D.decoding_radius())
sage: y = Chan(c)
sage: c == D.decode_to_code(y)
True
decode_to_message(r)#

Decode r to an element in message space of self.

Note

If the code associated to self has the same length as its dimension, r will be unencoded as is. In that case, if r is not a codeword, the output is unspecified.

INPUT:

  • r – a codeword of self

OUTPUT:

  • a vector of self message space

EXAMPLES:

sage: F = GF(59)
sage: n, k = 40, 12
sage: C = codes.GeneralizedReedSolomonCode(F.list()[:n], k)
sage: D = codes.decoders.GRSGaoDecoder(C)
sage: c = C.random_element()
sage: Chan = channels.StaticErrorRateChannel(C.ambient_space(),
....:                                        D.decoding_radius())
sage: y = Chan(c)
sage: D.connected_encoder().unencode(c) == D.decode_to_message(y)
True
decoding_radius()#

Return maximal number of errors that self can decode

OUTPUT:

  • the number of errors as an integer

EXAMPLES:

sage: F = GF(59)
sage: n, k = 40, 12
sage: C = codes.GeneralizedReedSolomonCode(F.list()[:n], k)
sage: D = codes.decoders.GRSGaoDecoder(C)
sage: D.decoding_radius()
14
class sage.coding.grs_code.GRSKeyEquationSyndromeDecoder(code)#

Bases: Decoder

Decoder for (Generalized) Reed-Solomon codes which uses a Key equation decoding based on the syndrome polynomial to correct errors in codewords.

This algorithm uses early terminated extended euclidean algorithm to solve the key equations, as described in [Rot2006], pp. 183-195.

INPUT:

  • code – The associated code of this decoder.

EXAMPLES:

sage: F = GF(59)
sage: n, k = 40, 12
sage: C = codes.GeneralizedReedSolomonCode(F.list()[1:n+1], k)
sage: D = codes.decoders.GRSKeyEquationSyndromeDecoder(C)
sage: D
Key equation decoder for [40, 12, 29] Reed-Solomon Code over GF(59)

Actually, we can construct the decoder from C directly:

sage: D = C.decoder("KeyEquationSyndrome")
sage: D
Key equation decoder for [40, 12, 29] Reed-Solomon Code over GF(59)
decode_to_code(r)#

Correct the errors in r and returns a codeword.

Note

If the code associated to self has the same length as its dimension, r will be returned as is.

INPUT:

  • r – a vector of the ambient space of self.code()

OUTPUT:

  • a vector of self.code()

EXAMPLES:

sage: F = GF(59)
sage: n, k = 40, 12
sage: C = codes.GeneralizedReedSolomonCode(F.list()[1:n+1], k)
sage: D = codes.decoders.GRSKeyEquationSyndromeDecoder(C)
sage: c = C.random_element()
sage: Chan = channels.StaticErrorRateChannel(C.ambient_space(),
....:                                        D.decoding_radius())
sage: y = Chan(c)
sage: c == D.decode_to_code(y)
True
decode_to_message(r)#

Decode r to an element in message space of self

Note

If the code associated to self has the same length as its dimension, r will be unencoded as is. In that case, if r is not a codeword, the output is unspecified.

INPUT:

  • r – a codeword of self

OUTPUT:

  • a vector of self message space

EXAMPLES:

sage: F = GF(59)
sage: n, k = 40, 12
sage: C = codes.GeneralizedReedSolomonCode(F.list()[1:n+1], k)
sage: D = codes.decoders.GRSKeyEquationSyndromeDecoder(C)
sage: c = C.random_element()
sage: Chan = channels.StaticErrorRateChannel(C.ambient_space(),
....:                                        D.decoding_radius())
sage: y = Chan(c)
sage: D.connected_encoder().unencode(c) == D.decode_to_message(y)
True
decoding_radius()#

Return maximal number of errors that self can decode

OUTPUT:

  • the number of errors as an integer

EXAMPLES:

sage: F = GF(59)
sage: n, k = 40, 12
sage: C = codes.GeneralizedReedSolomonCode(F.list()[1:n+1], k)
sage: D = codes.decoders.GRSKeyEquationSyndromeDecoder(C)
sage: D.decoding_radius()
14
class sage.coding.grs_code.GeneralizedReedSolomonCode(evaluation_points, dimension, column_multipliers=None)#

Bases: AbstractLinearCode

Representation of a (Generalized) Reed-Solomon code.

INPUT:

  • evaluation_points – a list of distinct elements of some finite field \(F\)

  • dimension – the dimension of the resulting code

  • column_multipliers – (default: None) list of non-zero elements of \(F\); all column multipliers are set to 1 if default value is kept

EXAMPLES:

Often, one constructs a Reed-Solomon code by taking all non-zero elements of the field as evaluation points, and specifying no column multipliers (see also ReedSolomonCode() for constructing classical Reed-Solomon codes directly):

sage: F = GF(7)
sage: evalpts = [F(i) for i in range(1,7)]
sage: C = codes.GeneralizedReedSolomonCode(evalpts, 3)
sage: C
[6, 3, 4] Reed-Solomon Code over GF(7)

More generally, the following is a Reed-Solomon code where the evaluation points are a subset of the field and includes zero:

sage: F = GF(59)
sage: n, k = 40, 12
sage: C = codes.GeneralizedReedSolomonCode(F.list()[:n], k)
sage: C
[40, 12, 29] Reed-Solomon Code over GF(59)

It is also possible to specify the column multipliers:

sage: F = GF(59)
sage: n, k = 40, 12
sage: colmults = F.list()[1:n+1]
sage: C = codes.GeneralizedReedSolomonCode(F.list()[:n], k, colmults)
sage: C
[40, 12, 29] Generalized Reed-Solomon Code over GF(59)

SageMath implements efficient decoding algorithms for GRS codes:

sage: F = GF(11)
sage: n, k = 10, 5
sage: C = codes.GeneralizedReedSolomonCode(F.list()[1:n+1], k)
sage: r = vector(F, (8, 2, 6, 10, 6, 10, 7, 6, 7, 2))
sage: C.decode_to_message(r)
(3, 6, 6, 3, 1)
column_multipliers()#

Return the vector of column multipliers of self.

EXAMPLES:

sage: F = GF(11)
sage: n, k = 10, 5
sage: C = codes.GeneralizedReedSolomonCode(F.list()[:n], k)
sage: C.column_multipliers()
(1, 1, 1, 1, 1, 1, 1, 1, 1, 1)
covering_radius()#

Return the covering radius of self.

The covering radius of a linear code \(C\) is the smallest number \(r\) s.t. any element of the ambient space of \(C\) is at most at distance \(r\) to \(C\).

As GRS codes are Maximum Distance Separable codes (MDS), their covering radius is always \(d-1\), where \(d\) is the minimum distance. This is opposed to random linear codes where the covering radius is computationally hard to determine.

EXAMPLES:

sage: F = GF(2^8, 'a')
sage: n, k = 256, 100
sage: C = codes.GeneralizedReedSolomonCode(F.list()[:n], k)
sage: C.covering_radius()
156
dual_code()#

Return the dual code of self, which is also a GRS code.

EXAMPLES:

sage: F =  GF(59)
sage: colmults = [ F._random_nonzero_element() for i in range(40) ]
sage: C = codes.GeneralizedReedSolomonCode(F.list()[:40], 12, colmults)
sage: Cd = C.dual_code(); Cd
[40, 28, 13] Generalized Reed-Solomon Code over GF(59)

The dual code of the dual code is the original code:

sage: C == Cd.dual_code()
True
evaluation_points()#

Return the vector of field elements used for the polynomial evaluations.

EXAMPLES:

sage: F = GF(11)
sage: n, k = 10, 5
sage: C = codes.GeneralizedReedSolomonCode(F.list()[:n], k)
sage: C.evaluation_points()
(0, 1, 2, 3, 4, 5, 6, 7, 8, 9)
is_generalized()#

Return whether self is a Generalized Reed-Solomon code or a regular Reed-Solomon code.

self is a Generalized Reed-Solomon code if its column multipliers are not all 1.

EXAMPLES:

sage: F = GF(11)
sage: n, k = 10, 5
sage: C = codes.GeneralizedReedSolomonCode(F.list()[:n], k)
sage: C.column_multipliers()
(1, 1, 1, 1, 1, 1, 1, 1, 1, 1)
sage: C.is_generalized()
False
sage: colmults = [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 1]
sage: C2 = codes.GeneralizedReedSolomonCode(F.list()[:n], k, colmults)
sage: C2.is_generalized()
True
minimum_distance()#

Return the minimum distance between any two words in self.

Since a GRS code is always Maximum-Distance-Separable (MDS), this returns C.length() - C.dimension() + 1.

EXAMPLES:

sage: F = GF(59)
sage: n, k = 40, 12
sage: C = codes.GeneralizedReedSolomonCode(F.list()[:n], k)
sage: C.minimum_distance()
29
multipliers_product()#

Return the component-wise product of the column multipliers of self with the column multipliers of the dual GRS code.

This is a simple Cramer’s rule-like expression on the evaluation points of self. Recall that the column multipliers of the dual GRS code are also the column multipliers of the parity check matrix of self.

EXAMPLES:

sage: F = GF(11)
sage: n, k = 10, 5
sage: C = codes.GeneralizedReedSolomonCode(F.list()[:n], k)
sage: C.multipliers_product()
[10, 9, 8, 7, 6, 5, 4, 3, 2, 1]
parity_check_matrix()#

Return the parity check matrix of self.

EXAMPLES:

sage: F = GF(11)
sage: n, k = 10, 5
sage: C = codes.GeneralizedReedSolomonCode(F.list()[:n], k)
sage: C.parity_check_matrix()
[10  9  8  7  6  5  4  3  2  1]
[ 0  9  5 10  2  3  2 10  5  9]
[ 0  9 10  8  8  4  1  4  7  4]
[ 0  9  9  2 10  9  6  6  1  3]
[ 0  9  7  6  7  1  3  9  8  5]
parity_column_multipliers()#

Return the list of column multipliers of the parity check matrix of self. They are also column multipliers of the generator matrix for the dual GRS code of self.

EXAMPLES:

sage: F = GF(11)
sage: n, k = 10, 5
sage: C = codes.GeneralizedReedSolomonCode(F.list()[:n], k)
sage: C.parity_column_multipliers()
[10, 9, 8, 7, 6, 5, 4, 3, 2, 1]
weight_distribution()#

Return the list whose \(i\)’th entry is the number of words of weight \(i\) in self.

Computing the weight distribution for a GRS code is very fast. Note that for random linear codes, it is computationally hard.

EXAMPLES:

sage: F = GF(11)
sage: n, k = 10, 5
sage: C = codes.GeneralizedReedSolomonCode(F.list()[:n], k)
sage: C.weight_distribution()                                               # optional - sage.symbolic
[1, 0, 0, 0, 0, 0, 2100, 6000, 29250, 61500, 62200]
sage.coding.grs_code.ReedSolomonCode(base_field, length, dimension, primitive_root=None)#

Construct a classical Reed-Solomon code.

A classical \([n,k]\) Reed-Solomon code over \(\GF{q}\) with \(1 \le k \le n\) and \(n | (q-1)\) is a Reed-Solomon code whose evaluation points are the consecutive powers of a primitive \(n\)’th root of unity \(\alpha\), i.e. \(\alpha_i = \alpha^{i-1}\), where \(\alpha_1, \ldots, \alpha_n\) are the evaluation points. A classical Reed-Solomon codes has all column multipliers equal \(1\).

Classical Reed-Solomon codes are cyclic, unlike most Generalized Reed-Solomon codes.

Use GeneralizedReedSolomonCode if you instead wish to construct non-classical Reed-Solomon and Generalized Reed-Solomon codes.

INPUT:

  • base_field – the finite field for which to build the classical Reed-Solomon code.

  • length – the length of the classical Reed-Solomon code. Must divide \(q-1\) where \(q\) is the cardinality of base_field.

  • dimension – the dimension of the resulting code.

  • primitive_root – (default: None) a primitive \(n\)’th root of unity to use for constructing the classical Reed-Solomon code. If not supplied, one will be computed and can be recovered as C.evaluation_points()[1] where \(C\) is the code returned by this method.

EXAMPLES:

sage: C = codes.ReedSolomonCode(GF(7), 6, 3); C
[6, 3, 4] Reed-Solomon Code over GF(7)

This code is cyclic as can be seen by coercing it into a cyclic code:

sage: Ccyc = codes.CyclicCode(code=C); Ccyc
[6, 3] Cyclic Code over GF(7)

sage: Ccyc.generator_polynomial()
x^3 + 3*x^2 + x + 6

Another example over an extension field:

sage: C = codes.ReedSolomonCode(GF(64,'a'), 9, 4); C
[9, 4, 6] Reed-Solomon Code over GF(64)

The primitive \(n\)’th root of unity can be recovered as the 2nd evaluation point of the code:

sage: alpha = C.evaluation_points()[1]; alpha
a^5 + a^4 + a^2 + a

We can also supply a different primitive \(n\)’th root of unity:

sage: beta = alpha^2; beta
a^4 + a
sage: beta.multiplicative_order()
9
sage: D = codes.ReedSolomonCode(GF(64), 9, 4, primitive_root=beta); D
[9, 4, 6] Reed-Solomon Code over GF(64)
sage: C == D
False