A new structure for Reed-Solomon codes in Sage

[sagetrac-dlucas]

This ticket proposes a new implementation for Generalized Reed-Solomon codes in Sage.
It contains:

• a new code class, GeneralizedReedSolomonCode, which wraps Reed-Solomon code in the object-oriented structure introduced in Prepare linear_code for inheritance #18099,
• a first new encoder, GRSEvaluationVectorEncoder, which can encode words from a message space which is a vector space, and
• a second new encoder, GRSEvaluationPolynomialEncoder, which can encode words from a message space which is a polynomial ring.

This new implementation properly sets GRS codes in the object-oriented structure, which allows the user to use specific methods and algorithms to encode (and later decode) words. It also introduces the notion of generalized Reed-Solomon codes, which means that the user can now set a list of column multipliers for the code.

It also allows to compute parity-check matrix and generator matrix from the parameters of the code, through dedicated methods. It allows super-fast computation of certain - usually exponential - properties, such as weight distribution.

As GRS codes are now objects in Sage, it is also possible to ask a GRS code for its specific parameters (like the list of its evaluation points, or its column multipliers).

The two provided encoders follow the structure introduced in #18376.

This ticket also removes the old ReedSolomonCode method from the global namespace as it was deprecated more than a year ago (see #15445).

More details about GRS codes can be found in the docstring of the provided code.

Depends on #18376

Component: coding theory

Author: David Lucas, Johan Sebastian Rosenkilde Nielsen

Branch/Commit: eabe7e0

Reviewer: Johan Sebastian Rosenkilde Nielsen, David Lucas

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

[sagetrac-dlucas]

Branch: u/dlucas/grs

[sagetrac-dlucas]

New commits:

d854eb8

New Generalized Reed Solomon code object in Sage, coming with two encoders

[sagetrac-dlucas]

Commit: d854eb8

[sagetrac-dlucas]

Author: David Lucas

[sagetrac-git]

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

0645f58	Updated to 6.9beta6 and fixed conflict
dc470be	Overwrote some methods from linear_code

[sagetrac-git]

Changed commit from d854eb8 to dc470be

[sagetrac-dlucas]

comment:6

I updated this ticket to latest beta, and added a few new methods, it's still in the needs_review state.

[johanrosenkilde]

comment:7

This is not a review: just a comment. I slightly modified the description to underline the awesomeness of your latest commit ("overwrote a few methods"). Perhaps you could also add to the docstring of those overwritten methods that they are fast for this code (since a user would otherwise assume they are slow)?

Johan

[sagetrac-git]

Changed commit from dc470be to f8c2d7a

[sagetrac-git]

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

f8c2d7a

Updated to 6.10beta0 and resolved conflicts

[sagetrac-dlucas]

Changed dependencies from #18376, #18813 to #18376

[sagetrac-dlucas]

comment:9

I updated this ticket by resolving merge conflicts with latest beta, removing dependency to #18813 and fixing broken doctests in thematic tutorial related to coding theory.

It's now open for review as it does not depend on unmerged ticket anymore.

[sagetrac-git]

Changed commit from f8c2d7a to fa4dd71

[sagetrac-git]

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

fa4dd71

Update to latest beta

[sagetrac-dlucas]

comment:12

Fixed merge conflicts after release of 6.10beta3. Still open for review.

[sagetrac-git]

Changed commit from fa4dd71 to 1c1f182

[sagetrac-git]

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

1c1f182

Merged with latest beta version and fixed conflicts

[sagetrac-git]

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

aed4aa2

Added grs.py in reference manual and fixed error in grs.py documentation

[sagetrac-git]

Changed commit from 1c1f182 to aed4aa2

[johanrosenkilde]

Changed branch from u/dlucas/grs to u/jsrn/grs

[johanrosenkilde]

Changed commit from aed4aa2 to 0e82848

[johanrosenkilde]

comment:16

I read through everything. I've polished a number of doc-tests and doc-strings, both for clarity, correctness and paedagogy. Also, I've removed unencode_nocheck on the vector-style encoder (since the inherited one is much faster), and I've added input sanity checks to encode for the polynomial-style encoder.

If you can accept my modifications, I give this ticket the green light.

---

New commits:

5578ea7	Fixes to field checks at construction. Some doc corrections
af21ded	Save private lists as tuples instead. Small changes to some docstrings and some examples.
2323380	GRS parity check matrix from the dual code
667f89f	rm special impl. of GRSEvaluationVectorEncoder.unencode_nocheck
8733405	Some improved doc-strings and doc-tests
229b5cf	Some code beautification
fe7e9de	Sanity-checks on input for GRSEvaluationPolynomialEncoder
6e7013b	Small doc-string improvements in linear_code and encoder
0e82848	More small docstring improvements

[sagetrac-git]

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

91e2e3b

Doc-string typesetting fix

[sagetrac-git]

Changed commit from 0e82848 to 91e2e3b

[sagetrac-dlucas]

comment:18

Hello,

It seems that your changes actually broke something...

If you look in src/doc/en/thematic_tutorials.coding_theory.rst lines 614-619, you'll see that the following input:

sage: F.<a> = GF(3^2,"a")
sage: pts = [0,1,a,a^2,2*a,2*a+1]
sage: C = codes.GeneralizedReedSolomonCode(pts, 4)

is not accepted anymore.

Furthermore, the following:

sage: F.<a> = GF(3^2,"a")
sage: C = codes.GeneralizedReedSolomonCode(F.list()[:6], 4)

is accepted but sage: C returns [6, 4, 3] Generalized Reed-Solomon Code over Finite Field of size 3 and the over Finite Field of size 3 looks weird to me.

David

[johanrosenkilde]

comment:19

Merde... Good catch.

[sagetrac-dlucas]

comment:20

Yup. Oh, by the way I got tricked by that quite a lot of times (until I add these into my test script), there's two external files using methods from coding, namely:

• src/doc/en/constructions/linear_codes.rst and
• src/doc/en/thematic_tutorials/coding_theory.rst.

They do contain doctests, so remember to test these as well as the coding folder when you make changes.

[johanrosenkilde]

comment:21

Got it, thanks.

[sagetrac-git]

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

eabe7e0

Reworked coercion of evaluation pts and col mults and refined tests.

[sagetrac-git]

Changed commit from 91e2e3b to eabe7e0

[johanrosenkilde]

comment:23

Ok, coercion and conversion galore! I've rolled back to a refined version of your "let the vector constructor take care of conversion for me"-solution: now eval pts and col mults are converted simultaneously to find a common parent field. This forbids e.g. having eval pts in F(59) but col mults in F(61) (which was allowed with your version).
I also added a check and test for sanity of the dimension parameter.

[sagetrac-dlucas]

Changed author from David Lucas to David Lucas, Johan Sebastian Rosenkilde Nielsen

[sagetrac-dlucas]

Reviewer: Johan Sebastian Rosenkilde Nielsen, David Lucas

[sagetrac-dlucas]

comment:24

Ok, tests pass and I agree with your changes.
I give the green light.
I added you as an author & a reviewer.

[vbraun]

Changed branch from u/jsrn/grs to eabe7e0