Implemented constructions for Kasami codes

[Ivo-Maffei]

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.

Depends on #21226

CC: @dimpase @johanrosenkilde @xcaruso

Component: coding theory

Keywords: linear_codes

Author: Ivo Maffei

Branch/Commit: b94cc3b

Reviewer: Dima Pasechnik

Issue created by migration from https://trac.sagemath.org/ticket/30085

[dimpase]

comment:2

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?

[dimpase]

comment:3

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.

[sagetrac-git]

Changed commit from 8fe145b to b9fe409

[sagetrac-git]

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

b9fe409

added drg to docstring; added minimum dist tests

[sagetrac-git]

Changed commit from b9fe409 to b413fee

[sagetrac-git]

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/gh-emes4/coding/no_metric' of git://trac.sagemath.org/sage into rank_metric
0a115d0	Removed zero method. Added field extension method.
5ea97ac	Merge branch 'u/gh-emes4/coding/linear_rank_metric' of git://trac.sagemath.org/sage into rank_metric_codes
3f0d00c	Merge remote-tracking branch 'trac/develop' into HEAD
ffb8297	take into account map change in trac:#28481
b413fee	merged u/dimpase/coding/linear_rank_metric

[Ivo-Maffei]

Dependencies: #21226

[johanrosenkilde]

comment:7

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.

[johanrosenkilde]

comment:8

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).

[sagetrac-git]

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

140ea7e

swapped kasami codes to a class

[sagetrac-git]

Changed commit from b413fee to 140ea7e

[sagetrac-git]

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

babe9ad

Merge branch 'develop' into kasami_codes

[sagetrac-git]

Changed commit from 140ea7e to babe9ad

[dimpase]

Reviewer: Dima Pasechnik

[dimpase]

comment:11

Johan, are you happy with the design now? (tests pass, by the way)

[xcaruso]

comment:12

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?

[xcaruso]

comment:13

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

[sagetrac-git]

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

fe8d9a6	incorporated auxiliary functions
12462e0	fix bug and whitespaces

[sagetrac-git]

Changed commit from babe9ad to 12462e0

[johanrosenkilde]

comment:15

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) Kasami code" may confuse users. Consider
  e.g. printing "[n, k] (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?

[xcaruso]

comment:16

Replying to @johanrosenkilde:

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.

[dimpase]

comment:17

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.

[johanrosenkilde]

comment:18

@xcaruso: 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).)

[johanrosenkilde]

comment:19

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()

[Ivo-Maffei]

comment:20

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 @johanrosenkilde to something that doesn't emit any warning.

[sagetrac-git]

Changed commit from 12462e0 to 466961f

[sagetrac-git]

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

9946dba	Merge branch 'develop' into kasami_codes
466961f	added references to Kasami's papers; new generator function method; all line within 80 columns

[Ivo-Maffei]

comment:22

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.

[dimpase]

comment:23

I'd check on : vs ::, and perhaps missing empty lines before lists with *-items.

I'm building your branch now, will see later myself.

[sagetrac-git]

Changed commit from 466961f to 4597564

[sagetrac-git]

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

cb710e1	fix docstring whitespaces
4597564	improve formattting without breaking docstring

[xcaruso]

comment:25

Another point: you should document the function __eq__

[sagetrac-git]

Changed commit from 4597564 to a2b060c

[sagetrac-git]

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

5c22a09	make `__eq__` function clearer
a2b060c	added more documentaion on __eq__

[dimpase]

this fixed docbuild errors

[dimpase]

comment:27

Attachment: typeset.diff.gz

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

[sagetrac-git]

Changed commit from a2b060c to b94cc3b

[sagetrac-git]

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

b94cc3b

fixed docstring build error

[xcaruso]

comment:29

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?

[xcaruso]

comment:30

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

[dimpase]

comment:31

#21226 has been fixed, so this looks good to go, too.

[vbraun]

Changed branch from u/gh-Ivo-Maffei/kasami_codes to b94cc3b