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: |

### Description (last modified by )

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.

**Note:**See TracTickets for help on using tickets.