Gabidulin Code¶

This module provides the GabidulinCode, which constructs Gabidulin Codes that are the rank metric equivalent of Reed Solomon codes and are defined as the evaluation codes of degree-restricted skew polynomials.

This module also provides GabidulinPolynomialEvaluationEncoder, an encoder with a skew polynomial message space and GabidulinVectorEvaluationEncoder, an encoder based on the generator matrix. It also provides a decoder GabidulinGaoDecoder which corrects errors using the Gao algorithm in the rank metric.

AUTHOR:

Arpit Merchant (2016-08-16)
Marketa Slukova (2019-08-19): initial version

class sage.coding.gabidulin_code.GabidulinCode(base_field, length, dimension, sub_field=None, twisting_homomorphism=None, evaluation_points=None)[source]¶

Bases: AbstractLinearRankMetricCode

A Gabidulin Code.

DEFINITION:

A linear Gabidulin code Gab[n, k] over \(F_{q^m}\) of length \(n\) (at most \(m\)) and dimension \(k\) (at most \(n\)) is the set of all codewords, that are the evaluation of a \(q\)-degree restricted skew polynomial \(f(x)\) belonging to the skew polynomial constructed over the base ring \(F_{q^m}\) and the twisting homomorphism \(\sigma\).

\[\{ \text{Gab[n, k]} = \big\{ (f(g_0) f(g_1) ... f(g_{n-1})) = f(\textbf{g}) : \text{deg}_{q}f(x) < k \big\} \}\]

where the fixed evaluation points \(g_0, g_1,..., g_{n-1}\) are linearly independent over \(F_{q^m}\).

EXAMPLES:

A Gabidulin Code can be constructed in the following way:

Sage

sage: Fqm = GF(16)
sage: Fq = GF(4)
sage: C = codes.GabidulinCode(Fqm, 2, 2, Fq)
sage: C
[2, 2, 1] linear Gabidulin code over GF(16)/GF(4)

Python

>>> from sage.all import *
>>> Fqm = GF(Integer(16))
>>> Fq = GF(Integer(4))
>>> C = codes.GabidulinCode(Fqm, Integer(2), Integer(2), Fq)
>>> C
[2, 2, 1] linear Gabidulin code over GF(16)/GF(4)

dual_code()[source]¶

Return the dual code \(C^{\perp}\) of self, the code \(C\),

\[C^{\perp} = \{ v \in V\ |\ v\cdot c = 0,\ \forall c \in C \}.\]

EXAMPLES:

Sage

sage: C = codes.GabidulinCode(GF(2^10), 5, 2)
sage: C1 = C.dual_code(); C1
[5, 3, 3] linear Gabidulin code over GF(1024)/GF(2)
sage: C == C1.dual_code()
True

Python

>>> from sage.all import *
>>> C = codes.GabidulinCode(GF(Integer(2)**Integer(10)), Integer(5), Integer(2))
>>> C1 = C.dual_code(); C1
[5, 3, 3] linear Gabidulin code over GF(1024)/GF(2)
>>> C == C1.dual_code()
True

evaluation_points()[source]¶

Return the evaluation points of self.

EXAMPLES:

Sage

sage: Fqm = GF(5^20)
sage: Fq = GF(5^4)
sage: C = codes.GabidulinCode(Fqm, 4, 4, Fq)
sage: C.evaluation_points()
[1, z20, z20^2, z20^3]

Python

>>> from sage.all import *
>>> Fqm = GF(Integer(5)**Integer(20))
>>> Fq = GF(Integer(5)**Integer(4))
>>> C = codes.GabidulinCode(Fqm, Integer(4), Integer(4), Fq)
>>> C.evaluation_points()
[1, z20, z20^2, z20^3]

minimum_distance()[source]¶

Return the minimum distance of self.

Since Gabidulin Codes are Maximum-Distance-Separable (MDS), this returns: self.length() - self.dimension() + 1.

EXAMPLES:

Sage

sage: Fqm = GF(5^20)
sage: Fq = GF(5)
sage: C = codes.GabidulinCode(Fqm, 20, 15, Fq)
sage: C.minimum_distance()
6

Python

>>> from sage.all import *
>>> Fqm = GF(Integer(5)**Integer(20))
>>> Fq = GF(Integer(5))
>>> C = codes.GabidulinCode(Fqm, Integer(20), Integer(15), Fq)
>>> C.minimum_distance()
6

parity_check_matrix()[source]¶

Return the parity check matrix of self.

This is the generator matrix of the dual code of self.

EXAMPLES:

Sage

sage: C = codes.GabidulinCode(GF(2^3), 3, 2)
sage: C.parity_check_matrix()
[        1        z3 z3^2 + z3]
sage: C.parity_check_matrix() == C.dual_code().generator_matrix()
True

Python

>>> from sage.all import *
>>> C = codes.GabidulinCode(GF(Integer(2)**Integer(3)), Integer(3), Integer(2))
>>> C.parity_check_matrix()
[        1        z3 z3^2 + z3]
>>> C.parity_check_matrix() == C.dual_code().generator_matrix()
True

parity_evaluation_points()[source]¶

Return the parity evaluation points of self.

These form the first row of the parity check matrix of self.

EXAMPLES:

Sage

sage: C = codes.GabidulinCode(GF(2^10), 5, 2)
sage: list(C.parity_check_matrix().row(0)) == C.parity_evaluation_points() #indirect_doctest
True

Python

>>> from sage.all import *
>>> C = codes.GabidulinCode(GF(Integer(2)**Integer(10)), Integer(5), Integer(2))
>>> list(C.parity_check_matrix().row(Integer(0))) == C.parity_evaluation_points() #indirect_doctest
True

twisting_homomorphism()[source]¶

Return the twisting homomorphism of self.

EXAMPLES:

Sage

sage: Fqm = GF(5^20)
sage: Fq = GF(5^4)
sage: C = codes.GabidulinCode(Fqm, 5, 3, Fq)
sage: C.twisting_homomorphism()
Frobenius endomorphism z20 |--> z20^(5^4) on Finite Field in z20 of size 5^20

Python

>>> from sage.all import *
>>> Fqm = GF(Integer(5)**Integer(20))
>>> Fq = GF(Integer(5)**Integer(4))
>>> C = codes.GabidulinCode(Fqm, Integer(5), Integer(3), Fq)
>>> C.twisting_homomorphism()
Frobenius endomorphism z20 |--> z20^(5^4) on Finite Field in z20 of size 5^20

class sage.coding.gabidulin_code.GabidulinGaoDecoder(code)[source]¶

Bases: Decoder

Gao style decoder for Gabidulin Codes.

INPUT:

code – the associated code of this decoder

EXAMPLES:

Sage

sage: Fqm = GF(16)
sage: Fq = GF(4)
sage: C = codes.GabidulinCode(Fqm, 2, 2, Fq)
sage: D = codes.decoders.GabidulinGaoDecoder(C)
sage: D
Gao decoder for [2, 2, 1] linear Gabidulin code over GF(16)/GF(4)

Python

>>> from sage.all import *
>>> Fqm = GF(Integer(16))
>>> Fq = GF(Integer(4))
>>> C = codes.GabidulinCode(Fqm, Integer(2), Integer(2), Fq)
>>> D = codes.decoders.GabidulinGaoDecoder(C)
>>> D
Gao decoder for [2, 2, 1] linear Gabidulin code over GF(16)/GF(4)

Alternatively, we can construct the encoder from C directly:

Sage

sage: D = C.decoder("Gao")
sage: D
Gao decoder for [2, 2, 1] linear Gabidulin code over GF(16)/GF(4)

Python

>>> from sage.all import *
>>> D = C.decoder("Gao")
>>> D
Gao decoder for [2, 2, 1] linear Gabidulin code over GF(16)/GF(4)

decode_to_code(r)[source]¶

Return the decoded codeword corresponding to the received word \(r\).

INPUT:

r – received codeword

OUTPUT: the decoded codeword corresponding to the received codeword

EXAMPLES:

Sage

sage: Fqm = GF(3^20)
sage: Fq = GF(3)
sage: C = codes.GabidulinCode(Fqm, 5, 3, Fq)
sage: D = codes.decoders.GabidulinGaoDecoder(C)
sage: E = codes.encoders.GabidulinPolynomialEvaluationEncoder(C)
sage: S.<x> = Fqm['x', C.twisting_homomorphism()]
sage: z20 = Fqm.gen()
sage: p = x
sage: codeword_vector = E.encode(p, "vector")
sage: codeword_vector
(1, z20^3, z20^6, z20^9, z20^12)
sage: l = list(codeword_vector)
sage: l[0] = l[1] #make an error
sage: D.decode_to_code(vector(l))
(1, z20^3, z20^6, z20^9, z20^12)

Python

>>> from sage.all import *
>>> Fqm = GF(Integer(3)**Integer(20))
>>> Fq = GF(Integer(3))
>>> C = codes.GabidulinCode(Fqm, Integer(5), Integer(3), Fq)
>>> D = codes.decoders.GabidulinGaoDecoder(C)
>>> E = codes.encoders.GabidulinPolynomialEvaluationEncoder(C)
>>> S = Fqm['x', C.twisting_homomorphism()]; (x,) = S._first_ngens(1)
>>> z20 = Fqm.gen()
>>> p = x
>>> codeword_vector = E.encode(p, "vector")
>>> codeword_vector
(1, z20^3, z20^6, z20^9, z20^12)
>>> l = list(codeword_vector)
>>> l[Integer(0)] = l[Integer(1)] #make an error
>>> D.decode_to_code(vector(l))
(1, z20^3, z20^6, z20^9, z20^12)

decode_to_message(r)[source]¶

Return the skew polynomial (message) corresponding to the received word \(r\).

INPUT:

r – received codeword

OUTPUT: the message corresponding to the received codeword

EXAMPLES:

Sage

sage: Fqm = GF(2^9)
sage: Fq = GF(2^3)
sage: C = codes.GabidulinCode(Fqm, 2, 2, Fq)
sage: D = codes.decoders.GabidulinGaoDecoder(C)
sage: E = codes.encoders.GabidulinPolynomialEvaluationEncoder(C)
sage: S.<x> = Fqm['x', C.twisting_homomorphism()]
sage: z9 = Fqm.gen()
sage: p = (z9^6 + z9^4)*x + z9^2 + z9
sage: codeword_vector = E.encode(p, "vector")
sage: r = D.decode_to_message(codeword_vector)
sage: r
(z9^6 + z9^4)*x + z9^2 + z9

Python

>>> from sage.all import *
>>> Fqm = GF(Integer(2)**Integer(9))
>>> Fq = GF(Integer(2)**Integer(3))
>>> C = codes.GabidulinCode(Fqm, Integer(2), Integer(2), Fq)
>>> D = codes.decoders.GabidulinGaoDecoder(C)
>>> E = codes.encoders.GabidulinPolynomialEvaluationEncoder(C)
>>> S = Fqm['x', C.twisting_homomorphism()]; (x,) = S._first_ngens(1)
>>> z9 = Fqm.gen()
>>> p = (z9**Integer(6) + z9**Integer(4))*x + z9**Integer(2) + z9
>>> codeword_vector = E.encode(p, "vector")
>>> r = D.decode_to_message(codeword_vector)
>>> r
(z9^6 + z9^4)*x + z9^2 + z9

decoding_radius()[source]¶

Return the decoding radius of the Gabidulin Gao Decoder.

EXAMPLES:

Sage

sage: Fqm = GF(5^20)
sage: Fq = GF(5)
sage: C = codes.GabidulinCode(Fqm, 20, 4, Fq)
sage: D = codes.decoders.GabidulinGaoDecoder(C)
sage: D.decoding_radius()
8

Python

>>> from sage.all import *
>>> Fqm = GF(Integer(5)**Integer(20))
>>> Fq = GF(Integer(5))
>>> C = codes.GabidulinCode(Fqm, Integer(20), Integer(4), Fq)
>>> D = codes.decoders.GabidulinGaoDecoder(C)
>>> D.decoding_radius()
8

class sage.coding.gabidulin_code.GabidulinPolynomialEvaluationEncoder(code)[source]¶

Bases: Encoder

Encoder for Gabidulin codes which uses evaluation of skew polynomials to obtain codewords.

Let \(C\) be a Gabidulin code of length \(n\) and dimension \(k\) over some finite field \(F = GF(q^m)\). We denote by \(\alpha_i\) its evaluations points, where \(1 \leq i \leq n\). Let \(p\), a skew polynomial of degree at most \(k-1\) in \(F[x]\), be the message.

The encoding of \(m\) will be the following codeword:

\[(p(\alpha_1), \dots, p(\alpha_n)).\]

EXAMPLES:

Sage

sage: Fqm = GF(16)
sage: Fq = GF(4)
sage: C = codes.GabidulinCode(Fqm, 2, 2, Fq)
sage: E = codes.encoders.GabidulinPolynomialEvaluationEncoder(C)
sage: E
Polynomial evaluation style encoder for
 [2, 2, 1] linear Gabidulin code over GF(16)/GF(4)

Python

>>> from sage.all import *
>>> Fqm = GF(Integer(16))
>>> Fq = GF(Integer(4))
>>> C = codes.GabidulinCode(Fqm, Integer(2), Integer(2), Fq)
>>> E = codes.encoders.GabidulinPolynomialEvaluationEncoder(C)
>>> E
Polynomial evaluation style encoder for
 [2, 2, 1] linear Gabidulin code over GF(16)/GF(4)

Alternatively, we can construct the encoder from C directly:

Sage

sage: E = C.encoder("PolynomialEvaluation")
sage: E
Polynomial evaluation style encoder for
 [2, 2, 1] linear Gabidulin code over GF(16)/GF(4)

Python

>>> from sage.all import *
>>> E = C.encoder("PolynomialEvaluation")
>>> E
Polynomial evaluation style encoder for
 [2, 2, 1] linear Gabidulin code over GF(16)/GF(4)

encode(p, form='vector')[source]¶

Transform the polynomial p into a codeword of code().

The output codeword can be represented as a vector or a matrix, depending on the form input.

INPUT:

p – a skew polynomial from the message space of self of degree less than self.code().dimension()
form – type parameter taking strings “vector” or “matrix” as values and converting the output codeword into the respective form (default: 'vector')

OUTPUT: a codeword corresponding to \(p\) in vector or matrix form

EXAMPLES:

Sage

sage: Fqm = GF(2^9)
sage: Fq = GF(2^3)
sage: C = codes.GabidulinCode(Fqm, 2, 2, Fq)
sage: E = codes.encoders.GabidulinPolynomialEvaluationEncoder(C)
sage: S.<x> = Fqm['x', C.twisting_homomorphism()]
sage: z9 = Fqm.gen()
sage: p = (z9^6 + z9^2 + z9 + 1)*x + z9^7 + z9^5 + z9^4 + z9^2
sage: codeword_vector = E.encode(p, "vector"); codeword_vector
(z9^7 + z9^6 + z9^5 + z9^4 + z9 + 1, z9^6 + z9^5 + z9^3 + z9)
sage: codeword_matrix = E.encode(p, "matrix"); codeword_matrix
[           z3     z3^2 + z3]
[           z3             1]
[         z3^2 z3^2 + z3 + 1]

Python

>>> from sage.all import *
>>> Fqm = GF(Integer(2)**Integer(9))
>>> Fq = GF(Integer(2)**Integer(3))
>>> C = codes.GabidulinCode(Fqm, Integer(2), Integer(2), Fq)
>>> E = codes.encoders.GabidulinPolynomialEvaluationEncoder(C)
>>> S = Fqm['x', C.twisting_homomorphism()]; (x,) = S._first_ngens(1)
>>> z9 = Fqm.gen()
>>> p = (z9**Integer(6) + z9**Integer(2) + z9 + Integer(1))*x + z9**Integer(7) + z9**Integer(5) + z9**Integer(4) + z9**Integer(2)
>>> codeword_vector = E.encode(p, "vector"); codeword_vector
(z9^7 + z9^6 + z9^5 + z9^4 + z9 + 1, z9^6 + z9^5 + z9^3 + z9)
>>> codeword_matrix = E.encode(p, "matrix"); codeword_matrix
[           z3     z3^2 + z3]
[           z3             1]
[         z3^2 z3^2 + z3 + 1]

message_space()[source]¶

Return the message space of the associated code of self.

EXAMPLES:

Sage

sage: Fqm = GF(5^20)
sage: Fq = GF(5^4)
sage: C = codes.GabidulinCode(Fqm, 4, 4, Fq)
sage: E = codes.encoders.GabidulinPolynomialEvaluationEncoder(C)
sage: E.message_space()
Ore Polynomial Ring in x over Finite Field in z20 of size 5^20
 twisted by z20 |--> z20^(5^4)

Python

>>> from sage.all import *
>>> Fqm = GF(Integer(5)**Integer(20))
>>> Fq = GF(Integer(5)**Integer(4))
>>> C = codes.GabidulinCode(Fqm, Integer(4), Integer(4), Fq)
>>> E = codes.encoders.GabidulinPolynomialEvaluationEncoder(C)
>>> E.message_space()
Ore Polynomial Ring in x over Finite Field in z20 of size 5^20
 twisted by z20 |--> z20^(5^4)

unencode_nocheck(c)[source]¶

Return the message corresponding to the codeword c.

Use this method with caution: it does not check if c belongs to the code, and if this is not the case, the output is unspecified.

INPUT:

c – a codeword of code()

OUTPUT:

a skew polynomial of degree less than self.code().dimension()

EXAMPLES:

Sage

sage: Fqm = GF(2^9)
sage: Fq = GF(2^3)
sage: C = codes.GabidulinCode(Fqm, 2, 2, Fq)
sage: E = codes.encoders.GabidulinPolynomialEvaluationEncoder(C)
sage: S.<x> = Fqm['x', C.twisting_homomorphism()]
sage: z9 = Fqm.gen()
sage: p = (z9^6 + z9^4)*x + z9^2 + z9
sage: codeword_vector = E.encode(p, "vector")
sage: E.unencode_nocheck(codeword_vector)
(z9^6 + z9^4)*x + z9^2 + z9

Python

>>> from sage.all import *
>>> Fqm = GF(Integer(2)**Integer(9))
>>> Fq = GF(Integer(2)**Integer(3))
>>> C = codes.GabidulinCode(Fqm, Integer(2), Integer(2), Fq)
>>> E = codes.encoders.GabidulinPolynomialEvaluationEncoder(C)
>>> S = Fqm['x', C.twisting_homomorphism()]; (x,) = S._first_ngens(1)
>>> z9 = Fqm.gen()
>>> p = (z9**Integer(6) + z9**Integer(4))*x + z9**Integer(2) + z9
>>> codeword_vector = E.encode(p, "vector")
>>> E.unencode_nocheck(codeword_vector)
(z9^6 + z9^4)*x + z9^2 + z9

class sage.coding.gabidulin_code.GabidulinVectorEvaluationEncoder(code)[source]¶

Bases: Encoder

This method constructs the vector evaluation encoder for Gabidulin Codes.

INPUT:

code – the associated code of this encoder

EXAMPLES:

Sage

sage: Fqm = GF(16)
sage: Fq = GF(4)
sage: C = codes.GabidulinCode(Fqm, 2, 2, Fq)
sage: E = codes.encoders.GabidulinVectorEvaluationEncoder(C)
sage: E
Vector evaluation style encoder for [2, 2, 1] linear Gabidulin code over GF(16)/GF(4)

Python

>>> from sage.all import *
>>> Fqm = GF(Integer(16))
>>> Fq = GF(Integer(4))
>>> C = codes.GabidulinCode(Fqm, Integer(2), Integer(2), Fq)
>>> E = codes.encoders.GabidulinVectorEvaluationEncoder(C)
>>> E
Vector evaluation style encoder for [2, 2, 1] linear Gabidulin code over GF(16)/GF(4)

Alternatively, we can construct the encoder from C directly:

Sage

sage: E = C.encoder("VectorEvaluation")
sage: E
Vector evaluation style encoder for [2, 2, 1] linear Gabidulin code over GF(16)/GF(4)

Python

>>> from sage.all import *
>>> E = C.encoder("VectorEvaluation")
>>> E
Vector evaluation style encoder for [2, 2, 1] linear Gabidulin code over GF(16)/GF(4)

generator_matrix()[source]¶

Return the generator matrix of self.

EXAMPLES:

Sage

sage: Fqm = GF(2^9)
sage: Fq = GF(2^3)
sage: C = codes.GabidulinCode(Fqm, 3, 3, Fq)
sage: (list(C.generator_matrix().row(1))
....:   == [C.evaluation_points()[i]**(2**3) for i in range(3)])
True

Python

>>> from sage.all import *
>>> Fqm = GF(Integer(2)**Integer(9))
>>> Fq = GF(Integer(2)**Integer(3))
>>> C = codes.GabidulinCode(Fqm, Integer(3), Integer(3), Fq)
>>> (list(C.generator_matrix().row(Integer(1)))
...   == [C.evaluation_points()[i]**(Integer(2)**Integer(3)) for i in range(Integer(3))])
True