Information set decoding for linear codes

[sagetrac-dlucas]

This ticket proposes an implementation of Lee-Brickell algorithm refinement for the information set decoding.

It depends on #19653 for the reimplementation of C.random_element.

Depends on #19653

CC: @jlavauzelle

Component: coding theory

Author: David Lucas, Johan Rosenkilde, Yann Laigle-Chapuy

Branch/Commit: eb2efb3

Reviewer: Yann Laigle-Chapuy

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

[sagetrac-dlucas]

Branch: u/dlucas/information_set_decoding

[sagetrac-dlucas]

Commit: 645e329

[sagetrac-dlucas]

comment:2

I pushed the first version of the code for this ticket.

---

New commits:

884d8ab	New decoder, InformationSetDecoder
351b30c	Set this new decoder in other code families and in the catalog
645e329	Fixed broken doctests

[sagetrac-git]

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

6292df9	window_size and number_errors are now class arguments
e72a5ab	Rewrote `_repr_` and `_latex_` methods, fixed a typo
f2c074c	decode_to_code now iterates over the whole range of provided errors
0e1391d	Added *args to Decoder/Encoder-related methods in AbstractLinearCode

[sagetrac-git]

Changed commit from 645e329 to 0e1391d

[sagetrac-dlucas]

Author: David Lucas

[sagetrac-dlucas]

comment:4

I made some changes:

• window_size and number_errors (previously p and w) are no longer parameters of decode_to_code but class arguments to provide at construction time. number_errors can be provided as a tuple/list, and in that case, the decoder will iterate over it when trying to decode a word.

• I completely reworked the documentation, explained how the algorithm works and added a lot of doctests.

• I completed input sanitization with some extra checks.

• I fixed a stupid bug: only **kwargs was considered on Decoder/Encoder-related methods from AbstractLinearCode, like decoder(). So, C.decoder('InformationSet', 2, 2) was not working...

This is now open for review.

[sagetrac-git]

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

8192769

Updated to 7.1beta6 and fixed conflicts

[sagetrac-git]

Changed commit from 0e1391d to 8192769

[sagetrac-git]

Changed commit from 8192769 to 924be79

[sagetrac-git]

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

465cd56	Merge branch 'develop' into information_set_decoding
59de997	Added information set decoder to Hamming codes
924be79	Minor changes to the information set decoder

[sagetrac-dlucas]

comment:7

I updated this ticket to latest beta, fixed broken doctests, and did minor changes to the decoder (I refined its types and rewrote a line in the documentation).
It's still open for review.

[sagetrac-git]

Changed commit from 924be79 to 93066b1

[sagetrac-git]

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

62468b9	Updated to latest beta and fixed conflict
93066b1	Fixed silly copy-paste mistake in ISD's decoder_type

[sagetrac-dlucas]

comment:9

I updated this ticket to 7.3b2, and fixed a bug.
Still open for review.

Best,

David

[sagetrac-ylchapuy]

comment:10

Here are my two cents:

• you should use itertools instead of Subsets
• you shouldn't enumerate the information_set but take them at random (otherwise you might get stuck a long time with bad choices)
• why use while True loops instead of just for?

all in all, here is how I would do it (notations from the article you cite):

import itertools
def LeeBrickell(r, C, w, p):
    G = C.generator_matrix()
    n = C.length()
    k = C.dimension()
    Fstar = list(C.base_ring())[1:]
    while True:
        # step 1.
        I = sample(range(n), k)
        Gi = G.matrix_from_columns(I)
        try:
            Gi_inv = Gi.inverse()
        except ZeroDivisionError:
            continue
        G = Gi_inv * G
        #step 2.
        y = r - vector([r[i] for i in I]) * G
        g = G.rows()
        #step 3.
        for A in itertools.combinations(range(k), p):
            for m in itertools.product(Fstar, repeat=p):
                e = y - sum(m[i]*g[A[i]] for i in range(p))
                if e.hamming_weight() == w:
                    return r - e

[sagetrac-ylchapuy]

Reviewer: Yann Laigle-Chapuy

[sagetrac-ylchapuy]

comment:11

You should also check if the resulting word is in the code (it might not be the case if you try to decode beyond the minimal distance).

[sagetrac-ylchapuy]

comment:12

In case you want to optimize this a bit, you can replace the itertools enumerations with sage.combinat.gray_codes stuff (and if the field is GF(2) get rid of the itertools.product).

This is probably better kept for another ticket.

[sagetrac-git]

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

50018f6

Fix doctest failure in doc. Add docstring and test to __hash__

[johanrosenkilde]

comment:63

Indeed. These omissions are fixed now.

[sagetrac-ylchapuy]

comment:64

Ok, I finally took the time to build the doc and check it out. Build without a fuss and LGTM.

Your long doctest with codes.QuadraticResidueCode(59, GF(3)) takes around 150ms on my machine, I don't know if I would call this long but it's not a problem.

The bot is also green, so let's move forward: positive review :)

[johanrosenkilde]

comment:65

Great! Thanks for the cooperation - I think this has become a really nice addition to Sage. I'm looking forward to seeing your implementation in #23244.

[vbraun]

comment:66

sage -t --long src/sage/coding/information_set_decoder.py
**********************************************************************
File "src/sage/coding/information_set_decoder.py", line 553, in sage.coding.information_set_decoder.LeeBrickellISDAlgorithm.calibrate
Failed example:
    A.time_estimate()/5 < avg and avg < A.time_estimate() * 5 # long time
Expected:
    True
Got:
    False
**********************************************************************
1 item had failures:
   1 of  15 in sage.coding.information_set_decoder.LeeBrickellISDAlgorithm.calibrate
    [170 tests, 1 failure, 5.71 s]

[kiwifb]

comment:67

Replying to @vbraun:

sage -t --long src/sage/coding/information_set_decoder.py
**********************************************************************
File "src/sage/coding/information_set_decoder.py", line 553, in sage.coding.information_set_decoder.LeeBrickellISDAlgorithm.calibrate
Failed example:
    A.time_estimate()/5 < avg and avg < A.time_estimate() * 5 # long time
Expected:
    True
Got:
    False
**********************************************************************
1 item had failures:
   1 of  15 in sage.coding.information_set_decoder.LeeBrickellISDAlgorithm.calibrate
    [170 tests, 1 failure, 5.71 s]

I couldn't get that on my setup while repeating the test a 1000 time.

[johanrosenkilde]

comment:68

Hmm, we were also in doubt about that test, as you can see from the discussion above. I had believed that it was fairly stable now, but evidently timing behaviour on the build bots are not very dependable.

So perhaps we should simply remove the test - what do you think? Any alternative suggestions for how we could test the calibration code?

[vbraun]

comment:69

• Don't test that the timings have particular values
• Do test that timings can be collected
• Do test that your code makes the right decisions when you specify timings

[sagetrac-git]

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

eb2efb3

Replace brittle calibration test with a test for proper selection

[sagetrac-git]

Changed commit from 50018f6 to eb2efb3

[johanrosenkilde]

comment:71

Replying to @vbraun:

• Don't test that the timings have particular values
• Do test that timings can be collected
• Do test that your code makes the right decisions when you specify timings

OK, I've pushed a patch removing the offending test and instead making a small refactor such that we can test the last item on your list.

It seems a pity, however, that there is no good way to test that the calibrated timings have anything to do with reality.

[sagetrac-ylchapuy]

comment:73

OK, let's do it that way (and the failure in the docbuild is unrelated)

LGTM

[vbraun]

Changed branch from u/jsrn/information_set_decoding to eb2efb3