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 codeword

  • unencode – method decoding a codeword into a message

  • message_space – ambient space of messages that can be encoded

  • code – code of the encoder

For more information about the Encoder class, see Encoder

A new decoder must have the following methods:

  • decode_to_code or decode_to_message – method decoding a word from the input space into either a codeword or a message

  • input_space – ambient space of words that can be decoded

  • code – 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: 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().__init__(length, "EncoderName", "DecoderName", "metric"). “EncoderName” and “DecoderName” are set to None 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 in sage.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 in sage.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 encoder MyEncoderClass to MyNewCodeClass under the name MyEncoderName. All I need to do is to write this line in the __init__.py file: MyNewCodeClass._registered_encoders["NameOfMyEncoder"] = MyEncoderClass and all instances of MyNewCodeClass will be able to use instances of MyEncoderClass.

  • fill the dictionary of its decoders in sage.coding.__init__ file. Example: I want to link the encoder MyDecoderClass to MyNewCodeClass under the name MyDecoderName. All I need to do is to write this line in the __init__.py file: MyNewCodeClass._registered_decoders["NameOfMyDecoder"] = MyDecoderClass and all instances of MyNewCodeClass will be able to use instances of MyDecoderClass.

As the class AbstractCode is not designed to be instantiated, 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 to self, and not to any member of the class of self. To know how to add an sage.coding.decoder.Decoder, please refer to the documentation of AbstractCode.

INPUT:

  • name – the string name for the decoder

  • decoder – 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().__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 to self, and not to any member of the class of self. To know how to add an sage.coding.encoder.Encoder, please refer to the documentation of AbstractCode.

INPUT:

  • name – the string name for the encoder

  • encoder – 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().__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 of self 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().__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)#

Correct the errors in word and returns a codeword.

INPUT:

  • word – an element in the ambient space as self

  • decoder_name – (default: None) Name of the decoder which will be used to decode word. The default decoder of self will be used if default value is kept.

  • args, kwargs – all additional arguments are forwarded to decoder()

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 as self

  • decoder_name – (default: None) Name of the decoder which will be used to decode word. The default decoder of self will be used if default value is kept.

  • args, kwargs – all additional arguments are forwarded to decoder()

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 of self 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) if classes is set to True, return instead a dict 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 code

  • encoder_name – (default: None) Name of the encoder which will be used to encode word. The default encoder of self 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 of self 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 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: 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) if classes is set to True, return instead a dict 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 of self.

  • encoder_name – (default: None) name of the decoder which will be used to decode word. The default decoder of self will be used if default value is kept.

  • nocheck – (default: False) checks if c is in self. You might set this to True to disable the check for saving computation. Note that if c is not in self and nocheck = True, then the output of unencode() is not defined (except that it will be in the message space of self).

  • 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 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: c = vector(GF(2), (1, 1, 0, 0, 1, 1, 0))
sage: C.unencode(c)
(0, 1, 1, 0)