Decoder

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 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(SubclassName, self).__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()

Returns 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()
Linear code of length 7, dimension 4 over Finite Field of size 2
connected_encoder()

Returns 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 Linear code of length 7, dimension 4 over Finite Field of size 2
decode_to_code(r)

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

Decodes r to the message space of meth:\(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. These types describe the nature of self and its decoding algorithm.

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

EXAMPLES:

We call it on a class:

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

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', 'unique'}
decoding_radius(**kwargs)

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

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

Returns 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: exceptions.Exception

Special exception class to indicate an error during decoding.