#19623: Syndrome decoder is not a syndrome decoder
-------------------------------------+-------------------------------------
Reporter: dlucas | Owner:
Type: enhancement | Status: needs_review
Priority: major | Milestone: sage-7.1
Component: coding theory | Resolution:
Keywords: | Merged in:
Authors: David Lucas | Reviewers: Julien Lavauzelle
Report Upstream: N/A | Work issues:
Branch: | Commit:
u/dlucas/generic_decoders | 4d70e2c87e7c2e50171ee24ca7c6200ff29d0250
Dependencies: | Stopgaps:
-------------------------------------+-------------------------------------
Comment (by jsrn):
Hi,
Sounds cool! I'll take a closer look later on.
> I made some naming choices for the new decoder types here, which I like
you to discuss, especially `"might_create_decoding_error"` which is awful.
I did not have a better idea, sorry...
>
> By the way, this question is more or less related, does anyone remember
what a `complete` decoder is? I cannot remember this... Which once again
proves I need to write a proper list of these types in the introductory
thematic tutorial.
Yeah, `might_create_decoding_error` is pretty bad :-) `complete` refers to
the fact that it decodes every word in the ambient space. It's more or
less a synonym of one of the meanings of "maximum-likelihood", I guess,
whenever the decoder is also `unique`. I.e. Syndrome decoder is `complete`
when the decoding radius is the covering radius.
There is a type-discussion on this Issue on our bitbucket repo:
https://bitbucket.org/lucasdavid/sage_coding_project/issues/40/decoder-
introspection
The decoder you're doing now is similar to Power decoding of RS codes
(which I gave types `hard-decision`, `unique`, `might-fail`): both
decoders give a unique answer and return a closest codeword. However,
Power decoding "might fail" in the sense that it doesn't give *any answer
at all*. While SyndromeDecoder "might fail" in the sense that it gives you
*another* close codeword than what you sent. As opposed to this,
Guruswami-Sudan "always succeeds" in the sense that *your* codeword is
guaranteed to be on the list of outputs (up to the decoding radius).
We therefore seem to have an issue with what we mean by "might-fail" in
case of decoding beyond d/2. Perhaps "might-error" is a good choice, to
mirror the "decoding failure/decoding error" terminology of coding theory.
Yes, a list should be made of the "common" types (all we have used so far)
of decoders, and an explanation. In the doc-string of `decoder_type`,
there should be a clear explanation on how to look up what they mean.
(another ticket of course). Perhaps even in the doc-string for
`decoder_type`, if the explanations can be made short enough, since the
function is always the original `Decoder.decoder_type`.
Best,
Johan
--
Ticket URL: <http://trac.sagemath.org/ticket/19623#comment:27>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at https://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/d/optout.
