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.

[dlucas]

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.

[danielaugot]

Hi everyone,

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

Daniel

[arpitdm]

Replying to 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.

[danielaugot]

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 <tab> completion

[dlucas]

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

[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

[dlucas]

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

[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

[dlucas]

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]

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

[cheuberg]

doctest failures in patchbot?

[dimpase]

indeed. One is easy to fix:

--- a/src/sage/coding/golay_code.py
+++ b/src/sage/coding/golay_code.py
@@ -8,7 +8,7 @@ perfect codes, while their extended versions are self-dual codes.
 
 REFERENCES:
 
-    - [HP03]_ pp. 31-33 for a definition of Golay codes.
+    - [HP2003]_ pp. 31-33 for a definition of Golay codes.
 

the other two (failures of long tests --- have the authors ever checked these?) would need work:

File "src/sage/coding/linear_code.py", line 1170, in sage.coding.linear_code.AbstractLinearCode.chinen_polynomial
Failed example:
    C.chinen_polynomial()       # long time
...
ZeroDivisionError: rational division by zero

File "src/sage/matroids/catalog.py", line 1420, in sage.matroids.catalog.ExtendedBinaryGolayCode
Failed example:
    C.is_permutation_equivalent(codes.GolayCode(GF(2)) # long time
Exception raised:
...
SyntaxError: unexpected EOF while parsing

[danielaugot]

The following tests are passed. For the binary case, let us try the manual extension

sage: G = codes.GolayCode(GF(2),False) #shortened binary Golay code
sage: G0 = codes.GolayCode(GF(2),True) #binary Golay code
sage: G0prime = G.extended_code() # manual extension
sage: G0.generator_matrix() * G0prime.parity_check_matrix().transpose() == 0 # basic test of mathematical correctness
True

Let us try self-duality

sage: G0perp = G0.dual_code()
sage: G0.generator_matrix() * G0perp.generator_matrix().transpose() == 0 # basic test of mathematical correctness
True

Same business for the ternary code: extension

sage: G = codes.GolayCode(GF(3),False) # shortened ternary Golay code
sage: G0 = codes.GolayCode(GF(3),True) # ternary Golay code
sage: G0prime = G.extended_code() # manual extension
sage: G0.generator_matrix() * G0prime.parity_check_matrix().transpose() == 0 # basic test of mathematical correctness
True

self-duality

sage: G0perp = G0.dual_code()
sage: G0.generator_matrix() * G0perp.generator_matrix().transpose() == 0 # basic test of mathematical correctness
True

[git]

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

​c802c81	Merge ticket 21418 into 20908_rework_coding_index
​ac2dd76	Improved some more module doc strings. Fixed a merge bug. Added a ref to Feulner.
​8185e87	Updated to latest beta and fixed conflicts
​b77de0f	Added new file that introduces the new parity-check code class. Initializes code class, generator matrix encoder class, straightforward encoder class and minimum distance method.
​0b0d2f8	Correcting mistakes. Two errors are still waiting for correction: ParityCheckCodeStraightforwardEncoder.unencode_nocheck and ParityCheckCodeGeneratorMatrixEncoder.__init__
​62abcd7	Fixed merge conflict.
​1aa4b4e	Fixed doctests. Shorter output. Generator matrix encoder inherits from the generic one. Fixed encoders. Cleaned the code.
​19e299e	Merged 21328 and fixed broken doctests
​f64841f	Move cyclic code heading
​6ca8937	merged ticket 20908

[danielaugot]

Almost OK, but the test coverage

./sage -t --long src/sage/coding/

does not work because chinen_polynomial() BOOMs on the ternary Golay code.

[dimpase]

Are you debugging this?

[danielaugot]

I was trying to check golay_code.py, and also adding some tests.

This is passed:

./sage -t --long src/sage/coding/golay_code.py

This is also passed:

./sage -t src/sage/coding/

but this one fails:

./sage -t --long src/sage/coding/

because of linear_code.py.

I have not much time to investigate why chinen_polynomial() fails in linear_code.py.

I do not know the best way to make progress : remove the test, deprecate the function, understand why the code is not functionning on the ternary Golay code ?

[dimpase]

The bug is in zeta_polynomial(), as should be clear from the log:

sage -t --long --warn-long 63.1 coding/linear_code.py
**********************************************************************
File "coding/linear_code.py", line 1176, in sage.coding.linear_code.AbstractLinearCode.chinen_polynomial
Failed example:
    C.chinen_polynomial()       # long time
Exception raised:
    Traceback (most recent call last):
      File "/home/scratch/dimpase/sage/sage/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 498, in _run
        self.compile_and_execute(example, compiler, test.globs)
      File "/home/scratch/dimpase/sage/sage/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 861, in compile_and_execute
        exec(compiled, globs)
      File "<doctest sage.coding.linear_code.AbstractLinearCode.chinen_polynomial[3]>", line 1, in <module>
        C.chinen_polynomial()       # long time
      File "/home/scratch/dimpase/sage/sage/local/lib/python2.7/site-packages/sage/coding/linear_code.py", line 1199, in chinen_polynomial
        P = RT(C.zeta_polynomial())
      File "/home/scratch/dimpase/sage/sage/local/lib/python2.7/site-packages/sage/coding/linear_code.py", line 3437, in zeta_polynomial
        b = [Bs[i]/binomial(n,i+d) for i in range(len(Bs))]
      File "sage/structure/element.pyx", line 1711, in sage.structure.element.Element.__truediv__ (build/cythonized/sage/structure/element.c:13260)
        return coercion_model.bin_op(left, right, truediv)
      File "sage/structure/coerce.pyx", line 1053, in sage.structure.coerce.CoercionModel_cache_maps.bin_op (build/cythonized/sage/structure/coerce.c:9336)
        return PyObject_CallObject(op, xy)
      File "sage/structure/element.pyx", line 1709, in sage.structure.element.Element.__truediv__ (build/cythonized/sage/structure/element.c:13225)
        return (<Element>left)._div_(right)
      File "sage/rings/rational.pyx", line 2313, in sage.rings.rational.Rational._div_ (build/cythonized/sage/rings/rational.c:21599)
        raise ZeroDivisionError('rational division by zero')
    ZeroDivisionError: rational division by zero

Indeed, here it is:

sage: C = codes.GolayCode(GF(3), False)
sage: C.zeta_polynomial()
---------------------------------------------------------------------------
ZeroDivisionError                         Traceback (most recent call last)
<ipython-input-4-8fcefbaf83d4> in <module>()
----> 1 C.zeta_polynomial()

/home/scratch/dimpase/sage/sage/local/lib/python2.7/site-packages/sage/coding/linear_code.pyc in zeta_polynomial(self, name)
   3435         B = A(x+y,y,T)-(x+y)**n
   3436         Bs = B.coefficients()
-> 3437         b = [Bs[i]/binomial(n,i+d) for i in range(len(Bs))]
   3438         r = n-d-dperp+2
   3439         P_coeffs = []
...
ZeroDivisionError: rational division by zero

so just some silly indexing bug, binomial(n,i+d) becomes 0...

[dimpase]

And digging further, one sees that the weight enumerator of codes.GolayCode(GF(3), False) is inconsistent with the Sage's convention that it is homogeneous bivariate polynomial rather than the univariate one:

sage: C = codes.GolayCode(GF(3), False)
sage: C.weight_enumerator()
24*x^11 + 110*x^9 + 330*x^8 + 132*x^6 + 132*x^5 + 1

whereas

sage: C=codes.HammingCode(GF(2), 3)
sage: C.weight_enumerator()
x^7 + 7*x^4*y^3 + 7*x^3*y^4 + y^7

and

sage: C=codes.GolayCode(GF(3),False)
sage: L=LinearCode(C.generator_matrix())
sage: L.weight_enumerator()
x^11 + 132*x^6*y^5 + 132*x^5*y^6 + 330*x^3*y^8 + 110*x^2*y^9 + 24*y^11

So the bug is in the code in the branch under review, and trivial to fix.

TLDR: before blaming old code, make sure that the new code is not buggy :-)

[git]

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

​686b278	Merge branch 'public/newgolaycodesclass' of trac.sagemath.org:sage into goco
​6bf9d4b	weight_enumerator from the parent class is OK - and typos fixed

[dimpase]

removed the useless (the one from the parent class is just as fast) weight_enumerator(). And fixed typos in weight distributions data (yes, indeed, do you guys ever check the code you write? :-( ).

[dimpase]

Replying to dimpase:

removed the useless (the one from the parent class is just as fast) weight_enumerator(). And fixed typos in weight distributions data (yes, indeed, do you guys ever check the code you write? :-( ).

yes, this does fix the Chinen polynomial bug, as the weight enumerators are now correct.

[danielaugot]

All tests pass, with the option --long.

[vbraun]

[dochtml] OSError: [coding   ] /mnt/disk/home/release/Sage/local/lib/python2.7/site-packages/sage/coding/golay_code.py:docstring of sage.coding.golay_code:8: WARNING: citation not found: HP03
[dochtml] 
Makefile:1083: recipe for target 'doc-html' failed

[git]

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

​7c91f04

fixed the ref

[dimpase]

IMHO we deserve co-authorship on this :-)

[danielaugot]

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

[vbraun]

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

[git]

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

​3ef25b4

missing ')' added to the doctest

[dimpase]

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]

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

[git]

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

​801dc10

fixed broken by deprecation doctest

[dimpase]

all right, all right...

[danielaugot]

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