Opened 2 years ago

Closed 2 years ago

#18928 closed enhancement (fixed)

A new structure for Reed-Solomon codes in Sage

Reported by: dlucas Owned by:
Priority: major Milestone: sage-6.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) Commit: eabe7e0c1bc48564540602846a77ee3744c093f4
Dependencies: #18376 Stopgaps:

Description (last modified by jsrn)

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 #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.

Change History (25)

comment:1 Changed 2 years ago by dlucas

  • Description modified (diff)

comment:2 Changed 2 years ago by dlucas

  • Branch set to u/dlucas/grs

comment:3 Changed 2 years ago by dlucas

  • Commit set to d854eb899cbe3affffe9e7a17a07def3fbcb37b6
  • Status changed from new to needs_review

New commits:

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

comment:4 Changed 2 years ago by dlucas

  • Authors set to David Lucas

comment:5 Changed 2 years ago by git

  • Commit changed from d854eb899cbe3affffe9e7a17a07def3fbcb37b6 to dc470becd64eeba63d64f328de5152c7aed83403

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

0645f58Updated to 6.9beta6 and fixed conflict
dc470beOverwrote some methods from linear_code

comment:6 Changed 2 years ago by dlucas

  • Milestone changed from sage-6.8 to sage-6.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 2 years ago by jsrn

  • 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 2 years ago by git

  • Commit changed from dc470becd64eeba63d64f328de5152c7aed83403 to f8c2d7afe506f08947d89ec77c2b189e3b7265e7

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

f8c2d7aUpdated to 6.10beta0 and resolved conflicts

comment:9 Changed 2 years ago by dlucas

  • 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 2 years ago by dlucas

  • Milestone changed from sage-6.9 to sage-6.10

comment:11 Changed 2 years ago by git

  • Commit changed from f8c2d7afe506f08947d89ec77c2b189e3b7265e7 to fa4dd71cefb1c124739a5b06b93e004c5cf451e6

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

fa4dd71Update to latest beta

comment:12 Changed 2 years ago by dlucas

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

comment:13 Changed 2 years ago by git

  • Commit changed from fa4dd71cefb1c124739a5b06b93e004c5cf451e6 to 1c1f1820e21b8c359279886154ac835dc96c563f

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

1c1f182Merged with latest beta version and fixed conflicts

comment:14 Changed 2 years ago by git

  • Commit changed from 1c1f1820e21b8c359279886154ac835dc96c563f to aed4aa279a390bbef9057c9d6c0dcc86d28589fd

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

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

comment:15 Changed 2 years ago by jsrn

  • Branch changed from u/dlucas/grs to u/jsrn/grs

comment:16 Changed 2 years ago by jsrn

  • Commit changed from aed4aa279a390bbef9057c9d6c0dcc86d28589fd to 0e828483e4674799ff0f8d6a328ccd854aef8cf1

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

comment:17 Changed 2 years ago by git

  • Commit changed from 0e828483e4674799ff0f8d6a328ccd854aef8cf1 to 91e2e3b20e0a903c57073ecd30b7cc73e25012b5

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

91e2e3bDoc-string typesetting fix

comment:18 Changed 2 years ago by dlucas

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

comment:19 Changed 2 years ago by jsrn

Merde... Good catch.

comment:20 Changed 2 years ago by dlucas

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.

comment:21 Changed 2 years ago by jsrn

Got it, thanks.

comment:22 Changed 2 years ago by git

  • Commit changed from 91e2e3b20e0a903c57073ecd30b7cc73e25012b5 to eabe7e0c1bc48564540602846a77ee3744c093f4

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

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

comment:23 Changed 2 years ago by jsrn

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 2 years ago by dlucas

  • Authors changed from David Lucas to David Lucas, Johan Sebastian Rosenkilde Nielsen
  • 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 2 years ago by vbraun

  • Branch changed from u/jsrn/grs to eabe7e0c1bc48564540602846a77ee3744c093f4
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.