Changes between Version 1 and Version 4 of Ticket #18813


Ignore:
Timestamp:
Jun 29, 2015, 7:21:46 PM (7 years ago)
Author:
David Lucas
Comment:

Legend:

Unmodified
Added
Removed
Modified
  • Ticket #18813

    • Property Status changed from new to needs_review
    • Property Authors changed from to David Lucas
    • Property Cc Johan Rosenkilde Jean-Pierre Flori Vincent Delecroix Luca De Feo added
    • Property Dependencies changed from to #18376
    • Property Branch changed from to u/dlucas/decoder
    • Property Commit changed from to c2583d8334f5f9ff962a91a6e19d5978867a267c
  • Ticket #18813 – Description

    v1 v4  
    1717== Design ==
    1818
    19 Decoding depends on the algorithm used to find and correct the errors in a provided word.
    20 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.
    21 And there also exist probabilistic decoding algorithms, alongside with deterministic ones.
    22 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.
    2319
    24 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.
     20What "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.
    2521
    26 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.   
     22To 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.
    2723
    28 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.
    29 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`.
     24Decodig 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.
     25
     26As 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`.
     27
     28Furthermore, 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`.
    3029
    3130With 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.