#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 | b2b9e8270a95e7478760532827be04cecb906510
Dependencies: | Stopgaps:
-------------------------------------+-------------------------------------
Comment (by jsrn):
Hi
> - `covering_radius` now returns `min(maximum_error_weight, half-min-
dist`). I changed its docstring and added a note to explain it performs a
minimum distance computation, which can be long...
You mean `decoding_radius` I'm sure :-) But you completely misunderstood
what I wrote before, I'm afraid. By your updated docstring, then clearly
`decoding_radius` should return `maximum_error_weight`.
I just had a pretty cool idea: When building the lookup-table you're
actually *computing the minimum distance*! If `t` is the lowest weight at
which you detect a collision, i.e. see a syndrome that has already
occurred before, then the minimum distance is `2t` or `2t-1` (you can
determine which it was by inspecting the weight of the errors that
collided). In any case, "half the minimum distance decoding" will be `t`
errors.
If `maximum_error_weight < t` then `_build_lookup_table` will never see a
collision, and so it can *know* that the minimum distance is greater.
Hence, it can know it is a bounded distance decoder. If
`maximum_error_weight = t`, then a collision will be seen at this weight,
and so the decoder can know it is a minimum distance decoder. If
`maximum_error_weight > t`, then it knows that it will sometimes fail, but
it will mostly decode up to `min(maximum_error_weight, covering_radius)`
(see below). There should be some appropriate keywords in `type`
distinguishing these cases.
Once the infrastructure we talked about previously is in place, the `Code`
could be informed of this minimum distance.
In the same vein, you're *also* computing the covering radius. For if
`w+1` is the first weight where *every* error weight collides with a
lower-weight error, then `w` is the covering radius.
Now, if `maximum_error_weight < w`, then `_build_lookup_table` will never
see this event, and so it clearly doesn't determine the covering radius.
In that case, `maximum_error_weight` is truly the decoding radius (except
that if `maximum_error_weight >= d/2$` then it might sometime return
another minimum weight error, and not the one that was added).
If `maximum_error_weight > w`, then we *know* that incorrect decoding will
be performed for *all* error patterns of weight `> w`. So in
`maximum_error_weight()` and the string representations, and elsewhere,
should we really return the user-supplied `maximum_error_weight` and not
`w`? It's not terribly important to me, except that it should be possible
for the user to retrieve `w` (possibly by informing `Code` of this
covering radius and the user then calls `Code.covering_radius`). I would,
though, posit that in case `maximum_error_weight` is used instead of `w`,
then `maximum_error_weight` should be capped at `n-k` at construction
time. Higher than that clearly makes no sense.
> - I rewrote `_list_all_error_values`, which now takes an input parameter
`weight` and builds only the exhaustive list of error values of weight
`weight`. It now uses `cartesian_product` instead of `Permutation`.
There's no need to return a `list`. Just return the `cartesian_product`
object. And in the inner `for`-loop of `_build_lookup_table`, instead of
looping over `j`, do a `for error in error_values_of_weight[t]` or
something.
In Python, a `list` is concretely instantiated and takes space in memory.
A
`generating_expression` takes next to no memory. When you can, use
`generating_expression`.
We're down to aesthetics now, but wouldn't it be nicer to inline
`_list_all_error_values` so you don't need to construct `l` time and
again? You could e.g. make a generating expression which generates the
generating expressions:
{{{
error_position_tables = [ cartesian_product([l]*weight) for weight in
range(maximum_error_weight) ]
}}}
> - Finally, I fixed a few broken doctests, and removed the keyword
`complete` in `decoder_type` as computing the covering radius can only be
done by a call to a method forcing the use of optional library Guava.
Ticket #19913 proposes a new `covering_radius` method which has a Python
alternative to Guava. Once this ticket (or #19913) gets reviewed, I'll do
the appropriate updates wrt. covering radius in the remaining one.
By my arguments above, you can add `complete` whenever the covering radius
was determined during `_build_lookup_table`.
Also, I just noticed that `__eq__` is wrong: it doesn't compare
`maximum_error_weight`.
Best,
Johan
--
Ticket URL: <http://trac.sagemath.org/ticket/19623#comment:17>
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.
