New decoding structure for linear codes

[sagetrac-dlucas]

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

What "Decoding" means depends on the algorithm used to find and correct the errors in a provided word. For instance, there are 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. Others will return a list of codewords, which contain the original codeword. Some decoding algorithms are probabilistic, some are deterministic.

To describe the variety of behaviours, we introduce a list of "types", called _decoder_type which is a set of keywords describing the semantics of the decoding algorithm represented by the class.

Decodig usually recovers codewords close to the provided words. Some decoding algorithms, however, naturally decode directly to the message from which the codeword was obtained. This is e.g. the case with the Berlekamp-Welch or the Guruswami-Sudan algorithms. Since both uses are natural and in common use in theory and practice, we provide two different methods: decode_to_code and decode_to_message. The former corrects the errors and return an element from the code, while the latter corrects the errors and returns an element from a message space. 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.

As is discussed in #18376, a code can have many message spaces, and the map between a message space and the code is given by an Encoder. The decode_to_message will pertain to a certain such Encoder, so we introduce the string field _connected_encoder_name to point to this encoder. A user can acquire the actual Encoder object by calling Decoder.connected_encoder.

Furthermore, we propose here the exact same structure of registration for decoders as the one we introduced in #18376, and the same handling of it on the level of codes: each code will have a default_decoder, so if one does not want to be bothered by multiple decoding algorithms 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.

Depends on #18376

CC: @johanrosenkilde @jpflori @videlec @defeo @ClementPernet

Component: coding theory

Author: David Lucas

Branch/Commit: cf5ac32

Reviewer: Clément Pernet

Issue created by migration from https://trac.sagemath.org/ticket/18813

[sagetrac-dlucas]

Branch: u/dlucas/decoder

[sagetrac-dlucas]

Commit: c2583d8

[sagetrac-dlucas]

Dependencies: #18376

[sagetrac-dlucas]

New commits:

d79c19b	New abstract structure for decoders
d7d9520	Moved decoding methods from decoder.py to decoder classes in linear_code.py
19193de	Changes related to decoders in linear_code.py
c2583d8	Added a decoders_catalog file, added the import, added decoder-related files to the index

[sagetrac-dlucas]

Author: David Lucas

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

f286a64	Update to 6.9beta4
ee33302	Propaged comments got from #18376

[sagetrac-git]

Changed commit from c2583d8 to ee33302

[sagetrac-dlucas]

comment:7

I modified this tickets accordingly with reviewer's remarks in #18376, as these two are quite symmetrical. It's still ready for review.

[sagetrac-git]

Changed commit from ee33302 to 218b777

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

218b777

Updated to 6.10beta0 and fixed some elements according to #18376

[sagetrac-dlucas]

comment:10

I merged with latest beta and resolved conflicts.
I also updated some things accordingly with what was said in #18376, fixed a typo in encoder and added forgotten GPL licence blocks in encoders_catalog and decoders_catalog.

Still pending for review.

[sagetrac-git]

Changed commit from 218b777 to d5bdb8e

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

431183d	Updated to 6.10beta1
d5bdb8e	Fixed broken doctests and added one docstring

[sagetrac-dlucas]

comment:12

I fixed a few things patchbot was complaining about. It'll probably continue to complain on coverage but I don't see the point of adding doctests on a deprecated function so if the reviewer agrees I'm going to ignore this warning.
This is still pending for review.

[sagetrac-git]

Changed commit from d5bdb8e to fa63514

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

fa63514

Fixed conflicts after merge

[sagetrac-dlucas]

comment:14

I updated to latest beta and fixed the conflicts that arose after that merge. It's ready for review again.

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

0f29ad3

Lazy imported linear_code in sd_codes

[sagetrac-git]

Changed commit from fa63514 to 0f29ad3

[sagetrac-dlucas]

comment:28

I definitely agree. But these methods were written before me, and all I did here was to make them fit in the new structure.
Writing a true (and efficient) syndrome decoder is of course on the map, as a short term goal, but I think it does not belong to this ticket.

[ClementPernet]

comment:29

decoder.py line 184: connectoed -> connected

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

7c965dd

Integrated reviewer's comments

[sagetrac-git]

Changed commit from ddd1eb1 to 7c965dd

[sagetrac-dlucas]

comment:31

Last push fixes all your comments but the last one. I wait for the (potential) other remarks before writing another patch :)

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

68ab6b7

Fixed typo in decoder.py

[sagetrac-git]

Changed commit from 7c965dd to 68ab6b7

[sagetrac-dlucas]

comment:33

As you just told me it was ok, here's the fix for the typo you noticed.

[sagetrac-git]

Changed commit from 68ab6b7 to 51a7874

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

51a7874

Fixed typo in syndrome method docstring

[ClementPernet]

comment:35

All my remarks have been addressed.
I'm giving this ticket a positive review.

[ClementPernet]

Reviewer: cpernet

[ClementPernet]

Changed reviewer from cpernet to Clément Pernet

[vbraun]

comment:38

Merge conflict, possibly with #16080

[sagetrac-git]

Changed commit from 51a7874 to cf5ac32

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

c9f3a98	trac #16080 changing imports of urllib,urrlib2,urlparse for py3 compatibility
ab05e06	trac #16080 correct one doctest
3ac77d3	trac #16080 move back 3 imports inside functions
99699f6	trac #16080 now redone using six.moves
f848c3b	trac #16080 correcting some imports
3098f5f	Merge branch 'public/16080' into 6.10.b5
cf5ac32	Fixed merge conflict with 16080

[sagetrac-dlucas]

comment:40

I merged in #16080 and fixed the conflict in linear_code.py.
This should do the trick!

[ClementPernet]

comment:41

This merge works for me.
Positive review.

[vbraun]

Changed branch from u/dlucas/decoder to cf5ac32