Opened 7 months ago
Last modified 4 months ago
#31723 needs_review enhancement
Patterson Decoder for binary Goppa codes
Reported by:  ghgiucesare  Owned by:  

Priority:  major  Milestone:  sage9.5 
Component:  coding theory  Keywords:  coding theory, goppa codes, patterson decoder; 
Cc:  caruso, dimpase  Merged in:  
Authors:  Giuseppe Cesare, Ferdinando Zullo  Reviewers:  Xavier Caruso, Dima Pasechnik 
Report Upstream:  N/A  Work issues:  
Branch:  u/ghgiucesare/patterson_decoder (Commits, GitHub, GitLab)  Commit:  e62cd8a8b7b1af149b9d445d3b58535cc0702d35 
Dependencies:  Stopgaps: 
Description (last modified by )
Decoder for binary Goppa codes whose defining polynomials are square free which uses Patterson decoding algorithm in order to correct errors in words. The Patterson decoder makes use of the terminated extended Euclidean algorithm. For further details see
 Patterson: The algebraic decoding of Goppa codes, IEEE Transactions on Information Theory 21.2 (1975), pp. 203207.
Johan S. H. Rosenkilde gave us a feedback on the first draft of this decoder and also suggested us possible reviewers. So, we would like to thank him.
Attachments (1)
Change History (14)
Changed 7 months ago by
comment:1 Changed 7 months ago by
Could you post a branch, rather than an attachment?
comment:2 Changed 7 months ago by
 Description modified (diff)
comment:3 Changed 7 months ago by
 Branch set to u/ghgiucesare/31723patterson_decoder_for_binary_goppa_codes
comment:4 Changed 7 months ago by
 Branch u/ghgiucesare/31723patterson_decoder_for_binary_goppa_codes deleted
comment:5 Changed 7 months ago by
 Branch set to u/ghgiucesare/31723patterson_decoder_for_binary_goppa_codes
comment:6 Changed 7 months ago by
 Branch u/ghgiucesare/31723patterson_decoder_for_binary_goppa_codes deleted
comment:7 Changed 7 months ago by
 Branch set to u/ghgiucesare/31723patterson_decoder_for_binary_goppa_codes
comment:8 Changed 7 months ago by
 Branch u/ghgiucesare/31723patterson_decoder_for_binary_goppa_codes deleted
comment:9 Changed 7 months ago by
 Branch set to u/ghgiucesare/patterson_decoder
comment:10 Changed 7 months ago by
 Commit set to e62cd8a8b7b1af149b9d445d3b58535cc0702d35
after many attempts maybe I did it correctly now... sorry, this is my first ticket.
New commits:
e62cd8a  Decoder for binary Goppa codes whose defining polynomials are square free which uses Patterson decoding algorithm in order to correct errors in words.

comment:11 Changed 7 months ago by
 Status changed from new to needs_review
The method _partial_xgcd_gen
is called only once; is it really useful to have a special method for this? (Something that makes more sense according to me is to have a general shared function for this task which could be defined for example in the class handling univariate polynomials; but, more simply, you can just put your code directly in the caller method _decode_to_code_and_message
.)
Another general remark is that the documentation is not always correctly formatted. See https://doc.sagemath.org/html/en/developer/coding_basics.html#thedocstringofafunctioncontent for details. In addition you should probably add TESTS sections (in the documentation) for checking that errors are handled correctly.
comment:12 Changed 7 months ago by
Ok, we will make these changes then. Thank you.
comment:13 Changed 4 months ago by
 Milestone changed from sage9.4 to sage9.5
Setting a new milestone for this ticket based on a cursory review.
Patterson Decoder