Bug in Reed-Solomon encoder and error-erasure decoder

[johanrosenkilde]

The following two snippets demonstrate two bugs when working with GeneralizedReedSolomonCode:

sage: F = GF(59)
sage: n, k = 40, 12
sage: C = codes.GeneralizedReedSolomonCode(F.list()[:n], k)
sage: D = codes.decoders.GRSErrorErasureDecoder(C)
sage: y = (vector(F, [0, 0, 10, 0, 0, 22, 0, 0, 38, 8, 34, 14, 33, 0, 0, 39, 0, 0, 0, 0, 17, 36, 43, 30, 10, 15, 0, 0, 21, 10, 37, 0, 0, 0, 0, 0, 0, 0, 0, 42]),
sage:      vector(GF(2), [1, 1, 0, 1, 1, 0, 1, 1, 0, 0, 0, 0, 0, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0]))
sage: D.decode_to_code(y)
<BOOM>

Decoding to message works, but produces a vector of incorrect length (should equal the dimension, i.e. 12):

sage: m = D.decode_to_message(y)
sage: len(m)
11

(The bugs were found by introducing random seeding in #29945)

CC: @kliem

Component: coding theory

Keywords: reed-solomon decoding

Author: Johan Rosenkilde

Branch/Commit: b1fa133

Reviewer: Jonathan Kliem

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

[johanrosenkilde]

comment:1

The second error seems to be due to GeneralizedReedSolomonCode having a decode_to_message implemented, which incorrectly converts between polynomials and vectors. I don't see why it should have this method implemented - it should be provided in the correct way by AbstractCode.

[johanrosenkilde]

Dependencies: #29945

[johanrosenkilde]

Branch: u/jsrn/30045_bugs_in_grs

[kliem]

Commit: 18428ed

[kliem]

comment:4

As posted already on #29945, I would propose to just fix the problem and don't worry about #29945.

---

New commits:

18428ed

Remove unnecessary decode_to_message in GeneralizedReedSolomonCode

[johanrosenkilde]

comment:5

OK, then this is up for review.

[johanrosenkilde]

Changed dependencies from #29945 to none

[kliem]

comment:6

The bug fix should be tested with a doctest yet.

[sagetrac-git]

Changed commit from 18428ed to 36cff4a

[sagetrac-git]

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

36cff4a

Add doc-test for 30045

[johanrosenkilde]

comment:8

Right you are.

[kliem]

comment:9

Can you please add the doctest that was removed with the method somewhere.

Also

-    Test that the bug in #30045 is fixed::
+    Test that the bug in :trac:`30045` is fixed::

[kliem]

Reviewer: Jonathan Kliem

[kliem]

comment:10

And missing author name. Otherwise this looks good.

[sagetrac-git]

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

f7ae23b

Reinstate deleted doctest/example in a meaningful place

[sagetrac-git]

Changed commit from 36cff4a to f7ae23b

[sagetrac-git]

Changed commit from f7ae23b to b1fa133

[sagetrac-git]

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

b1fa133

Fix trac ticket link

[johanrosenkilde]

Author: Johan Rosenkilde

[johanrosenkilde]

comment:13

Thanks for the patience! It's been a while since I last fixed something in Sage ;-)

[kliem]

comment:14

LGTM. Thanks for fixing this.

[vbraun]

Changed branch from u/jsrn/30045_bugs_in_grs to b1fa133