Opened 3 years ago

Closed 3 years ago

#19666 closed enhancement (fixed)

Guruswami-Sudan decoder for GRS codes

Reported by: dlucas Owned by:
Priority: major Milestone: sage-7.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 dlucas)

This ticket introduces a new decoder for GRS codes, the Guruswami-Sudan 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 root-finding algorithm based using Roth-Ruckenstein 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 dlucas

  • Branch set to u/dlucas/gs_list_decoding

comment:2 Changed 3 years ago by dlucas

  • Commit set to b338a056fc5cd86a8ba0900884719e1ca486730e
  • Description modified (diff)
  • Reviewers set to dlucas
  • Status changed from new to needs_review

First of all, I set it to needs_review because I can't set it to needs_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:

27b2d87Added new docstrings and a new method to get GS's decoding radius
b808f57Ported methods for Roth-Ruckenstein algotihm. No doc yet.
6b83929Fully working GS with linear algebra interpolation step
19a31c7Cleaned up some mess
78e8f6bSome extra cleaning
29d1c98Fully doctested and documented GS decoder
d3e6c76Moved GS decoder from grs file to GS folder
632092fCleaned utils.py file
4979fc9Cleaned interpolation file
b338a05Cleaned rootfinding.py and polished the decoder

comment:3 Changed 3 years ago by dlucas

  • Status changed from needs_review to needs_work

comment:4 Changed 3 years ago by dlucas

  • Dependencies set to #19653

comment:5 Changed 3 years ago by git

  • Commit changed from b338a056fc5cd86a8ba0900884719e1ca486730e to 49a3a957acbb3aa285038949368600b27d251079

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

6f42db9A better error message in case one provides a wrong rootfinder/interpolation algorithm
2f98916Removed depedency in trac #19653
19c56c6Polished documentation, added copyright and authors field in every GS-related file
49a3a95New, better method to compute maxd

comment:6 Changed 3 years ago by dlucas

  • 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 git

  • Commit changed from 49a3a957acbb3aa285038949368600b27d251079 to f016123bbd4508980208e4c4c5cabf19009d09d4

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

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
91e2e3bDoc-string typesetting fix
eabe7e0Reworked coercion of evaluation pts and col mults and refined tests.
f016123Merged in latest branch from #18928

comment:8 Changed 3 years ago by dlucas

  • Dependencies set to #18928

I merged latest branch from #18928 and added this ticket as a dependency.

comment:9 Changed 3 years ago by jsrn

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

comment:10 Changed 3 years ago by jsrn

  • 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:

391f892Change 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
4dc81ceRm find_maximum_satisfiable util function
4b9f4dbMake guruswami_sudan_decoding_radius work when restricting s or l.
9c0664eRename parameter functions. Improved some doc.

comment:11 Changed 3 years ago by dlucas

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

comment:12 Changed 3 years ago by dlucas

  • 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:

80e4293Added a few new doctests to the decoder. Embellished a few lines of code.
5f75508Renamed methods in interpolation.py and embellished some code
e820c8eMoved and renamed IMPOSSIBLE_PARAMS from utils.py to gs_decoder.py. Added a related doctest in the decoder
bb5ba9dFixed typo in utils.py

comment:13 Changed 3 years ago by git

  • Commit changed from bb5ba9dd779a156d1deb0c6358e21c1c73a3a34e to 533e26d706c40fe3e99e1f0b878c35fbad45a17c

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

2cfa8d7Merge branch 'develop' into gs_list_decoding
533e26dFixed bug in documentation

comment:14 Changed 3 years ago by dlucas

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 git

  • Commit changed from 533e26d706c40fe3e99e1f0b878c35fbad45a17c to bffad129290d342e467ca2d13d066092d8060411

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

bffad12Fixed broken doctest

comment:16 Changed 3 years ago by git

  • Commit changed from bffad129290d342e467ca2d13d066092d8060411 to 2a32f423aa1faeecf3fd18042ee311698c77f8c9

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

2a32f42Updated to latest beta

comment:17 Changed 3 years ago by dlucas

Updated to latest beta, still open for review.

comment:18 Changed 3 years ago by git

  • Commit changed from 2a32f423aa1faeecf3fd18042ee311698c77f8c9 to 9a4ebbb3fd5321615028fc729e07f4262d32d55b

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

4f683e3Update to 7.1beta3
caed7eeFixed deprecated import
9a4ebbbRenamed class parameters

comment:19 Changed 3 years ago by dlucas

  • Milestone changed from sage-6.10 to sage-7.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 jsrn

A trivial test seems to be failing in the thematic tutorial.

comment:21 Changed 3 years ago by git

  • Commit changed from 9a4ebbb3fd5321615028fc729e07f4262d32d55b to 8d0eb756ecff2958a7642c60786b75b69cb875f6

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

8d0eb75Fixed broken doctest

comment:22 Changed 3 years ago by dlucas

A trivial test seems to be failing in the thematic tutorial.

Oops, sorry. Fixed now.

comment:23 Changed 3 years ago by jsrn

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

comment:24 Changed 3 years ago by jsrn

  • 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 doc-tests. Please look through my changes and see if you agree.

Tomorrow, I'll do some blackbox-testing 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:

009c437Improved some doctests and -strings
5e3b5ccFix completely broken doctest
241bcd1Fix another broken doc-test (in that it didn't test anything and the setup was incorrect)
b326a52Collapse one helper function, and make a proper test for gs_interpolation_linalg
ecd5c0fMore clever way of picking a non-zero element from the kernel (I think)
d5e5f35Documentation to the root finding module
4169e8bFixed a bug in some code being validated in the wrong place. Improved
5f03b11More doc-strings and rm a single assert
8f2ce97Reflow doc-string
0c7b80dMore robust testing: use sets instead of lists. Semantic tests on output. Corner case on zero input
Last edited 3 years ago by jsrn (previous) (diff)

comment:25 Changed 3 years ago by jsrn

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 Guruswami-Sudan algorithm is mathematically equivalent to the Berlekamp-Welch, 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 git

  • Commit changed from 0c7b80d275d22ad900eaaaec5c92352bbdf37b8b to 2b0975090d03abeef343811a934646a33bcedc16

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

2b09750Make the example one where the decoding results in a list

comment:27 Changed 3 years ago by jsrn

OK, so I've made one last modification to the docs, and I've black-box 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 follow-up: Changed 3 years ago by dlucas

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 dlucas

  • 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 jsrn

  • 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 hard-coded 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 Guruswami-Sudan 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:

8133531Fixed typo in decode_to_message
b4bc257Removed #random flag from _flatten_once doctest

comment:31 Changed 3 years ago by git

  • Commit changed from b4bc2572e40c26757fe80e4676d139519aef159e to 29448cea10786283b840b6c9576b21bd6857305b

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

29448ceChanged title of rootfinding.py

comment:32 Changed 3 years ago by dlucas

  • 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 jsrn

  • 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 vbraun

  • Branch changed from u/dlucas/gs_list_decoding to 29448cea10786283b840b6c9576b21bd6857305b
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.