Opened 3 years ago
Closed 3 years ago
#19666 closed enhancement (fixed)
GuruswamiSudan decoder for GRS codes
Reported by:  dlucas  Owned by:  

Priority:  major  Milestone:  sage7.1 
Component:  coding theory  Keywords:  
Cc:  jsrn  Merged in:  
Authors:  Johan Sebastian Rosenkilde Nielsen, David Lucas  Reviewers:  David Lucas, Johan Sebastian Rosenkilde Nielsen 
Report Upstream:  N/A  Work issues:  
Branch:  29448ce (Commits)  Commit:  29448cea10786283b840b6c9576b21bd6857305b 
Dependencies:  #18928  Stopgaps: 
Description (last modified by )
This ticket introduces a new decoder for GRS codes, the GuruswamiSudan list decoder. The code proposed here relies extensively on the code written by Johan Nielsen in codinglib. He wrote all the algorithms and mathematical content.
Alongside with the decoder itself, this ticket introduces a rootfinding algorithm based using RothRuckenstein algorithm and an interpolation algorithm using linear algebra to solve a linear system of equations.
Change History (34)
comment:1 Changed 3 years ago by
 Branch set to u/dlucas/gs_list_decoding
comment:2 Changed 3 years ago by
 Commit set to b338a056fc5cd86a8ba0900884719e1ca486730e
 Description modified (diff)
 Reviewers set to dlucas
 Status changed from new to needs_review
comment:3 Changed 3 years ago by
 Status changed from needs_review to needs_work
comment:4 Changed 3 years ago by
 Dependencies set to #19653
comment:5 Changed 3 years ago by
 Commit changed from b338a056fc5cd86a8ba0900884719e1ca486730e to 49a3a957acbb3aa285038949368600b27d251079
Branch pushed to git repo; I updated commit sha1. New commits:
6f42db9  A better error message in case one provides a wrong rootfinder/interpolation algorithm

2f98916  Removed depedency in trac #19653

19c56c6  Polished documentation, added copyright and authors field in every GSrelated file

49a3a95  New, better method to compute maxd

comment:6 Changed 3 years ago by
 Dependencies #19653 deleted
 Status changed from needs_work to needs_review
I removed dependency in #19653, enhanced the documentation, added an Author
and a copyright block in the new files and there's a new method to compute maxd
.
This is now officially open for review.
comment:7 Changed 3 years ago by
 Commit changed from 49a3a957acbb3aa285038949368600b27d251079 to f016123bbd4508980208e4c4c5cabf19009d09d4
Branch pushed to git repo; I updated commit sha1. Last 10 new commits:
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

91e2e3b  Docstring typesetting fix

eabe7e0  Reworked coercion of evaluation pts and col mults and refined tests.

f016123  Merged in latest branch from #18928

comment:8 Changed 3 years ago by
 Dependencies set to #18928
I merged latest branch from #18928 and added this ticket as a dependency.
comment:9 Changed 3 years ago by
 Branch changed from u/dlucas/gs_list_decoding to u/jsrn/gs_list_decoding
comment:10 Changed 3 years ago by
 Commit changed from f016123bbd4508980208e4c4c5cabf19009d09d4 to 9c0664e0fee966fec5f86f31e4afc36dc292c27f
While working on a review, I fixed a number of smallish things. Since I interrupted the review, and I'm not sure when I'll get back to it right now, I pushed those changes here. Consider them RFCs.
New commits:
391f892  Change list_decoding_radius to johnson_bound. Decoder should fail on too large tau

f0ee3af  _repr_ and _latex_ should print dec range and params. Improved doc of class

4dc81ce  Rm find_maximum_satisfiable util function

4b9f4db  Make guruswami_sudan_decoding_radius work when restricting s or l.

9c0664e  Rename parameter functions. Improved some doc.

comment:11 Changed 3 years ago by
 Branch changed from u/jsrn/gs_list_decoding to u/dlucas/gs_list_decoding
comment:12 Changed 3 years ago by
 Commit changed from 9c0664e0fee966fec5f86f31e4afc36dc292c27f to bb5ba9dd779a156d1deb0c6358e21c1c73a3a34e
I agree with your changes, which I integrated to my branch. On my side, I also fixed some typos and bugs, rewrote some documentation and renamed a few methods.
New commits:
80e4293  Added a few new doctests to the decoder. Embellished a few lines of code.

5f75508  Renamed methods in interpolation.py and embellished some code

e820c8e  Moved and renamed IMPOSSIBLE_PARAMS from utils.py to gs_decoder.py. Added a related doctest in the decoder

bb5ba9d  Fixed typo in utils.py

comment:13 Changed 3 years ago by
 Commit changed from bb5ba9dd779a156d1deb0c6358e21c1c73a3a34e to 533e26d706c40fe3e99e1f0b878c35fbad45a17c
comment:14 Changed 3 years ago by
I updated this ticket to latest beta, and fixed a bug I found, it's still open for review.
comment:15 Changed 3 years ago by
 Commit changed from 533e26d706c40fe3e99e1f0b878c35fbad45a17c to bffad129290d342e467ca2d13d066092d8060411
Branch pushed to git repo; I updated commit sha1. New commits:
bffad12  Fixed broken doctest

comment:16 Changed 3 years ago by
 Commit changed from bffad129290d342e467ca2d13d066092d8060411 to 2a32f423aa1faeecf3fd18042ee311698c77f8c9
Branch pushed to git repo; I updated commit sha1. New commits:
2a32f42  Updated to latest beta

comment:17 Changed 3 years ago by
Updated to latest beta, still open for review.
comment:18 Changed 3 years ago by
 Commit changed from 2a32f423aa1faeecf3fd18042ee311698c77f8c9 to 9a4ebbb3fd5321615028fc729e07f4262d32d55b
comment:19 Changed 3 years ago by
 Milestone changed from sage6.10 to sage7.1
I'm dusting a bit this ticket: I updated it to latest beta, fixed broken doctests. I noticed that some class parameters names were not prefixed by an underscore, which I fixed.
David
comment:20 Changed 3 years ago by
A trivial test seems to be failing in the thematic tutorial.
comment:21 Changed 3 years ago by
 Commit changed from 9a4ebbb3fd5321615028fc729e07f4262d32d55b to 8d0eb756ecff2958a7642c60786b75b69cb875f6
Branch pushed to git repo; I updated commit sha1. New commits:
8d0eb75  Fixed broken doctest

comment:22 Changed 3 years ago by
A trivial test seems to be failing in the thematic tutorial.
Oops, sorry. Fixed now.
comment:23 Changed 3 years ago by
 Branch changed from u/dlucas/gs_list_decoding to u/jsrn/gs_list_decoding
comment:24 Changed 3 years ago by
 Commit changed from 8d0eb756ecff2958a7642c60786b75b69cb875f6 to 0c7b80d275d22ad900eaaaec5c92352bbdf37b8b
I've reviewed the code by hand now, and modified a bunch of stuff, most of it related to docs and doctests. Please look through my changes and see if you agree.
Tomorrow, I'll do some blackboxtesting of the code. Then the green light should come (if you accept my modifications).
(note that there are more commits than the 10 listed below)
Best, Johan
Last 10 new commits:
009c437  Improved some doctests and strings

5e3b5cc  Fix completely broken doctest

241bcd1  Fix another broken doctest (in that it didn't test anything and the setup was incorrect)

b326a52  Collapse one helper function, and make a proper test for gs_interpolation_linalg

ecd5c0f  More clever way of picking a nonzero element from the kernel (I think)

d5e5f35  Documentation to the root finding module

4169e8b  Fixed a bug in some code being validated in the wrong place. Improved

5f03b11  More docstrings and rm a single assert

8f2ce97  Reflow docstring

0c7b80d  More robust testing: use sets instead of lists. Semantic tests on output. Corner case on zero input

comment:25 Changed 3 years ago by
This is not necessarily a bug but more a discussion: if there are no nearby codewords this implementation is going to return an empty list. If s = ell = 1
then the GuruswamiSudan algorithm is mathematically equivalent to the BerlekampWelch, see #19653. If there are no nearby codewords (i.e. with d/2
radius), then *that* implementation will throw a DecodingError
. But this implementation will just return []
.
I'm not saying that's necessarily wrong. Having a list decoder, you'd like to use []
as a valid response. It just means that the algorithm finished completely as it should, and there were no nearby codewords. I just want to be sure that we take this decision with open eyes, and that we possibly document it somewhere.
comment:26 Changed 3 years ago by
 Commit changed from 0c7b80d275d22ad900eaaaec5c92352bbdf37b8b to 2b0975090d03abeef343811a934646a33bcedc16
Branch pushed to git repo; I updated commit sha1. New commits:
2b09750  Make the example one where the decoding results in a list

comment:27 Changed 3 years ago by
OK, so I've made one last modification to the docs, and I've blackbox tested the decoder some more. I give the green light to your porting of my code. So now you just need to green light my modifications the last two days.
Best, Johan
comment:28 followup: ↓ 30 Changed 3 years ago by
I read all your changes, and I agree with most, I made a few small changes by myself:
 There was an typo in
decode_to_message
's doctest because of which the test failed. I fixed it.
_flatten_once
doctest had the flag#random
while its output is not random, thus I removed this flag.
One remark: In #19653, I changed all my hardcoded doctests related to decode_to_*
methods by examples looking like this:
build the code, say C build the decoder, say D generate a random element of the code, say c create a channel which creates as many errors as the decoder's decoding radius transmit c to get y check if c == D.decode_to_code(y) [resp. D.connected_encoder().unencode(c) == D.decode_to_message(y)]
which I think is a bit better. For instance, it allows us to pick larger codes for tests as you don't have to write the codewords...
Here, I noticed you picked your examples so you get a list of size > 1
, which I think is a good idea. I don't see a way to use this kind of tests AND guarantee that list size will be at least two though...
Also, I don't really like the new title of interpolation.py
module as it appears in the index of modules:
Finding F[x]roots, or modular F[x] roots, in polynomials over F[x][y], where F is a (finite) field.
With such a title, one does not immediately see how this module refers to codes/decoding imho. It's a matter of taste I guess, so I'm not asking to change it, I'm just pointing it.
On my side, I give the greenlight to all your changes. If you agree with mine, I think we're good to go.
David
comment:29 Changed 3 years ago by
 Branch changed from u/jsrn/gs_list_decoding to u/dlucas/gs_list_decoding
comment:30 in reply to: ↑ 28 Changed 3 years ago by
 Commit changed from 2b0975090d03abeef343811a934646a33bcedc16 to b4bc2572e40c26757fe80e4676d139519aef159e
 There was an typo in
decode_to_message
's doctest because of which the test failed. I fixed it.
_flatten_once
doctest had the flag#random
while its output is not random, thus I removed this flag.
OK.
Here, I noticed you picked your examples so you get a list of
size > 1
, which I think is a good idea. I don't see a way to use this kind of tests AND guarantee that list size will be at least two though...
Well, there is a way to autogenerate received words with a list size > 1, but I think that would be total overkill. I vote for keeping the hardcoded decoding example here to demonstrate the list size >1 while keeping simplicity. But I understand why you changed the format of the other tests, and it makes sense.
Also, I don't really like the new title of
interpolation.py
module as it appears in the index of modules:Finding F[x]roots, or modular F[x] roots, in polynomials over F[x][y], where F is a (finite) field.
With such a title, one does not immediately see how this module refers to codes/decoding imho. It's a matter of taste I guess, so I'm not asking to change it, I'm just pointing it.
Fair point. I guess I was exactly thinking about the modules' potential outside coding theory. Can we strike a balance:
Finding F[x] roots for (F[x])[y] polynomials, with F a (finite) field, as used in the GuruswamiSudan decoding algorithm.
On my side, I give the greenlight to all your changes. If you agree with mine, I think we're good to go.
Cool. Let's agree on the above title and then ship it.
New commits:
8133531  Fixed typo in decode_to_message

b4bc257  Removed #random flag from _flatten_once doctest

comment:31 Changed 3 years ago by
 Commit changed from b4bc2572e40c26757fe80e4676d139519aef159e to 29448cea10786283b840b6c9576b21bd6857305b
Branch pushed to git repo; I updated commit sha1. New commits:
29448ce  Changed title of rootfinding.py

comment:32 Changed 3 years ago by
 Reviewers changed from dlucas to David Lucas
I changed the title to what you suggested. It's good for me, but I leave you the final word on it.
David
comment:33 Changed 3 years ago by
 Reviewers changed from David Lucas to David Lucas, Johan Sebastian Rosenkilde Nielsen
 Status changed from needs_review to positive_review
Cool.
comment:34 Changed 3 years ago by
 Branch changed from u/dlucas/gs_list_decoding to 29448cea10786283b840b6c9576b21bd6857305b
 Resolution set to fixed
 Status changed from positive_review to closed
First of all, I set it to
needs_review
because I can't set it toneeds_work
, but it still lacks a small enhancement before being open for review.I already added myself as a reviewer because I read Johan's code while porting it. Of course, I'll need someone to review my changes and documentation
;)
Last 10 new commits:
Added new docstrings and a new method to get GS's decoding radius
Ported methods for RothRuckenstein algotihm. No doc yet.
Fully working GS with linear algebra interpolation step
Cleaned up some mess
Some extra cleaning
Fully doctested and documented GS decoder
Moved GS decoder from grs file to GS folder
Cleaned utils.py file
Cleaned interpolation file
Cleaned rootfinding.py and polished the decoder