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

Returns the set of types of self. These types describe the nature of self and its decoding algorithm.

EXAMPLES:

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.