Opened 7 years ago

Last modified 7 years ago

#18813 closed enhancement

New decoding structure for linear codes — at Version 1

Reported by: David Lucas Owned by:
Priority: major Milestone: sage-6.10
Component: coding theory Keywords:
Cc: Johan Rosenkilde, Jean-Pierre Flori, Vincent Delecroix, Luca De Feo, Clément Pernet Merged in:
Authors: Reviewers:
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges

Description (last modified by David Lucas)

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.

Notes

This ticket relies on the encoding structure proposed on trac #18376, as every decoder has to be linked with an encoder.

The original decoding algorithms, which were in decoder.py are now in two different Decoder objects in linear_code.py. I removed the guava one as the call to guava's decoding algorithm returned a guava error.

Change History (1)

comment:1 Changed 7 years ago by David Lucas

Description: modified (diff)
Note: See TracTickets for help on using tickets.