Generalized Reed-Solomon code

Given \(n\) different evaluation points \(\alpha_1, \dots, \alpha_n\) from some finite field \(F\), and \(n\) column multipliers \(\beta_1, \dots, \beta_n\), the corresponding 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 \}\]

This file contains the following elements:

class sage.coding.grs.GRSBerlekampWelchDecoder(code)

Bases: sage.coding.decoder.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 [HJ04] pp. 51-52 for details.

REFERENCES:

[HJ04]Tom Hoeholdt and Joern Justesen, A Course In Error-Correcting Codes, EMS, 2004

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] Generalized Reed-Solomon Code over Finite Field of size 59

Actually, we can construct the decoder from C directly:

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

Corrects 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

TESTS:

If one tries to decode a word which is too far from any codeword, an exception is raised:

sage: e = vector(F,[0, 0, 54, 23, 1, 0, 0, 0, 53, 21, 0, 0, 0, 34, 6, 11, 0, 0, 16, 0, 0, 0, 9, 0, 10, 27, 35, 0, 0, 0, 0, 46, 0, 0, 0, 0, 0, 0, 44, 0]); e.hamming_weight()
15
sage: D.decode_to_code(c + e)
Traceback (most recent call last):
...
DecodingError: Decoding failed because the number of errors exceeded the decoding radius

If one tries to decode something which is not in the ambient space of the code, an exception is raised:

sage: D.decode_to_code(42)
Traceback (most recent call last):
...
ValueError: The word to decode has to be in the ambient space of the code

The bug detailed in trac ticket #20340 has been fixed:

sage: C = codes.GeneralizedReedSolomonCode(GF(59).list()[:40], 12)
sage: c = C.random_element()
sage: D = C.decoder("BerlekampWelch")
sage: D.decode_to_code(c) == c
True
decode_to_message(r)

Decodes 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

TESTS:

If one tries to decode a word which is too far from any codeword, an exception is raised:

sage: e = vector(F,[0, 0, 54, 23, 1, 0, 0, 0, 53, 21, 0, 0, 0, 34, 6, 11, 0, 0, 16, 0, 0, 0, 9, 0, 10, 27, 35, 0, 0, 0, 0, 46, 0, 0, 0, 0, 0, 0, 44, 0]); e.hamming_weight()
15
sage: D.decode_to_message(c + e)
Traceback (most recent call last):
...
DecodingError: Decoding failed because the number of errors exceeded the decoding radius

If one tries to decode something which is not in the ambient space of the code, an exception is raised:

sage: D.decode_to_message(42)
Traceback (most recent call last):
...
ValueError: The word to decode has to be in the ambient space of the code

The bug detailed in trac ticket #20340 has been fixed:

sage: C = codes.GeneralizedReedSolomonCode(GF(59).list()[:40], 12)
sage: c = C.random_element()
sage: D = C.decoder("BerlekampWelch")
sage: E = D.connected_encoder()
sage: m = E.message_space().random_element()
sage: c = E.encode(m)
sage: D.decode_to_message(c) == m
True
decoding_radius()

Returns 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.GRSErrorErasureDecoder(code)

Bases: sage.coding.decoder.Decoder

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

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] Generalized Reed-Solomon Code over Finite Field of size 59

Actually, we can construct the decoder from C directly:

sage: D = C.decoder("ErrorErasure")
sage: D
Error-Erasure decoder for [40, 12, 29] Generalized Reed-Solomon Code over Finite Field of size 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

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.

INPUT:

  • word_and_erasure_vector – a pair of vectors, where first element is a codeword of self and second element is a vector of GF(2) containing erasure positions

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

TESTS:

If one tries to decode a word with too many erasures, it returns an exception:

sage: Chan = channels.ErrorErasureChannel(C.ambient_space(), 0, C.minimum_distance() + 1)
sage: y = Chan(c)
sage: D.decode_to_message(y)
Traceback (most recent call last):
...
DecodingError: Too many erasures in the received word

If one tries to decode something which is not in the ambient space of the code, an exception is raised:

sage: D.decode_to_message((42, random_vector(GF(2), C.length())))
Traceback (most recent call last):
...
ValueError: The word to decode has to be in the ambient space of the code

If one tries to pass an erasure_vector which is not a vector over GF(2) of the same length as code’s, an exception is raised:

sage: D.decode_to_message((C.random_element(), 42))
Traceback (most recent call last):
...
ValueError: The erasure vector has to be a vector over GF(2) of the same length as the code
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.GRSEvaluationPolynomialEncoder(code, polynomial_ring=None)

Bases: sage.coding.encoder.Encoder

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

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] Generalized Reed-Solomon Code over Finite Field of size 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] Generalized Reed-Solomon Code over Finite Field of size 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)

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

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

TESTS:

The bug described in trac ticket #20744 is now fixed:

sage: F = GF(11)
sage: Fm.<my_variable> = F[]
sage: n, k = 10 , 5
sage: C = codes.GeneralizedReedSolomonCode(F.list()[:n], k)
sage: E = C.encoder("EvaluationPolynomial", polynomial_ring = Fm)
sage: p = my_variable^2 + 3*my_variable + 10
sage: c = E.encode(p)
sage: c in C
True
message_space()

Returns 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()

Returns 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)

Returns 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:

  • An 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.GRSEvaluationVectorEncoder(code)

Bases: sage.coding.encoder.Encoder

Encoder for Generalized Reed-Solomon codes which encodes vectors into codewords.

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] Generalized Reed-Solomon Code over Finite Field of size 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] Generalized Reed-Solomon Code over Finite Field of size 59
generator_matrix()

Returns a generator matrix of self

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.GRSGaoDecoder(code)

Bases: sage.coding.decoder.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 [G02] for details.

REFERENCES:

[G02]Shuhong Gao, A new algorithm for decoding Reed-Solomon Codes, January 31, 2002

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] Generalized Reed-Solomon Code over Finite Field of size 59

Actually, we can construct the decoder from C directly:

sage: D = C.decoder("Gao")
sage: D
Gao decoder for [40, 12, 29] Generalized Reed-Solomon Code over Finite Field of size 59
decode_to_code(r)

Corrects 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

TESTS:

If one tries to decode a word which is too far from any codeword, an exception is raised:

sage: e = vector(F,[0, 0, 54, 23, 1, 0, 0, 0, 53, 21, 0, 0, 0, 34, 6, 11, 0, 0, 16, 0, 0, 0, 9, 0, 10, 27, 35, 0, 0, 0, 0, 46, 0, 0, 0, 0, 0, 0, 44, 0]); e.hamming_weight()
15
sage: D.decode_to_code(c + e)
Traceback (most recent call last):
...
DecodingError: Decoding failed because the number of errors exceeded the decoding radius

If one tries to decode something which is not in the ambient space of the code, an exception is raised:

sage: D.decode_to_code(42)
Traceback (most recent call last):
...
ValueError: The word to decode has to be in the ambient space of the code

The bug detailed in trac ticket #20340 has been fixed:

sage: C = codes.GeneralizedReedSolomonCode(GF(59).list()[:40], 12)
sage: c = C.random_element()
sage: D = C.decoder("Gao")
sage: c = C.random_element()
sage: D.decode_to_code(c) == c
True
decode_to_message(r)

Decodes 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

TESTS:

If one tries to decode a word which is too far from any codeword, an exception is raised:

sage: e = vector(F,[0, 0, 54, 23, 1, 0, 0, 0, 53, 21, 0, 0, 0, 34, 6, 11, 0, 0, 16, 0, 0, 0, 9, 0, 10, 27, 35, 0, 0, 0, 0, 46, 0, 0, 0, 0, 0, 0, 44, 0]); e.hamming_weight()
15
sage: D.decode_to_message(c + e)
Traceback (most recent call last):
...
DecodingError: Decoding failed because the number of errors exceeded the decoding radius

If one tries to decode something which is not in the ambient space of the code, an exception is raised:

sage: D.decode_to_message(42)
Traceback (most recent call last):
...
ValueError: The word to decode has to be in the ambient space of the code

The bug detailed in trac ticket #20340 has been fixed:

sage: C = codes.GeneralizedReedSolomonCode(GF(59).list()[:40], 12)
sage: c = C.random_element()
sage: D = C.decoder("Gao")
sage: E = D.connected_encoder()
sage: m = E.message_space().random_element()
sage: c = E.encode(m)
sage: D.decode_to_message(c) == m
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.GRSKeyEquationSyndromeDecoder(code)

Bases: sage.coding.decoder.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 [R06], 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] Generalized Reed-Solomon Code over Finite Field of size 59

Actually, we can construct the decoder from C directly:

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

Corrects 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

TESTS:

If one tries to decode a word with too many errors, it returns an exception:

sage: Chan = channels.StaticErrorRateChannel(C.ambient_space(), D.decoding_radius()+1)
sage: y = Chan(c)
sage: D.decode_to_message(y)
Traceback (most recent call last):
...
DecodingError: Decoding failed because the number of errors exceeded the decoding radius

If one tries to decode something which is not in the ambient space of the code, an exception is raised:

sage: D.decode_to_code(42)
Traceback (most recent call last):
...
ValueError: The word to decode has to be in the ambient space of the code
decode_to_message(r)

Decodes``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.GeneralizedReedSolomonCode(evaluation_points, dimension, column_multipliers=None)

Bases: sage.coding.linear_code.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:

A Reed-Solomon code can be constructed by taking all non-zero elements of the field as evaluation points, and specifying no column multipliers:

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] Generalized Reed-Solomon Code over Finite Field of size 7

More generally, the following is a GRS 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] Generalized Reed-Solomon Code over Finite Field of size 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 Finite Field of size 59
column_multipliers()

Returns the column multipliers of self as a vector.

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()

Returns 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
decode_to_message(r)

Decodes``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(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)
dual_code()

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

EXAMPLES:

sage: F =  GF(59)
sage: colmults = [ F.random_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 Finite Field of size 59

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

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

Returns the evaluation points of self as a vector.

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)
minimum_distance()

Returns the minimum distance of 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()

Returns 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 is 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()

Returns 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()

Returns the list of column multipliers of self‘s parity check matrix.

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()

Returns 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()
[1, 0, 0, 0, 0, 0, 2100, 6000, 29250, 61500, 62200]