An Abstract Class for Rank Metric Codes

[arpitdm]

We propose to implement AbstractRankMetricCode, an abstract class for rank metric codes which will initialize the basic parameters that every rank metric code possesses. This will inherit from AbstractCode class. Further, we propose to add rank-metric based methods to compute distance, weight and allow for matrix to vector (and reverse) conversions between representations. Finally, we create a generic representative class LinearRankMetricCode as well as encoding (generator matrix, systematic) and decoding (nearest neighbour) methods.

CC: @sagetrac-dlucas @johanrosenkilde @dimpase @xcaruso @Adurand8 @mbombar @vbraun

Component: coding theory

Author: Arpit Merchant, Marketa Slukova, Johan Rosenkilde

Branch: 899d390

Reviewer: Dima Pasechnik, Johan Rosenkilde, Xavier Caruso

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

[arpitdm]

Branch: u/arpitdm/abstract_linear_rank_metric_code_class

[arpitdm]

comment:2

1. I've written a basic constructor for the class along with a couple of getter methods.
2. I've added some modified rank-metric based methods.
3. And deleted some methods from the ALC class according to the schema described in past discussions. There's about 10 more that need to be deleted similarly. I'm trying to see if this be written more compactly. Open to ideas.

More to follow.

---

New commits:

7e4b3a3

added a very basic constructor, a couple of basic getter methods and deleted a couple of methods from ALC class. added some rank distance, rank weight, to_matrix_representation and from_matrix_representation.

[arpitdm]

Commit: 7e4b3a3

[sagetrac-dlucas]

comment:3

Hello,

I won't comment extensively for now, as there's still a lot to do.
I just have one small comment/remark to keep in mind for later: when you will work on documentation, remember to carefully explain which representation you chose (matrix vs. vector) and how to get the other one to be sure users do understand how this class works
and what they should expect from it.

David

[johanrosenkilde]

comment:4

Replying to @sagetrac-dlucas:

Hello,

I won't comment extensively for now, as there's still a lot to do.
I just have one small comment/remark to keep in mind for later: when you will work on documentation, remember to carefully explain which representation you chose (matrix vs. vector) and how to get the other one to be sure users do understand how this class works
and what they should expect from it.

Seconded. And remember to explain that this class only supports rank-metric codes which are linear over the big field!

Best,
Johan

[johanrosenkilde]

comment:5

What's the state of this? What is missing? When do you plan to do it?

Best,
Johan

[johanrosenkilde]

comment:6

I think the class should be call AbstractLinearRankMetricCode by the way. It's terribly long, but the Linear is important.

[emes4]

Changed commit from 7e4b3a3 to none

[emes4]

Dependencies: #28073

[emes4]

Changed author from Arpit Merchant to Arpit Merchant, Marketa Slukova

[emes4]

Changed branch from u/arpitdm/abstract_linear_rank_metric_code_class to u/gh-emes4/coding/linear_rank_metric

[sagetrac-git]

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

64f446a	Merge branch 'develop' of git://trac.sagemath.org/sage into abstract_code
53e445b	added base_ring and length parameter to AbstractCode
5e6dffe	Fixed some dependencies. Category still set up wrong.
ba4fc53	Merge branch 'abstract_code' into t/28073/abstract_code
e8edfeb	Fixed unclean merge.
880aebb	Fixed default decoder/encoder dependencies. Set to None by default.
d115600	No category set up and base_field in AbstractCode. No encoder/decoder error msgs. Documentation and tests.
82fdc3c	Merge branch 'develop' of git://trac.sagemath.org/sage into rank_metric
5c0fd69	Merge branch 'develop' of git://trac.sagemath.org/sage into rank_metric
a251c61	Inheriting from Abstract Code. Encoding, decoding methods. Generic LinearRankMetricCode class.

[sagetrac-git]

Commit: a251c61

[sagetrac-git]

Changed commit from a251c61 to 05476b3

[sagetrac-git]

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

05476b3

Generator matrix methods in AbstractLinearRankMetricCode

[sagetrac-git]

Changed commit from 05476b3 to 08b6e4f

[sagetrac-git]

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

524efc8	Inheriting from Abstract Code. Encoding, decoding methods. Generic LinearRankMetricCode class.
77fc1e2	Generator matrix methods in AbstractLinearRankMetricCode
08b6e4f	Merge branch 'u/gh-emes4/coding/linear_rank_metric' of git://trac.sagemath.org/sage into rank_metric

[emes4]

Changed dependencies from #28073 to #28073, #28209

[sagetrac-git]

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

8442aa6	documentation
086fa74	AbstractLinearRankMetricCode done
c39e3ca	Classes and methods done.
12bb30f	Generic documentation.

[sagetrac-git]

Changed commit from 08b6e4f to 12bb30f

[emes4]

comment:15

Finished up everything and added documentation and doc tests. Few notes:

I kept the parameter requirement that the length of the code has to be at most the degree of the extension.

I didn't manage to turn off the experimental warning, except for handling it in doc tests.

I will add a doctest for the method decode_to_code when Gabidulin codes are in place.

There is no test for linearity over the big field and also no test for the finite field extension in the initialising parameters of AbstractLinearRankMetricCode.

I also added a very slow algorithm for computing the minimum distance.

[sagetrac-git]

Changed commit from 12bb30f to 72df923

[sagetrac-git]

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

2bf73f8	Merge branch 'develop' of git://trac.sagemath.org/sage into t/28073/abstract_code
487e9e2	Category related methods added. Encoder/decoder documentation specified for linear codes.
40df01e	Finished up documentation.
b7cab95	Merge branch 'u/gh-emes4/coding/abstract_code' of git://trac.sagemath.org/sage into rank_metric
25ca9b7	Merge branch 'develop' of git://trac.sagemath.org/sage into rank_metric
72df923	Documentation tree link and fixes. Updated Sage.

[emes4]

Changed dependencies from #28073, #28209 to #28073

[xcaruso]

comment:41

Thanks.

Since I haven't really looked into the code of this ticket, I let Dima give again a positive review if appropriate.

Btw, I'm wondering: is it preferable to implement __eq__, __ne__, etc. or _richcmp_? I believed that the latter solution was better, but I'm not sure.

[xcaruso]

comment:42

Note also that the patchbot reported some warning (pyflakes, pycodestyle and blocks).

[dimpase]

comment:43

Thanks. First time I missed the _eq_ problem, as I thought it's just some kind of Python3 formality. Looks OK now.

[vbraun]

comment:44

PDF docs don't build:

[docpdf] l.4668 \(1,^^H
[docpdf]               eta,\ldots,^^Heta^{sm}\) be the power basis that SageMath uses to

[dimpase]

comment:45

hmm, is \beta the problem, or \ldots, or both?

[xcaruso]

comment:46

I'm not 100% sure but I think it comes from \beta. However, I don't know what's wrong.

Besides, reading this doctest, I find that it's not very clear; for instance, what is q is implicit and not obvious, I would say. Moreover, the two notations GF(q) and F_{q} are used to refer to the same object (namely, the finite field with q elements) and I think that they are both incorrect, the correct one being \GF(q).

[dimpase]

comment:47

by the way, there are typos - beta vs \beta in 6 places.

Perhaps \beta must be added to some silly list... (and/or written in utf-8)

[dimpase]

Changed commit from 5f46031 to 899d390

[dimpase]

Changed dependencies from #28350 to none

[dimpase]

Changed branch from u/jsrn/coding/linear_rank_metric to u/dimpase/coding/linear_rank_metric

[dimpase]

comment:48

ok, this works with pdf

---

New commits:

899d390

make \beta unicode

[vbraun]

Changed branch from u/dimpase/coding/linear_rank_metric to 899d390

[dimpase]

comment:50

the last commit did not make it into the beta, or got overwritten

[dimpase]

Changed commit from 899d390 to none

[dimpase]

comment:51

Volker, something went missing with this merge, e.g. the last commit, ​899d390, did not get merged.
​

[vbraun]

comment:52

This ticket isn't in any relased beta yet. 899d390 will be in 9.2.beta7 which I'm releasing right now

[dimpase]

comment:53

OK - it was confusing that it was marked as closed already.