#18813: New decoding structure for linear codes
-----------------------------+----------------------------
Reporter: dlucas | Owner:
Type: enhancement | Status: new
Priority: major | Milestone: sage-6.8
Component: coding theory | Keywords:
Merged in: | Authors:
Reviewers: | Report Upstream: N/A
Work issues: | Branch:
Commit: | Dependencies:
Stopgaps: |
-----------------------------+----------------------------
For now, linear codes don't have a proper structure for decoding, where
"decoding" means using an error-correction algorithm to recover the
original codeword.
We propose in this ticket a new structure, designed to handle word ->
codeword and word -> message transformations.
We provide the following:
- An abstract class `Decoder`, for inheritances purposes. Every
`Decoder` will inherit from this class. It contains:
- a default constructor;
- `decode_to_code` and `decode_to_message` default implementation;
- several methods to get information on the instance of the class
and
- explanations on what to do to create a new decoder subclass.
- An exception class `DecodingFailure`, for errors related to decoding
algorithms.
- Methods for decoding handling in `AbstractLinearCode` (see Design)
== Design ==
Decoding depends on the algorithm used to find and correct the errors in a
provided word.
For instance, there exists decoding algorithms able to locate and correct
up to a certain amount of errors, and will fail if there is more errors
than this bound. Some others will return a list of codewords containing
the original codeword.
And there also exist probabilistic decoding algorithms, alongside with
deterministic ones.
To describe these behaviours, we introduced a list of type, called
`_decoder_type` which is a set of keywords describing the decoding
algorithm used in the class.
Besides, different decoding algorithms might return different elements,
even if they work for the same code family. For instance, with Reed-
Solomon codes, key equation decoding returns a vector, while Berlekamp-
Welch decoding algorithm returns a polynomial. To keep this behaviour, we
added a field `connected_encoder_name`, which contains the name of the
encoder used by the decoder when it comes to encode/unencode operations.
We also propose to the user two different decoding methods,
`decode_to_code` and `decode_to_message`, the former correcting the errors
and returning an element from the code, the latter correcting the errors
and returning an element from the message space of its
`connected_encoder`. Thanks to a default implementation, reimplmenting
both is not needed. One only needs to override one of these two methods in
a `Decoder` class, and the default implementation will be used to perform
the other one.
Furthermore, we propose here the exact same structure of registration for
decoders as the one we introduced in #18376, namely. We also propose the
same default behaviour for codes.
Each code will have a `default_encoder`, so if one does not want to be
bothered by multiple decoding algorithm when he just wants to decode a
word `y` for his code `C`, all he has to do is to write
`C.decode_to_code(y)`, and the default decoder will be used to correct the
errors in `y`.
With this structure, we are able to represent different decoding
algorithms for each code, even if they have different behaviour. We also
have a versatile structure which allows specific experimentation on chosen
decoding algorithms alongside with generic decodings in which the
algorithm does not matter.
== Note ==
This ticket relies on the encoding structure proposed on trac #18376, as
every decoder has to be linked with an encoder.
--
Ticket URL: <http://trac.sagemath.org/ticket/18813>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/d/optout.
