#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:
-------------------------------------+-------------------------------------
Comment (by dlucas):
Replying to [comment:9 jlavauzelle]:
> 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`.
True enough. I'll made the changes.
> * 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)
> }}}
I have the same feeling, I'll perform some tests to verify this
(empirically), and I will remove these checks if they prove themselves
useless.
> * 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.
Indeed, this is a copy-paste mistake. Regarding the handling of `is_zero`,
I'm not sure that's the best behaviour. I somehow feel the user still
wants the table to be built, as, after all, the user will use this decoder
to actually correct errors. So, even if it's not used when decoding a
vector with a zero syndrome, I still feel it should be built on the first
decoding attempt, whichever the syndrome of the word to decode. I'm not
strongly for this solution though, so if you think it's a bad idea, I'm ok
to drop it.
> * 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`.
Well, it's more a design choice that a question of bounds here, as
`number_errors` is a proper getter method for the number of errors chosen
at construction time, while `decoding_radius` is a method we have for
every decoder (got from the abstract class `Decoder`) and made for the
user to catch the maximal number of errors the user's decoder can decode.
So, the user should not use `number_errors`, it's more the internal getter
to avoid ugly direct calls like `self._number_errors`. But you're right,
it's somehow confusing... What about changing `number_errors` into a
private method?
> * 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`.
Indeed. That's why I added a note regarding this issue in the class'
documentation. Rereading it, I should make it more explicit though, as it
does not state clearly that if you go further a certain number of errors
`t`, you probably won't get the original codeword in which you got `t`
errors.
Regarding the descriptive message, well, I just wanted it to remind all
the input parameters the user set. I'll try to find a better way to say
it.
David
--
Ticket URL: <http://trac.sagemath.org/ticket/19623#comment:11>
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.
