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: gh-emes4
Priority: major Milestone:
Component: coding theory Keywords:
Cc: dlucas, jsrn, dimpase, caruso, gh-Adurand8 Merged in:
Authors: Arpit Merchant, Marketa Slukova Reviewers:
Report Upstream: N/A Work issues:
Branch: u/gh-emes4/coding/linear_rank_metric (Commits) Commit: 0a115d0f608465d1f59cdd2068add8669df912e7
Dependencies: #28350 Stopgaps:

Description (last modified by gh-emes4)

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.

Change History (27)

comment:1 Changed 3 years ago by arpitdm

  • Branch set to u/arpitdm/abstract_linear_rank_metric_code_class

comment:2 Changed 3 years ago by arpitdm

  • Commit set to 7e4b3a3b6fb6b6bcce84f85007b0ae0574f5c37f
  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:

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

comment:3 follow-up: Changed 3 years ago by 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

comment:4 in reply to: ↑ 3 Changed 3 years ago by 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

comment:5 Changed 3 years ago by jsrn

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 jsrn

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 gh-emes4

  • Authors changed from Arpit Merchant to Arpit Merchant, Marketa Slukova
  • Branch changed from u/arpitdm/abstract_linear_rank_metric_code_class to u/gh-emes4/coding/linear_rank_metric
  • Commit 7e4b3a3b6fb6b6bcce84f85007b0ae0574f5c37f deleted
  • Dependencies set to #28073
  • Description modified (diff)

comment:8 Changed 5 months ago by git

  • Commit set to a251c61567015e7159d231a6b828ef617ee5566b

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

64f446aMerge branch 'develop' of git://trac.sagemath.org/sage into abstract_code
53e445badded base_ring and length parameter to AbstractCode
5e6dffeFixed some dependencies. Category still set up wrong.
ba4fc53Merge branch 'abstract_code' into t/28073/abstract_code
e8edfebFixed unclean merge.
880aebbFixed default decoder/encoder dependencies. Set to None by default.
d115600No category set up and base_field in AbstractCode. No encoder/decoder error msgs. Documentation and tests.
82fdc3cMerge branch 'develop' of git://trac.sagemath.org/sage into rank_metric
5c0fd69Merge branch 'develop' of git://trac.sagemath.org/sage into rank_metric
a251c61Inheriting from Abstract Code. Encoding, decoding methods. Generic LinearRankMetricCode class.

comment:9 Changed 5 months ago by git

  • Commit changed from a251c61567015e7159d231a6b828ef617ee5566b to 05476b32a4a94be0d02eba67c9922217ccf7dc9f

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

05476b3Generator matrix methods in AbstractLinearRankMetricCode

comment:10 Changed 5 months ago by gh-emes4

  • Owner changed from (none) to gh-emes4

comment:11 Changed 5 months ago by git

  • Commit changed from 05476b32a4a94be0d02eba67c9922217ccf7dc9f to 08b6e4f604eb23e53fdb60e7ee724c643b46b125

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

524efc8Inheriting from Abstract Code. Encoding, decoding methods. Generic LinearRankMetricCode class.
77fc1e2Generator matrix methods in AbstractLinearRankMetricCode
08b6e4fMerge branch 'u/gh-emes4/coding/linear_rank_metric' of git://trac.sagemath.org/sage into rank_metric

comment:12 Changed 5 months ago by gh-emes4

  • Cc dimpase added

comment:13 Changed 5 months ago by gh-emes4

  • Dependencies changed from #28073 to #28073, #28209

comment:14 Changed 5 months ago by git

  • Commit changed from 08b6e4f604eb23e53fdb60e7ee724c643b46b125 to 12bb30f72616d49a2755693c73943e0660873b4e

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

8442aa6documentation
086fa74AbstractLinearRankMetricCode done
c39e3caClasses and methods done.
12bb30fGeneric documentation.

comment:15 Changed 5 months ago by 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.

comment:16 Changed 5 months ago by gh-emes4

  • Status changed from new to needs_review

comment:17 Changed 5 months ago by git

  • Commit changed from 12bb30f72616d49a2755693c73943e0660873b4e to 72df923bd65ea122a6b56ef7930e8f07569ecfb9

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

2bf73f8Merge branch 'develop' of git://trac.sagemath.org/sage into t/28073/abstract_code
487e9e2Category related methods added. Encoder/decoder documentation specified for linear codes.
40df01eFinished up documentation.
b7cab95Merge branch 'u/gh-emes4/coding/abstract_code' of git://trac.sagemath.org/sage into rank_metric
25ca9b7Merge branch 'develop' of git://trac.sagemath.org/sage into rank_metric
72df923Documentation tree link and fixes. Updated Sage.

comment:18 Changed 4 months ago by gh-emes4

  • Dependencies changed from #28073, #28209 to #28073

comment:19 Changed 4 months ago by jsrn

  • 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
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".

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().
Last edited 4 months ago by jsrn (previous) (diff)

comment:20 Changed 4 months ago by jsrn

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 gh-emes4

  • Dependencies changed from #28073 to #28350

comment:22 Changed 4 months ago by git

  • Commit changed from 72df923bd65ea122a6b56ef7930e8f07569ecfb9 to d4d3e89225c99905740c59610d8fb3c51973ed03

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

ef7b797Merge branch 'develop' of git://trac.sagemath.org/sage into t/28073/abstract_code
9608a23Documentation and example fixes.
5230b19Merge #27634
318b444Module inheritance. Ambient_space and __call__ changes.
3996761Merge commit '8b01cc5df9e1508250976b08b4d2212aecb02927' of git://trac.sagemath.org/sage into t/28073/abstract_code
a4582a3Merge branch 'develop' of git://trac.sagemath.org/sage into t/28073/abstract_code
4dbc878documentation fix
45cf76eClass linear_code_no_metric. Moved stuff from linear_code.
f7d9438Merge in 28350, Linear Code No Metric
d4d3e89No 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 gh-emes4

  • 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 git

  • Commit changed from d4d3e89225c99905740c59610d8fb3c51973ed03 to 1e32a0cadd9fba911695d4a975a06b115abc5adf

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

1e32a0cSuper method of LinearRankMetricCode includes basis.

comment:25 Changed 4 months ago by git

  • Commit changed from 1e32a0cadd9fba911695d4a975a06b115abc5adf to 0a115d0f608465d1f59cdd2068add8669df912e7

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

3917048Merge branch 'develop' of git://trac.sagemath.org/sage into rank_metric
01d9a3dMerge branch 'develop' of git://trac.sagemath.org/sage into t/28350/abstract_linear_code_no_metric_class
226ffbfAdded no metric to coding documentation index. Moved zero method from AbstractLinearCode. Changed base_field check.
bd31704Merge branch 'u/gh-emes4/coding/no_metric' of git://trac.sagemath.org/sage into rank_metric
0a115d0Removed zero method. Added field extension method.

comment:26 Changed 3 months ago by caruso

  • Cc caruso added

comment:27 Changed 3 months ago by gh-Adurand8

  • Cc gh-Adurand8 added
Note: See TracTickets for help on using tickets.