Generic structures for linear codes over the rank metric#
Rank Metric#
In coding theory, the most common metric is the Hamming metric, where distance between two codewords is given by the number of positions in which they differ. An alternative to this is the rank metric. Take two fields, \(F_q\) and \(F_{q^m}\), and define a code \(C\) to be a set of vectors of length \(n\) with entries from \(F_{q^m}\). Let \(c\) be a codeword. We can represent it as an \(m \times n\) matrix \(M\) over \(F_q\).
A detailed description on the relationship between the two representations can
be found in sage.coding.linear_rank_metric.to_matrix_representation()
and sage.coding.linear_rank_metric.from_matrix_representation()
.
We can define a metric using the rank of the matrix representation of the codewords. A distance between two codewords \(a, b\) is the rank of the matrix representation of \(a - b\). A weight of a codeword \(c\) is the rank of the matrix representation of \(c\).
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
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)
.
Linear Rank Metric Code and Gabidulin Codes#
The class sage.coding.linear_rank_metric.LinearRankMetricCode
is the
analog of sage.coding.linear_code.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 the main family of structured linear rank metric codes. These codes are the rank-metric analog of Reed-Solomon codes.
AbstractLinearRankMetricCode
#
This is a base class designed to contain methods, features and parameters shared by every linear rank metric code. For instance, generic algorithms for computing the minimum distance, etc. Many of these algorithms are slow, e.g. exponential in the code length. It also contains methods for swapping between vector and matrix representation of elements.
AbstractLinearCodeNoMetric
is an abstract class for linear rank metric codes,
so any linear rank metric code class should inherit from this class.
Also AbstractLinearCodeNoMetric
should never itself be instantiated.
See sage.coding.linear_rank_metric.AbstractLinearRankMetricCode
for details and examples.
LinearRankMetricCode
#
This class is used to represent arbitrary and unstructured linear rank metric
codes. It mostly relies directly on generic methods provided by
AbstractLinearRankMetricCode
, which means that basic operations on the code
(e.g. computation of the minimum distance) will use slow algorithms.
A LinearRankMetricCode
is instantiated by providing a generator:
sage: G = Matrix(GF(64), [[1,1,0], [0,0,1]])
sage: C = codes.LinearRankMetricCode(G, GF(4))
sage: C
[3, 2] linear rank metric code over GF(64)/GF(4)
sage: C.generator_matrix()
[1 1 0]
[0 0 1]
sage: c = vector(GF(64), (1, 1, 1))
sage: c in C
True
Further references#
Read more about rank metric and Gabidulin codes
AUTHORS:
Marketa Slukova (2019-08-16): initial version
- class sage.coding.linear_rank_metric.AbstractLinearRankMetricCode(base_field, sub_field, length, default_encoder_name, default_decoder_name, basis=None)#
Bases:
sage.coding.linear_code_no_metric.AbstractLinearCodeNoMetric
Abstract class for linear rank metric codes.
This class contains methods that can be used on families of linear rank metric codes. Every linear rank metric code class should inherit from this abstract class.
This class is intended for codes which are linear over the
base_field
.Codewords of rank metric codes have two representations. They can either be written as a vector of length \(n\) over \(GF(q^m)\), or an \(m \times n\) matrix over \(GF(q)\). This implementation principally uses the vector representation. However, one can always get the matrix representation using the
sage.coding.linear_rank_metric.AbstractLinearRankMetricCode.to_matrix()
method. To go back to a vector, use thesage.coding.linear_rank_metric.AbstractLinearRankMetricCode.from_matrix()
method.Instructions on how to make a new family of rank metric codes is analogous to making a new family of linear codes over the Hamming metric, instructions for which are in
sage.coding.linear_code.AbstractLinearCode
. For an example on, seesage.coding.linear_rank_metric.AbstractLinearRankMetricCode.__init__()
Warning
A lot of methods of the abstract class rely on the knowledge of a generator matrix. It is thus strongly recommended to set an encoder with a generator matrix implemented as a default encoder.
- extension_degree()#
Return \(m\), the degree of the field extension of
self
.Let
base_field
be \(GF(q^m)\) andsub_field
be \(GF(q)\). Then this function returns \(m\).EXAMPLES:
sage: G = Matrix(GF(64), [[1,1,0], [0,0,1]]) sage: C = codes.LinearRankMetricCode(G, GF(4)) sage: C.extension_degree() 3
- field_extension()#
Return the field extension of
self
.Let
base_field
be some field \(F_{q^m}\) andsub_field
\(F_{q}\). This function returns the vector space of dimension \(m\) over \(F_{q}\).EXAMPLES:
sage: G = Matrix(GF(64), [[1,1,0], [0,0,1]]) sage: C = codes.LinearRankMetricCode(G, GF(4)) sage: C.field_extension() Vector space of dimension 3 over Finite Field in z2 of size 2^2
- matrix_form_of_vector(word)#
Return the matrix representation of a word.
INPUT:
word
– a vector over thebase_field
ofself
EXAMPLES:
sage: G = Matrix(GF(64), [[1,1,0], [0,0,1]]) sage: C = codes.LinearRankMetricCode(G, GF(4)) sage: x = GF(64).gen() sage: a = vector(GF(64), (x + 1, x + 1, 1)) sage: C.matrix_form_of_vector(a) [1 1 1] [1 1 0] [0 0 0]
- minimum_distance()#
Return the minimum distance of
self
.This algorithm simply iterates over all the elements of the code and returns the minimum weight.
EXAMPLES:
sage: F.<a> = GF(8) sage: G = Matrix(F, [[1,a,a^2,0]]) sage: C = codes.LinearRankMetricCode(G, GF(2)) sage: C.minimum_distance() 3
- rank_distance_between_vectors(left, right)#
Return the rank of the matrix of
left
-right
.INPUT:
left
– a vector over thebase_field
ofself
right
– a vector over thebase_field
ofself
EXAMPLES:
sage: G = Matrix(GF(64), [[1,1,0], [0,0,1]]) sage: C = codes.LinearRankMetricCode(G, GF(4)) sage: x = GF(64).gen() sage: a = vector(GF(64), (x + 1, x + 1, 1)) sage: b = vector(GF(64), (1, 0, 0)) sage: C.rank_distance_between_vectors(a, b) 2
- rank_weight_of_vector(word)#
Return the weight of the word, i.e. its rank.
INPUT:
word
– a vector over thebase_field
ofself
EXAMPLES:
sage: G = Matrix(GF(64), [[1,1,0], [0,0,1]]) sage: C = codes.LinearRankMetricCode(G, GF(4)) sage: x = GF(64).gen() sage: a = vector(GF(64), (x + 1, x + 1, 1)) sage: C.rank_weight_of_vector(a) 2
- sub_field()#
Return the sub field of
self
.EXAMPLES:
sage: G = Matrix(GF(64), [[1,1,0], [0,0,1]]) sage: C = codes.LinearRankMetricCode(G, GF(4)) sage: C.sub_field() Finite Field in z2 of size 2^2
- vector_form_of_matrix(word)#
Return the vector representation of a word.
INPUT:
word
– a matrix over thesub_field
ofself
EXAMPLES:
sage: G = Matrix(GF(64), [[1,1,0], [0,0,1]]) sage: C = codes.LinearRankMetricCode(G, GF(4)) sage: x = GF(64).gen() sage: m = Matrix(GF(4), [[1, 1, 1], [1, 1, 0], [0, 0, 0]]) sage: C.vector_form_of_matrix(m) (z6 + 1, z6 + 1, 1)
- class sage.coding.linear_rank_metric.LinearRankMetricCode(generator, sub_field=None, basis=None)#
Bases:
sage.coding.linear_rank_metric.AbstractLinearRankMetricCode
Linear rank metric codes over a finite field, represented using a generator matrix.
This class should be used for arbitrary and unstructured linear rank metric codes. This means that basic operations on the code, such as the computation of the minimum distance, will use generic, slow algorithms.
If you are looking for constructing a code from a more specific family, see if the family has been implemented by investigating
codes.<tab>
. These more specific classes use properties particular to that family to allow faster algorithms, and could also have family-specific methods.EXAMPLES:
sage: G = Matrix(GF(64), [[1,1,0], [0,0,1]]) sage: C = codes.LinearRankMetricCode(G, GF(4)) sage: C [3, 2] linear rank metric code over GF(64)/GF(4) sage: C.base_field() Finite Field in z6 of size 2^6 sage: C.sub_field() Finite Field in z2 of size 2^2 sage: C.length() 3 sage: C.dimension() 2 sage: C[2] (z6, z6, 0) sage: E = codes.encoders.LinearCodeGeneratorMatrixEncoder(C) sage: word = vector(C.base_field(), [1, 0]) sage: E(word) (1, 1, 0)
- generator_matrix(encoder_name=None, **kwargs)#
Return a generator matrix of
self
.INPUT:
encoder_name
– (default:None
) name of the encoder which will be used to compute the generator matrix.self._generator_matrix
will be returned if default value is kept.kwargs
– all additional arguments are forwarded to the construction of the encoder that is used.
EXAMPLES:
sage: G = Matrix(GF(64), [[1,1,0], [0,0,1]]) sage: C = codes.LinearRankMetricCode(G, GF(4)) sage: C.generator_matrix() [1 1 0] [0 0 1]
- class sage.coding.linear_rank_metric.LinearRankMetricCodeNearestNeighborDecoder(code)#
Bases:
sage.coding.decoder.Decoder
Construct a decoder for Linear Rank Metric Codes.
This decoder will decode to the nearest codeword found.
- decode_to_code(r)#
Corrects the errors in
word
and returns a codeword.INPUT:
r
– a codeword ofself
OUTPUT:
a vector of
self
’s message space
EXAMPLES:
sage: F.<a> = GF(4) sage: G = Matrix(F, [[1,1,0]]) sage: C = codes.LinearRankMetricCode(G, GF(2)) sage: D = codes.decoders.LinearRankMetricCodeNearestNeighborDecoder(C) sage: D.decode_to_code(vector(F, [a, a, 1])) (a, a, 0)
- decoding_radius()#
Return maximal number of errors
self
can decode.EXAMPLES:
sage: F.<a> = GF(8) sage: G = Matrix(F, [[1,a,a^2,0]]) sage: C = codes.LinearRankMetricCode(G, GF(2)) sage: D = codes.decoders.LinearRankMetricCodeNearestNeighborDecoder(C) sage: D.decoding_radius() 1
- sage.coding.linear_rank_metric.from_matrix_representation(w, base_field=None, basis=None)#
Return a vector representation of a matrix
w
overbase_field
in terms ofbasis
.Given an \(m \times n\) matrix over \(F_q\) and some
basis
of \(F_{q^m}\) over \(F_q\), we can represent each of its columns as an element of \(F_{q^m}\), yielding a vector of length \(n\) over \(F_q\).In case
base_field
is not given, we take \(F_{q^m}\), the field extension of \(F_q\) of degree \(m\), the number of rows ofw
.INPUT:
w
– a matrix over some field \(F_q\)base_field
– (default:None
) an extension field of \(F_q\). If not specified, it is the field \(F_{q^m}\), where \(m\) is the number of rows ofw
.basis
– (default:None
) a basis of \(F_{q^m}\) as a vector space overF_q
. If not specified, given that \(q = p^s\), let \(1,\beta,\ldots,\beta^{sm}\) be the power basis that SageMath uses to represent \(F_{q^m}\). The default basis is then \(1,\beta,\ldots,\beta^{m-1}\).
EXAMPLES:
sage: from sage.coding.linear_rank_metric import from_matrix_representation sage: m = Matrix(GF(4), [[1, 1, 1], [1, 1, 0], [0, 0, 0]]) sage: from_matrix_representation(m) (z6 + 1, z6 + 1, 1) sage: v = vector(GF(4), (1, 0, 0)) sage: from_matrix_representation(v) Traceback (most recent call last): ... TypeError: Input must be a matrix
- sage.coding.linear_rank_metric.rank_distance(a, b, sub_field=None, basis=None)#
Return the rank of
a
-b
as a matrix oversub_field
.Take two vectors
a
,b
over some field \(F_{q^m}\). This function converts them to matrices over \(F_q\) and calculates the rank of their difference.If
sub_field
is not specified, we take the prime subfield \(F_q\) of \(F_{q^m}\).INPUT:
a
– a vector over some field \(F_{q^m}\)b
– a vector over some field \(F_{q^m}\)sub_field
– (default:None
) a sub field of \(F_{q^m}\). If not specified, it is the prime subfield \(F_p\) of \(F_{q^m}\).basis
– (default:None
) a basis of \(F_{q^m}\) as a vector space oversub_field
. If not specified, given that \(q = p^s\), let \(1,\beta,\ldots,\beta^{sm}\) be the power basis that SageMath uses to represent \(F_{q^m}\). The default basis is then \(1,\beta,\ldots,\beta^{m-1}\).
EXAMPLES:
sage: from sage.coding.linear_rank_metric import rank_distance sage: x = GF(64).gen() sage: a = vector(GF(64), (x + 1, x + 1, 1)) sage: b = vector(GF(64), (1, 0, 0)) sage: rank_distance(a, b, GF(4)) 2 sage: c = vector(GF(4), (1, 0, 0)) sage: rank_distance(a, c, GF(4)) Traceback (most recent call last): ... ValueError: The base field of (z6 + 1, z6 + 1, 1) and (1, 0, 0) has to be the same sage: d = Matrix(GF(64), (1, 0, 0)) sage: rank_distance(a, d, GF(64)) Traceback (most recent call last): ... TypeError: Both inputs have to be vectors sage: e = vector(GF(64), (1, 0)) sage: rank_distance(a, e, GF(64)) Traceback (most recent call last): ... ValueError: The length of (z6 + 1, z6 + 1, 1) and (1, 0) has to be the same
- sage.coding.linear_rank_metric.rank_weight(c, sub_field=None, basis=None)#
Return the rank of
c
as a matrix oversub_field
.If
c
is a vector over some field \(F_{q^m}\), the function converts it into a matrix over \(F_q\).INPUT:
c
– a vector over some field \(F_{q^m}\); or a matrix over \(F_q\)sub_field
– (default:None
) a sub field of \(F_{q^m}\). If not specified, it is the prime subfield \(F_p\) of \(F_{q^m}\).basis
– (default:None
) a basis of \(F_{q^m}\) as a vector space oversub_field
. If not specified, given that \(q = p^s\), let \(1,\beta,\ldots,\beta^{sm}\) be the power basis that SageMath uses to represent \(F_{q^m}\). The default basis is then \(1,\beta,\ldots,\beta^{m-1}\).
EXAMPLES:
sage: from sage.coding.linear_rank_metric import rank_weight sage: x = GF(64).gen() sage: a = vector(GF(64), (x + 1, x + 1, 1)) sage: rank_weight(a, GF(4)) 2
- sage.coding.linear_rank_metric.to_matrix_representation(v, sub_field=None, basis=None)#
Return a matrix representation of
v
oversub_field
in terms ofbasis
.Let \((b_1, b_2, \ldots, b_m)\), \(b_i \in GF(q^m)\), be a basis of \(GF(q^m)\) as a vector space over \(GF(q)\). Take an element \(x \in GF(q^m)\). We can write \(x\) as \(x = u_1 b_1 + u_2 b_2 + \ldots u_m b_m\), where \(u_i \in GF(q)\). This way we can represent an element from \(GF(q^m)\) as a vector of length \(m\) over \(GF(q)\).
Given a vector
v
of length \(n\) over some field \(F_{q^m}\), we can represent each entry as a vector of length \(m\), yielding an \(m \times n\) matrix oversub_field
. In casesub_field
is not given, we take the prime subfield \(F_p\) of \(F_{q^m}\).INPUT:
v
– a vector over some field \(F_{q^m}\)sub_field
– (default:None
) a sub field of \(F_{q^m}\). If not specified, it is the prime subfield \(F_p\) of \(F_{q^m}\).basis
– (default:None
) a basis of \(F_{q^m}\) as a vector space oversub_field
. If not specified, given that \(q = p^s\), let \(1,\beta,\ldots,\beta^{sm}\) be the power basis that SageMath uses to represent \(F_{q^m}\). The default basis is then \(1,\beta,\ldots,\beta^{m-1}\).
EXAMPLES:
sage: from sage.coding.linear_rank_metric import to_matrix_representation sage: x = GF(64).gen() sage: a = vector(GF(64), (x + 1, x + 1, 1)) sage: to_matrix_representation(a, GF(4)) [1 1 1] [1 1 0] [0 0 0] sage: m = Matrix(GF(4), [[1, 1, 1], [1, 1, 0], [0, 0, 0]]) sage: to_matrix_representation(m) Traceback (most recent call last): ... TypeError: Input must be a vector