Opened 3 years ago
Last modified 3 months ago
#21226 needs_review enhancement
An Abstract Class for Rank Metric Codes
Reported by:  arpitdm  Owned by:  ghemes4 

Priority:  major  Milestone:  
Component:  coding theory  Keywords:  
Cc:  dlucas, jsrn, dimpase, caruso, ghAdurand8  Merged in:  
Authors:  Arpit Merchant, Marketa Slukova  Reviewers:  
Report Upstream:  N/A  Work issues:  
Branch:  u/ghemes4/coding/linear_rank_metric (Commits)  Commit:  0a115d0f608465d1f59cdd2068add8669df912e7 
Dependencies:  #28350  Stopgaps: 
Description (last modified by )
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 rankmetric 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.
Change History (27)
comment:1 Changed 3 years ago by
 Branch set to u/arpitdm/abstract_linear_rank_metric_code_class
comment:2 Changed 3 years ago by
 Commit set to 7e4b3a3b6fb6b6bcce84f85007b0ae0574f5c37f
comment:3 followup: ↓ 4 Changed 3 years ago by
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
comment:4 in reply to: ↑ 3 Changed 3 years ago by
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 rankmetric codes which are linear over the big field!
Best, Johan
comment:5 Changed 3 years ago by
What's the state of this? What is missing? When do you plan to do it?
Best, Johan
comment:6 Changed 3 years ago by
I think the class should be call AbstractLinearRankMetricCode
by the way. It's terribly long, but the Linear
is important.
comment:7 Changed 5 months ago by
 Branch changed from u/arpitdm/abstract_linear_rank_metric_code_class to u/ghemes4/coding/linear_rank_metric
 Commit 7e4b3a3b6fb6b6bcce84f85007b0ae0574f5c37f deleted
 Dependencies set to #28073
 Description modified (diff)
comment:8 Changed 5 months ago by
 Commit set to a251c61567015e7159d231a6b828ef617ee5566b
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.

comment:9 Changed 5 months ago by
 Commit changed from a251c61567015e7159d231a6b828ef617ee5566b to 05476b32a4a94be0d02eba67c9922217ccf7dc9f
Branch pushed to git repo; I updated commit sha1. New commits:
05476b3  Generator matrix methods in AbstractLinearRankMetricCode

comment:10 Changed 5 months ago by
 Owner changed from (none) to ghemes4
comment:11 Changed 5 months ago by
 Commit changed from 05476b32a4a94be0d02eba67c9922217ccf7dc9f to 08b6e4f604eb23e53fdb60e7ee724c643b46b125
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/ghemes4/coding/linear_rank_metric' of git://trac.sagemath.org/sage into rank_metric

comment:12 Changed 5 months ago by
 Cc dimpase added
comment:13 Changed 5 months ago by
 Dependencies changed from #28073 to #28073, #28209
comment:14 Changed 5 months ago by
 Commit changed from 08b6e4f604eb23e53fdb60e7ee724c643b46b125 to 12bb30f72616d49a2755693c73943e0660873b4e
comment:15 Changed 5 months ago by
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.
comment:16 Changed 5 months ago by
 Status changed from new to needs_review
comment:17 Changed 5 months ago by
 Commit changed from 12bb30f72616d49a2755693c73943e0660873b4e to 72df923bd65ea122a6b56ef7930e8f07569ecfb9
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/ghemes4/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.

comment:18 Changed 4 months ago by
 Dependencies changed from #28073, #28209 to #28073
comment:19 Changed 4 months ago by
 Status changed from needs_review to needs_work
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 Hammingmetric 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 matrixbased 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 rankmetric analog of ReedSolomon codes".
 The headline
AbstractLinearCode
should beAbstractLinearRankMetricCode
.
 "However, using the encoder/decoder framework requires the vector
representation of codewords". This caveat is important but perhaps not
wellplaced 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 anm * m
matrix) and the result is then cached. Your two functions throw away theRelativeFiniteFieldExtension
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 globalscope functions and only have them inside
AbstractLinearRankMetricCode
. Then theRelativeFiniteFieldExtension
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 thefield_extension
(which should be aRelativeFiniteFieldExtension
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 needbase_field
since this is just the base field ofv
. 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 thesub_field
nor thebase_field
. However, thebase_field
should be possible to supply in case the user has constructed the big field using a specific irreducible polynomial, say.
For
rank_weight
andrank_distance
, we should use the same signature asto_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 inRelativeFiniteFieldExtension
, so it's not your fault, but it should be documented somewhere. This is not welldocumented inRelativeFiniteFieldExtension
either, I realise. Perhaps you could add the following paragraph to the class doc ofRelativeFiniteFieldExtension
, together with some shorter description of the same in your to/from matrixfunctions along with a reference to the doc ofRelativeFiniteFieldExtension
:
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^{m1}` is a basis of `F_{q^m}` over `F_q`. This class uses that basis.
 The conformal checks in
rank_distance
should be before theto_matrix_representation
calls. (the number of columns is the length ofa
andb
and the number of rows is taken care of by the check onbase_ring
.
 You are missing INPUT blocks to many functions, in particular all the globalscope 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 forAbstractLinearRankMetricCode
.
 I think we should apply the same convention as in
(Abstract)LinearCode
, that a subclass ofAbstractLinearRankMetricCode
must supply a generator matrix. Then__iter__
and__hash__
can be defined onAbstractLinearRankMetricCode
.
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 ofLinearRankMetricCode
. 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 rankmetric 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()
returnsNone
when the user didn't supply a specificfield_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 ofself
.".
 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 calledminimum_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
, usesage.rings.infinity.infinity
(possibly with capital letter?) instead offloat('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 classAbstractLinearCodeNoMetric
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 bothAbstractLinearCode
andAbstractLinearRankMetricCode
inherits fromAbstractLinearCodeNoMetric
.
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 doctest for bothLinearCode
andLinearRankMetricCode
usingTestSuite
(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 introduceAbstractLinearCodeNoMetric
as suggested above, then we have to follow this convention anyway.
In LinearRankMetricCode
:
 The reason the
__init__
argumentgenerator
is not calledgenerator_matrix
is that we also accept e.g. a code or a vector space. That's why we have the complicatedtry...except
block. Please fix the INPUT doc.
 Perhaps the order of arguments should be
__init__(generator_matrix, sub_field)
andsub_field
could be optional, defaulting to the prime field ofbase_field
.
 In
_repr_
and_latex_
we should include the subfield. 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 rankmetric encoders, and just useLinearCodeGeneratorMatrixEncoder
andLinearCodeSystematicEncoder
(after suitable modifications in their doc and perhaps adding a doctest where they are invoked with aLinearRankMetricCode
.). I think this will work, but I'm not completely sure.
 In
LinearRankMetricCodeNearestNeighborDecoder.decode_to_code
, you could benefit from introducingC = self.code()
.
comment:20 Changed 4 months ago by
Concerning my text added to the module doc, one can actually convert to a linear code simply by doing C_hamm = LinearCode(C)
.
comment:21 Changed 4 months ago by
 Dependencies changed from #28073 to #28350
comment:22 Changed 4 months ago by
 Commit changed from 72df923bd65ea122a6b56ef7930e8f07569ecfb9 to d4d3e89225c99905740c59610d8fb3c51973ed03
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.

comment:23 Changed 4 months ago by
 Status changed from needs_work to needs_review
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.
comment:24 Changed 4 months ago by
 Commit changed from d4d3e89225c99905740c59610d8fb3c51973ed03 to 1e32a0cadd9fba911695d4a975a06b115abc5adf
Branch pushed to git repo; I updated commit sha1. New commits:
1e32a0c  Super method of LinearRankMetricCode includes basis.

comment:25 Changed 4 months ago by
 Commit changed from 1e32a0cadd9fba911695d4a975a06b115abc5adf to 0a115d0f608465d1f59cdd2068add8669df912e7
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/ghemes4/coding/no_metric' of git://trac.sagemath.org/sage into rank_metric

0a115d0  Removed zero method. Added field extension method.

comment:26 Changed 3 months ago by
 Cc caruso added
comment:27 Changed 3 months ago by
 Cc ghAdurand8 added
More to follow.
New commits:
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.