Opened 6 years ago
Closed 6 years ago
#18928 closed enhancement (fixed)
A new structure for ReedSolomon codes in Sage
Reported by:  dlucas  Owned by:  

Priority:  major  Milestone:  sage6.10 
Component:  coding theory  Keywords:  
Cc:  Merged in:  
Authors:  David Lucas, Johan Sebastian Rosenkilde Nielsen  Reviewers:  Johan Sebastian Rosenkilde Nielsen, David Lucas 
Report Upstream:  N/A  Work issues:  
Branch:  eabe7e0 (Commits, GitHub, GitLab)  Commit:  eabe7e0c1bc48564540602846a77ee3744c093f4 
Dependencies:  #18376  Stopgaps: 
Description (last modified by )
This ticket proposes a new implementation for Generalized ReedSolomon codes in Sage. It contains:
 a new code class,
GeneralizedReedSolomonCode
, which wraps ReedSolomon code in the objectoriented structure introduced in #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 objectoriented structure, which allows the user to use specific methods and algorithms to encode (and later decode) words. It also introduces the notion of generalized ReedSolomon codes, which means that the user can now set a list of column multipliers for the code.
It also allows to compute paritycheck matrix and generator matrix from the parameters of the code, through dedicated methods. It allows superfast 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.
Change History (25)
comment:1 Changed 6 years ago by
 Description modified (diff)
comment:2 Changed 6 years ago by
 Branch set to u/dlucas/grs
comment:3 Changed 6 years ago by
 Commit set to d854eb899cbe3affffe9e7a17a07def3fbcb37b6
 Status changed from new to needs_review
comment:4 Changed 6 years ago by
comment:5 Changed 6 years ago by
 Commit changed from d854eb899cbe3affffe9e7a17a07def3fbcb37b6 to dc470becd64eeba63d64f328de5152c7aed83403
comment:6 Changed 6 years ago by
 Milestone changed from sage6.8 to sage6.9
I updated this ticket to latest beta, and added a few new methods, it's still in the needs_review state.
comment:7 Changed 6 years ago by
 Description modified (diff)
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
comment:8 Changed 6 years ago by
 Commit changed from dc470becd64eeba63d64f328de5152c7aed83403 to f8c2d7afe506f08947d89ec77c2b189e3b7265e7
Branch pushed to git repo; I updated commit sha1. New commits:
f8c2d7a  Updated to 6.10beta0 and resolved conflicts

comment:9 Changed 6 years ago by
 Dependencies changed from #18376, #18813 to #18376
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.
comment:10 Changed 6 years ago by
 Milestone changed from sage6.9 to sage6.10
comment:11 Changed 6 years ago by
 Commit changed from f8c2d7afe506f08947d89ec77c2b189e3b7265e7 to fa4dd71cefb1c124739a5b06b93e004c5cf451e6
Branch pushed to git repo; I updated commit sha1. New commits:
fa4dd71  Update to latest beta

comment:12 Changed 6 years ago by
Fixed merge conflicts after release of 6.10beta3. Still open for review.
comment:13 Changed 6 years ago by
 Commit changed from fa4dd71cefb1c124739a5b06b93e004c5cf451e6 to 1c1f1820e21b8c359279886154ac835dc96c563f
Branch pushed to git repo; I updated commit sha1. New commits:
1c1f182  Merged with latest beta version and fixed conflicts

comment:14 Changed 6 years ago by
 Commit changed from 1c1f1820e21b8c359279886154ac835dc96c563f to aed4aa279a390bbef9057c9d6c0dcc86d28589fd
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

comment:15 Changed 6 years ago by
 Branch changed from u/dlucas/grs to u/jsrn/grs
comment:16 Changed 6 years ago by
 Commit changed from aed4aa279a390bbef9057c9d6c0dcc86d28589fd to 0e828483e4674799ff0f8d6a328ccd854aef8cf1
I read through everything. I've polished a number of doctests and docstrings, both for clarity, correctness and paedagogy. Also, I've removed unencode_nocheck
on the vectorstyle encoder (since the inherited one is much faster), and I've added input sanity checks to encode
for the polynomialstyle 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 docstrings and doctests

229b5cf  Some code beautification

fe7e9de  Sanitychecks on input for GRSEvaluationPolynomialEncoder

6e7013b  Small docstring improvements in linear_code and encoder

0e82848  More small docstring improvements

comment:17 Changed 6 years ago by
 Commit changed from 0e828483e4674799ff0f8d6a328ccd854aef8cf1 to 91e2e3b20e0a903c57073ecd30b7cc73e25012b5
Branch pushed to git repo; I updated commit sha1. New commits:
91e2e3b  Docstring typesetting fix

comment:18 Changed 6 years ago by
Hello,
It seems that your changes actually broke something...
If you look in src/doc/en/thematic_tutorials.coding_theory.rst
lines 614619, 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 ReedSolomon Code over Finite Field of size 3
and the over Finite Field of size 3 looks weird to me.
David
comment:19 Changed 6 years ago by
Merde... Good catch.
comment:20 Changed 6 years ago by
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
andsrc/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.
comment:21 Changed 6 years ago by
Got it, thanks.
comment:22 Changed 6 years ago by
 Commit changed from 91e2e3b20e0a903c57073ecd30b7cc73e25012b5 to eabe7e0c1bc48564540602846a77ee3744c093f4
Branch pushed to git repo; I updated commit sha1. New commits:
eabe7e0  Reworked coercion of evaluation pts and col mults and refined tests.

comment:23 Changed 6 years ago by
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.
comment:24 Changed 6 years ago by
 Reviewers set to Johan Sebastian Rosenkilde Nielsen, David Lucas
 Status changed from needs_review to positive_review
Ok, tests pass and I agree with your changes. I give the green light. I added you as an author & a reviewer.
comment:25 Changed 6 years ago by
 Branch changed from u/jsrn/grs to eabe7e0c1bc48564540602846a77ee3744c093f4
 Resolution set to fixed
 Status changed from positive_review to closed
New commits:
New Generalized Reed Solomon code object in Sage, coming with two encoders