Gabidulin Codes

[arpitdm]

A Linear Gabidulin Code Gab[n,k] over F_{q^m} of length n <= m and dimension k <= n is the set of all words, formed by the operator evaluation of a q-degree restricted skew polynomial (with frobenius endomorphism and a finite field) f(x) \in S_{F_{q^m}}[x].

i.e. Gab[n,k] = {(f(g_0), f(g_1),..., f(g_{n-1})) = f(g): deg(f) < k}

where g_0,...,g_{n-1} are fixed elements belonging to F_{q^m} and are linearly independent over F_{q}

This ticket proposes a new class for Gabidulin Codes along with encoders and decoders for it.

CC: @sagetrac-dlucas @johanrosenkilde @xcaruso @emes4 @Adurand8

Component: coding theory

Author: Arpit Merchant, Marketa Slukova

Branch: 64af632

Reviewer: Dima Pasechnik, Johan Rosenkilde

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

[arpitdm]

Branch: u/arpitdm/gabidulin_codes

[arpitdm]

comment:2

A few points:

1. I've not added the tests and documentation for now since the code design is still in flux.
2. The file compiles successfully and one can create the code and codewords in vector form, i.e. F_{q^m}ⁿ.
3. One problem right now is that, although the dual code and the parity check matrix that are constructed are correct (verified by trying G*H^T = 0, as well as checking linear independence of h_0, h_1,..., h_{n-1}), I am using a random element from the right kernel of the coefficient matrix (Equation 2.28 of Antonia Wachter-Zeh's PhD thesis). And so dual of the dual code does not give me the original code. solve_right returns the trivial (all-zeros) solution.
4. Should there be a def generator_matrix method within the code class itself?

---

New commits:

ddaef41

Initial construction of the Gabidulin Code class. PolynomialEvaluationEncoder and GeneratorMatrixEncoder also included.

[arpitdm]

Commit: ddaef41

[sagetrac-dlucas]

comment:3

Hello,

To answer your question (4.), for now, yes, I guess you need to have such a method.
Later on, when the abstract class to manage rank-metric codes will be implemented we can
replicate the design used in AbstractLinearCode, but for now, copy-pasting generator_matrix
from AbstractLinearCode and put it in GabidulinCode is fine.

Some remarks:

1. You don't have to use backslashes to jump lines when you're in a parenthesis/square bracket block.
   For instance, you can write:

% (self.length(), self.dimension(), \
self.minimum_distance(), self.base_field())

as

% (self.length(), self.dimension(),
self.minimum_distance(), self.base_field())

2. Lines 19-34 are more or less copy-pasted from relative_finite_field_extension.py, and are not necessary. Take lines 19-20 for instance: it's a carbon copy of lines 116-117 of relative_finite_field_extension.py (except you replaced must be by has to be in the error message)... Which basically means you run the same sanity check twice: first time on lines 19-20 and second time line 49 when calling the constructing a RelativeFiniteFieldExtension. I think you should just remove all those tests and let RelativeFiniteFieldExtension do its job on sanitizing.

3. In the same vein: you copy-pasted a lot of getter from relative_finite_field_extension.py, and I'm not sure it makes sense. The user might be a bit puzzled by absolute_field_power which returns something of little relevance wrt. the Gabidulin code. Furthermore, if the user desperately needs to access this value, they can still access it by the RelativeFiniteFieldExtension returned by relative_finite_field_extension (this one we should keep).

4. There's some kind of naming conflict: evaluation_points and linearly_independent_elements are the same (see line 68), but while the user has to write linearly_independent_elements=stuff at construction time, they have to write my_code.evaluation_points() to access them from the constructed code. I think you should choose one name and stick to it. I vote for evaluation_points for consistency with grs.py.

5. Remember to not call methods in for loops except it's absolutely necessary. You do this on lines 96-97, 180-184 and 212. E.g. line 182, as return value of p.coefficients() never changes throughout the iterations, I would store it in a local variable and use this local variable instead.

Otherwise it seems good.

Best,

David

[johanrosenkilde]

comment:4

Noticed the following: In one place, you should be computing sigma^t(g) for some power t and some element g, where sigma is the Frobenius automorphism. You implement this as pow(sigma(g), t), but that's not what it means. Rather, it means sigma( sigma( ... sigma(g)...), where there is t sigmas. In another place, you compute simply g<sup>(q</sup>t) instead of calling sigma, which is also bad style; it should again be sigma called t times on g.

[johanrosenkilde]

comment:5

Also, avoid "log" if you can:

• s = log(q,p) should be s = relative_field.degree(). Similar with sm.
• m should be sm / m. Check if the division goes well.

[sagetrac-git]

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

de61ca4	Importing ring_element, integral_domain and principal_ideal_domain were throwing deprecation warnings. Updated the import statements according to Tickets 19167 and 20011.
9d21b54	module that implements class 'Side' with Left and Right as the two instances.
9de7bc1	Merge branch 'u/arpitdm/skew_polynomials' of git://trac.sagemath.org/sage into skew_polynomials
9c526ad	Fixed doctests caused by deprecation warnings, inability to access private variables, AttributeError in accessing of parent, and .
a06c2bf	Merge branch 'u/arpitdm/skew_polynomials' of git://trac.sagemath.org/sage into skew_polynomials
18c7982	Fixed bug with integer coercion
c6183bc	Merge branch 'develop' into temp3
dd5c575	Editing declarations of cython functions so as to make them compatible.
60b7869	Merge branch 'u/arpitdm/skew_polynomials' of git://trac.sagemath.org/sage into gabidulin_codes
40a3d37	Refactored code based on comments 3, 4 and 5. Added support for vector_to_matrix and matrix_to_vector representations of codewords. Added methods for rank_weight of a codeword and rank_distance between two codewords.

[sagetrac-git]

Changed commit from ddaef41 to 40a3d37

[arpitdm]

comment:7

Oh! I thought I only added the gabidulin.py file to my commit. Is there a way I can remove the skew polynomial files from this ticket?

Also, @johanrosenkilde, you mention I computed g^qt in the generator matrix of the code. According to Equation 2.27 of the PhD thesis, there is no sigma in the formation of the elements of the generator matrix.

[sagetrac-git]

Changed commit from 40a3d37 to 799d871

[sagetrac-git]

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

799d871

Added support for in the PolynomialEvaluationEncoder. This includes methods for fast lagrange-type interpolation of skew polynomials, minimum subspace polynomials and multi point evaluation of skew polynomials.