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()
ordecode_to_message()
. You can also override the optional methoddecoding_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 ofself
.
OUTPUT:
- a vector of
code()
.
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 ofself
.
OUTPUT:
- a vector of
message_space()
.
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 ofself
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
‘sconnected_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
- inherit from
-
exception
sage.coding.decoder.
DecodingError
¶ Bases:
exceptions.Exception
Special exception class to indicate an error during decoding.