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, \(\GF{q}\) and \(\GF{q^m}\), and define a code \(C\) to be a set of vectors of length \(n\) with entries from \(\GF{q^m}\). Let \(c\) be a codeword. We can represent it as an \(m \times n\) matrix \(M\) over \(\GF{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 \(\GF{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 \(\GF{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: 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 the sage.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, see sage.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}\) and sub_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 \(\GF{q^m}\) and sub_field \(\GF{q}\). This function returns the vector space of dimension \(m\) over \(\GF{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 the base_field of self

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 the base_field of self

• right – a vector over the base_field of self

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 the base_field of self

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 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: 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: 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: 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 of self

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 over base_field in terms of basis.

Given an \(m \times n\) matrix over \(\GF{q}\) and some basis of \(\GF{q^m}\) over \(\GF{q}\), we can represent each of its columns as an element of \(\GF{q^m}\), yielding a vector of length \(n\) over \(\GF{q}\).

In case base_field is not given, we take \(\GF{q^m}\), the field extension of \(\GF{q}\) of degree \(m\), the number of rows of w.

INPUT:

• w – a matrix over some field \(\GF{q}\)

• base_field – (default: None) an extension field of \(\GF{q}\). If not specified, it is the field \(\GF{q^m}\), where \(m\) is the number of rows of w.

• basis – (default: None) a basis of \(\GF{q^m}\) as a vector space over \(\GF{q}\). If not specified, given that \(q = p^s\), let \(1,\beta,\ldots,\beta^{sm}\) be the power basis that SageMath uses to represent \(\GF{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 over sub_field.

Take two vectors a, b over some field \(\GF{q^m}\). This function converts them to matrices over \(\GF{q}\) and calculates the rank of their difference.

If sub_field is not specified, we take the prime subfield \(\GF{q}\) of \(\GF{q^m}\).

INPUT:

• a – a vector over some field \(\GF{q^m}\)

• b – a vector over some field \(\GF{q^m}\)

• sub_field – (default: None) a sub field of \(\GF{q^m}\). If not specified, it is the prime subfield \(\GF{p}\) of \(\GF{q^m}\).

• basis – (default: None) a basis of \(\GF{q^m}\) as a vector space over sub_field. If not specified, given that \(q = p^s\), let \(1,\beta,\ldots,\beta^{sm}\) be the power basis that SageMath uses to represent \(\GF{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 over sub_field.

If c is a vector over some field \(\GF{q^m}\), the function converts it into a matrix over \(\GF{q}\).

INPUT:

• c – a vector over some field \(\GF{q^m}\); or a matrix over \(\GF{q}\)

• sub_field – (default: None) a sub field of \(\GF{q^m}\). If not specified, it is the prime subfield \(\GF{p}\) of \(\GF{q^m}\).

• basis – (default: None) a basis of \(\GF{q^m}\) as a vector space over sub_field. If not specified, given that \(q = p^s\), let \(1,\beta,\ldots,\beta^{sm}\) be the power basis that SageMath uses to represent \(\GF{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 over sub_field in terms of basis.

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 \(\GF{q^m}\), we can represent each entry as a vector of length \(m\), yielding an \(m \times n\) matrix over sub_field. In case sub_field is not given, we take the prime subfield \(\GF{p}\) of \(\GF{q^m}\).

INPUT:

• v – a vector over some field \(\GF{q^m}\)

• sub_field – (default: None) a sub field of \(\GF{q^m}\). If not specified, it is the prime subfield \(\GF{p}\) of \(\GF{q^m}\).

• basis – (default: None) a basis of \(\GF{q^m}\) as a vector space over sub_field. If not specified, given that \(q = p^s\), let \(1,\beta,\ldots,\beta^{sm}\) be the power basis that SageMath uses to represent \(\GF{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