A new structure for Cyclic codes

[sagetrac-dlucas]

This ticket proposes a new implementation for cyclic codes.

It contains:

• a new code class, CyclicCode,
• a dedicated encoder to compute the generator matrix of a Cyclic Code, and
• an encoder whose message space is a polynomial ring.

This new structure has the following features:

• it is now possible to build a cyclic code in three different ways:
  • either by using the generator polynomial, which is passed as an argument,
  • either by using the defining set, which is passed as an argument (and can even be partial), or
  • by passing a linear code as argument. In that case, a generator polynomial will be computed (if possible) and used to reformat the input code as a cyclic code.
• it also comes with a method to compute the BCH bound, either from a constructed code or directly from the necessary parameters.

Depends on #20284

CC: @johanrosenkilde @ClementPernet

Component: coding theory

Keywords: sd75

Author: David Lucas, Julien Lavauzelle

Branch/Commit: d6f6bde

Reviewer: Daniel Augot, Yann Laigle-Chapuy

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

[sagetrac-dlucas]

Branch: u/dlucas/cyclic_code

[sagetrac-dlucas]

Author: David Lucas

[sagetrac-dlucas]

Commit: 6bcc1e7

[sagetrac-dlucas]

Dependencies: #20039

[sagetrac-dlucas]

comment:2

I pushed my work, as it is almost done.
There's still one bug to fix, documented in defining_set's broken docstring.

---

Last 10 new commits:

77f0629	Merged #19897
37bb7ac	Updated introductory thematic tutorial with a paragraph on decoders and message spaces
1220403	Merge branch 'develop' into grs_decoders
4340598	Removed deprecated import
b840682	Updated to 7.1beta3 and fixed conflict
d70d6aa	Removed `__ne__` methods
1808bb1	Some fixes to the decoder. Merged with GRS decoders branch to have fast examples
9c5405f	Fixed a bug because of which it was impossible to build a PC matrix when the subfield was the prime field
f3ca628	Merge branch 'subfield_subcode' into cyclic_code
6bcc1e7	Class for cyclic and two encoders for this class

[sagetrac-git]

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

d9618bf

Fixed bug in defining_set

[sagetrac-git]

Changed commit from 6bcc1e7 to d9618bf

[sagetrac-dlucas]

comment:4

Ok, found it and fixed it. It's now open for review.

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. Last 10 new commits:

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
5093dce	Update to 7.1beta5
f3b4b11	Fixed typo in Guruswami-Sudan doc
bab6bf7	Merge branch 'grs_decoders' into cyclic_code

[sagetrac-git]

Changed commit from d9618bf to bab6bf7

[sagetrac-dlucas]

comment:6

I merged with latest beta, fixed conflicts with GRS branch, this is still open for review.

[sagetrac-git]

Changed commit from bab6bf7 to fbfcb9f

[sagetrac-git]

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

c302015	Update to 7.1beta6
0e148fd	Fixed some broken doctests
c7350e2	Changed some doctests in code_construction
9de5ebf	Updated to 7.1
b034726	Fixed doctests in code_constructions.py
fbfcb9f	Changed imports in binary_code.pyx

[sagetrac-dlucas]

comment:8

I fixed the broken doctests in code_constructions.py.
They occured because the old implementation of CyclicCode allowed to use generator polynomials which do not divide x^n - 1, n being the length of the code.
I fixed this by replacing these polynomials (say, g) by gcd(g, x^n - 1).

This is still open for review.

[sagetrac-git]

Changed commit from fbfcb9f to 0ee7bb6

[sagetrac-git]

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

beadf6d	Merge branch 'develop' into cyclic_code
0ee7bb6	It is now possible to choose the primitive element to use as a root

[sagetrac-dlucas]

comment:11

I updated to the latest beta.
I also added a new optional argument: primitive_element. If filled, it will be used as the "base root" for the consecutive root sequence of the generator polynomial over the splitting field.

[sagetrac-git]

Changed commit from 0ee7bb6 to e459f10

[sagetrac-git]

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

97484cf	Merged into 7.3beta5, fixed conflicts, removed old field_embedding.py file
ea19a06	Removed subfield_subcode.py
61976d3	cyclic_code.py now uses relative_finite_field_extension.py
6335358	Fixed doctests in code_constructions.py
7366cbe	Enhanced module documentation, class' and global method's documentation
c328827	Removed `__ne__` methods
141bb64	Enhanced documentation of various methods in CyclicCode
a210e73	Improved documentation of both encoders
e459f10	Helper methods are now private methods

[sagetrac-dlucas]

Changed dependencies from #20039 to #20284

[sagetrac-dlucas]

comment:13

Hello,

I updated this ticket to latest beta version (7.3b5) and made some changes:

• I removed dependency to Subfield subcodes #20039.
• I improved documentation in many places, by defining terms more precisely.
• I removed now useless __ne__ methods
• I changed helper methods and made them private methods.

This is open for review.

David

[sagetrac-git]

Changed commit from 0f4fe27 to 6f235d6

[sagetrac-git]

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

2161696	Merged to latest beta (7.4.beta6).
75a222d	Rewrote doctest of two deprecated functions for best test coverage.
6f235d6	Doctests now pass.

[jlavauzelle]

comment:64

Hi,

I updated to the latest beta (7.4.beta6).

Still open for review.

Julien

[jlavauzelle]

Changed keywords from none to sd75

[sagetrac-git]

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

e74c828	Updated to latest beta (7.4.rc0).
8ee0d57	Updated to latest beta (7.4).

[sagetrac-git]

Changed commit from 6f235d6 to 8ee0d57

[sagetrac-ylchapuy]

Reviewer: Daniel Augot, Yann Laigle-Chapuy

[sagetrac-ylchapuy]

comment:66

Previous comments have been taken into account, tests pass (failures on gentoo seem unrelated), coverage for the new file is 100%, doc builds and looks OK.

All good for me.

[vbraun]

comment:67

Conflicts; Please wait for next beta and then fix the references:

[dochtml] [coding   ] /mnt/disk/home/release/Sage/local/lib/python2.7/site-packages/sage/coding/cyclic_code.py:docstring of sage.coding.cyclic_code:1: WARNING: citation not found: R06
[dochtml] [coding   ] /mnt/disk/home/release/Sage/local/lib/python2.7/site-packages/sage/coding/cyclic_code.py:docstring of sage.coding.cyclic_code:24: WARNING: citation not found: R06

[sagetrac-git]

Changed commit from 8ee0d57 to 75144a4

[sagetrac-git]

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

3bf1515	Updated to latest beta (7.5.beta0).
75144a4	Fixed references.

[sagetrac-git]

Changed commit from 75144a4 to d6f6bde

[sagetrac-git]

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

cc97a23	Merged with latest beta (7.5.beta2) and fixed conflicts.
d6f6bde	Shorter print for cyclic codes

[jlavauzelle]

comment:71

Hi,

I updated to the latest beta (7.5.beta2) and fixed conflicts.

Following #21691, I also produced shorter printing for cyclic codes (basically, I removed the generator polynomial which can have a quite long printing).

Best,

Julien

[vbraun]

Changed branch from u/jlavauzelle/cyclic_code to d6f6bde