#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 jlavauzelle):
Hi,
Well, I don't know key equation decoding that much, so I didn't review all
the ticket yet. But I can post my first comments so that you start
modifying the code while I go further on key equation.
coding_theory.srt
* l.125: created --> create
* l.146: to build the [12, 6] GRS code --> to build a ...
* in the example which follows, you give a [6, 3] GRS code (instead of
[12, 6]). As your example is quite big, I think you should put the [6, 3]
everywhere.
* l.253: it seems that your decoder decodes 2 errors, whereas the [6,3]
GRS minimum distance is 4. It means the standard decoder you use is not a
half minimum distance one, which is quite inefficient for such a
structured code. Two possibilities: either you keep this standard decoder,
or you change it to Gao decoder. If you choose to change, do not forget to
modify the tutorial.
* l.337: put quotes around `EvaluationVector` and `C`
* l.352: match --> matches
* l.375: "The default encoder for a code is always one with vector
behaviour, so when we call..." To me, this sentence is strange. Maybe
"always uses vectors" or "always has a standard vector space as message
space".
* l.380: whose length are --> is
* l.390: remove the "then"
* l.364, 442, 446, 550: why did you write "#random" ?
* l.547: "over which has 1" sounds weird.
* l.567: "For instance, we did not mention how Sage manages bounds on
codes." Does it manage them ?
* l.585: "to create you own codes" --> your
decoders_catalog.py
* l.16: broken link with `grs.GRSKeyEquationSyndromeDecoder
<sage.coding.grs.GRSKeyEquationDecoder>`
grs.py
* l. 1083: I dislike the function naming: `precompute` is too general. I
also think your documentation is not precise enough : there are many monic
polynomials vanishing on the evaluation points; your function returns the
only one whose zeroes are exactly the evaluation points.
* l. 1107: `G = 1` --> `G = PolRing.one()`
* l. 1113: Your documentation is not very clear:
- "Returns the greatest common divisor of a and b." --> your function
doesn't do that
- "where d is the dimension of self.code() and k its dimension." -->
I think you meant the code length for d.
- OUTPUT: a tuple of polynomials (r, s) where r is to the xgcd of a
and b and s is the Bezout coefficient of a.
---> as it is written, it is not an *extended* gcd algorithm, as you
don't perform the "backward step". It doesn't either return a gcd, but one
of its multiples. And I think you should mention the Euclidean algorithm
somewhere. Maybe something like: "the algorithm performs the classical
Euclidean algorithm until a remainder has degree less than (n+k)/2, and
return (r,s) such that in the last step, we have r = a*s + b*t".
* l. 1280: Don't you need to check the `input_space` also (as in
GRSGaoDecoder and GRSBerlekampWelchDecoder)?
* l. 1383: if `e` is the number of erasures and `d` the minimum distance,
then the decoding_radius is `(d-1-e)//2`.
* l. 1372 and after: you can remove backslashes when you wrap a line
* l.1470: `(code.base_field())(0)` --> `code.base_field().zero()`.
Besides, your comment: `ValueError("Impossible to decode a GRS code which
contains 0 amongst its evaluation points")` is a bit wrong. I would
prefer: "This decoder can't be initialized with a GRS code whose
evaluation points contains 0"
* l. 1525 (partial xgcd): same comments as in the partial_xgcd of Gao
decoder.
Julien
--
Ticket URL: <http://trac.sagemath.org/ticket/19653#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.
