Opened 16 months ago

Last modified 4 months ago

#31723 needs_review enhancement

Patterson Decoder for binary Goppa codes

Reported by: gh-giucesare Owned by:
Priority: major Milestone: sage-9.7
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/gh-giucesare/patterson_decoder (Commits, GitHub, GitLab) Commit: e62cd8a8b7b1af149b9d445d3b58535cc0702d35
Dependencies: Stopgaps:

Status badges

Description (last modified by gh-giucesare)

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

  1. Patterson: The algebraic decoding of Goppa codes, IEEE Transactions on Information Theory 21.2 (1975), pp. 203-207.

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)

patterson_decoder.py (12.0 KB) - added by gh-giucesare 16 months ago.
Patterson Decoder

Download all attachments as: .zip

Change History (16)

Changed 16 months ago by gh-giucesare

Patterson Decoder

comment:1 Changed 16 months ago by dimpase

Could you post a branch, rather than an attachment?

comment:2 Changed 16 months ago by gh-giucesare

  • Description modified (diff)

comment:3 Changed 16 months ago by gh-giucesare

  • Branch set to u/gh-giucesare/31723-patterson_decoder_for_binary_goppa_codes

comment:4 Changed 16 months ago by gh-giucesare

  • Branch u/gh-giucesare/31723-patterson_decoder_for_binary_goppa_codes deleted

comment:5 Changed 16 months ago by gh-giucesare

  • Branch set to u/gh-giucesare/31723-patterson_decoder_for_binary_goppa_codes

comment:6 Changed 16 months ago by gh-giucesare

  • Branch u/gh-giucesare/31723-patterson_decoder_for_binary_goppa_codes deleted

comment:7 Changed 16 months ago by gh-giucesare

  • Branch set to u/gh-giucesare/31723-patterson_decoder_for_binary_goppa_codes

comment:8 Changed 16 months ago by gh-giucesare

  • Branch u/gh-giucesare/31723-patterson_decoder_for_binary_goppa_codes deleted

comment:9 Changed 16 months ago by gh-giucesare

  • Branch set to u/gh-giucesare/patterson_decoder

comment:10 Changed 16 months ago by gh-giucesare

  • Commit set to e62cd8a8b7b1af149b9d445d3b58535cc0702d35

after many attempts maybe I did it correctly now... sorry, this is my first ticket.


New commits:

e62cd8aDecoder 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 16 months ago by caruso

  • 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#the-docstring-of-a-function-content for details. In addition you should probably add TESTS sections (in the documentation) for checking that errors are handled correctly.

comment:12 Changed 16 months ago by gh-giucesare

Ok, we will make these changes then. Thank you.

comment:13 Changed 13 months ago by mkoeppe

  • Milestone changed from sage-9.4 to sage-9.5

Setting a new milestone for this ticket based on a cursory review.

comment:14 Changed 8 months ago by mkoeppe

  • Milestone changed from sage-9.5 to sage-9.6

Stalled in needs_review or needs_info; likely won't make it into Sage 9.5.

comment:15 Changed 4 months ago by mkoeppe

  • Milestone changed from sage-9.6 to sage-9.7
Note: See TracTickets for help on using tickets.