Codes¶
Class supporting methods available for any type of code (linear, non-linear) and over any metric (Hamming, rank).
There are further abstract classes representing certain types of codes. For
linear codes,
AbstractLinearCodeNoMetric
contains
all the methods that any linear code can use regardless of its metric.
Inheriting from this class are base classes for linear codes over specific
metrics. For example, AbstractLinearCode
is a
base class for all linear codes over the Hamming metric.
Take the class HammingCode
. This
class inherits from AbstractLinearCode
, since
it is a linear code over the Hamming metric.
AbstractLinearCode
then inherits from
AbstractLinearCodeNoMetric
, since it
is a linear code. Finally, this class inherits from
AbstractCode
, since it is a code.
The following diagram shows the inheritance relationship in the coding module:
AbstractCode
+ AbstractLinearCodeNoMetric
| + AbstractLinearCode
| | + ParityCheckCode
| | + HammingCode
| | + CyclicCode
| | + BCHCode
| | + GolayCode
| | + ReedMullerCode
| | + GeneralizedReedSolomonCode
| | + GoppaCode
| + AbstractLinearRankMetricCode
Any class inheriting from AbstractCode can use the encode/decode framework.
The encoder/decoder framework within the coding module offers the creation and use of encoders/decoders independently of codes. An encoder encodes a message into a codeword. A decoder decodes a word into a codeword or a message, possibly with error-correction.
Instead of creating specific encoders/decoders for every code family, some
encoders/decoders can be used by multiple code families. The encoder/decoder
framework enables just that. For example,
LinearCodeGeneratorMatrixEncoder
can be used by any code that has a generator matrix. Similarly,
LinearCodeNearestNeighborDecoder
can be used
for any linear code with Hamming metric.
When creating a new code family, investigate the encoder/decoder catalogs,
codes.encoders
and codes.decoders
, to see if there are suitable
encoders/decoders for your code family already implemented. If this is the case,
follow the instructions in AbstractCode
to set these up.
A new encoder must have the following methods:
encode
– method encoding a message into a codewordunencode
– method decoding a codeword into a messagemessage_space
– ambient space of messages that can be encodedcode
– code of the encoder
For more information about the Encoder class, see
Encoder
A new decoder must have the following methods:
decode_to_code
ordecode_to_message
– method decoding a word from the input space into either a codeword or a messageinput_space
– ambient space of words that can be decodedcode
– code of the decoder
For more information about the Decoder class, see
Decoder
- class sage.coding.abstract_code.AbstractCode(length, default_encoder_name=None, default_decoder_name=None, metric='Hamming')¶
Bases:
sage.structure.parent.Parent
Abstract class for codes.
This class contains all the methods that can be used on any code and on any code family. As opposed to
sage.coding.linear_code.AbstractLinearCode
, this class makes no assumptions about linearity, metric, finiteness or the number of alphabets.The abstract notion of “code” that is implicitly used for this class is any enumerable subset of a cartesian product \(A_1 \times A_2 \times \ldots \times A_n\) for some sets \(A_i\). Note that this class makes no attempt to directly represent the code in this fashion, allowing subclasses to make the appropriate choices. The notion of metric is also not mathematically enforced in any way, and is simply stored as a string value.
Every code-related class should inherit from this abstract class.
To implement a code, you need to:
inherit from AbstractCode
call AbstractCode
__init__
method in the subclass constructor. Example:super(SubclassName, self).__init__(length, "EncoderName", "DecoderName", "metric")
. “EncoderName” and “DecoderName” are set toNone
by default, a generic code class such as AbstractCode does not necessarily have to have general encoders/decoders. However, if you want to use the encoding/decoding methods, you have to add these.since this class does not specify any category, it is highly recommended to set up the category framework in the subclass. To do this, use the
Parent.__init__(self, base, facade, category)
function in the subclass constructor. A good example is insage.coding.linear_code.AbstractLinearCode
.it is also recommended to override the
ambient_space
method, which is required by__call__
to use the encoder/decoder framework, one has to set up the category and related functions
__iter__
and__contains__
. A good example is insage.coding.linear_code.AbstractLinearCode
.add the following two lines on the class level:
_registered_encoders = {} _registered_decoders = {}
fill the dictionary of its encoders in
sage.coding.__init__.py
file. Example: I want to link the encoderMyEncoderClass
toMyNewCodeClass
under the nameMyEncoderName
. All I need to do is to write this line in the__init__.py
file:MyNewCodeClass._registered_encoders["NameOfMyEncoder"] = MyEncoderClass
and all instances ofMyNewCodeClass
will be able to use instances ofMyEncoderClass
.fill the dictionary of its decoders in
sage.coding.__init__
file. Example: I want to link the encoderMyDecoderClass
toMyNewCodeClass
under the nameMyDecoderName
. All I need to do is to write this line in the__init__.py
file:MyNewCodeClass._registered_decoders["NameOfMyDecoder"] = MyDecoderClass
and all instances ofMyNewCodeClass
will be able to use instances ofMyDecoderClass
.
As AbstractCode is not designed to be implemented, it does not have any representation methods. You should implement
_repr_
and_latex_
methods in the subclass.- add_decoder(name, decoder)¶
Adds an decoder to the list of registered decoders of
self
.Note
This method only adds
decoder
toself
, and not to any member of the class ofself
. To know how to add ansage.coding.decoder.Decoder
, please refer to the documentation ofAbstractCode
.INPUT:
name
– the string name for the decoderdecoder
– the class name of the decoder
EXAMPLES:
First of all, we create a (very basic) new decoder:
sage: class MyDecoder(sage.coding.decoder.Decoder): ....: def __init__(self, code): ....: super(MyDecoder, self).__init__(code) ....: def _repr_(self): ....: return "MyDecoder decoder with associated code %s" % self.code()
We now create a new code:
sage: C = codes.HammingCode(GF(2), 3)
We can add our new decoder to the list of available decoders of C:
sage: C.add_decoder("MyDecoder", MyDecoder) sage: sorted(C.decoders_available()) ['InformationSet', 'MyDecoder', 'NearestNeighbor', 'Syndrome']
We can verify that any new code will not know MyDecoder:
sage: C2 = codes.HammingCode(GF(2), 3) sage: sorted(C2.decoders_available()) ['InformationSet', 'NearestNeighbor', 'Syndrome']
- add_encoder(name, encoder)¶
Adds an encoder to the list of registered encoders of
self
.Note
This method only adds
encoder
toself
, and not to any member of the class ofself
. To know how to add ansage.coding.encoder.Encoder
, please refer to the documentation ofAbstractCode
.INPUT:
name
– the string name for the encoderencoder
– the class name of the encoder
EXAMPLES:
First of all, we create a (very basic) new encoder:
sage: class MyEncoder(sage.coding.encoder.Encoder): ....: def __init__(self, code): ....: super(MyEncoder, self).__init__(code) ....: def _repr_(self): ....: return "MyEncoder encoder with associated code %s" % self.code()
We now create a new code:
sage: C = codes.HammingCode(GF(2), 3)
We can add our new encoder to the list of available encoders of C:
sage: C.add_encoder("MyEncoder", MyEncoder) sage: sorted(C.encoders_available()) ['MyEncoder', 'Systematic']
We can verify that any new code will not know MyEncoder:
sage: C2 = codes.HammingCode(GF(2), 3) sage: sorted(C2.encoders_available()) ['Systematic']
- ambient_space()¶
Return an error stating
ambient_space
ofself
is not implemented.This method is required by
__call__()
.EXAMPLES:
sage: from sage.coding.abstract_code import AbstractCode sage: class MyCode(AbstractCode): ....: def __init__(self, length): ....: super(MyCode, self).__init__(length) sage: C = MyCode(3) sage: C.ambient_space() Traceback (most recent call last): ... NotImplementedError: No ambient space implemented for this code.
- decode_to_code(word, decoder_name=None, *args, **kwargs)¶
Corrects the errors in
word
and returns a codeword.INPUT:
word
– an element in the ambient space asself
decoder_name
– (default:None
) Name of the decoder which will be used to decodeword
. The default decoder ofself
will be used if default value is kept.args
,kwargs
– all additional arguments are forwarded todecoder()
OUTPUT:
A vector of
self
.
EXAMPLES:
sage: G = Matrix(GF(2), [[1,1,1,0,0,0,0],[1,0,0,1,1,0,0],[0,1,0,1,0,1,0],[1,1,0,1,0,0,1]]) sage: C = LinearCode(G) sage: word = vector(GF(2), (1, 1, 0, 0, 1, 1, 0)) sage: w_err = word + vector(GF(2), (1, 0, 0, 0, 0, 0, 0)) sage: C.decode_to_code(w_err) (1, 1, 0, 0, 1, 1, 0)
It is possible to manually choose the decoder amongst the list of the available ones:
sage: sorted(C.decoders_available()) ['InformationSet', 'NearestNeighbor', 'Syndrome'] sage: C.decode_to_code(w_err, 'NearestNeighbor') (1, 1, 0, 0, 1, 1, 0)
- decode_to_message(word, decoder_name=None, *args, **kwargs)¶
Correct the errors in word and decodes it to the message space.
INPUT:
word
– an element in the ambient space asself
decoder_name
– (default:None
) Name of the decoder which will be used to decodeword
. The default decoder ofself
will be used if default value is kept.args
,kwargs
– all additional arguments are forwarded todecoder()
OUTPUT:
A vector of the message space of
self
.
EXAMPLES:
sage: G = Matrix(GF(2), [[1,1,1,0,0,0,0],[1,0,0,1,1,0,0],[0,1,0,1,0,1,0],[1,1,0,1,0,0,1]]) sage: C = LinearCode(G) sage: word = vector(GF(2), (1, 1, 0, 0, 1, 1, 0)) sage: C.decode_to_message(word) (0, 1, 1, 0)
It is possible to manually choose the decoder amongst the list of the available ones:
sage: sorted(C.decoders_available()) ['InformationSet', 'NearestNeighbor', 'Syndrome'] sage: C.decode_to_message(word, 'NearestNeighbor') (0, 1, 1, 0)
- decoder(decoder_name=None, *args, **kwargs)¶
Return a decoder of
self
.INPUT:
decoder_name
– (default:None
) name of the decoder which will be returned. The default decoder ofself
will be used if default value is kept.args
,kwargs
– all additional arguments will be forwarded to the constructor of the decoder that will be returned by this method
OUTPUT:
a decoder object
Besides creating the decoder and returning it, this method also stores the decoder in a cache. With this behaviour, each decoder will be created at most one time for
self
.EXAMPLES:
sage: G = Matrix(GF(2), [[1,1,1,0,0,0,0],[1,0,0,1,1,0,0],[0,1,0,1,0,1,0],[1,1,0,1,0,0,1]]) sage: C = LinearCode(G) sage: C.decoder() Syndrome decoder for [7, 4] linear code over GF(2) handling errors of weight up to 1
If there is no decoder for the code, we return an error:
sage: from sage.coding.abstract_code import AbstractCode sage: class MyCodeFamily(AbstractCode): ....: def __init__(self, length, field): ....: sage.coding.abstract_code.AbstractCode.__init__(self, length) ....: Parent.__init__(self, base=field, facade=False, category=Sets()) ....: self._field = field ....: def field(self): ....: return self._field ....: def _repr_(self): ....: return "%d dummy code over GF(%s)" % (self.length(), self.field().cardinality()) sage: D = MyCodeFamily(5, GF(2)) sage: D.decoder() Traceback (most recent call last): ... NotImplementedError: No decoder implemented for this code.
If the name of a decoder which is not known by
self
is passed, an exception will be raised:sage: sorted(C.decoders_available()) ['InformationSet', 'NearestNeighbor', 'Syndrome'] sage: C.decoder('Try') Traceback (most recent call last): ... ValueError: There is no Decoder named 'Try'. The known Decoders are: ['InformationSet', 'NearestNeighbor', 'Syndrome']
Some decoders take extra arguments. If the user forgets to supply these, the error message attempts to be helpful:
sage: C.decoder('InformationSet') Traceback (most recent call last): ... ValueError: Constructing the InformationSet decoder failed, possibly due to missing or incorrect parameters. The constructor requires the arguments ['number_errors']. It takes the optional arguments ['algorithm']. It accepts unspecified arguments as well. See the documentation of sage.coding.information_set_decoder.LinearCodeInformationSetDecoder for more details.
- decoders_available(classes=False)¶
Returns a list of the available decoders’ names for
self
.INPUT:
classes
– (default:False
) ifclasses
is set toTrue
, return instead adict
mapping available decoder name to the associated decoder class.
OUTPUT: a list of strings, or a \(dict\) mapping strings to classes.
EXAMPLES:
sage: G = Matrix(GF(2), [[1,1,1,0,0,0,0],[1,0,0,1,1,0,0],[0,1,0,1,0,1,0],[1,1,0,1,0,0,1]]) sage: C = LinearCode(G) sage: C.decoders_available() ['InformationSet', 'NearestNeighbor', 'Syndrome'] sage: dictionary = C.decoders_available(True) sage: sorted(dictionary.keys()) ['InformationSet', 'NearestNeighbor', 'Syndrome'] sage: dictionary['NearestNeighbor'] <class 'sage.coding.linear_code.LinearCodeNearestNeighborDecoder'>
- encode(word, encoder_name=None, *args, **kwargs)¶
Transforms an element of a message space into a codeword.
INPUT:
word
– an element of a message space of the codeencoder_name
– (default:None
) Name of the encoder which will be used to encodeword
. The default encoder ofself
will be used if default value is kept.args
,kwargs
– all additional arguments are forwarded to the construction of the encoder that is used..
One can use the following shortcut to encode a word
C(word)
OUTPUT:
a vector of
self
.
EXAMPLES:
sage: G = Matrix(GF(2), [[1,1,1,0,0,0,0],[1,0,0,1,1,0,0],[0,1,0,1,0,1,0],[1,1,0,1,0,0,1]]) sage: C = LinearCode(G) sage: word = vector((0, 1, 1, 0)) sage: C.encode(word) (1, 1, 0, 0, 1, 1, 0) sage: C(word) (1, 1, 0, 0, 1, 1, 0)
It is possible to manually choose the encoder amongst the list of the available ones:
sage: sorted(C.encoders_available()) ['GeneratorMatrix', 'Systematic'] sage: word = vector((0, 1, 1, 0)) sage: C.encode(word, 'GeneratorMatrix') (1, 1, 0, 0, 1, 1, 0)
- encoder(encoder_name=None, *args, **kwargs)¶
Returns an encoder of
self
.The returned encoder provided by this method is cached.
This methods creates a new instance of the encoder subclass designated by
encoder_name
. While it is also possible to do the same by directly calling the subclass’ constructor, it is strongly advised to use this method to take advantage of the caching mechanism.INPUT:
encoder_name
– (default:None
) name of the encoder which will be returned. The default encoder ofself
will be used if default value is kept.args
,kwargs
– all additional arguments are forwarded to the constructor of the encoder this method will return.
OUTPUT:
an Encoder object.
Note
The default encoder always has \(F^{k}\) as message space, with \(k\) the dimension of
self
and \(F\) the base ring ofself
.EXAMPLES:
sage: G = Matrix(GF(2), [[1,1,1,0,0,0,0],[1,0,0,1,1,0,0],[0,1,0,1,0,1,0],[1,1,0,1,0,0,1]]) sage: C = LinearCode(G) sage: C.encoder() Generator matrix-based encoder for [7, 4] linear code over GF(2)
If there is no encoder for the code, we return an error:
sage: from sage.coding.abstract_code import AbstractCode sage: class MyCodeFamily(AbstractCode): ....: def __init__(self, length, field): ....: sage.coding.abstract_code.AbstractCode.__init__(self, length) ....: Parent.__init__(self, base=field, facade=False, category=Sets()) ....: self._field = field ....: def field(self): ....: return self._field ....: def _repr_(self): ....: return "%d dummy code over GF(%s)" % (self.length(), self.field().cardinality()) sage: D = MyCodeFamily(5, GF(2)) sage: D.encoder() Traceback (most recent call last): ... NotImplementedError: No encoder implemented for this code.
We check that the returned encoder is cached:
sage: C.encoder.is_in_cache() True
If the name of an encoder which is not known by
self
is passed, an exception will be raised:sage: sorted(C.encoders_available()) ['GeneratorMatrix', 'Systematic'] sage: C.encoder('NonExistingEncoder') Traceback (most recent call last): ... ValueError: There is no Encoder named 'NonExistingEncoder'. The known Encoders are: ['GeneratorMatrix', 'Systematic']
Some encoders take extra arguments. If the user incorrectly supplies these, the error message attempts to be helpful:
sage: C.encoder('Systematic', strange_parameter=True) Traceback (most recent call last): ... ValueError: Constructing the Systematic encoder failed, possibly due to missing or incorrect parameters. The constructor requires no arguments. It takes the optional arguments ['systematic_positions']. See the documentation of sage.coding.linear_code_no_metric.LinearCodeSystematicEncoder for more details.
- encoders_available(classes=False)¶
Returns a list of the available encoders’ names for
self
.INPUT:
classes
– (default:False
) ifclasses
is set toTrue
, return instead adict
mapping available encoder name to the associated encoder class.
OUTPUT: a list of strings, or a \(dict\) mapping strings to classes.
EXAMPLES:
sage: G = Matrix(GF(2), [[1,1,1,0,0,0,0],[1,0,0,1,1,0,0],[0,1,0,1,0,1,0],[1,1,0,1,0,0,1]]) sage: C = LinearCode(G) sage: C.encoders_available() ['GeneratorMatrix', 'Systematic'] sage: dictionary = C.encoders_available(True) sage: sorted(dictionary.items()) [('GeneratorMatrix', <class 'sage.coding.linear_code.LinearCodeGeneratorMatrixEncoder'>), ('Systematic', <class 'sage.coding.linear_code_no_metric.LinearCodeSystematicEncoder'>)]
- length()¶
Returns the length of this code.
EXAMPLES:
sage: C = codes.HammingCode(GF(2), 3) sage: C.length() 7
- list()¶
Return a list of all elements of this code.
EXAMPLES:
sage: C = codes.HammingCode(GF(2), 3) sage: Clist = C.list() sage: Clist[5]; Clist[5] in C (1, 0, 1, 0, 1, 0, 1) True
- metric()¶
Return the metric of
self
.EXAMPLES:
sage: C = codes.HammingCode(GF(2), 3) sage: C.metric() 'Hamming'
- random_element(*args, **kwds)¶
Returns a random codeword; passes other positional and keyword arguments to
random_element()
method of vector space.OUTPUT:
Random element of the vector space of this code
EXAMPLES:
sage: C = codes.HammingCode(GF(4,'a'), 3) sage: C.random_element() # random test (1, 0, 0, a + 1, 1, a, a, a + 1, a + 1, 1, 1, 0, a + 1, a, 0, a, a, 0, a, a, 1)
Passes extra positional or keyword arguments through:
sage: C.random_element(prob=.5, distribution='1/n') # random test (1, 0, a, 0, 0, 0, 0, a + 1, 0, 0, 0, 0, 0, 0, 0, 0, a + 1, a + 1, 1, 0, 0)
- unencode(c, encoder_name=None, nocheck=False, **kwargs)¶
Returns the message corresponding to
c
.This is the inverse of
encode()
.INPUT:
c
– a codeword ofself
.encoder_name
– (default:None
) name of the decoder which will be used to decodeword
. The default decoder ofself
will be used if default value is kept.nocheck
– (default:False
) checks ifc
is inself
. You might set this toTrue
to disable the check for saving computation. Note that ifc
is not inself
andnocheck = True
, then the output ofunencode()
is not defined (except that it will be in the message space ofself
).kwargs
– all additional arguments are forwarded to the construction of the encoder that is used.
OUTPUT:
an element of the message space of
encoder_name
ofself
.
EXAMPLES:
sage: G = Matrix(GF(2), [[1,1,1,0,0,0,0],[1,0,0,1,1,0,0],[0,1,0,1,0,1,0],[1,1,0,1,0,0,1]]) sage: C = LinearCode(G) sage: c = vector(GF(2), (1, 1, 0, 0, 1, 1, 0)) sage: C.unencode(c) (0, 1, 1, 0)