Opened 14 months ago

Closed 5 months ago

Last modified 5 months ago

#20787 closed enhancement (fixed)

A class to manage Golay Codes

Reported by: arpitdm Owned by:
Priority: major Milestone: sage-7.6
Component: coding theory Keywords: sd75
Cc: dlucas, jsrn, richmond, jlavauzelle, danielaugot Merged in:
Authors: Arpit Merchant, David Lucas, Dima Pasechnik, Daniel Augot Reviewers: Dima Pasechnik, Daniel Augot
Report Upstream: N/A Work issues:
Branch: 801dc10 (Commits) Commit:
Dependencies: Stopgaps:

Description

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.

Change History (43)

comment:1 Changed 14 months ago by arpitdm

  • Branch set to u/arpitdm/golay_codes

comment:2 Changed 11 months ago by dlucas

  • Commit set to 72cae05801296575da9a3c6f4a3b58526ace7643

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:

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

comment:3 Changed 11 months ago by dlucas

  • Cc richmond jlavauzelle danielaugot added
  • Keywords sd75 added
  • Milestone changed from sage-7.3 to sage-7.4
  • Status changed from new to needs_info

comment:4 follow-up: Changed 11 months ago by danielaugot

Hi everyone,

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

Daniel

comment:5 in reply to: ↑ 4 Changed 11 months ago by 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.

comment:6 Changed 11 months ago by danielaugot

  • Branch changed from u/arpitdm/golay_codes to u/danielaugot/golay_codes

comment:7 Changed 11 months ago by danielaugot

  • Commit changed from 72cae05801296575da9a3c6f4a3b58526ace7643 to f7f62c718dd9cf6d5d2d3bae82f2f750e0f69d2a

Hi Arpit

now codes.GolayCode? is in the namespace.

Daniel


New commits:

797d4d5Merge branch 'u/arpitdm/golay_codes' of git://trac.sagemath.org/sage into golay_codes/20787
f7f62c7added the new GolayCode class to codes_catalog.py to have it shown by <tab> completion

comment:8 Changed 11 months ago by dlucas

  • Branch changed from u/danielaugot/golay_codes to u/dlucas/golay_codes

comment:9 Changed 11 months ago by dlucas

  • Commit changed from f7f62c718dd9cf6d5d2d3bae82f2f750e0f69d2a to ae268705b6112ee7d3df4843b01009ac3f7d248d

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:

88e3c5aMerge branch 'u/arpitdm/golay_codes' of trac.sagemath.org:sage into golay_codes
3df3149Rewrote some doctests, completed some methods for Golay codes
ba10ab9Hardcoded weight enumerators
356752bCompleted weight distribution/enumerator methods. Changed constructor's allowed input
248b7b2Made Golay codes and their encoder available
d6475c5Fixed dual_code method
3f302beCompletely reworked the constructor
ae26870Merge branch 'u/danielaugot/golay_codes' of trac.sagemath.org:sage into golay_codes

comment:10 Changed 11 months ago by git

  • Commit changed from ae268705b6112ee7d3df4843b01009ac3f7d248d to fa89d95956214cc1263c8a1f569e533359cc051b

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

b085683Got rid of the specific encoder, implemented a method generator_matrix
76d0fd2Implemented parity_check_matrix method
8dc7757Removed useless import statements
79730b2Improved _repr_ and _latex_
0b46ac3Doctests now pass
432ff31Added golay_code.py to index.rst
fa89d95Deprecated old *GolayCode methods

comment:11 Changed 11 months ago by dlucas

  • Authors changed from Arpit Merchant to Arpit Merchant, David Lucas
  • Status changed from needs_info to needs_review

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

Last edited 11 months ago by dlucas (previous) (diff)

comment:12 Changed 11 months ago by git

  • Commit changed from fa89d95956214cc1263c8a1f569e533359cc051b to 2db3057ebba6d8baf1c2004dae7aede7af53c5c0

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

0438bb2Update to 7.4beta2
63c9df8Fixed broken doctests in matroids/catalog.py
25d0e7aFixed broken doctests in graphs/strongly_regular_db.pyx
2db3057Fixed broken doctest in linear_code.py

comment:13 Changed 11 months ago by 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

comment:14 Changed 7 months ago by 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.

comment:15 Changed 7 months ago by dimpase

  • Branch changed from u/dlucas/golay_codes to public/newgolaycodesclass
  • Commit changed from 2db3057ebba6d8baf1c2004dae7aede7af53c5c0 to 44a25be9e37bd1d4b8d33f1b85bd02626de35a14
  • Milestone changed from sage-7.4 to sage-7.5

New commits:

4ad7107rebased over 7.5.rc1, fixed typo
a37b9ebfixed broken doctest in the file header
44a25befixed copy/pasted Ternay few times, etc

comment:16 Changed 6 months ago by cheuberg

  • Status changed from needs_review to needs_work

doctest failures in patchbot?

comment:17 Changed 6 months ago by dimpase

  • Reviewers set to Dima Pasechnik

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

comment:18 Changed 5 months ago by 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

comment:19 Changed 5 months ago by git

  • Commit changed from 44a25be9e37bd1d4b8d33f1b85bd02626de35a14 to 6ca8937e75667a47f8543a38223a5a4b6ba73c38

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

c802c81Merge ticket 21418 into 20908_rework_coding_index
ac2dd76Improved some more module doc strings. Fixed a merge bug. Added a ref to Feulner.
8185e87Updated to latest beta and fixed conflicts
b77de0fAdded new file that introduces the new parity-check code class. Initializes code class, generator matrix encoder class, straightforward encoder class and minimum distance method.
0b0d2f8Correcting mistakes. Two errors are still waiting for correction: ParityCheckCodeStraightforwardEncoder.unencode_nocheck and ParityCheckCodeGeneratorMatrixEncoder.__init__
62abcd7Fixed merge conflict.
1aa4b4eFixed doctests. Shorter output. Generator matrix encoder inherits from the generic one. Fixed encoders. Cleaned the code.
19e299eMerged 21328 and fixed broken doctests
f64841fMove cyclic code heading
6ca8937merged ticket 20908

comment:20 Changed 5 months ago by 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.

comment:21 Changed 5 months ago by dimpase

  • Milestone changed from sage-7.5 to sage-7.6

Are you debugging this?

comment:22 Changed 5 months ago by 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 ?

Last edited 5 months ago by danielaugot (previous) (diff)

comment:23 Changed 5 months ago by 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...

comment:24 Changed 5 months ago by 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 :-)

Last edited 5 months ago by dimpase (previous) (diff)

comment:25 Changed 5 months ago by dimpase

  • Work issues set to fix weight_enumerator()

comment:26 Changed 5 months ago by git

  • Commit changed from 6ca8937e75667a47f8543a38223a5a4b6ba73c38 to 6bf9d4b11523aaf7fcf69dc73d87352eefb29a8b

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

686b278Merge branch 'public/newgolaycodesclass' of trac.sagemath.org:sage into goco
6bf9d4bweight_enumerator from the parent class is OK - and typos fixed

comment:27 follow-up: Changed 5 months ago by dimpase

  • Status changed from needs_work to needs_review
  • Work issues fix weight_enumerator() deleted

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? :-( ).

comment:28 in reply to: ↑ 27 Changed 5 months ago by 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.

comment:29 Changed 5 months ago by danielaugot

All tests pass, with the option --long.

comment:30 Changed 5 months ago by danielaugot

  • Reviewers changed from Dima Pasechnik to Dima Pasechnik, Daniel Augot
  • Status changed from needs_review to positive_review

comment:31 Changed 5 months ago by vbraun

  • Status changed from positive_review to needs_work
[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

comment:32 Changed 5 months ago by git

  • Commit changed from 6bf9d4b11523aaf7fcf69dc73d87352eefb29a8b to 7c91f044424e788f274bae111524a894c9671aba

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

7c91f04fixed the ref

comment:33 Changed 5 months ago by dimpase

  • Authors changed from Arpit Merchant, David Lucas to Arpit Merchant, David Lucas, Dima Pasechnik, Daniel Augot
  • Status changed from needs_work to positive_review

IMHO we deserve co-authorship on this :-)

comment:34 Changed 5 months ago by danielaugot

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

comment:35 Changed 5 months ago by vbraun

  • Status changed from positive_review to needs_work
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

comment:36 Changed 5 months ago by git

  • Commit changed from 7c91f044424e788f274bae111524a894c9671aba to 3ef25b45c870917bc4ee0e31e4015b4f23eb476d

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

3ef25b4missing ')' added to the doctest

comment:37 Changed 5 months ago by 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?

comment:38 Changed 5 months ago by dimpase

  • Status changed from needs_work to positive_review

comment:39 Changed 5 months ago by vbraun

  • Status changed from positive_review to needs_work

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

comment:40 Changed 5 months ago by git

  • Commit changed from 3ef25b45c870917bc4ee0e31e4015b4f23eb476d to 801dc1033b0dc2083dcc1984b0ebad6229ec0e7b

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

801dc10fixed broken by deprecation doctest

comment:41 Changed 5 months ago by dimpase

  • Status changed from needs_work to positive_review

all right, all right...

comment:42 Changed 5 months ago by vbraun

  • Branch changed from public/newgolaycodesclass to 801dc1033b0dc2083dcc1984b0ebad6229ec0e7b
  • Resolution set to fixed
  • Status changed from positive_review to closed

comment:43 Changed 5 months ago by danielaugot

  • Commit 801dc1033b0dc2083dcc1984b0ebad6229ec0e7b deleted

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

Note: See TracTickets for help on using tickets.