Opened 7 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.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/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 7 months ago.
Patterson Decoder

Download all attachments as: .zip

Change History (14)

Changed 7 months ago by gh-giucesare

Patterson Decoder

comment:1 Changed 7 months ago by dimpase

Could you post a branch, rather than an attachment?

comment:2 Changed 7 months ago by gh-giucesare

  • Description modified (diff)

comment:3 Changed 7 months ago by gh-giucesare

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

comment:4 Changed 7 months ago by gh-giucesare

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

comment:5 Changed 7 months ago by gh-giucesare

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

comment:6 Changed 7 months ago by gh-giucesare

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

comment:7 Changed 7 months ago by gh-giucesare

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

comment:8 Changed 7 months ago by gh-giucesare

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

comment:9 Changed 7 months ago by gh-giucesare

  • Branch set to u/gh-giucesare/patterson_decoder

comment:10 Changed 7 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 7 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 7 months ago by gh-giucesare

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

comment:13 Changed 4 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.

Note: See TracTickets for help on using tickets.