An Abstract Class for Rank Metric Codes

5b3bd7e6-c3f3-4830-a555-991f5e6beec0 commented 8 years ago

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

5b3bd7e6-c3f3-4830-a555-991f5e6beec0 commented 8 years ago

Branch: u/arpitdm/abstract_linear_rank_metric_code_class

5b3bd7e6-c3f3-4830-a555-991f5e6beec0 commented 8 years ago

comment:2

I've written a basic constructor for the class along with a couple of getter methods.
I've added some modified rank-metric based methods.
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.

5b3bd7e6-c3f3-4830-a555-991f5e6beec0 commented 8 years ago

Commit: 7e4b3a3

1861b8a9-77f0-4f35-8431-8514a75b40d1 commented 8 years ago

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 commented 8 years ago

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 commented 8 years ago

comment:5

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

Best, Johan

johanrosenkilde commented 8 years ago

comment:6

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

emes4 commented 5 years ago

Changed commit from 7e4b3a3 to none

emes4 commented 5 years ago

Dependencies: #28073

emes4 commented 5 years ago

Description changed:

--- 
+++ 
@@ -1,3 +1,3 @@
-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 `AbstractLinearCode` class so that all relevant methods can be accessed and the others will be deleted. Further, we propose to add rank-metric based methods to compute distance, weight and allow for matrix to vector (and reverse) conversions between representations.
+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.

emes4 commented 5 years ago

Changed author from Arpit Merchant to Arpit Merchant, Marketa Slukova

emes4 commented 5 years ago

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

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 5 years ago

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

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 5 years ago

Commit: a251c61

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 5 years ago

Changed commit from a251c61 to 05476b3

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 5 years ago

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

05476b3 Generator matrix methods in AbstractLinearRankMetricCode

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 5 years ago

Changed commit from 05476b3 to 08b6e4f

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 5 years ago

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 commented 5 years ago

Changed dependencies from #28073 to #28073, #28209

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 5 years ago

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

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

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 5 years ago

Changed commit from 08b6e4f to 12bb30f

emes4 commented 5 years ago

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.

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 5 years ago

Changed commit from 12bb30f to 72df923

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 5 years ago

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 commented 5 years ago

Changed dependencies from #28073, #28209 to #28073

johanrosenkilde commented 5 years ago

comment:19

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 LinearCodeandLinearRankMetricCodeusingTestSuite(see the documentation forTestSuite` 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().

johanrosenkilde commented 5 years ago

comment:20

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

emes4 commented 5 years ago

Changed dependencies from #28073 to #28350

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 5 years ago

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

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 5 years ago

Changed commit from 72df923 to d4d3e89

emes4 commented 5 years ago

comment:23

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.

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 5 years ago

Changed commit from d4d3e89 to 1e32a0c

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 5 years ago

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

1e32a0c Super method of LinearRankMetricCode includes basis.

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 5 years ago

Changed commit from 1e32a0c to 0a115d0

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 5 years ago

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

xcaruso commented 4 years ago

Changed branch from u/gh-emes4/coding/linear_rank_metric to u/caruso/coding/linear_rank_metric

xcaruso commented 4 years ago

Changed commit from 0a115d0 to 5ea97ac

xcaruso commented 4 years ago

comment:29

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 commented 4 years ago

comment:30

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 commented 4 years ago

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

dimpase commented 4 years ago

Reviewer: Dima Pasechnik

dimpase commented 4 years ago

comment:32

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`

dimpase commented 4 years ago

Changed commit from 5ea97ac to ffb8297

dimpase commented 4 years ago

Changed author from Arpit Merchant, Marketa Slukova to Arpit Merchant, Marketa Slukova, Xavier Caruso

johanrosenkilde commented 4 years ago

Changed reviewer from Dima Pasechnik to Dima Pasechnik, Johan Rosenkilde

johanrosenkilde commented 4 years ago

comment:34

Awesome!

xcaruso commented 4 years ago

comment:36

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

xcaruso commented 4 years ago

Changed reviewer from Dima Pasechnik, Johan Rosenkilde to Dima Pasechnik, Johan Rosenkilde, Xavier Caruso

xcaruso commented 4 years ago

Changed author from Arpit Merchant, Marketa Slukova, Xavier Caruso to Arpit Merchant, Marketa Slukova

johanrosenkilde commented 4 years ago

comment:38

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

sagemath / sage

An Abstract Class for Rank Metric Codes #21226