A class to manage Golay Codes

[arpitdm]

There are four types of Golay Codes, Extended Binary, Binary, Extended Ternary and Ternary. The aim of this ticket is to refactor the current methods for constructing these codes into one single Golay Code class (based on the new API) that provides for combinatorial properties as well as encoding and decoding algorithms for each type of Golay code.

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

Component: coding theory

Keywords: sd75

Author: Arpit Merchant, David Lucas, Dima Pasechnik, Daniel Augot

Branch: 801dc10

Reviewer: Dima Pasechnik, Daniel Augot

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

[arpitdm]

Branch: u/arpitdm/golay_codes

[sagetrac-dlucas]

Commit: 72cae05

[sagetrac-dlucas]

comment:2

Hello,

I'm completing the implementation pushed by Arpit some months ago.
I have one question related to extended Golay codes:

As extended codes are implemented as a proper class in Sage, from which it is possible to
get the "structured representation" of the extended code, if it exists, it would be possible to do the following:

    sage: C = codes.GolayCode("binary", "extended")
    sage: C
    Extended code coming from [23, 12, 8] Golay code over GF(2)
    sage: C.structured_representation()
    [24, 12, 8] Golay code over GF(2)

However, I think it is not the best way to do it, as I'm quite sure no one cares
about the fact that an extended Golay is an extended code, but one cares about extended
Golay codes being Golay codes, with their set of specific properties.

That's why I suggest we just return a Golay code and drop the extended description if
someone asks for an extended Golay code.

Another question:

for now, the constructor works as follow:

GolayCode(alphabet, extended), where alphabet has to be either binary or ternary and extended is a boolean.
Do you think it's a good idea to allow the user to pass GF(2)/GF(3) directly to
alphabet? It seems quite natural to me to allow such an input.
Also, I'd tend to set extended to False by default.
Any comments?

David

---

New commits:

72cae05

Added new file that introduces the new Golay code class. Initializes code class and generator matrix encoder class and preliminary methods such as minimum distance.

[sagetrac-dlucas]

Changed keywords from none to sd75

[sagetrac-danielaugot]

comment:4

Hi everyone,

there is no codes.GolayCode in my namespace. As a consequence ./sage -t src/codes/coding vastly fails.

Daniel

[arpitdm]

comment:5

Replying to @sagetrac-danielaugot:

Hi everyone,

there is no codes.GolayCode in my namespace. As a consequence ./sage -t src/codes/coding vastly fails.

Daniel

As of now, there isn't a single class in Sage for Golay codes. You need to use codes.BinaryGolayCode, codes.ExtendedBinaryGolayCode, codes.TernaryGolayCode, codes.ExtendedTernaryGolayCode.

[sagetrac-danielaugot]

Changed branch from u/arpitdm/golay_codes to u/danielaugot/golay_codes

[sagetrac-danielaugot]

comment:7

Hi Arpit

now codes.GolayCode is in the namespace.

Daniel

---

New commits:

797d4d5	Merge branch 'u/arpitdm/golay_codes' of git://trac.sagemath.org/sage into golay_codes/20787
f7f62c7	added the new GolayCode class to codes_catalog.py to have it shown by completion

[sagetrac-danielaugot]

Changed commit from 72cae05 to f7f62c7

[sagetrac-dlucas]

Changed branch from u/danielaugot/golay_codes to u/dlucas/golay_codes

[sagetrac-dlucas]

comment:9

Thanks for doing this Daniel!

I actually did it on my side this morning, and intended to push it later.

Anyway, my latest push
contains some fixes wrt. input sanitization, plus some bug fixes
(e.g. dual_code method was returning self whichever Golay code self was...
Which includes codes whose length is odd, G23 and G11, which is mathematically impossible).

Please note that quite a lot of doctests are still broken, I'm working on it.
The encoder is far from being fully implemented, and I did not investigate
decoding capabilities nor properties related to Golay codes' automorphism groups.
I'm not sure I'll take care of automorphism groups in this ticket BTW.

David

---

New commits:

88e3c5a	Merge branch 'u/arpitdm/golay_codes' of trac.sagemath.org:sage into golay_codes
3df3149	Rewrote some doctests, completed some methods for Golay codes
ba10ab9	Hardcoded weight enumerators
356752b	Completed weight distribution/enumerator methods. Changed constructor's allowed input
248b7b2	Made Golay codes and their encoder available
d6475c5	Fixed dual_code method
3f302be	Completely reworked the constructor
ae26870	Merge branch 'u/danielaugot/golay_codes' of trac.sagemath.org:sage into golay_codes

[sagetrac-dlucas]

Changed commit from f7f62c7 to ae26870

[sagetrac-git]

Changed commit from ae26870 to fa89d95

[sagetrac-git]

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

b085683	Got rid of the specific encoder, implemented a method generator_matrix
76d0fd2	Implemented parity_check_matrix method
8dc7757	Removed useless import statements
79730b2	Improved `_repr_` and _latex_
0b46ac3	Doctests now pass
432ff31	Added golay_code.py to index.rst
fa89d95	Deprecated old *GolayCode methods

[sagetrac-dlucas]

Changed author from Arpit Merchant to Arpit Merchant, David Lucas

[sagetrac-dlucas]

comment:11

Hello,

I finished the implementation of a proper class for Golay codes.
Some notes on design:

• codes.GolayCode now takes GF(2)/GF(3) as input instead of "binary"/"ternary", and extended=True/False instead of a string "true"/"false". I also chose to set extended to True by default.

• This ticket does not implement anything related to automorphism groups of Golay codes.

• I completely removed the encoder proposed in the initial implementation, as it was a
  copy of linear_code.LinearCodeGeneratorMatrixEncoder.

• I chose to slightly modify the output of _str_ if the code is extended or not.
  codes.GolayCode(GF(2), True) replies "blah extended Golay code blah", and
  codes.GolayCode(GF(2), False) replies "blah Golay code blah". I think such a
  behaviour is more informative to the user than just outputting the triple [n, k, d].

Opening for review.

David

[sagetrac-git]

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

0438bb2	Update to 7.4beta2
63c9df8	Fixed broken doctests in matroids/catalog.py
25d0e7a	Fixed broken doctests in graphs/strongly_regular_db.pyx
2db3057	Fixed broken doctest in linear_code.py

[sagetrac-git]

Changed commit from fa89d95 to 2db3057

[sagetrac-dlucas]

comment:13

Hello,

I updated this branch to the latest beta (7.4b2), and fixed some broken doctests I forgot last time.
According to the patchbot, there's one more doctest to fix in linear_code.py, l.1396...
Except that it passes just fine on my machine (while the patchbot complains about some ZeroDivisionError).

David

[dimpase]

comment:14

there is a misprint (missing r) in coding/code_constructions.py

deprecation(20787, "codes.ExtendedTernayGolayCode...

I also think that in the examples the parameter extended= should be present,
otherwise it's very confusing that GolayCode(GF(2)) returns the extended code.

I will post a rebased branch with these changes.

[dimpase]

New commits:

4ad7107	rebased over 7.5.rc1, fixed typo
a37b9eb	fixed broken doctest in the file header
44a25be	fixed copy/pasted Ternay few times, etc

[sagetrac-git]

Changed commit from 6bf9d4b to 7c91f04

[sagetrac-git]

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

7c91f04

fixed the ref

[dimpase]

Changed author from Arpit Merchant, David Lucas to Arpit Merchant, David Lucas, Dima Pasechnik, Daniel Augot

[dimpase]

comment:33

IMHO we deserve co-authorship on this :-)

[sagetrac-danielaugot]

comment:34

I could build the documentation after a make doc-clean.

[vbraun]

comment:35

sage -t --long src/sage/matroids/catalog.py
4733**********************************************************************
4734File "src/sage/matroids/catalog.py", line 1420, in sage.matroids.catalog.ExtendedBinaryGolayCode
4735Failed example:
4736    C.is_permutation_equivalent(codes.GolayCode(GF(2)) # long time
4737Exception raised:
4738    Traceback (most recent call last):
4739      File "/Users/buildslave-sage/slave/sage_git/build/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 498, in _run
4740        self.compile_and_execute(example, compiler, test.globs)
4741      File "/Users/buildslave-sage/slave/sage_git/build/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 859, in compile_and_execute
4742        compiled = compiler(example)
4743      File "/Users/buildslave-sage/slave/sage_git/build/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 496, in <lambda>
4744        example.source, filename, "single", compileflags, 1)
4745      File "<doctest sage.matroids.catalog.ExtendedBinaryGolayCode[2]>", line 1
4746        C.is_permutation_equivalent(codes.GolayCode(GF(Integer(2))) # long time
4747                                                                              ^
4748    SyntaxError: unexpected EOF while parsing
4749*********************************************************************

and

sage -t --long src/sage/numerical/backends/generic_backend.pyx
5210**********************************************************************
5211File "src/sage/numerical/backends/generic_backend.pyx", line 1752, in sage.numerical.backends.generic_backend.get_solver
5212Failed example:
5213    delsarte_bound_additive_hamming_space(11,3,4,solver=glpk_exact_solver) # long time
5214Expected:
5215    glp_exact...
5216    ...
5217    OPTIMAL SOLUTION FOUND
5218    8
5219Got:
5220    doctest:warning
5221

[sagetrac-git]

Changed commit from 7c91f04 to 3ef25b4

[sagetrac-git]

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

3ef25b4

missing ')' added to the doctest

[dimpase]

comment:37

the 2nd error comes from #20908 - this ticket has nothing to do with it...

Got:
    doctest:warning
...
    DeprecationWarning: This function will soon be removed from the global namespace. Please call it using codes.bounds.delsarte_bound_additive_hamming_space instead
    See http://trac.sagemath.org/20908 for details.

Where would you like this to be fixed?

[vbraun]

comment:39

Daniel merged #20908 into this branch, so you you need to fix both #20908 and this branch.

[sagetrac-git]

Changed commit from 3ef25b4 to 801dc10

[sagetrac-git]

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

801dc10

fixed broken by deprecation doctest

[dimpase]

comment:41

all right, all right...

[vbraun]

Changed branch from public/newgolaycodesclass to 801dc10

[sagetrac-danielaugot]

comment:43

Thanks a lot, Dima, for so much help. Daniel

[sagetrac-danielaugot]

Changed commit from 801dc10 to none