Decoders#

Representation of an error-correction algorithm for a code.

AUTHORS:

  • David Joyner (2009-02-01): initial version

  • David Lucas (2015-06-29): abstract class version

class sage.coding.decoder.Decoder(code, input_space, connected_encoder_name)#

Bases: sage.structure.sage_object.SageObject

Abstract top-class for Decoder objects.

Every decoder class for linear codes (of any metric) should inherit from this abstract class.

To implement an decoder, you need to:

  • inherit from Decoder

  • call Decoder.__init__ in the subclass constructor. Example: super().__init__(code, input_space, connected_encoder_name). By doing that, your subclass will have all the parameters described above initialized.

  • Then, you need to override one of decoding methods, either decode_to_code() or decode_to_message(). You can also override the optional method decoding_radius().

  • By default, comparison of Decoder (using methods __eq__ and __ne__ ) are by memory reference: if you build the same decoder twice, they will be different. If you need something more clever, override __eq__ and __ne__ in your subclass.

  • As Decoder is not designed to be instantiated, it does not have any representation methods. You should implement _repr_ and _latex_ methods in the subclass.

code()#

Return the code for this Decoder.

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: D = C.decoder()
sage: D.code()
[7, 4] linear code over GF(2)
connected_encoder()#

Return the connected encoder 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: D = C.decoder()
sage: D.connected_encoder()
Generator matrix-based encoder for [7, 4] linear code over GF(2)
decode_to_code(r)#

Correct the errors in r and returns a codeword.

This is a default implementation which assumes that the method decode_to_message() has been implemented, else it returns an exception.

INPUT:

  • r – a element of the input space of self.

OUTPUT:

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: word in C
True
sage: w_err = word + vector(GF(2), (1, 0, 0, 0, 0, 0, 0))
sage: w_err in C
False
sage: D = C.decoder()
sage: D.decode_to_code(w_err)
(1, 1, 0, 0, 1, 1, 0)
decode_to_message(r)#

Decode r to the message space of connected_encoder().

This is a default implementation, which assumes that the method decode_to_code() has been implemented, else it returns an exception.

INPUT:

  • r – a element of the input space of self.

OUTPUT:

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: D = C.decoder()
sage: D.decode_to_message(w_err)
(0, 1, 1, 0)
classmethod decoder_type()#

Returns the set of types of self.

This method can be called on both an uninstantiated decoder class, or on an instance of a decoder class.

The types of a decoder are a set of labels commonly associated with decoders which describe the nature and behaviour of the decoding algorithm. It should be considered as an informal descriptor but can be coarsely relied upon for e.g. program logic.

The following are the most common types and a brief definition:

Decoder type

Definition

always-succeed

The decoder always returns a closest codeword if the number of errors is up to the decoding radius.

bounded-distance

Any vector with Hamming distance at most decoding_radius() to a codeword is decodable to some codeword. If might-fail is also a type, then this is not a guarantee but an expectancy.

complete

The decoder decodes every word in the ambient space of the code.

dynamic

Some of the decoder’s types will only be determined at construction time (depends on the parameters).

half-minimum-distance

The decoder corrects up to half the minimum distance, or a specific lower bound thereof.

hard-decision

The decoder uses no information on which positions are more likely to be in error or not.

list-decoder

The decoder outputs a list of likely codewords, instead of just a single codeword.

might-fail

The decoder can fail at decoding even within its usual promises, e.g. bounded distance.

not-always-closest

The decoder does not guarantee to always return a closest codeword.

probabilistic

The decoder has internal randomness which can affect running time and the decoding result.

soft-decision

As part of the input, the decoder takes reliability information on which positions are more likely to be in error. Such a decoder only works for specific channels.

EXAMPLES:

We call it on a class:

sage: codes.decoders.LinearCodeSyndromeDecoder.decoder_type()
{'dynamic', 'hard-decision'}

We can also call it on a instance of a Decoder class:

sage: G = Matrix(GF(2), [[1, 0, 0, 1], [0, 1, 1, 1]])
sage: C = LinearCode(G)
sage: D = C.decoder()
sage: D.decoder_type()
{'complete', 'hard-decision', 'might-error'}
decoding_radius(**kwargs)#

Return the maximal number of errors that self is able to correct.

This is an abstract method and it should be implemented in subclasses.

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: D = codes.decoders.LinearCodeSyndromeDecoder(C)
sage: D.decoding_radius()
1
input_space()#

Return the input 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: D = C.decoder()
sage: D.input_space()
Vector space of dimension 7 over Finite Field of size 2
message_space()#

Return the message space of self’s connected_encoder().

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: D = C.decoder()
sage: D.message_space()
Vector space of dimension 4 over Finite Field of size 2
exception sage.coding.decoder.DecodingError#

Bases: Exception

Special exception class to indicate an error during decoding.