#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 | 7cbcca2969f5a72776eaff64951318a6c3c89a84
Dependencies: #18928, #19897 | Stopgaps:
-------------------------------------+-------------------------------------
Comment (by jlavauzelle):
*** Key equation decoder ***
That's fine. I'm convinced we can do more efficient (e.g. "cache"
`alpha[j]**l`, doing matrix-vector computation, or maybe using some kind
of parity-check matrix) to compute the syndrome polynomial, but that's
clearly not the point of the ticket.
*** Runs ***
Well, I don't know if that's important to fix them, but I found some non-
caught (or badly caught) running errors:
- when running [`Gao`/`Key`/`Berlekamp`] decoder with a GRS code of
dimension k = n (a "full code" with distance 1, ok that's a weird
code...): the decoder is built, but when trying to `decode_to_message` a
word `y`, it begins by checking if `y` is a codeword by compute its
syndrome, which is done by using the parity check matrix, which doesn't
exist due to dimension issues. Thus the following error is raised:
`ValueError: The dimension must be a positive integer at most the length
of the code.` I suggest two solutions (but the second one seems to be the
best one, see remark below):
- we prevent the construction of a decoder for such a code (in a way,
it has no sense to decode that code)
- the decoder returns the input word
- when running [`Gao`/`Key`/`Berlekamp`] decoder with a GRS code of
dimension k=n-1 (distance 2) on a noisy word with 1 error, some weird
things happen (for the moment, I don't have any solution for these
issues):
- for `KeyEquationDecoder`, it tries to decode and fails almost every
time (I would say with proba (q-1)/q, as if it was random).
- for `GaoDecoder`, `decode_to_code` raises `ValueError: The
polynomial to encode must have degree at most k-1 when trying to re-encode
the message`. It means `decode_to_message` outputs a polynomial with too
high degree (k).
- for `BerlekampDecoder`, that's a random mix of the two previous
behaviour (sooo weird...).
In fact, the previous issues are more important that I thought. For
example, see the following script:
{{{
C = codes.GeneralizedReedSolomonCode(GF(16,'a').list()[1:], 12)
D = C.decoder(C.decoders_available()[2])
Chan = channels.ErrorErasureChannel(C.ambient_space(),0,3)
c = C.random_element()
y,era = Chan(c)
mp = D.decode_to_message(tuple([z, era]))
}}}
The [15,12,4]-GRS code is clearly not a trivial code, but I still get the
strange error from the "full code", because in the `ErasureError` decoding
algorithm, we puncture the code on erasures, and call the error decoding
algorithm on the punctured code (which is the full code).
*** Another remark ***
If you set Gao decoder as the default decoder for GRS, you should also set
`EvaluationPolynomial` as the default encoder, otherwise we do not have
`decode_to_message(encode(x)) = x`.
--
Ticket URL: <http://trac.sagemath.org/ticket/19653#comment:21>
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.
