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.

[arpitdm]

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.

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

David

[jsrn]

Replying to 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

[jsrn]

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

Best, Johan

[jsrn]

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

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

[git]

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

​05476b3

Generator matrix methods in AbstractLinearRankMetricCode

[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

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

[gh-emes4]

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.

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

[jsrn]

This looks very good! Though my list of comments below is long, I think that this first stab at the class is very good work :-)

In the module doc of linear_rank_metric:

• Add the following paragraphs:

This module allows representing rank metric codes which are linear over the
big field `F_{q^m}`, i.e. the usual linearity condition when the codewords are
considered in vector form. One can also consider rank metric codes which are
only linear over `F_q`, but these are not currently supported in SageMath.

Note that linear rank metric codes per the definition of this file are
mathematically just linear block codes, and so could be considered as a
:class:`sage.coding.linear_code.LinearCode`. However, since most of the
functionality of that class is specific to the Hamming metric, the two notions
are implemented as entirely different in SageMath. If you wish to investigate
Hamming-metric properties of a linear rank metric code ``C``, you can easily
convert it by calling ``C_hamm = LinearCode(C.generator_matrix())``.

• Remove the sentence "One of the main uses ...". This is subjective and very much subject to change :-) Further, the main thrust of rank metric codes in the last 15 years are their applications in network coding, and not crypto.

• "The class (...).LinearRankMetricCode is a representative of ...". Perhaps this sentence should be something like

"The class (...).LinearRankMetricCode is the analog of (...).LinearCode, i.e. it is a generator matrix-based representation of a linear rank metric code without specific knowledge on the structure of the code.

• "Gabidulin codes are ... studied at the moment". Just remove "studied at the moment". The sentence after could be reformulated to "These codes are the rank-metric analog of Reed-Solomon codes".

• The headline AbstractLinearCode should be AbstractLinearRankMetricCode.

• "However, using the encoder/decoder framework requires the vector representation of codewords". This caveat is important but perhaps not well-placed here. I think I'd rather like to see it in the class doc of AbstractLinearRankMetricCode during a complete example of how to implement a code class.

• "so any linear code rank metric" -> "so any linear rank metric code".

• Under Further references, I think the link to Wikipedia should be a proper citation inserted into the citation file, see ​http://doc.sagemath.org/html/en/developer/coding_basics.html

Dima, what do you say?

About the to/from matrix repr:

• The class RelativeFiniteFieldExtension does a lot of computation the first time it is used (inverting an m * m matrix) and the result is then cached. Your two functions throw away the RelativeFiniteFieldExtension object each time they are called. You need to somehow cache that object between invocations of the function having the same base field and sub field.

One solution is to drop your global-scope functions and only have them inside AbstractLinearRankMetricCode. Then the RelativeFiniteFieldExtension object can be placed as a private field of the code object after the first time it is used. In fact, I see now that you allow the user to supply the field_extension (which should be a RelativeFiniteFieldExtension object) but you don't use it!

The downside is that it does make sense to have those functions outside the class. By using the @cached_method decorator or one of its friends, you might be able to more or less manually indicate that the RelativeFiniteFieldExtension object should be cached between invocations

• to_matrix_representation doesn't really need base_field since this is just the base field of v. Perhaps the argument order should be `v, sub_field=None, and if sub_field` is not set, then the prime field is just assumed.

A similar thing holds for from_matrix_representation: here we need neither the sub_field nor the base_field. However, the base_field should be possible to supply in case the user has constructed the big field using a specific irreducible polynomial, say.

For rank_weight and rank_distance, we should use the same signature as to_matrix_representation.

Note that both of these functions are severely limited in that they do not allow the user to select the basis of GF(q^m)/GF(q). This is of course due to exactly that limitation in RelativeFiniteFieldExtension, so it's not your fault, but it should be documented somewhere. This is not well-documented in RelativeFiniteFieldExtension either, I realise. Perhaps you could add the following paragraph to the class doc of RelativeFiniteFieldExtension, together with some shorter description of the same in your to/from matrix-functions along with a reference to the doc of RelativeFiniteFieldExtension:

This class currently does not support choosing an arbitrary basis of `F_{q^m}`
over `F_q`, but instead uses the following: if `q = p^s`, then let
`1,\beta,\ldots,\beta^{sm}` be the power basis that SageMath uses to represent
`F_{q^m}`. Then `1,\beta,\ldots,beta^{m-1}` is a basis of `F_{q^m}` over `F_q`.
This class uses that basis.

• The conformal checks in rank_distance should be before the to_matrix_representation calls. (the number of columns is the length of a and b and the number of rows is taken care of by the check on base_ring.

• You are missing INPUT blocks to many functions, in particular all the global-scope matrix functions.

In AbstractLinearRankMetricCode:

• Class doc: "The current implementation (...) supports only the vector representation. This means that to use the encoder/decoder framework. one has to work with vectors". Let's shorten that instead as something like:

"This implementation principally uses the vector representation."

Most users wouldn't care about the technical detail of "the encoder/decoder framework". That's just stuff that should work :-) Using the vector form is also a perfectly natural choice (and another would be to principally use the matrix form), and I don't think we really have to argue about it.

I'm OK with your "Instructions on how ..." block, but add also a reference to the __init__ doc which actually contains an example for AbstractLinearRankMetricCode.

• I think we should apply the same convention as in (Abstract)LinearCode, that a subclass of AbstractLinearRankMetricCode must supply a generator matrix. Then __iter__ and __hash__ can be defined on AbstractLinearRankMetricCode.

This also means we don't have to override __iter__ it in the examples.

This would be conformed to anyway by the refactor with AbstractLinearCodeNoMetric I suggest below.

• The MyRankMetricCode example is basically a stripped version of LinearRankMetricCode. Perhaps we should make it into an easy specific family, e.g.

         sage: from sage.coding.linear_rank_metric import AbstractLinearRankMetricCode
         sage: class RankRepetitionCode(AbstractLinearRankMetricCode):
         ....:   def __init__(self, base_field, sub_field, length):
         ....:       sage.coding.linear_rank_metric.AbstractLinearRankMetricCode.__init__(self, base_field, sub_field, length, 1, "GeneratorMatrix", "NearestNeighbor")
         ....:       beta = base_field.gen()
         ....:       self._generator_matrix = matrix(base_field, [[ beta^i for i in range(length) ]]) 
         ....:   def generator_matrix(self):
         ....:       return self._generator_matrix
         ....:   def _repr_(self):
         ....:       return "[%d, %d] my rank-metric repetition code over GF(%s)" % (self.length(), self.dimension(), self.base_field().cardinality())

Note that I didn't test this code. As long as `length <= |base_field/sub_field| then this code should have minimum rank distance length`.

• Currently the method field_extension() returns None when the user didn't supply a specific field_extension. In the refactor of this issue mentioned above, make sure that this method always makes sense.

• In the doc of extension_degree you could add the sentence "This is also the number of rows in the matrix form of a codeword of self.".

• Some method rename suggestions:

distance    -> rank_distance_between_vectors
weight      -> rank_weight_of_vector
to_matrix   -> matrix_form_of_vector
from_matrix -> vector_form_of_matrix

All their docs are sorely missing INPUT blocks.

• The question is whether minimum_distance should be called minimum_rank_distance? I'm torn between disliking the redundancy but liking the "explicit is better than implicit". Dima, what's your opinion?

• In minimum_distance, use sage.rings.infinity.infinity (possibly with capital letter?) instead of float('inf').

• In docs: "code word" -> "codeword".

• There's after all a fair amount of code duplication with AbstractLinearCode I'm thinking that we should make a class AbstractLinearCodeNoMetric which contains the methods:

`ambient_space`, `base_field`, `basis`, `dimension`, `generator_matrix`,
`parity_check_matrix`, `syndrome`, `__contains__`, `information_set`,
`is_information_set`, `dual_code`, `__getitem__`,
`systematic_generator_matrix`, `gens`, `__iter__`,
`is_permutation_automorphism`, `is_self_dual`, `is_self_orthogonal`,
`is_subcode`, `cardinality`, `permuted_code`, `rate`, `redundancy_matrix,
`standard_form`, `__hash__`

Not only is this a lot of saved copied code, it also adds a lot of service to the current proposed rank metric codes!

This could inherit from AbstractCode, and both AbstractLinearCode and AbstractLinearRankMetricCode inherits from AbstractLinearCodeNoMetric.

To properly test these methods both for linear codes and linear rank metric codes, perhaps we should add a _test_abstractcode_methods-function in `AbstractLinearCodeNoMetric? that can then be run in a doc-test for both LinearCode and LinearRankMetricCode using TestSuite (see the documentation for TestSuite to know what I mean). A test at this level of abstraction would often be nothing but calling the method and making sure it doesn't throw an exception, but a few of them could be slightly more interesting (like C.dual().dual() == C).

• We should follow the same convention as in AbstractLinearCode that the dimension is not given at construction time. For some codes it can be expensive to determine the dimension, e.g. for algebraic geometry codes. When designing these classes we were very careful that you don't pay for what you don't use, so construction is usually cheap, and then you pay only when calling whatever methods. Note that if you introduce AbstractLinearCodeNoMetric as suggested above, then we have to follow this convention anyway.

In LinearRankMetricCode:

• The reason the __init__ argument generator is not called generator_matrix is that we also accept e.g. a code or a vector space. That's why we have the complicated try...except block. Please fix the INPUT doc.

• Perhaps the order of arguments should be __init__(generator_matrix, sub_field) and sub_field could be optional, defaulting to the prime field of base_field.

• In _repr_ and _latex_ we should include the sub-field. So perhaps the printing should be something like:

[3, 2] linear rank metric code over GF(64)/GF(4)

• After introducing AbstractLinearCodeNoMetric perhaps we can completely avoid the two special rank-metric encoders, and just use LinearCodeGeneratorMatrixEncoder and LinearCodeSystematicEncoder (after suitable modifications in their doc and perhaps adding a doc-test where they are invoked with a LinearRankMetricCode.). I think this will work, but I'm not completely sure.

• In LinearRankMetricCodeNearestNeighborDecoder.decode_to_code, you could benefit from introducing C = self.code().

[jsrn]

Concerning my text added to the module doc, one can actually convert to a linear code simply by doing C_hamm = LinearCode(C).

[git]

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

​ef7b797	Merge branch 'develop' of git://trac.sagemath.org/sage into t/28073/abstract_code
​9608a23	Documentation and example fixes.
​5230b19	Merge #27634
​318b444	Module inheritance. Ambient_space and __call__ changes.
​3996761	Merge commit '8b01cc5df9e1508250976b08b4d2212aecb02927' of git://trac.sagemath.org/sage into t/28073/abstract_code
​a4582a3	Merge branch 'develop' of git://trac.sagemath.org/sage into t/28073/abstract_code
​4dbc878	documentation fix
​45cf76e	Class linear_code_no_metric. Moved stuff from linear_code.
​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.

[gh-emes4]

I made all the changes in Johan's comment.

Also merged in Linear Code No Metric and deleted the duplicate stuff.

I removed Relative Finite Field Extension and replaced it with vector_space method, which also allows the user to choose a basis, which is now an initialising parameter for AbstractLinearRankMetricCode and LinearRankMetricCode. I just noticed that I forgot to add the basis parameter in the Super method of LinearRankMetricCode, will fix that now.

I ran make ptestlong and there were no errors.

[git]

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

​1e32a0c

Super method of LinearRankMetricCode includes basis.

[git]

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

​3917048	Merge branch 'develop' of git://trac.sagemath.org/sage into rank_metric
​01d9a3d	Merge branch 'develop' of git://trac.sagemath.org/sage into t/28350/abstract_linear_code_no_metric_class
​226ffbf	Added no metric to coding documentation index. Moved zero method from AbstractLinearCode. Changed base_field check.
​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.

[caruso]

I merged with sage 9.1.beta2.

Let me also point out that #21413 (about general field extensions) is now merged. I think it would be nice to rely on it in order to allow for more general fields than finite fields. Any thoughts?

---

New commits:

​d49390e	merged version 9.1.beta1
​80ff011	Add function hash
​dbaaaa1	Merge branch 'develop' into t/28350/coding/no_metric
​5ea97ac	Merge branch 'u/gh-emes4/coding/linear_rank_metric' of git://trac.sagemath.org/sage into rank_metric_codes

[dimpase]

As I already said on #28350, I'd like to see the work of gh-emes4 merged, and then more hacking can start.

Aside from this, I'm all for more general fields to be possible.

[dimpase]

did a straightforward merge on trac/develop (9.2.beta3). Tests pass!

---

New commits:

​3f0d00c	Merge remote-tracking branch 'trac/develop' into HEAD
​ffb8297	take into account map change in trac:#28481

[jsrn]

Awesome!

[caruso]

The method sage.coding.linear_code_no_metric.__eq__ misses doctests.

[jsrn]

The __eq__ method is also incorrect: two codes (= vector spaces) may be equal though their generator matrices are not. I'm fixing this.

[jsrn]

I've fixed the issue with __eq__ by implementing and documenting a correct version. Then sage.coding.linear_code.AbstractLinearCode had a redundant (and less efficient) implementation of __eq__ that I removed. I also moved __ne__ from that class to AbstractLinearCodeNoMetric.

Using ./sage -coverage, I found that linear_rank_code had another method decode_to_code with no doctests. I added one. I discovered then that two other doctests of that file were running very slowly (>10 s), so I just changed the tests to a smaller ones which runs much faster.

---

New commits:

​150d834	Example for coding.linear_code_no_metric.__init__
​5f32a03	Merge branch 'u/dimpase/coding/linear_rank_metric' of git://trac.sagemath.org/sage into 21226_abstract_rank_metric
​4a770f8	Fix __eq__ and __ne__ for AbstractLinearCodeNoMetric, and remove it from AbstractLinearCode
​9ef1e9c	Add doctest to coding.linear_rank_metric.LinearRankMetricCodeNearestNeighborDecoder.decode_to_code
​5f46031	Make doctests of sage.coding.linear_rank_metric run 50 times faster

[caruso]

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.

[caruso]

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

[dimpase]

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

[vbraun]

PDF docs don't build:

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

[dimpase]

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

[caruso]

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]

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]

ok, this works with pdf

---

New commits:

​899d390

make \beta unicode

[dimpase]

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

[dimpase]

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

[vbraun]

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

[dimpase]

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