Definition of decoder's types

[David Lucas]

Hello,

As we agreed on the past few days, defining precisely our decoder's types is not that easy.

I copy hereafter the definitions I wrote while working on trac #19897. As I removed this table from this ticket, I opened a dedicated ticket, trac #20001 We should discuss these definitions so we all agree on before putting them in Sage.

• always-succeed: Always return a closest codeword if the number of errors is up to the decoding radius
• complete: Can decode every word in the ambient space of the code
• dynamic: The list of types will be dynamically updated at construction time
• half-minimum-distance: Its decoding radius is at most half the minimum distance of the code
• hard-decision: The symbols of the input word are taken from a finite set of values without any clue on their reliability
• list-decoder: Returns a list of codewords
• might-fail: Might fail at returning anything at all
• might-error: Might return a codeword which is not a closest codeword
• unique: Returns a single codeword

[Johan Rosenkilde]

Good. Please update the definitions wrt. what we discussed yesterday about the codeword, etc.

[Johan Rosenkilde]

Perhaps more informative:

dynamic: Some types depend on the parameters to the decoder.

[Johan Rosenkilde]

Could one write:

half-minimum-distance: The decoder corrects up to half the minimum distance, or a specific lower bound thereof.

I think we agreed to remove "might-error" since it's the absence of "always-succeed". By the same vein, we could remove "unique" I guess.

[Julien Lavauzelle]

Maybe I'm a bit biased by the fact I'm working on it, but would it be possible to consider a local decoding type, which would return a piece of the codeword (instead of the whole one) ?

This kind of decoding (e.g. locally decodable codes and locally recoverable codes) recently gained interest, but I don't know if it is standard enough to be put in your framework.

[Johan Rosenkilde]

"The framework" consists of the fact that we have types. The current list is completely non-exhaustive (for instance, it doesn't have "soft decoding" either). As soon as you finish your first local decoder, "local decoding" should be added as a type :-)

[Julien Lavauzelle]

Ok, nice ! I didn't understood how definitive and thorough this list aimed to be, now it's clear. :)

[Ricardo Alfaro]

I have some suggestions to reformat the decoder types. I wrote them in a txt file, but I do not see an attachment option here, so I am copying it below.. I am not expert on computer science verbiage, so you might find my suggestions in a mathematical verbiage.

---

Comments: To avoid some confusion, and clarify the purpose of the type, I suggest writing the type of a decoder as a vector? list? of three words.

The first entry would be the type of output it produces: Options: No output ; Single Output-correct; Single output-probable ; Multiple Output

The second entry would give the "closest upper bound" for the decoding_radius, where "upper bound" referes to the standards caharacteristic ofr this code: Options: half-minimum-distance ; covering-radius; minimum-distance ; length-dimension.

The third entry would be the type of the process: Options: Probablistic ; Deterministic

We can have a fourth entry to add other future options that give some more specific description of the decoder, but are not in the three categories mentioned above. Here you could enter the current options : Complete; hard-decision.

Some equivalences with the current words:

• always-succeed [Single Output-correct, -- , --]
• complete [-- , -- , complete]
• half-minimum-distance [ -- , half-minimum-distance, -- ]
• list-decoder [Multiple Output , -- , -- ]
• might-fail [No Output , -- , -- ]
• might-error [Single Output-probable, -- , -- ]

Regarding the "dynamic" type, I am somewhat confue: The definition above says: "The list of types will be updated at construction time"... This seems not to refer to a decoding type per se, but to the actual list of options. Also, the documentation refers to dynamic in : "If one checks the list of types of this decoder before constructing it, one will notice it contains the keyword dynamic. Indeed, the behaviour of the syndrome decoder depends on the maximum error weight one wants to handle, and how it compares to the minimum distance and the covering radius of code.

whihc means refers ot the dinamic nature of the number of errors we want to attempt to correct by giving a value to maximum_error_weight. I prefer this to be the actual definiton of dynamic and therefore does not need to be included as a decoder type.

[Johan Rosenkilde]

Perhaps all the text should be written as "The decoder ..." or similar. Other suggestions are:

• dynamic: Some of the decoder's types will only be determined at construction time (depends on the parameters).
• hard-decision: The decoder has no information on which positions are more likely to be in error or not.
• list-decoder: The decoder outputs a list of likely codewords, instead of just a single codeword.

Some new types we should probably add from the get-go:

• soft-decision: As part of the input, the decoder gets reliability information on which positions are more likely to be in error.
• bounded-distance: The minimum_distance() method of the decoder gives a bound on how many errors the decoder can correct.

For the doc string of decoder_types we should have some nice text. How about

Returns the set of types of ``self``.

The types of a decoder are a set of labels commonly associated with decoders which describe the nature and behaviour of the decoding algorithm. It should be considered as an informal descriptor but can be coarsely relied upon for e.g. program logic.

The following are the most common types and briefly what they mean.:

<The list with description above> 

[Johan Rosenkilde]

See #20001