Reed-Solomon codes and Generalized Reed-Solomon codes¶
Given different “evaluation points”
from some
finite field
, the corresponding Reed-Solomon code (RS code) of dimension
is the set:
More generally, given also “column multipliers”
,
the corresponding Generalized Reed-Solomon code (GRS code) of dimension
is
the set:
This file contains the following elements:
GeneralizedReedSolomonCode
, the class for GRS codesGRSEvaluationVectorEncoder
, an encoder with a vectorial message spaceGRSEvaluationPolynomialEncoder
, an encoder with a polynomial message spaceGRSBerlekampWelchDecoder
, a decoder which corrects errors using Berlekamp-Welch algorithmGRSGaoDecoder
, a decoder which corrects errors using Gao algorithmGRSErrorErasureDecoder
, a decoder which corrects both errors and erasuresGRSKeyEquationSyndromeDecoder
, a decoder which corrects errors using the key equation on syndrome polynomials
-
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 [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)¶ 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 ofself.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 ofself
.Note
If the code associated to
self
has the same length as its dimension,r
will be unencoded as is. In that case, ifr
is not a codeword, the output is unspecified.INPUT:
r
– a codeword ofself
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] 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 ofself
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, where
is the length of the code associated to
self
andits dimension,
r
will be returned as is. In either case, ifr
is not a codeword, the output is unspecified.INPUT:
word_and_erasure_vector
– a pair of vectors, where first element is a codeword ofself
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 receivesINPUT:
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 ofself
, if needed. It is set to(where
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)¶ Transforms the polynomial
p
into a codeword ofcode()
.INPUT:
p
– A polynomial from the message space ofself
of degree less thanself.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, useunencode()
.INPUT:
c
– A codeword ofcode()
.
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] 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
()¶ 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 [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)¶ 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 ofself.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 ofself
.Note
If the code associated to
self
has the same length as its dimension,r
will be unencoded as is. In that case, ifr
is not a codeword, the output is unspecified.INPUT:
r
– a codeword ofself
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 decodeOUTPUT:
- 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 [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)¶ 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 ofself.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, ifr
is not a codeword, the output is unspecified.INPUT:
r
– a codeword ofself
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 decodeOUTPUT:
- 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.
dimension
– The dimension of the resulting code.column_multipliers
– (default:None
) List of non-zero elements of. All column multipliers are set to 1 if default value is kept.
EXAMPLES:
A classical 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] 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)
-
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
is the smallest number
s.t. any element of the ambient space of
is at most at distance
to
.
As GRS codes are Maximum Distance Separable codes (MDS), their covering radius is always
, where
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, ifr
is not a codeword, the output is unspecified.INPUT:
r
– a codeword ofself
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 GF(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)
-
is_generalized
()¶ Return whether
self
is a Generalized Reed-Solomon code or a regular Reed-Solomon codeself
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
()¶ Returns the minimum distance of
self
. Since a GRS code is always Maximum-Distance-Separable (MDS), this returnsC.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 ofself
.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
‘th entry is the number of words of weight
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]
-
sage.coding.grs.
ReedSolomonCode
¶ alias of
GeneralizedReedSolomonCode