TestSet Decoder for LinearCodes

[sagetrac-imarquez]

A new version of the ticket #14973 adapted to the new coding Theory framework

CC: @johanrosenkilde @sagetrac-dlucas @sagetrac-danielaugot

Component: coding theory

Keywords: sd75

Author: Irene Márquez-Corbella, Miguel Marco

Branch/Commit: u/imarquez/groebner-decoder @ 76b83d7

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

[sagetrac-imarquez]

Branch: u/imarquez/groebner-decoder

[sagetrac-imarquez]

comment:2

This is a ticket still under work (documentation still needs some work)

---

New commits:

aea96cb	First Implementation of Groebner-Basis
0fa5896	First Implementation of TestSetDecoder

[sagetrac-imarquez]

Commit: 0fa5896

[sagetrac-danielaugot]

Changed branch from u/imarquez/groebner-decoder to u/danielaugot/groebner-decoder

[sagetrac-danielaugot]

Changed commit from 0fa5896 to de27033

[sagetrac-danielaugot]

comment:4

Hi Irene,

there was a very minor conflict (traling whitespace) in merging with develop.

Daniel

---

New commits:

de27033

merge solved, by removing a trailing whitespace

[sagetrac-imarquez]

Changed branch from u/danielaugot/groebner-decoder to u/imarquez/groebner-decoder

[sagetrac-git]

Changed commit from de27033 to 8f4bb7a

[sagetrac-git]

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

8f4bb7a

Eliminate the rest of the conflict marks

[sagetrac-imarquez]

comment:7

I will continue working in the documentation and extra functions in the following days.

[miguelmarco]

Changed branch from u/imarquez/groebner-decoder to u/mmarco/groebner-decoder

[sagetrac-imarquez]

Changed branch from u/mmarco/groebner-decoder to u/imarquez/groebner-decoder

[sagetrac-git]

Changed commit from 8f4bb7a to 76b83d7

[sagetrac-git]

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

76b83d7

Documentation correct

[sagetrac-imarquez]

comment:11

New functions have been added: coset_leaders, coset_weight_distribution, covering_radius(without Magma), newton_radius and unique_decoding_radius().

Documentation now is correct

[sagetrac-imarquez]

comment:12

Sorry before is covering_radius (without the optional package of GUAVA)

[sagetrac-dlucas]

comment:13

Hello Irene,

I actually implemented a version of covering_radius which does not use GUAVA in
#19913. It automatically detects if GUAVA is installed, and if it's not, it uses a
very slow Python algorithm instead of using GUAVA.

We should benchmark your implementation and mine, and keep the fastest one.
BTW, I did some benchmarking GUAVA vs. naive Python implementation, and GUAVA was
always faster (which is why I automatically use GUAVA calls if the user has GUAVA installed).

David

[miguelmarco]

comment:14

In the _insert_next_fq method, you treat these two different cases:

        if List:
            for i in s:
                new = v.__copy__()
                for q in Fqstar:
                    new[i]=q
                    if new not in List:
                        List.append(new.__copy__())
        else:
            for i in s:
                new = v.__copy__()
                for q in Fqstar:
                    new[i]=q
                    List.append(new.__copy__())

is it really what you want to do? wouldn't it make sense to just use the first case everywhere?

[johanrosenkilde]

comment:15

That whole helper-method can be simplified into an almost-one-liner: all error-vectors of weight 1 can be created as:

   I = identity_matrix(F, n)
   single_errs = ( a * I.row(i) for a in F for i in range(n) )

Now you want to extend List with the elements [ v + e for e in single_errs ].
But you want to avoid duplicating the elements already in List. Therefore you should use a set for List. This causes a small snag since sets only work for immutable vectors.

Assuming single_errs was computed outside at the beginning of the method, then the update of List in the loop of coset_leaders could look like

    shifts = [ v + e for e in single_errs ]
    for w in shifts: w.set_immutable()
    List.union(shifts)

List breaks the convention of starting variables with minuscule. What about the name worklist?

Best,
Johan

[johanrosenkilde]

comment:16

The keyword algorithm for the "one"/"all" of coset_leaders is not good: algorithm is reserved for different methods with which to compute the result. What about representative = True, where representative = False means to output all of them.

[ppurka]

comment:17

Replying to @miguelmarco:

In the _insert_next_fq method, you treat these two different cases:
is it really what you want to do? wouldn't it make sense to just use the first case everywhere?

I think the if condition should be kept. It makes a difference and avoids a linear search inside a for loop in the case List is empty.

This causes a small snag since sets only work for immutable vectors.

I think we should not return immutable vectors from coset leaders. The output might be used for further computations by the user and then it will create strange issues, which will be hard to debug. The less surprises we have for the user, the better it is.

List breaks the convention of starting variables with minuscule. What about the name worklist?

This can be done I suppose, just for consistency.

The keyword algorithm for the "one"/"all" of coset_leaders is not good

I agree. This is not really a different algorithm.

[sagetrac-ylchapuy]

comment:18

If you care about the coset_leaders method I see many improvements possibles:

• use deque instead of list for the worklist;
• append generators instead of real lists;
• take care to enumerate your candidates uniquely;
• use a hashed container for the syndromes already seen;
• early abort when you have seen all the possible syndromes;
• normalize syndromes (e.g. only keep those starting with 1).

Just as a quick model you might want to look at this:

import collections

def coset_leaders_one(C):
    H = C.parity_check_matrix().transpose()
    K = C.base_ring()
    q = K.cardinality()
    def my_generator(v):
        t = list(v)
        for i, vi in enumerate(v):
            if vi: break
            for a in K:
                if a:
                    t[i] = a
                    yield vector(t)
            t[i] = 0
    def normalize(s):
        for si in s:
            if si:
                return tuple(s / si)
        return tuple(s)
    z = vector(K, C.length())
    sz = normalize(C.syndrome(z))
    S = {sz: z}
    generators = collections.deque([my_generator(z)])
    target_size = (q ** H.ncols() - 1) // (q - 1) + 1
    while generators:
        g = generators.popleft()
        for v in g:
            syndrome = normalize(v*H)
            if syndrome not in S:
                S[syndrome] = v
                if len(S) == target_size:
                    r = [S.pop(sz)]
                    for s in S.values():
                        r.extend(a * s for a in K if a)
                    return r
                if not v[0]:
                    generators.append(my_generator(v))

You can adapt this for the case where you want them all.

[sagetrac-ylchapuy]

comment:19

You might also look at this implementation: u/ylchapuy/coset_leaders

[ppurka]

comment:20

@sagetrac-ylchapuy Thank you for this implementation. If you have this implementation in a Ticket somewhere please try to get it in first, and make this ticket a dependency of the other one. Your implementation is several hundred times faster than this one.

Meanwhile, I have been checking whether the coset leaders returned in your function "match" with the coset leaders returned by the implementation in this ticket. I haven't looked into it in detail, but there is a discrepancy. The discrepancy is not present for all codes though.

sage: from coset_1 import coset_leaders_one
sage: from coset_2 import coset_leaders
sage: C = codes.ReedSolomonCode(7,5,GF(8,'a'))
/mnt/usb/Installations/sage/src/bin/sage-ipython:1: DeprecationWarning: codes.Re
edSolomonCode is now deprecated. Please use codes.GeneralizedReedSolomonCode ins
tead.
See http://trac.sagemath.org/18928 for details.
  #!/usr/bin/env python
sage: L1 = coset_leaders_one(C)
sage: L2 = coset_leaders(C, "one")
sage: L2_2 = flatten(L2)
sage: L1bool = [False]*len(L1)
sage: L2bool = [False]*len(L2)
sage: Fqstar = C.base_ring().list()[1:]
sage: for i,w in enumerate(L1):
....:     wlist = [_*w for _ in Fqstar]
....:     for _w in wlist:
....:         if _w in L2_2:
....:             L1bool[i] = True
....:             break
....: for i,v in enumerate(L2_2):
....:     vlist = [_*v for _ in Fqstar]
....:     for _v in vlist:
....:         if _v in L1:
....:             L2bool[i] = True
....:             break
....:
sage: all(L1bool)
True
sage: all(L2bool)
False
sage: %time L1 = coset_leaders_one(C)
CPU times: user 6.67 ms, sys: 0 ns, total: 6.67 ms
Wall time: 6.02 ms
sage: %time L2 = coset_leaders(C)
CPU times: user 8.43 s, sys: 3.33 ms, total: 8.44 s
Wall time: 8.39 s
sage: len(L1)
64
sage: len(L2)
64
sage: len(L2_2)
64

[sagetrac-ylchapuy]

comment:21

Replying to @ppurka:

@sagetrac-ylchapuy Thank you for this implementation. If you have this implementation in a Ticket somewhere please try to get it in first, and make this ticket a dependency of the other one. Your implementation is several hundred times faster than this one.

The ticket where this should be done is #19913 .

Sadly I won't have time to do more on this in the foreseeable future, but would be pleased if someone else is motivated enough to integrate this on his own.

[sagetrac-ylchapuy]

comment:22

And as a side remark, the code in the branch from comment:19 is even much better.

6 time faster on your example code:

sage: C
[7, 5, 3] Generalized Reed-Solomon Code over Finite Field in a of size 2^3
sage: %timeit coset_leaders_one(C)
100 loops, best of 3: 3.03 ms per loop
sage: %timeit _coset_leaders(C)
1000 loops, best of 3: 477 µs per loop

and on a some bigger examples

sage: C = codes.random_linear_code(GF(7), 32, 27)
sage: %timeit coset_leaders_one(C)
1 loop, best of 3: 1.35 s per loop
sage: %timeit _coset_leaders(C)
10 loops, best of 3: 78.2 ms per loop
sage: C = codes.random_linear_code(GF(3), 32, 22)
sage: %timeit coset_leaders_one(C)
1 loop, best of 3: 23.8 s per loop
sage: %timeit _coset_leaders(C)
1 loop, best of 3: 1.18 s per loop

I didn't try with the implementation from here...