#20787 closed enhancement (fixed)
A class to manage Golay Codes
Reported by:  arpitdm  Owned by:  

Priority:  major  Milestone:  sage7.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 4 years ago by
 Branch set to u/arpitdm/golay_codes
comment:2 Changed 4 years ago by
 Commit set to 72cae05801296575da9a3c6f4a3b58526ace7643
comment:3 Changed 4 years ago by
 Cc richmond jlavauzelle danielaugot added
 Keywords sd75 added
 Milestone changed from sage7.3 to sage7.4
 Status changed from new to needs_info
comment:4 followup: ↓ 5 Changed 4 years ago by
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 4 years ago by
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 4 years ago by
 Branch changed from u/arpitdm/golay_codes to u/danielaugot/golay_codes
comment:7 Changed 4 years ago by
 Commit changed from 72cae05801296575da9a3c6f4a3b58526ace7643 to f7f62c718dd9cf6d5d2d3bae82f2f750e0f69d2a
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

comment:8 Changed 4 years ago by
 Branch changed from u/danielaugot/golay_codes to u/dlucas/golay_codes
comment:9 Changed 4 years ago by
 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:
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

comment:10 Changed 4 years ago by
 Commit changed from ae268705b6112ee7d3df4843b01009ac3f7d248d to fa89d95956214cc1263c8a1f569e533359cc051b
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

comment:11 Changed 4 years ago by
 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 takesGF(2)/GF(3)
as input instead of"binary"/"ternary"
, andextended=True/False
instead of a string"true"/"false"
. I also chose to setextended
toTrue
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"
, andcodes.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
comment:12 Changed 4 years ago by
 Commit changed from fa89d95956214cc1263c8a1f569e533359cc051b to 2db3057ebba6d8baf1c2004dae7aede7af53c5c0
comment:13 Changed 4 years ago by
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 4 years ago by
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 4 years ago by
 Branch changed from u/dlucas/golay_codes to public/newgolaycodesclass
 Commit changed from 2db3057ebba6d8baf1c2004dae7aede7af53c5c0 to 44a25be9e37bd1d4b8d33f1b85bd02626de35a14
 Milestone changed from sage7.4 to sage7.5
comment:16 Changed 4 years ago by
 Status changed from needs_review to needs_work
doctest failures in patchbot?
comment:17 Changed 4 years ago by
 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 selfdual codes. REFERENCES:   [HP03]_ pp. 3133 for a definition of Golay codes. +  [HP2003]_ pp. 3133 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 4 years ago by
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 selfduality
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
selfduality
sage: G0perp = G0.dual_code() sage: G0.generator_matrix() * G0perp.generator_matrix().transpose() == 0 # basic test of mathematical correctness True
comment:19 Changed 4 years ago by
 Commit changed from 44a25be9e37bd1d4b8d33f1b85bd02626de35a14 to 6ca8937e75667a47f8543a38223a5a4b6ba73c38
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 paritycheck 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

comment:20 Changed 4 years ago by
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 4 years ago by
 Milestone changed from sage7.5 to sage7.6
Are you debugging this?
comment:22 Changed 4 years ago by
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 ?
comment:23 Changed 4 years ago by
The bug is in zeta_polynomial()
, as should be clear from the log:
sage t long warnlong 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/sitepackages/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/sitepackages/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/sitepackages/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/sitepackages/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) <ipythoninput48fcefbaf83d4> in <module>() > 1 C.zeta_polynomial() /home/scratch/dimpase/sage/sage/local/lib/python2.7/sitepackages/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 = nddperp+2 3439 P_coeffs = [] ... ZeroDivisionError: rational division by zero
so just some silly indexing bug, binomial(n,i+d)
becomes 0...
comment:24 Changed 4 years ago by
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 :)
comment:25 Changed 4 years ago by
 Work issues set to fix weight_enumerator()
comment:26 Changed 4 years ago by
 Commit changed from 6ca8937e75667a47f8543a38223a5a4b6ba73c38 to 6bf9d4b11523aaf7fcf69dc73d87352eefb29a8b
comment:27 followup: ↓ 28 Changed 4 years ago by
 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 4 years ago by
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 4 years ago by
All tests pass, with the option long
.
comment:30 Changed 4 years ago by
 Reviewers changed from Dima Pasechnik to Dima Pasechnik, Daniel Augot
 Status changed from needs_review to positive_review
comment:31 Changed 4 years ago by
 Status changed from positive_review to needs_work
[dochtml] OSError: [coding ] /mnt/disk/home/release/Sage/local/lib/python2.7/sitepackages/sage/coding/golay_code.py:docstring of sage.coding.golay_code:8: WARNING: citation not found: HP03 [dochtml] Makefile:1083: recipe for target 'dochtml' failed
comment:32 Changed 4 years ago by
 Commit changed from 6bf9d4b11523aaf7fcf69dc73d87352eefb29a8b to 7c91f044424e788f274bae111524a894c9671aba
Branch pushed to git repo; I updated commit sha1. New commits:
7c91f04  fixed the ref

comment:33 Changed 4 years ago by
 Status changed from needs_work to positive_review
IMHO we deserve coauthorship on this :)
comment:34 Changed 4 years ago by
I could build the documentation after a make docclean
.
comment:35 Changed 4 years ago by
 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/buildslavesage/slave/sage_git/build/local/lib/python2.7/sitepackages/sage/doctest/forker.py", line 498, in _run 4740 self.compile_and_execute(example, compiler, test.globs) 4741 File "/Users/buildslavesage/slave/sage_git/build/local/lib/python2.7/sitepackages/sage/doctest/forker.py", line 859, in compile_and_execute 4742 compiled = compiler(example) 4743 File "/Users/buildslavesage/slave/sage_git/build/local/lib/python2.7/sitepackages/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 4 years ago by
 Commit changed from 7c91f044424e788f274bae111524a894c9671aba to 3ef25b45c870917bc4ee0e31e4015b4f23eb476d
Branch pushed to git repo; I updated commit sha1. New commits:
3ef25b4  missing ')' added to the doctest

comment:37 Changed 4 years ago by
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 4 years ago by
 Status changed from needs_work to positive_review
comment:39 Changed 4 years ago by
 Status changed from positive_review to needs_work
comment:40 Changed 4 years ago by
 Commit changed from 3ef25b45c870917bc4ee0e31e4015b4f23eb476d to 801dc1033b0dc2083dcc1984b0ebad6229ec0e7b
Branch pushed to git repo; I updated commit sha1. New commits:
801dc10  fixed broken by deprecation doctest

comment:41 Changed 4 years ago by
 Status changed from needs_work to positive_review
all right, all right...
comment:42 Changed 4 years ago by
 Branch changed from public/newgolaycodesclass to 801dc1033b0dc2083dcc1984b0ebad6229ec0e7b
 Resolution set to fixed
 Status changed from positive_review to closed
comment:43 Changed 4 years ago by
 Commit 801dc1033b0dc2083dcc1984b0ebad6229ec0e7b deleted
Thanks a lot, Dima, for so much help. Daniel
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:
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)
, wherealphabet
has to be eitherbinary
orternary
andextended
is a boolean. Do you think it's a good idea to allow the user to passGF(2)
/GF(3)
directly to alphabet? It seems quite natural to me to allow such an input. Also, I'd tend to setextended
toFalse
by default. Any comments?David
New commits:
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.