#30085 closed enhancement (fixed)

Implemented constructions for Kasami codes

Reported by: gh-Ivo-Maffei Owned by:
Priority: major Milestone: sage-9.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:

Status badges

Description

We added methods to generate the extended Kasami codes and the Kasami codes. For a definition of those codes see the book "Distance-Regular Graphs" by Brouwer et. al.

Attachments (1)

typeset.diff (4.8 KB) - added by dimpase 22 months ago.
this fixed docbuild errors

Download all attachments as: .zip

Change History (33)

comment:1 Changed 23 months ago by gh-Ivo-Maffei

  • Cc dimpase added
  • Status changed from new to needs_review

comment:2 Changed 23 months ago by dimpase

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?

comment:3 Changed 23 months ago by dimpase

  • Cc jsrn caruso added

A minor merge conflict with #21226 - perhaps base this on top of the branch of #21226.

Would be also nice to have it seen by coding theory people - I CCd two.

comment:4 Changed 23 months ago by git

  • Commit changed from 8fe145b3e32446926c68c66b0367837ef540327f to b9fe4094f24f2546a1f4119f5dbec61d8f6ca091

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

b9fe409added drg to docstring; added minimum dist tests

comment:5 Changed 23 months ago by git

  • Commit changed from b9fe4094f24f2546a1f4119f5dbec61d8f6ca091 to b413fee4402793e08f60de8740a6d2abf390611f

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

f7d9438Merge in 28350, Linear Code No Metric
d4d3e89No Metric changes. Removed Relative Finite Field Extension, added vector_space method and basis option. Doctests and documentation. Deleted rank metric specific encoders.
1e32a0cSuper method of LinearRankMetricCode includes basis.
3917048Merge branch 'develop' of git://trac.sagemath.org/sage into rank_metric
bd31704Merge branch 'u/gh-emes4/coding/no_metric' of git://trac.sagemath.org/sage into rank_metric
0a115d0Removed zero method. Added field extension method.
5ea97acMerge branch 'u/gh-emes4/coding/linear_rank_metric' of git://trac.sagemath.org/sage into rank_metric_codes
3f0d00cMerge remote-tracking branch 'trac/develop' into HEAD
ffb8297take into account map change in trac:#28481
b413feemerged u/dimpase/coding/linear_rank_metric

comment:6 Changed 23 months ago by gh-Ivo-Maffei

  • Dependencies set to #21226

comment:7 Changed 23 months ago by jsrn

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 sub-class 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 jsrn

If you insist on keeping these as functions, consider putting the functions in the code_constructions module (where other similar functions that produce LinearCodes are).

comment:9 Changed 23 months ago by git

  • Commit changed from b413fee4402793e08f60de8740a6d2abf390611f to 140ea7e83ce0ca9a839fd40911118c68720744c4

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

140ea7eswapped kasami codes to a class

comment:10 Changed 23 months ago by git

  • Commit changed from 140ea7e83ce0ca9a839fd40911118c68720744c4 to babe9ad0cb7be80970555053c77cf4cdf98e0012

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

babe9adMerge branch 'develop' into kasami_codes

comment:11 Changed 23 months ago by dimpase

  • 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 caruso

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 caruso

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 git

  • Commit changed from babe9ad0cb7be80970555053c77cf4cdf98e0012 to 12462e076b325a505ca83d13c78b2fa2630a44d3

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

fe8d9a6incorporated auxiliary functions
12462e0fix bug and whitespaces

comment:15 follow-up: Changed 22 months ago by jsrn

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 (see grs_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 Reed-Solomon 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 caruso

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.

Last edited 22 months ago by caruso (previous) (diff)

comment:17 Changed 22 months ago by dimpase

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 jsrn

@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 2-line implementation above and accept the warning for now. In #24279, we remove this warning. 2) Expand my 2-line implementation to a 5-line 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 jsrn

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]*(m-len(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 gh-Ivo-Maffei

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:

  1. the extended Kasami code (4,2) is empty, so I'm not sure how the minimum distance is defined;
  2. 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 git

  • Commit changed from 12462e076b325a505ca83d13c78b2fa2630a44d3 to 466961f832024f13ac67e208fd44f0779ed1d8ac

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

9946dbaMerge branch 'develop' into kasami_codes
466961fadded references to Kasami's papers; new generator function method; all line within 80 columns

comment:22 Changed 22 months ago by gh-Ivo-Maffei

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.sphinx-doc.org/en/master/usage/restructuredtext/basics.html). Any help is highly appreciated.

comment:23 Changed 22 months ago by dimpase

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 git

  • Commit changed from 466961f832024f13ac67e208fd44f0779ed1d8ac to 45975642179088d38bfdbf052315aa6fd4f82c3a

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

cb710e1fix docstring whitespaces
4597564improve formattting without breaking docstring

comment:25 Changed 22 months ago by caruso

Another point: you should document the function __eq__

comment:26 Changed 22 months ago by git

  • Commit changed from 45975642179088d38bfdbf052315aa6fd4f82c3a to a2b060c04945072f042b767e0dd3ecefdf81bd05

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

5c22a09make __eq__ function clearer
a2b060cadded more documentaion on __eq__

Changed 22 months ago by dimpase

this fixed docbuild errors

comment:27 Changed 22 months ago by dimpase

I've attached a diff which makes the docs build. (probably far from minimal, but OK)

comment:28 Changed 22 months ago by git

  • Commit changed from a2b060c04945072f042b767e0dd3ecefdf81bd05 to b94cc3b1a2a9ec61e294bc8310b77590b4f3df44

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

b94cc3bfixed docstring build error

comment:29 Changed 22 months ago by caruso

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 caruso

OK, I just realized that this method was added in #21226...

comment:31 Changed 22 months ago by dimpase

  • 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 vbraun

  • Branch changed from u/gh-Ivo-Maffei/kasami_codes to b94cc3b1a2a9ec61e294bc8310b77590b4f3df44
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.