#19653: New decoders for Generalized Reed-Solomon codes
-------------------------------------+-------------------------------------
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:
Report Upstream: N/A | Work issues:
Branch: | Commit:
u/dlucas/grs_decoders | d70d6aa219a0472d1e254a23b6e0427f5cc7e1b2
Dependencies: #18928, #19897 | Stopgaps:
-------------------------------------+-------------------------------------
Comment (by dlucas):
Hello,
Thanks a lot for this thorough review work!
A general remark: at the time I wrote my thematic tutorial, there was no
decoder in Sage but `syndrome` and `nearest_neighbor`, which both are
quite slow - hence the small codes.
Now that we have fast decoders, I prefer to default to bigger codes than
[6,3]-GRS in examples, just to illustrate that we are fast over not-so-
small codes.
== `grs.py` ==
- I changed default decoder, which is now `Gao`.
- I rewrote the documentation of `precompute`, which is now called
`_polynomial_vanishing_at_alphas`. Maybe not the best name ever
(`alphas`?) but it's better than `precompute`. By the way, it's now a
private method, which I think is quite better.
- I rewrote both `partial_xgcd` as you advised. I also made these private
methods, which was actually written in the doc but not done in practice...
- No need to check the `input_space` in `__eq__` as it comes directly from
`code`. If you check the input of all my decoders, you'll see the user
only provides `code`, and the input space is extracted from `code`. As the
user has no direct way to influence this, it's not necessary to test it in
equality checks.
- Fixed my mistake in error-erasure decoder's `decoding_radius`.
- I removed the hideous, useless backslashes which were lurking all over
the place.
- I rewrote the error message related to the construction of a key
equation syndrome decoder over a GRS code including a 0 in its evaluation
points. I also introduced a test to illustrate this check.
By the way, Roth's book explains well the key equation decoding (that's
where I learnt it). Chp 6, pp 183-196, especially 6.3.1 and 6.3.2 related
to key equations, 6.4 for the Euclidean algorithm, 6.5 for Forney's
formulæ, 6.6 for a summary of the algorithm.
== `coding_theory.rst` ==
- I fixed all the typos you notice.
- I "upgraded" all my [6,3] codes to [12, 6] codes. Twice better!
- With these new codes, d/2 now equals to 3, I updated the number of
errors accordingly.
- I rewrote the weird sentences you noticed.
To answer your questions:
> l.567: "For instance, we did not mention how Sage manages bounds on
codes." Does it manage them ?
In a way. There's no central mechanism to take care of bounds, register
the best upper- and lower-bound computed so far while working on a code.
However, some bounds are implemented, and I hid them behind
`codes.bounds`.
So, Sage can somehow compute a few bounds on minimum distance, best
parameters for codes and so on.
> l.364, 442, 446, 550: why did you write "#random" ?
Because I don't control the output. E.g., l507 a random element of `C` is
picked, and l550 (example flagged `#random`) I use my channel to create
*randomly* some errors/erasures in it.
Now, there's a way to control this randomness:
1) Use "hardcoded" vectors.
2) Write `set_random_seed(42)` before any random method. In that way, we
guarantee the error pattern will always be the same, and thus can write
the output of our method. See `channel_construction.py`, ll 210-215 for an
example.
I chose to *not* use this, as it's an introductory tutorial, designed for
beginners. I wanted to illustrate the ability of channels to add random
errors in words, and of decoders to correct these random errors. Plus, for
beginners, finding a statement such as `set_random_seed` might be
confusing imho.
So I more or less sacrificed doctest purity on the altar of
understandability. Which is not a big deal as these methods are properly
doctested in their respective files.
David
--
Ticket URL: <http://trac.sagemath.org/ticket/19653#comment:19>
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.
