New decoders for Generalized Reed-Solomon codes

[sagetrac-dlucas]

This ticket introduces four new different decoders for GRS codes, namely:

• GRSBerlekampWelchDecoder,
• GRSGaoDecoder,
• GRSKeyEquationSyndromeDecoder and
• GRSErrorErasureDecoder.

It requires the new structure for GRS codes introduced in ticket #18928

Depends on #18928
Depends on #19897

CC: @johanrosenkilde

Component: coding theory

Author: David Lucas

Branch/Commit: f3b4b11

Reviewer: Julien Lavauzelle

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

[sagetrac-dlucas]

Branch: u/dlucas/grs_decoders

[sagetrac-dlucas]

comment:2

I pushed the changes, it's now open for review.
Please note that I branched #18928 to work on this ticket.

---

New commits:

d854eb8	New Generalized Reed Solomon code object in Sage, coming with two encoders
0645f58	Updated to 6.9beta6 and fixed conflict
dc470be	Overwrote some methods from linear_code
f8c2d7a	Updated to 6.10beta0 and resolved conflicts
fa4dd71	Update to latest beta
1c1f182	Merged with latest beta version and fixed conflicts
74cc281	Four new decoders for GRS codes

[sagetrac-dlucas]

Author: David Lucas

[sagetrac-dlucas]

Commit: 74cc281

[sagetrac-git]

Changed commit from 74cc281 to b03d7b5

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. Last 10 new commits:

8733405	Some improved doc-strings and doc-tests
229b5cf	Some code beautification
fe7e9de	Sanity-checks on input for GRSEvaluationPolynomialEncoder
6e7013b	Small doc-string improvements in linear_code and encoder
0e82848	More small docstring improvements
91e2e3b	Doc-string typesetting fix
eabe7e0	Reworked coercion of evaluation pts and col mults and refined tests.
71070de	Merged with 18928 and fixed conflicts
9f4fb84	Improved docstrings and doctests
b03d7b5	Extra cleaning in documentation

[sagetrac-dlucas]

comment:4

I merged in #18928 latest version and did some fixes and improvements to the documentation.

[sagetrac-git]

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

4e1a184

Merge branch 'develop' into grs_decoders

[sagetrac-git]

Changed commit from b03d7b5 to 4e1a184

[sagetrac-dlucas]

comment:6

Updated to latest beta, still open for review.

[sagetrac-git]

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

ffed948

Merge branch 'u/dlucas/grs_decoders' of git://trac.sagemath.org/sage into grs_decoders

[sagetrac-git]

Changed commit from 4e1a184 to ffed948

[sagetrac-dlucas]

comment:8

Updated to latest beta, still open for review.

[sagetrac-git]

Changed commit from ffed948 to 37bb7ac

[sagetrac-git]

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

616219c	Update to latest beta
baa9f20	First version of the tutorial
cb65314	Update to latest beta
2057fee	Small fixes and improvements
77f0629	Merged #19897
37bb7ac	Updated introductory thematic tutorial with a paragraph on decoders and message spaces

[sagetrac-dlucas]

Changed dependencies from #18928 to #18928, #19897

[sagetrac-dlucas]

comment:10

I merged #19897 in, and updated the tutorial.

It's still open for review.

[sagetrac-git]

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

1220403	Merge branch 'develop' into grs_decoders
4340598	Removed deprecated import

[sagetrac-git]

Changed commit from 37bb7ac to 4340598

[sagetrac-dlucas]

comment:12

I updated this ticket to latest beta and removed a deprecated import statement, so broken doctests won't be broken anymore.

This is still open for review.

[sagetrac-git]

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

b840682

Updated to 7.1beta3 and fixed conflict

[sagetrac-git]

Changed commit from 4340598 to b840682

[sagetrac-git]

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

d70d6aa

Removed `__ne__` methods

[sagetrac-dlucas]

comment:37

And, (sorry, I forgot to add it...) I also made a new sanity check on the output polynomial for BerlekmapWelch and Gao: if the output polynomial is not in F[x], where F is the base ring of the code, it raises a DecodingError.

David

[johanrosenkilde]

comment:38

Your new checks seem good. But they were actually not what I was talking about - I wasn't very clear. Specifically for the BW decoder, let's say that more errors than (d-1)/2 occurs. In that case, all (almost) bets are off! So the division you do could for instance go fine, but you just end up with a polynomial h which is (when you encode it) nowhere near the received word you got. There are currently no checks for this.

It's similar, I'm pretty sure, with the other decoders.

I added exactly such a check on the Guruswami-Sudan decoder yesterday.

[johanrosenkilde]

comment:39

Two completely different things I just noticed:

• I think the line R(S.list_from_positions(xrange(0, l0+1))) can, and should, be written R(S[:l0+1]).

• In Berlekamp-Welch, and in Gao, you do a divisibility test followed by the actual division, i.e. you divide twice. You should instead use the quo_rem function to do the division once, and do the divisibility test by seeing if the remainder is zero.

[sagetrac-dlucas]

comment:40

Ok, I found something very annoying while working on writing an actual check on the output of decoding algortihms:

sage: C = codes.GeneralizedReedSolomonCode(GF(59).list()[1:40+1], 12)
sage: c1 = C.random_element()
sage: c2 = C[1]
sage: c1.parent() == c2.parent()
False

So if the input of decode_to_code, say r is generated through random_elements, all code like t his:

(r - decoded_word).hamming_weight() > self.decoding_radius():
    raise DecodingError("Decoding failed because the number of errors exceeded the decoding radius")

systematically fails because one cannot properly subtract two vectors whose parents are diffrent.

So I'll fix random_element method...

[johanrosenkilde]

comment:41

Damn. It's related to this sick semantics that the parent of a vector is the subspace. That's also causing trouble in the channels. We should try to fix that at the root, i.e. experiment with the scaffolding code at linear code construction time. Didn't Vincent write something about how to do this in the old sage-devel thread where we discussed the bug?

[sagetrac-git]

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

57dbfbf	Rewrote random_element method
7953d60	Proper sanity checks for output of decode_to_* methods
8673ac5	Optimized a bit polynomial division in Gao and BW

[sagetrac-git]

Changed commit from fca099e to 8673ac5

[sagetrac-dlucas]

comment:43

Damn. It's related to this sick semantics that the parent of a vector is the subspace. That's also causing trouble in the channels. We should try to fix that at the root, i.e. experiment with the scaffolding code at linear code construction time. Didn't Vincent write something about how to do this in the old sage-devel thread where we discussed the bug?

Ah, in the meanwhile I changed this method to something based on encoding a random element from the message space of the default encode of a code.
Probably not the best way to do it, I'm aware of that.

I made the other changes, but

I think the line R(S.list_from_positions(xrange(0, l0+1))) can, and should, be written R(S[:l0+1])

which I tried, but it did not work.

[johanrosenkilde]

comment:44

Ah, in the meanwhile I changed this method to something based on encoding a random element from the message space of the default encode of a code.
Probably not the best way to do it, I'm aware of that.

That's like pissing your pants to keep warm: it doesn't fix the problem in the gazillion other ways this could explode (such as using a StaticErrorRateChannel).

I think the line R(S.list_from_positions(xrange(0, l0+1))) can, and should, be written R(S[:l0+1])

Try harder, seriously... You need to call list on S[:l0+1] as well because the R(...) call is picky about getting a list and not a vector. I just did it, but it turns out it's slower than list_from_positions, so I guess you should just keep that though it looks horrendous.

[johanrosenkilde]

comment:45

Replying to @johanrosenkilde:

Ah, in the meanwhile I changed this method to something based on encoding a random element from the message space of the default encode of a code.
Probably not the best way to do it, I'm aware of that.

That's like pissing your pants to keep warm: it doesn't fix the problem in the gazillion other ways this could explode (such as using a StaticErrorRateChannel).

I totally take that back! I just looked through LinearCode and it seems there is no other way that we could end up with a codeword whose parent is the subvector-space. So the problem really was with random_element. Which means your fix is a good way to solve the problem :-) Sorry about the flame.

Let's discuss another time whether there is a more efficient way to do it, and whether this bizarre passing through of *args and **kwargs to random shouldn't be deprecated (can you please note this down somewhere so we don't forget though?).

Best,
Johan

[johanrosenkilde]

comment:46

(for instance, that the following works is not so good:

    C.random_element(monkey = 2)

But, as I said, that's for another patch.)

[sagetrac-git]

Changed commit from 8673ac5 to e1b6b09

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. Last 10 new commits:

d5e5f35	Documentation to the root finding module
4169e8b	Fixed a bug in some code being validated in the wrong place. Improved
5f03b11	More doc-strings and rm a single assert
8f2ce97	Reflow doc-string
0c7b80d	More robust testing: use sets instead of lists. Semantic tests on output. Corner case on zero input
2b09750	Make the example one where the decoding results in a list
8133531	Fixed typo in decode_to_message
b4bc257	Removed #random flag from _flatten_once doctest
29448ce	Changed title of rootfinding.py
e1b6b09	Merged now postive reviewed #19666 and fixed conflicts

[sagetrac-dlucas]

comment:48

I merged #19666 in this branch, and fixed conflicts.
This will prevent merge conflicts in this branch and #19666 ship in the same Sage beta.

[sagetrac-git]

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

5093dce	Update to 7.1beta5
f3b4b11	Fixed typo in Guruswami-Sudan doc

[sagetrac-git]

Changed commit from e1b6b09 to f3b4b11

[sagetrac-dlucas]

comment:50

As this one is not yet reviewed, I take the opportunity to fix a typo in Guruswami-Sudan documentation.

Still open for review.

[jlavauzelle]

Reviewer: Julien Lavauzelle

[jlavauzelle]

comment:51

Hi David,

All my previous tests now pass. I won't add anything, so if Johan agrees (and if the patchbot "question mark" isn't a problem), I let you put the ticket in positive review.

Really good job !

Julien

[sagetrac-dlucas]

comment:52

Hello,

(and if the patchbot "question mark" isn't a problem)

Nah, it's librae which has gone and done it again, see here, it's a completely unrelated test, which fails only on librae, not on the other bots.

I let you put the ticket in positive review

Please do, I don't want to take that from you (plural) ;)

David

[vbraun]

Changed branch from u/dlucas/grs_decoders to f3b4b11