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: 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 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!

Change History (9)

comment:1 Changed 6 years ago by dlucas

  • Description modified (diff)

comment:2 Changed 6 years ago by dlucas

  • Branch set to u/dlucas/checks_in_grs_decoders

comment:3 Changed 6 years ago by dlucas

  • Authors set to David Lucas
  • Commit set to d36fccfbef98ba0513bab1a5140c8667f8409d9c
  • Status changed from new to needs_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 6 years ago by git

  • Commit changed from d36fccfbef98ba0513bab1a5140c8667f8409d9c to 9f5f20d505adc41b34c03135eaef05ed0eb2ce5c

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

9f5f20dSlight optimization in Gao and BW decoders

comment:5 Changed 6 years ago by dlucas

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 jsrn

  • Branch changed from u/dlucas/checks_in_grs_decoders to u/jsrn/checks_in_grs_decoders

comment:7 Changed 6 years ago by jsrn

  • 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 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 6 years ago by dlucas

  • Status changed from needs_review to positive_review

I agree with your changes: giving positive review!

David

comment:9 Changed 6 years ago by vbraun

  • Branch changed from u/jsrn/checks_in_grs_decoders to 8f82e4eed97fe685862404856007c92a84746032
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.