A new structure for extended codes

[sagetrac-dlucas]

This ticket proposes a new implementation for extended codes.

It contains:

• a new code class, ExtendedCode

• a dedicated encoder to compute the generator matrix of an Extended Code.

• a dedicated decoder which uses the original code to correct errors

Depends on #19653

Component: coding theory

Author: David Lucas

Branch/Commit: e54ef7f

Reviewer: Julien Lavauzelle

Issue created by migration from https://trac.sagemath.org/ticket/20124

[sagetrac-dlucas]

Branch: u/dlucas/extended_codes

[sagetrac-dlucas]

Dependencies: #19653

[sagetrac-dlucas]

comment:3

I pushed the branch, this is now open for review.

---

Last 10 new commits:

c4ca177	Better doctests for Error-Erasure decoder, added sanity check on decode_to_messaage's input
a074cb8	Changed my helper methods into private methods
6ad583f	Fixed bug in KeyEquation decoder's decode_to_code, added sanity checks, enhanced doctests
fca099e	Added new sanity check on the output of BW and Gao decoder
57dbfbf	Rewrote random_element method
7953d60	Proper sanity checks for output of decode_to_* methods
8673ac5	Optimized a bit polynomial division in Gao and BW
e1b6b09	Merged now postive reviewed #19666 and fixed conflicts
f66aa6c	Merged branch related to GRS decoders
561ccd4	Added random_element method, fixed decoder so it handles properly list-decoders

[sagetrac-dlucas]

Author: David Lucas

[sagetrac-dlucas]

Commit: 561ccd4

[johanrosenkilde]

comment:4

Shouldn't LinearCode.extended_code use this?

[sagetrac-git]

Changed commit from 561ccd4 to 8b81ae3

[sagetrac-git]

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

e0f6692	Merge branch 'develop' into extended_codes
8b81ae3	extended_code() method over linear codes now returns an ExtendedCode object. Fixed related doctests.

[sagetrac-dlucas]

comment:6

Definitely. And it does now!

David

[sagetrac-git]

Changed commit from 8b81ae3 to 57ebe0c

[sagetrac-git]

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

57ebe0c

Updated to 7.3b1 and fixed conflicts

[sagetrac-dlucas]

comment:8

Hello,

I fixed conflicts that arose after the update to Sage 7.3beta1.
This is still open for review.

David

[jlavauzelle]

Changed branch from u/dlucas/extended_codes to u/jlavauzelle/extended_codes

[jlavauzelle]

Changed commit from 57ebe0c to 784975a

[jlavauzelle]

comment:10

Hi David,

I fixed some stuff in the doc, add sanity check and modified the decoding_radius method. Green light for the rest of the code.

Best,

Julien

---

New commits:

594e46c	Merge branch 'u/dlucas/extended_codes' of git://trac.sagemath.org/sage into u/jlavauzelle/extended_codes
0289f90	Merge branch 'u/dlucas/extended_codes' of git://trac.sagemath.org/sage into u/jlavauzelle/extended_codes
d05bfc4	Fix the documentation.
784975a	Added sanity checks. Fixed decoding_radius method arguments.

[jlavauzelle]

Reviewer: Julien Lavauzelle

[sagetrac-dlucas]

Changed branch from u/jlavauzelle/extended_codes to u/dlucas/extended_codes

[sagetrac-dlucas]

Changed commit from 784975a to 04e48ae

[sagetrac-dlucas]

comment:12

Hello,

There was a few broken doctests, which I fixed.
I agree with the changes you made on the ticket, and if you're ok with my fix, you can set this to positive_review.

Best,

David

---

New commits:

04e48ae

Fixed broken doctests

[jlavauzelle]

Changed branch from u/dlucas/extended_codes to u/jlavauzelle/extended_codes

[jlavauzelle]

Changed commit from 04e48ae to e54ef7f

[jlavauzelle]

comment:14

Hi David,

I agree with your fixes. Tests passed, doc is okay. I give the positive review.

Best,

Julien

---

New commits:

e54ef7f

Merge branch 'develop' into t/20124/extended_codes

[vbraun]

Changed branch from u/jlavauzelle/extended_codes to e54ef7f