Bug in Reed-Solomon encoder and error-erasure decoder
Closed this issue · 23 comments
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
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.
Description changed:
---
+++
@@ -13,10 +13,10 @@
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) Dependencies: #29945
Branch: u/jsrn/30045_bugs_in_grs
OK, then this is up for review.
Changed dependencies from #29945 to none
The bug fix should be tested with a doctest yet.
Branch pushed to git repo; I updated commit sha1. New commits:
36cff4a | Add doc-test for 30045 |
Right you are.
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::Reviewer: Jonathan Kliem
And missing author name. Otherwise this looks good.
Branch pushed to git repo; I updated commit sha1. New commits:
f7ae23b | Reinstate deleted doctest/example in a meaningful place |
Branch pushed to git repo; I updated commit sha1. New commits:
b1fa133 | Fix trac ticket link |
Author: Johan Rosenkilde
Thanks for the patience! It's been a while since I last fixed something in Sage ;-)
LGTM. Thanks for fixing this.
Changed branch from u/jsrn/30045_bugs_in_grs to b1fa133