#19623: Syndrome decoder is not a syndrome decoder
-------------------------------------+-------------------------------------
Reporter: dlucas | Owner:
Type: enhancement | Status: needs_work
Priority: major | Milestone: sage-7.0
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 | fc79446d6948143d32a9065410453379c79ef2b2
Dependencies: | Stopgaps:
-------------------------------------+-------------------------------------
Changes (by jlavauzelle):
* status: needs_review => needs_work
* reviewer: => Julien Lavauzelle
* cc: jlavauzelle (added)
Comment:
I add some new remarks:
* I think you could remove your `_list_all_error_values` method. For each
step of the main loop (//i.e.// for a given error weight `i`), you only
need `Permutations(l, i)`, with `l` equals to `i` times the list of non-
zero elements of GF(q). Thus you can save a lot of memory, using the both
iterators on `Permutations` and on `Subsets`.
* I'm not completely sure of what I'm saying now, but you can notice that
the ordering induced by the "composition" of these iterators respects the
one you want for updating the table (//i.e.// first hamming weight, then
lexicographic order). So in theory, you might never enter these blocks:
{{{
if (e.hamming_weight() == e_cur.hamming_weight()
and e < e_cur):
stop = False
lookup[s] = copy(e)
elif e.hamming_weight() < e_cur.hamming_weight():
stop = False
lookup[s] = copy(e)
}}}
* In `decode_to_code()`, you talk about decoding into the message space,
but I think you meant into the code instead. In the same function, you may
handle the case `s.is_zero()` before building the lookup table.
* I don't really understand the difference between `number_errors()` and
`decoding_radius()`. Is it a tight bound on the maximum number of errors
the decoder can decode ? Or just a way to remember what the user has set
in the `number_errors` parameter of the constructor ? Maybe you could make
them more explicit, like `error_max_weight`.
* I also think that your description of the decoder ("correcting up to
`number_errors` errors") could fool the user, as `number_errors` may be
set up to `n` whereas the decoder will never decode an error of weight
`n`.
--
Ticket URL: <http://trac.sagemath.org/ticket/19623#comment:9>
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.
