Opened 7 years ago

Closed 7 years ago

#20177 closed enhancement (fixed)

Better checks in GRS decoders

Reported by: David Lucas Owned by:
Priority: major Milestone: sage-7.1
Component: coding theory Keywords:
Cc: Merged in:
Authors: David Lucas Reviewers: Johan Sebastian Rosenkilde Nielsen
Report Upstream: N/A Work issues:
Branch: 8f82e4e (Commits, GitHub, GitLab) Commit: 8f82e4eed97fe685862404856007c92a84746032
Dependencies: Stopgaps:

Status badges

Description (last modified by David Lucas)

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!

Change History (9)

comment:1 Changed 7 years ago by David Lucas

Description: modified (diff)

comment:2 Changed 7 years ago by David Lucas

Branch: u/dlucas/checks_in_grs_decoders

comment:3 Changed 7 years ago by David Lucas

Authors: David Lucas
Commit: d36fccfbef98ba0513bab1a5140c8667f8409d9c
Status: newneeds_review

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:

2d73b3fAdded input sanitization on GRS decoders
d36fccfChanged checks on the output of decode_to_code methods, added input

comment:4 Changed 7 years ago by git

Commit: d36fccfbef98ba0513bab1a5140c8667f8409d9c9f5f20d505adc41b34c03135eaef05ed0eb2ce5c

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

9f5f20dSlight optimization in Gao and BW decoders

comment:5 Changed 7 years ago by David Lucas

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.

comment:6 Changed 7 years ago by Johan Rosenkilde

Branch: u/dlucas/checks_in_grs_decodersu/jsrn/checks_in_grs_decoders

comment:7 Changed 7 years ago by Johan Rosenkilde

Commit: 9f5f20d505adc41b34c03135eaef05ed0eb2ce5c8f82e4eed97fe685862404856007c92a84746032
Reviewers: Johan Sebastian Rosenkilde Nielsen

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:

8f82e4eClarification and non-randomization of some tests

comment:8 Changed 7 years ago by David Lucas

Status: needs_reviewpositive_review

I agree with your changes: giving positive review!


comment:9 Changed 7 years ago by Volker Braun

Branch: u/jsrn/checks_in_grs_decoders8f82e4eed97fe685862404856007c92a84746032
Resolution: fixed
Status: positive_reviewclosed
Note: See TracTickets for help on using tickets.