Better checks in GRS decoders

[sagetrac-dlucas]

Some checks on the output on decode_to_code for Gao, Berlekamp-Welch and Key-Equation Syndrome decoders are actually useless.

I also noticed that the nature of the input code of GRS decoders is never checked: one can perform the following:

C = codes.RandomLinearCode(10, 4, GF(7))
D = codes.decoders.GRSGaoDecoder(C)

and actually construct the decoder... Whose decoding methods will utterly fail with a terrible error message!

Component: coding theory

Author: David Lucas

Branch/Commit: 8f82e4e

Reviewer: Johan Sebastian Rosenkilde Nielsen

Issue created by migration from https://trac.sagemath.org/ticket/20177

[sagetrac-dlucas]

Description changed:

[sagetrac-dlucas]

Branch: u/dlucas/checks_in_grs_decoders

[sagetrac-dlucas]

Commit: d36fccf

[sagetrac-dlucas]

comment:3

I removed one useless check, fixed the bizarre ones, and added input sanitization on __init__ in every GRS decoder.

This is now open for review.

---

New commits:

2d73b3f	Added input sanitization on GRS decoders
d36fccf	Changed checks on the output of decode_to_code methods, added input

[sagetrac-dlucas]

Author: David Lucas

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

9f5f20d

Slight optimization in Gao and BW decoders

[sagetrac-git]

Changed commit from d36fccf to 9f5f20d

[sagetrac-dlucas]

comment:5

I regrouped the checks in a private method _decode_to_code_and_message which returns both the message and the corresponding codeword.

That way, if one does D.decode_to_code(r), it wont compute the codeword twice.

It's still open for review.

[johanrosenkilde]

Changed branch from u/dlucas/checks_in_grs_decoders to u/jsrn/checks_in_grs_decoders

[johanrosenkilde]

comment:7

It looks good. I modified the tests that showed failure behaviour under too many errors: "too many errors" is of course not well-defined (since the receiver doesn't know the sent codeword); the relevant measure is the distance to any codeword. Your test generated random errors of weight t+1, where t is the decoding radius, and that would still decode into some other codeword sometimes (albeit with extremely low probability). I now changed it to a fixed example.

If you can accept this, please set it to positive review.

---

New commits:

8f82e4e

Clarification and non-randomization of some tests