search

sagemath / sage

Main repository of SageMath
https://www.sagemath.org
Other
1.43k stars 479 forks source link

A new structure for Reed-Solomon codes in Sage #18928

Closed 1861b8a9-77f0-4f35-8431-8514a75b40d1 closed 8 years ago

1861b8a9-77f0-4f35-8431-8514a75b40d1 commented 9 years ago

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

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

1861b8a9-77f0-4f35-8431-8514a75b40d1 commented 9 years ago

Description changed:

--- 
+++ 
@@ -13,4 +13,6 @@

 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.
1861b8a9-77f0-4f35-8431-8514a75b40d1 commented 9 years ago

Branch: u/dlucas/grs

1861b8a9-77f0-4f35-8431-8514a75b40d1 commented 9 years ago

New commits:

d854eb8New Generalized Reed Solomon code object in Sage, coming with two encoders
1861b8a9-77f0-4f35-8431-8514a75b40d1 commented 9 years ago

Commit: d854eb8

1861b8a9-77f0-4f35-8431-8514a75b40d1 commented 9 years ago

Author: David Lucas

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

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

0645f58Updated to 6.9beta6 and fixed conflict
dc470beOverwrote some methods from linear_code
7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

Changed commit from d854eb8 to dc470be

1861b8a9-77f0-4f35-8431-8514a75b40d1 commented 9 years ago
comment:6

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

johanrosenkilde commented 9 years ago
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

johanrosenkilde commented 9 years ago

Description changed:

--- 
+++ 
@@ -7,7 +7,7 @@

 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 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).
7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

Changed commit from dc470be to f8c2d7a

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

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

f8c2d7aUpdated to 6.10beta0 and resolved conflicts
1861b8a9-77f0-4f35-8431-8514a75b40d1 commented 9 years ago

Changed dependencies from #18376, #18813 to #18376

1861b8a9-77f0-4f35-8431-8514a75b40d1 commented 9 years ago
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.

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

Changed commit from f8c2d7a to fa4dd71

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

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

fa4dd71Update to latest beta
1861b8a9-77f0-4f35-8431-8514a75b40d1 commented 9 years ago
comment:12

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

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 8 years ago

Changed commit from fa4dd71 to 1c1f182

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 8 years ago

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

1c1f182Merged with latest beta version and fixed conflicts
7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 8 years ago

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

aed4aa2Added grs.py in reference manual and fixed error in grs.py documentation
7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 8 years ago

Changed commit from 1c1f182 to aed4aa2

johanrosenkilde commented 8 years ago

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

johanrosenkilde commented 8 years ago

Changed commit from aed4aa2 to 0e82848

johanrosenkilde commented 8 years ago
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:

5578ea7Fixes to field checks at construction. Some doc corrections
af21dedSave private lists as tuples instead. Small changes to some docstrings and some examples.
2323380GRS parity check matrix from the dual code
667f89frm special impl. of GRSEvaluationVectorEncoder.unencode_nocheck
8733405Some improved doc-strings and doc-tests
229b5cfSome code beautification
fe7e9deSanity-checks on input for GRSEvaluationPolynomialEncoder
6e7013bSmall doc-string improvements in linear_code and encoder
0e82848More small docstring improvements
7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 8 years ago

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

91e2e3bDoc-string typesetting fix
7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 8 years ago

Changed commit from 0e82848 to 91e2e3b

1861b8a9-77f0-4f35-8431-8514a75b40d1 commented 8 years ago
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 commented 8 years ago
comment:19

Merde... Good catch.

1861b8a9-77f0-4f35-8431-8514a75b40d1 commented 8 years ago
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:

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

johanrosenkilde commented 8 years ago
comment:21

Got it, thanks.

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 8 years ago

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

eabe7e0Reworked coercion of evaluation pts and col mults and refined tests.
7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 8 years ago

Changed commit from 91e2e3b to eabe7e0

johanrosenkilde commented 8 years ago
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.

1861b8a9-77f0-4f35-8431-8514a75b40d1 commented 8 years ago

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

1861b8a9-77f0-4f35-8431-8514a75b40d1 commented 8 years ago

Reviewer: Johan Sebastian Rosenkilde Nielsen, David Lucas

1861b8a9-77f0-4f35-8431-8514a75b40d1 commented 8 years ago
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 commented 8 years ago

Changed branch from u/jsrn/grs to eabe7e0