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:  sage7.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: 
Description (last modified by )
Some checks on the output on decode_to_code
for Gao, BerlekampWelch and KeyEquation 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
Description:  modified (diff) 

comment:2 Changed 7 years ago by
Branch:  → u/dlucas/checks_in_grs_decoders 

comment:3 Changed 7 years ago by
Authors:  → David Lucas 

Commit:  → d36fccfbef98ba0513bab1a5140c8667f8409d9c 
Status:  new → needs_review 
comment:4 Changed 7 years ago by
Commit:  d36fccfbef98ba0513bab1a5140c8667f8409d9c → 9f5f20d505adc41b34c03135eaef05ed0eb2ce5c 

Branch pushed to git repo; I updated commit sha1. New commits:
9f5f20d  Slight optimization in Gao and BW decoders

comment:5 Changed 7 years ago by
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
Branch:  u/dlucas/checks_in_grs_decoders → u/jsrn/checks_in_grs_decoders 

comment:7 Changed 7 years ago by
Commit:  9f5f20d505adc41b34c03135eaef05ed0eb2ce5c → 8f82e4eed97fe685862404856007c92a84746032 

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 welldefined (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 nonrandomization of some tests

comment:8 Changed 7 years ago by
Status:  needs_review → positive_review 

I agree with your changes: giving positive review!
David
comment:9 Changed 7 years ago by
Branch:  u/jsrn/checks_in_grs_decoders → 8f82e4eed97fe685862404856007c92a84746032 

Resolution:  → fixed 
Status:  positive_review → closed 
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:
Added input sanitization on GRS decoders
Changed checks on the output of decode_to_code methods, added input