#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, GitHub, GitLab) | 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 5 years ago by
- Branch set to u/arpitdm/golay_codes
comment:2 Changed 5 years ago by
- Commit set to 72cae05801296575da9a3c6f4a3b58526ace7643
comment:3 Changed 5 years ago by
- 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: ↓ 5 Changed 5 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 5 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 5 years ago by
- Branch changed from u/arpitdm/golay_codes to u/danielaugot/golay_codes
comment:7 Changed 5 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 5 years ago by
- Branch changed from u/danielaugot/golay_codes to u/dlucas/golay_codes
comment:9 Changed 5 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 5 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 5 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 5 years ago by
- Commit changed from fa89d95956214cc1263c8a1f569e533359cc051b to 2db3057ebba6d8baf1c2004dae7aede7af53c5c0
comment:13 Changed 5 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 sage-7.4 to sage-7.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 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 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 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 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 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
|
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 sage-7.5 to sage-7.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 --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 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 follow-up: ↓ 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/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 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 co-authorship on this :-)
comment:34 Changed 4 years ago by
I could build the documentation after a make doc-clean
.
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/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 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.