arXiv:1705.07668v1 [] 22 May 2017

A decoding algorithm for Twisted Gabidulin codes∗
Tovohery Randrianarisoa

Joachim Rosenthal

Institute of Mathematics
University of Zurich
Switzerland
Email: tovohery.randrianarisoa@math.uzh.ch

Institute of Mathematics
University of Zurich
Switzerland
Email: rosenthal@math.uzh.ch

Abstract—In this work, we modify the decoding algorithm for
subspace codes by Kötter and Kschischang to get a decoding algorithm for (generalized) twisted Gabidulin codes. The decoding
algorithm we present applies to cases where the code is linear
over the base field Fq but not linear over Fqn .

Definition 1 (Linearized polynomial ring). Let Fqn /Fq be a
finite field extension of degree n. A linearized polynomial is a
polynomial of the form
n

f (x) = f0 x + f1 xq + · · · + fn xq .

I. I NTRODUCTION
The first construction of rank metric codes were independently given by [1], [2], [3]. These codes are called Gabidulin
codes. For this class of codes, distinct decoding algorithms
were provided to correct errors less than half the minimum
rank distance. It is also suggested that there are many classes
of linear rank metric codes [4] although there are only few
known general constructions. In a paper [5], Sheekey has
provided a new construction of rank metric codes which he
called twisted Gabidulin codes. This class of codes contains
the original Gabidulin codes but it also contains codes which
are not equivalent to Gabidulin codes. A more general class,
called generalized twisted Gabidulin codes were studied in
[6]. These rank metric codes have found many applications.
For example they can be used in cryptography and recently,
they were also used in network coding. But of course, in
order to use these codes, decoding algorithms are needed. For
Gabidulin codes, as we mentioned, there are already many
decoding algorithms in the literature. However, to this time,
there is no known algorithm to decode the general class of
(generalized) twisted Gabidulin codes. In this work we will
provide a decoding algorithm for some special cases of these
codes, where they are only linear over Fq but not linear over
the extension Fqn .
In Section II, we will introduce the rank metric codes and
the construction of twisted Gabidulin codes. In Section III, we
will provide the decoding algorithm for the twisted Gabidulin
codes. Note that in this work we will consider only codes of
full length i.e. with length equal to the degree of the extension
Fqn /Fq but everything still applies for codes with smaller
length.
II. R ANK

METRIC CODES

Before we start introducing rank metric codes, we first give
the notion of linearized polynomial ring.
∗ This

work was supported by SNF grant no. 169510.

If fn 6= 0, then we say that f (x) has q-degree n. The set
of these polynomials, denoted by Lq [x], forms a ring called
“linearized polynomial ring”, where the addition is done
componentwise and the multiplication is defined by the noncommutative formula
i

j

i

axq ◦ bxq = abq xq

i+j

, i, j ∈ N and a, b ∈ Fqn .

The above definition of the product is actually the composition of two polynomials.
i
Since the maps Fqn → Fqn , x 7→ xq , i ∈ N are linear
over Fq , then we see that the linearized polynomials actually
define linears maps Fqn → Fqn and linearity is over Fq . That
explains the reason why they are used in the context of rank
metric codes. The linearity allows us to easily compute the
rank norm of a codeword.
By the definition of the product in Lq [x], the ring is non
commutative and it is known that a linearized polynomial ring
admits a left/right Euclidean division. This division will later
be used in the decoding algorithm. For more information on
the linearized polynomial ring in the context of coding theory,
one can have a look at [7].
Definition 2 (Rank metric code). Let Fqn /Fq be a field
extension. A rank metric [n, M, d]-code over Fq is a subset of
Fnqn of size M such that the minimum distance between two
codewords x, y is d. The distance d(x, y) is defined by the
maximum number of linearly independent elements over Fq in
the set {(x1 − y1 ), · · · , (xn − yn )}, where x = (x1 , · · · , xn )
and y = (y1 , · · · , yn ).
The above definition of distance defines a norm which we
denote by rank(c) for a codeword c.
Theorem 1 ([2]). Let Fqn /Fq be a field extension and C be
a rank metric [n, M, d]-code over Fq . Then logqn (M ) ≤ n −
d + 1.

Definition 3. Codes for which the inequality in the previous
theorem is an equality are called maximal rank distance
(MRD) codes.
Typical examples of rank metric codes were constructed by
Gabidulin in [2]. The codes have the parameter [n, q nk , n −
k + 1] and have the property that they are an Fqn -subspace of
Fnqn . A more general construction was given in [5], where it is
also possible to get codes which are only Fq -subspaces. These
codes have the property that for given d, q, n and Fqn /Fq ,
M is maximal and therefore they are MRD codes. Due to
the linearity, the minimum distance of these codes are just
the minimum of the rank norm of the codewords. We will
now give the construction for these codes but before that,
we need the following proposition, which is needed for the
construction as well as for the decoding algorithm.This is just
a reformulation of a theorem in [5].
Proposition 4. Suppose that f is a linearized polynomial of
q-degree k over Fqn . If the dimension of the kernel of f in
Fqn is equal to k, then there is a non-zero z ∈ Fqn such that
f0 z = (−1)k fkq z q .
Proof. Suppose that the kernel V of f has dimension k. Let
{x0 , x1 , · · · , xk−1 } be a basis of the kernel of f . We define
P
i
the linearized polynomial h(x) = i hi xq by
x

h(x) =

xq

···

xq

k

xq0
..
.

···
..
.

xq0
..
.

xk−1

xqk−1

···

xqk−1

.

k

It is obvious that h(x) also vanishes on V . Therefore, we have
that hi = fi z for some non-zero z ∈ Fqn . Furthermore, by
computing the above determinant, we have h0 = (−1)k hqk .
The result follows.
We are now ready to provide the definition of twisted
Gabidulin codes which is due to Sheekey [5].
Definition 5. Let n, k, r be positive integers with k < n. Let
η be an element of Fqn such that N (η) 6= (−1)nk . Then the
set of linearized polynomials
k−1

C = {(f (α1 ), f (α2 ), · · · , f (αn )) , f ∈ G(η, r)} .
Remark 1.
(a) The original Gabidulin codes correspond to the case where
η = 0.
(b) When r 6= 0, then we have an MRD code which is linear
only over Fq .
(c) This construction can be generalized by replacing the
s
Frobenius map xq by xq , where (n, s) = 1. These are
the generalized twisted Gabidulin codes.
III. D ECODING

ALGORITHM

In this section we will provide a decoding algorithm for
some twisted Gabidulin codes. The algorithm can be generalized to the case of generalized twisted Gabidulin codes
by working on linearized polynomials. The algorithm we
present here is a modification of the algorithm by Köetter and
Kschischang which was used to decode subspace codes [7].
Let f ∈ G(η, r) be the message polynomial. It is encoded
into the codeword

k

x0
..
.

G(η, r) = {f0 x+f1 xq +· · ·+fk−1 xq

To construct the codewords of the code as we have defined
linear rank metric codes in Definition 2, we actually evaluate
these polynomials on a fixed basis {α1 , · · · , αn } of Fqn . So
our code is in fact

r

k

+ηf0q xq : fi ∈ Fqn }

represents an Fq -linear MRD code of size q nk , which is called
a twisted Gabidulin code.
In the above definition, we have given the rank metric code
as a set of linear maps. The rank norm is then the usual
definition of the rank of a linear map. This construction was
given by Sheekey in his paper [5]. To see that this construction
gives us an MRD codes, we use Proposition 4 to show that
the polynomials in G(η, r) can have kernel of dimension k − 1
at most. Namely, since N (η) 6= (−1)nk , we can see that
r+1
f0 z 6= (−1)k η q f0q z q for any z ∈ Fqn . The rank norm then
comes from the rank nullity theorem.

(f (α1 ), f (α2 ), · · · , f (αn )) .
This codeword is sent and we assume that the word
(r1 , r2 , · · · , rn ) was received. We define the error vector
e = (f (α1 ) − r1 , f (α2 ) − r2 , · · · , f (αn ) − rn )
rank errors happened, we
Under the assumption t < n−k+1
2
seek the unique codeword (f (α1 ), f (α2 ), · · · , f (αn )) , f ∈
G(η, r) such that e has rank t.
e = (e1 , · · · , en ) now defines an Fq -endomorphism
Fnq −→ Fqn
X
bi ei .
(b1 , · · · , bn ) 7−→
i

By the definition of rank, we see that the rank of this map
is rank(e). Therefore, by the rank nullity theorem, the kernel
V of this map is a subspace of dimension n − t.
We have
)
(
X
X
(1)
bi ri .
bi f (αi ) =
V = (b1 , · · · , bn ) :
i

i

Assume that we have two linearized polynomials P1 and
P2 , with degree at most n − t and n − t − k respectively.
Assume furthermore that P1 and P2 satisfy
P1 (αi ) − P2 (ri ) = 0 ∀i, 1 ≤ i ≤ n.

(2)

Choose (b1 , · · · , bn ) ∈ V , we thus have that
X
X
bi ri )
bi αi ) − P2 (
P1 (

Now the polynomial P1 − P2 ◦ f and h differ only by
a constant multiple so that, for any solution {ai , bi } of the
system of equations (2)

i
i
X
X
bi f (αi ))
bi αi ) − P2 (
=P1 (

a0 − b 0 f 0
h0
=
r+n−t−k .
hn−t
an−t − bn−t−k η qn−t−k f0q

i

i

X
X
bi αi )).
bi αi ) − P2 (f (
=P1 (

So we will use the above relation to compute f0 and we
will thus get

i

i

Therefore P1 − P2 ◦ f vanishes on a subspace W ≃ V of
dimension n − t.
First, assume that P2 and P1 are of the form
qn−t−1

q

P1 (x) = a0 x + a1 x + · · · + an−t−1 x

P2 (x) = b0 x + b1 xq + · · · + bn−t−k xq

n−t−k

qn−t

+ an−t x

k−1

.

r

(g(αq1 ) − r1 , g(αq2 ) − r2 , · · · , g(αqn ) − rn ) .
where
g(x) = f1 x + · · · + fk−1 xq

.

and of course
f (x) = f0 x + f1 xq + · · · + fk−1 xq

k

+ ηf0q xq .

With these forms, we see that P1 − P2 ◦ f is of q-degree
n − t at most where the two extreme monomials are

a0 − b 0 f 0

and

=
 n−t

n−t−k q r+n−t−k
xq .
B = an−t − bn−t−k η q
f0

Now we are ready to explain the decoding algorithm. First,
we want to solve the system of linear equations (2). This is a
system of n independent equations at most. We have 2n−2t−
k + 2 unknown. Since we consider that the error has rank, t <
n−k+1
, then we see that, the system (2) is underdetermined.
2
Namely the solution space of this system of equation is of
dimension 2 at least. This can be solved in polynomial time
using the Gaussian elimination.
As we have seen, we now have two polynomials P1 (x)
and P2 (x) such that (P1 − P2 ◦ f ) is of q-degree n − t
but also has n − t zeros. If one of a0 − b0 f0 and an−t −
n−t−k q r+n−t−k
is equal to 0, then we must have
bn−t−k η q
f0
P1 − P2 ◦ f = 0 as polynomial. Therefore, we have two
possibilities. In the first case we use a division algorithm
to recover the polynomial f by computing P1 /P2 . Notice
that the division is done in the linearized polynomial ring.
If that does not work, then the second possibility is that as
in the proof of proposition 4, we must have a polynomial
n−t
h(x) = h0 x + · · · + hn−t xq
such that h and P1 − P2 ◦ f
have the same zeroes and
h0 = (−1)n−t hqn−t ,

k−2

Finally, a decoding algorithm of Gabidulin code with allow us
to recover ri and thus we can recover the original message.
So, what remains is how do we find f0 from the relation 3.
Suppose we have two linearly independent solutions {ai , bi }
and {a′i , b′i } of the Equation (2). Then they form two polynomials with the same roots as h(x). Thus

A = (a0 − b0 f0 )x,

an−t − bn−t−k η qn−t−k f0q
a′0 − b′0 f0

r+n−t−k

a′n−t − b′n−t−k η qn−t−k f0q

r+n−t−k

In some case, we can solve this to recover f0 . For example, if
r = t+k mod n, then this becomes a polynomial equation of
degree two. This can be easily solved and we try out the two
values of f0 for decoding. This condition is needed here as the
above equation cannot be simply solved when the degree is
large. Moreover, in that case there may be many possibilities
for the solution f0 of the equations and this will render the
algorithm impracticable.
We summarize the decoding algorithm in the following. We
suppose that r = t + k mod n. And the message polynomial
is
f (x) = f0 x + f1 xq + · · · + fk−1 xq

k−1

r

k

+ ηf0q xq .

Algorithm: We are given a received codeword (r1 , · · · , rn ).
(I) Solve the system of linear equations in the variables bj
and aj ,
P1 (αi ) − P2 (ri ) = 0,

∀i, 1 ≤ i ≤ n

where
P1 (x) = a0 x + · · · + an−t xq

n−t

,

and
P2 (x) = b0 x + · · · + bn−t−k xq

and

hn−t = (−1)n−t

(3)

n−t−1

x0
x1
..
.

xq0
xq1
..
.

···
···
..
.

xq0
n−t−1
xq1
..
.

xn−t−1

xqn−t−1

···

xqn−t−1

n−t−1

n−t−k

.

Get two linearly independent solutions {ai , bi }, {a′i , b′i }.
(II) For the above solutions, compute P1 /P2 as a polynomial
division in the linearized polynomial ring. One can
easily check if the quotient is the original message by
comparing its rank distance to the received codeword.

(III) If the previous step does not give the original message,
then solve for f0 in the equation
a′0 − b′0 f0
a0 − b 0 f 0
= ′
n−t−k
q
an−t − bn−t−k η
f0
an−t − b′n−t−k η qn−t−k f0
This is equivalent to a polynomial equation of degree 2.
(IV) We now recover
f0 , and remove the contribution of
qr qk
f0 x + ηf0 x from the received word. Any decoding
algorithm of Gabidulin codes can now be used to
recover
k−2
g(x) = f1 x + · · · + fk−1 xq
For the complexity, we give a brief explanation of why it
is polynomial. Step I is solving a system of linear equations
and thus it can be done in polynomial time. In fact finding
two linearly independent solutions can be done in O(n3 ). For
Step II, the polynomial division in the linearized polynomial
ring as it was described in [7] can also be done in polynomial
time. This is O(n2 ) . For Step III, solving a polynomial system
of degree 2 is easy. Finally, for Step IV, we just need to use
any existing decoding algorithm of Gabidulin codes. There are
plenty of those and they can be executed in polynomial time
[8], [9], [10]. To conclude, this decoding algorithm is actually
dominated by the the first step and thus the overal complexity
if O(n3 ). If one uses the the Interpolate procedure in [7], the
overall complexity can even be reduced to O(n2 ).
IV. C ONCLUSION
In this paper, we described a decoding algorithm for some
particular case of the twisted Gabidulin codes. We have
shown that the algorithm can be run in polynomial time. Our
algorithm is an adaptation of the decoding algorithm by Kötter
and Kschischang. However, the case only concerns a code
which is linear over the field Fq , where r = t + k mod n.
For the practical point of view, we want to decode codes which
are linear over the extension Fqn , that is for the case where
r = 0. In this regards, more work should be done on this
decoding algorithm.The goal of the paper was to introduce an
algorithm for decoding twisted Gabidulin codes. This can be
tweaked to get faster algorithm but we leave that for a future
work.
R EFERENCES
[1] P. Delsarte, “Bilinear forms over a finite field, with applications to coding
theory,” Journal of Combinatorial Theory, Series A, vol. 25, no. 3, pp.
226 – 241, 1978.
[2] E. Gabidulin, “Theory of codes with maximum rank distance.” Probl.
Inf. Transm., vol. 21, pp. 1–12, 1985.
[3] R. M. Roth, “Maximum-rank array codes and their application to
crisscross error correction,” IEEE Trans. Inf. Theor., vol. 37, no. 2, pp.
328–336, Sep. 2006.
[4] A. Neri, A. Horlemann-Trautmann, T. Randrianarisoa, and J. Rosenthal,
“On the genericity of maximum rank distance and gabidulin codes,”
CoRR, vol. abs/1605.05972, 2016.
[5] J. Sheekey, “A new family of linear maximum rank distance codes,”
arXiv:1504.01581, 2015.
[6] G. Lunardon, R. Trombetti, and Y. Zhou, “Generalized Twisted
Gabidulin Codes,” arXiv:1507.07855, 2015.

[7] R. Koetter and F. Kschischang, “Coding for errors and erasures in
random network coding,” Information Theory, IEEE Transactions on,
vol. 54, no. 8, pp. 3579–3591, Aug 2008.
[8] P. Loidreau, A Welch–Berlekamp Like Algorithm for Decoding Gabidulin
Codes. Berlin, Heidelberg: Springer Berlin Heidelberg, 2006, pp. 36–
45.
[9] A. Wachter-Zeh, V. Afanassiev, and V. Sidorenko, “Fast decoding of
gabidulin codes,” Des. Codes Cryptography, vol. 66, no. 1-3, pp. 57–
73, Jan. 2013.
[10] G. Robert, “A quadratic welch-berlekamp algorithm to decode generalized gabidulin codes, and some variants,” in 2016 IEEE International
Symposium on Information Theory (ISIT), July 2016, pp. 2559–2563.

