#19623: Syndrome decoder is not a syndrome decoder
-------------------------------------+-------------------------------------
Reporter: dlucas | Owner:
Type: enhancement | Status: needs_work
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/jsrn/generic_decoders | 8a52ca1f60a52176fd588f76e4658ad549c7f249
Dependencies: | Stopgaps:
-------------------------------------+-------------------------------------
Changes (by jsrn):
* status: needs_review => needs_work
* commit: 590d18ccf6fdecd4d86aeb7e7d95c9d7a2502b4f =>
8a52ca1f60a52176fd588f76e4658ad549c7f249
Comment:
OK, so I looked through the new version of the ticket, and I took the
liberty of patching various things directly.
- I think the semantics that `decoding_radius` returns `d/2` when you
decode way beyond `d/2` makes no sense. I've changed `decoding_radius` to
have same semantics as `maximum_error_weight`, and I've removed
`self._decoding_radius`.
- I changed a number of docs and elaborated on the description of the
decoder. I added a note that it's exponential time. I didn't check
typesetting of the compiled docs, sorry.
- I renamed `self.lookup_table` to `self.syndrome_table`. Hope you agree
with me.
- I fixed how the types are dynamically assigned. It was done weirdly
before.
- I fixed several bugs in your by-now quite overworked
`_build_lookup_table`. There were bugs related to both the minimum
distance and covering radius, leading to catastrophic behaviour in the
final decoder. Firstly, since you hadn't added the zero-syndrome to your
table, both early termination and determination of minimum distance was
buggy. I added this to the table. Secondly, your early termination didn't
actually break out of the loop. Consequently, you never terminated early
and you usually did not correctly determine the covering radius. This was
blatantly obvious in the doctest you used everywhere, since the covering
radius for that code is actually 1. This leaves all the doctests currently
failing. I didn't fix it properly since I realised that a better example
is probably called for, and I didn't have time to do that myself now.
- Probably the above calls for some doctests that actually tests the
minimum-distance determining and covering-radius determining behaviour. I
leave it to you to be the judge of that.
Please, try to test your code and sanity check the output before you put
it up for review. This is getting bothersome...
----
New commits:
||[http://git.sagemath.org/sage.git/commit/?id=510cf2350798bfe88249c9797454ecdca49ffcfa
510cf23]||{{{Merge branch 'u/dlucas/generic_decoders' of
git://trac.sagemath.org/sage into 19623_syndrome_decoder}}}||
||[http://git.sagemath.org/sage.git/commit/?id=f2b87148ba4e1ca5d6ab6b2291e3780f0550518b
f2b8714]||{{{Rm if that will never happen}}}||
||[http://git.sagemath.org/sage.git/commit/?id=3158728ceb9fee5f5aee152047b1db06e12215ea
3158728]||{{{Modifications to doc strings}}}||
||[http://git.sagemath.org/sage.git/commit/?id=7e8473c01cb188be81cd87a7df9b8bb53a6ac50a
7e8473c]||{{{Fix decoder type handling and corner case wrt. all-zero-
syndrome}}}||
||[http://git.sagemath.org/sage.git/commit/?id=88f1824a153a37e8131e9b22dd196dbc060433aa
88f1824]||{{{Fix the decoding radius in examples}}}||
||[http://git.sagemath.org/sage.git/commit/?id=8a52ca1f60a52176fd588f76e4658ad549c7f249
8a52ca1]||{{{Actually early terminate in the early termination}}}||
--
Ticket URL: <http://trac.sagemath.org/ticket/19623#comment:35>
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.
