Opened 6 years ago
Closed 6 years ago
#20177 closed enhancement (fixed)
Better checks in GRS decoders
Reported by:  dlucas  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 6 years ago by
 Description modified (diff)
comment:2 Changed 6 years ago by
 Branch set to u/dlucas/checks_in_grs_decoders
comment:3 Changed 6 years ago by
 Commit set to d36fccfbef98ba0513bab1a5140c8667f8409d9c
 Status changed from new to needs_review
comment:4 Changed 6 years ago by
 Commit changed from d36fccfbef98ba0513bab1a5140c8667f8409d9c to 9f5f20d505adc41b34c03135eaef05ed0eb2ce5c
Branch pushed to git repo; I updated commit sha1. New commits:
9f5f20d  Slight optimization in Gao and BW decoders

comment:5 Changed 6 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 6 years ago by
 Branch changed from u/dlucas/checks_in_grs_decoders to u/jsrn/checks_in_grs_decoders
comment:7 Changed 6 years ago by
 Commit changed from 9f5f20d505adc41b34c03135eaef05ed0eb2ce5c to 8f82e4eed97fe685862404856007c92a84746032
 Reviewers set to 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 6 years ago by
 Status changed from needs_review to positive_review
I agree with your changes: giving positive review!
David
comment:9 Changed 6 years ago by
 Branch changed from u/jsrn/checks_in_grs_decoders to 8f82e4eed97fe685862404856007c92a84746032
 Resolution set to fixed
 Status changed from positive_review to 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