Opened 23 months ago
Closed 22 months ago
#30085 closed enhancement (fixed)
Implemented constructions for Kasami codes
Reported by:  ghIvoMaffei  Owned by:  

Priority:  major  Milestone:  sage9.2 
Component:  coding theory  Keywords:  linear_codes 
Cc:  dimpase, jsrn, caruso  Merged in:  
Authors:  Ivo Maffei  Reviewers:  Dima Pasechnik 
Report Upstream:  N/A  Work issues:  
Branch:  b94cc3b (Commits, GitHub, GitLab)  Commit:  b94cc3b1a2a9ec61e294bc8310b77590b4f3df44 
Dependencies:  #21226  Stopgaps: 
Description
We added methods to generate the extended Kasami codes and the Kasami codes. For a definition of those codes see the book "DistanceRegular Graphs" by Brouwer et. al.
Attachments (1)
Change History (33)
comment:1 Changed 23 months ago by
 Cc dimpase added
 Status changed from new to needs_review
comment:2 Changed 23 months ago by
comment:3 Changed 23 months ago by
 Cc jsrn caruso added
comment:4 Changed 23 months ago by
 Commit changed from 8fe145b3e32446926c68c66b0367837ef540327f to b9fe4094f24f2546a1f4119f5dbec61d8f6ca091
Branch pushed to git repo; I updated commit sha1. New commits:
b9fe409  added drg to docstring; added minimum dist tests

comment:5 Changed 23 months ago by
 Commit changed from b9fe4094f24f2546a1f4119f5dbec61d8f6ca091 to b413fee4402793e08f60de8740a6d2abf390611f
Branch pushed to git repo; I updated commit sha1. Last 10 new commits:
f7d9438  Merge in 28350, Linear Code No Metric

d4d3e89  No Metric changes. Removed Relative Finite Field Extension, added vector_space method and basis option. Doctests and documentation. Deleted rank metric specific encoders.

1e32a0c  Super method of LinearRankMetricCode includes basis.

3917048  Merge branch 'develop' of git://trac.sagemath.org/sage into rank_metric

bd31704  Merge branch 'u/ghemes4/coding/no_metric' of git://trac.sagemath.org/sage into rank_metric

0a115d0  Removed zero method. Added field extension method.

5ea97ac  Merge branch 'u/ghemes4/coding/linear_rank_metric' of git://trac.sagemath.org/sage into rank_metric_codes

3f0d00c  Merge remotetracking branch 'trac/develop' into HEAD

ffb8297  take into account map change in trac:#28481

b413fee  merged u/dimpase/coding/linear_rank_metric

comment:6 Changed 23 months ago by
 Dependencies set to #21226
comment:7 Changed 23 months ago by
I don't know these codes, but I a priori think it would be better to follow the general convention for codes that they be classes. The idea is that if one has special knowledge on such codes (e.g. know either their minimum distance, their weight enumerator, etc.) then a subclass of AbstractLinearCode? would be able to override those methods with specialised, fast ones. Converting your functions to classes requires a bit more boilerplate, but you can follow the thematic tutorial on this.
comment:8 Changed 23 months ago by
If you insist on keeping these as functions, consider putting the functions in the code_constructions
module (where other similar functions that produce LinearCode
s are).
comment:9 Changed 23 months ago by
 Commit changed from b413fee4402793e08f60de8740a6d2abf390611f to 140ea7e83ce0ca9a839fd40911118c68720744c4
Branch pushed to git repo; I updated commit sha1. New commits:
140ea7e  swapped kasami codes to a class

comment:10 Changed 23 months ago by
 Commit changed from 140ea7e83ce0ca9a839fd40911118c68720744c4 to babe9ad0cb7be80970555053c77cf4cdf98e0012
Branch pushed to git repo; I updated commit sha1. New commits:
babe9ad  Merge branch 'develop' into kasami_codes

comment:11 Changed 23 months ago by
 Reviewers set to Dima Pasechnik
Johan, are you happy with the design now? (tests pass, by the way)
comment:12 Changed 23 months ago by
I think it is not a good idea to put all the interesting doctests in underscore functions.
Actually, I do not see why you need those helper functions. Couldn't you put directly all your code in the method generator_matrix
?
comment:13 Changed 22 months ago by
Moreover, on patchbot's report:
sage t long src/sage/coding/kasami_codes.pyx # Timed out
I think it is more reasonable to remove
sage: C = codes.KasamiCode(64,4) sage: C.minimum_distance() # long time 4
and
sage: C = codes.KasamiCode(64,4, extended=False) sage: C.minimum_distance() # long time 3
comment:14 Changed 22 months ago by
 Commit changed from babe9ad0cb7be80970555053c77cf4cdf98e0012 to 12462e076b325a505ca83d13c78b2fa2630a44d3
comment:15 followup: ↓ 16 Changed 22 months ago by
Structural comments:
 Please reference (also) Kasami's original paper(s): this is more correct and is for many academics more easily obtained than Brouwer's book.
 Please add the definition of Kasami codes in the top of the file. The definition is short and compact (at least the one given in Brouwer). In particular, it should be explicitly mentioned that these are binary codes. They are in fact subfield subcodes of the code having those three equations as parity checks (see also below), so that could be emphasised.
 According to Brouwer, the minimum distance of (extended) Kasami codes is
always known. Such cases are exactly the motivation for special classes for a
code family: please override
minimum_distance
to return this number without computation.
 Kasami's 1966 technical report is about "weight distributions" of codes. Is
the entire weight distribution of (extended) Kasami codes known? In that case,
it would be much nicer to override
weight_distribution
to return this without having to go through the whole code (seegrs_code.py
for an example). I won't insist, though.
 Whether it's the extended Kasami code or not should perhaps be stored in a local parameter instead of matching on the length all the time.
 I'm concerned that the string epresentation of the code is confusing. Normally we say "[n, k] linear code" or "[n, k] Generalized ReedSolomon code" etc., and printing "(s, t) <Extended> Kasami code" may confuse users. Consider e.g. printing "[n, k] <Extended> (s, t)Kasami code".
Code comments:
There are many lines exceeding 80 chars. Is this not still a convention of SageMath?
generator_matrix
is much more complicated than it needs to be: Note that the
Kasami code is a subfield subcode of a code with 3 parity checks over GF(s)
.
Here is a few lines of code which produces a generator matrix for the Kasami
code:
s = 8 t = 4 n = s F = GF(s) Cext = codes.from_parity_check_matrix(matrix(F, 3, n, [[1]*n, F.list(), [ a^(t+1) for a in F]])) G = codes.SubfieldSubcode(Cext, GF(2)).generator_matrix()
The main disadvantage is that this currently emits a warning, because #24279 is still not merged. Perhaps this is a good motivation to finish up that ticket, and use the shorter, more mathematical code for Kasami codes?
comment:16 in reply to: ↑ 15 Changed 22 months ago by
Replying to jsrn:
The main disadvantage is that this currently emits a warning, because #24279 is still not merged. Perhaps this is a good motivation to finish up that ticket, and use the shorter, more mathematical code for Kasami codes?
Of course, it would be very nice to close #24279 and subsequent tickets but I would let this for another time since I'm not sure it will be an easy job. Indeed, notice that #21413 is now ready (and merged!) and that several people (including possibly myself at some point) are working on implementing relative finite fields extensions in #28485, which could be a (better?) alternative to #24279.
comment:17 Changed 22 months ago by
long lines in the code (apart from output of doctests) should not be too long  officially, 80 chars, make it 90 if really needed, but no more.
comment:18 Changed 22 months ago by
@caruso: Sure, it's a valid point to not wish to defer progress here by first fixing up stuff elsewhere. I definitely wouldn't wait for #28485, since #24279 is a much easier fix using stuff already shipped in Sage. If not waiting for either tickets is preferred, I see two good options: 1) Use my 2line implementation above and accept the warning for now. In #24279, we remove this warning. 2) Expand my 2line implementation to a 5line one which basically implements the meat of SubfieldSubcode
itself using the GF(s).vector space()
method (or simply uses a.polynomial().list()
since we're going down to GF(2)
.)
comment:19 Changed 22 months ago by
Here is an implementation avoiding SubfieldSubcode
:
s, t= 16, 4 m = log(s, 2) F = GF(s) Hext = matrix(F, 3, s, [[1]*s, F.list(), [ a^(t+1) for a in F]]) def exp(row): return matrix(F, len(row), m, [ l + [0]*(mlen(l)) for l in [ a.polynomial().list() for a in row ]])\ .transpose() H = block_matrix(GF(2), 3, 1, [ exp(row) for row in Hext.rows() ]) G = H.right_kernel().basis_matrix()
comment:20 Changed 22 months ago by
Thanks for the feedback, I'm now working on fixing all point raised. I have little knowledge of coding theory but I need the Kasami codes for a later ticket.
I referenced the Kasami's papers which are quoted by Brouwer and Wikipedia, but I don't see how these relates to these codes.
Brouwer does not provide a proof for the minimum distances stated and I believe they are wrong. For instance:
 the extended Kasami code (4,2) is empty, so I'm not sure how the minimum distance is defined;
 the extended Kasami code (8,2) has only 2 vectors (zero vector and one vector), so has minimum distance 8 not 6 as stated by Brouwer.
I have no idea if the weight distribution of these codes is known.
As far as the generator matrix is concerned, I'm happy that there is a quicker way to compute it. I'll try to expand what suggested by @jsrn to something that doesn't emit any warning.
comment:21 Changed 22 months ago by
 Commit changed from 12462e076b325a505ca83d13c78b2fa2630a44d3 to 466961f832024f13ac67e208fd44f0779ed1d8ac
comment:22 Changed 22 months ago by
The doctoring doesn't compile. I get an error
OSError: docstring of sage.coding.kasami_codes:18: WARNING: Unexpected indentation.
I really don't see what's wrong as it matches the sphinx guidelines (https://www.sphinxdoc.org/en/master/usage/restructuredtext/basics.html). Any help is highly appreciated.
comment:23 Changed 22 months ago by
I'd check on :
vs ::
, and perhaps missing empty lines before lists with *
items.
I'm building your branch now, will see later myself.
comment:24 Changed 22 months ago by
 Commit changed from 466961f832024f13ac67e208fd44f0779ed1d8ac to 45975642179088d38bfdbf052315aa6fd4f82c3a
comment:25 Changed 22 months ago by
Another point: you should document the function __eq__
comment:26 Changed 22 months ago by
 Commit changed from 45975642179088d38bfdbf052315aa6fd4f82c3a to a2b060c04945072f042b767e0dd3ecefdf81bd05
comment:27 Changed 22 months ago by
I've attached a diff which makes the docs build. (probably far from minimal, but OK)
comment:28 Changed 22 months ago by
 Commit changed from a2b060c04945072f042b767e0dd3ecefdf81bd05 to b94cc3b1a2a9ec61e294bc8310b77590b4f3df44
Branch pushed to git repo; I updated commit sha1. New commits:
b94cc3b  fixed docstring build error

comment:29 Changed 22 months ago by
Sorry, I was meaning the __eq__
method you added in sage.coding.linear_code_no_metric
; it misses doctests.
Btw, I'm not quite sure but it's maybe better to implement _richcmp_
than __eq__
(actually, it's what I'm doing usually). Does somebody know more about this?
comment:30 Changed 22 months ago by
OK, I just realized that this method was added in #21226...
comment:31 Changed 22 months ago by
 Status changed from needs_review to positive_review
#21226 has been fixed, so this looks good to go, too.
comment:32 Changed 22 months ago by
 Branch changed from u/ghIvoMaffei/kasami_codes to b94cc3b1a2a9ec61e294bc8310b77590b4f3df44
 Resolution set to fixed
 Status changed from positive_review to closed
OK, could you add checks on things like minimal distances of these codes? Also, IIRC they are used to construct certain d.r.g.'s  could you mention which ones?