ISSN 2148-838Xhttp://dx.doi.org/10.13069/jacodesmath.369863

J. Algebra Comb. Discrete Appl.
5(1) • 29–43

Received: 17 December 2016
Accepted: 6 October 2017

Journal of Algebra Combinatorics Discrete Structures and Applications

A module minimization approach to Gabidulin
decoding via interpolation

Research Article

Anna-Lena Horlemann-Trautmann,∗ Margreta Kuijper

Abstract: We focus on iterative interpolation-based decoding of Gabidulin codes and present an algorithm that
computes a minimal basis for an interpolation module. We extend existing results for Reed-Solomon
codes in showing that this minimal basis gives rise to a parametrization of elements in the module
that lead to all Gabidulin decoding solutions that are at a fixed distance from the received word.
Our module-theoretic approach strengthens the link between Gabidulin decoding and Reed-Solomon
decoding, thus providing a basis for further work into Gabidulin list decoding.

2010 MSC: 11T71, 94B35

Keywords: Gabidulin codes, Linearized polynomials, Interpolation, Minimal basis, Parametrization, Polynomial
modules, Rank metric, Iterative algorithm.

1. Introduction

Over the last decade there has been increased interest in Gabidulin codes, mainly because of their
relevance to network coding [12, 23] and distributed storage [20]. Gabidulin codes are optimal rank-metric
codes over a field Fqm (where q is a prime power). They are named after the work of Gabidulin in [9] and
have independently been presented earlier by Delsarte in [6]. These codes can be seen as the q-analog of
Reed-Solomon codes, using q-linearized polynomials instead of arbitrary polynomials. They are optimal
in the sense that they are not only MDS codes with respect to the Hamming metric, but also achieve the
Singleton bound with respect to the rank metric and are thus MRD (maximum rank distance) codes.

The decoding of Gabidulin codes has obtained a fair amount of attention in the literature, starting
with work on decoding within the unique decoding radius in [9, 10] and more recently [16, 19, 21, 25]. If

∗ This author was partially supported by Swiss National Science Foundation Fellowship no. 147304.
Anna-Lena Horlemann-Trautmann; Faculty of Mathematics and Statistics, University of St. Gallen, St. Gallen,

Switzerland (email: anna-lena.horlemann@unisg.ch).
Margreta Kuijper (Corresponding Author); Department of Electrical and Electronic Engineering, University of

Melbourne, VIC 3010, Australia (email: mkuijper@unimelb.edu.au).

29

http://orcid.org/0000-0003-2685-2343
http://orcid.org/0000-0001-9223-9550


A.-L. Horlemann-Trautmann, M. Kuijper / J. Algebra Comb. Discrete Appl. 5(1) (2018) 29–43

n is the length of the Gabidulin code and k denotes the dimension of the code as a linear space over the
field Fqm, the unique decoding radius is given by b(n − k)/2c. A main open question is whether there
exist parameter sets for which Gabidulin codes can be (list) decoded beyond the unique decoding radius
efficiently. This paper seeks to contribute to current research efforts on this open question.

Using the close resemblance between Reed-Solomon codes and Gabidulin codes, the paper [16] trans-
lates Gabidulin decoding into a set of polynomial interpolation conditions. Essentially, this setup is
also used in the papers [12, 27] that present iterative algorithms that perform Gabidulin list decoding
with a list size of 1. In this paper we present an iterative algorithm that bears similarity to the ones
in [12, 16, 27]. As new results we show that the algorithm computes a minimal basis for an interpolation
module that we associate with the received word. This result enables a parametrization of elements in
the module that lead to all Gabidulin decoding solutions that are at a fixed distance from the received
word. Thus we present a module minimization interpretation of the pioneering work by Loidreau [16].

The paper is structured as follows. In the next section we present several preliminaries on q-linearized
polynomials and Gabidulin codes, including the polynomial interpolation conditions from [16]. Subsection
2.3 deals with modules over the ring of linearized polynomials and draws attention to minimal bases
of these modules and their Predictable Leading Monomial property. In Section 3 we reformulate the
Gabidulin decoding requirements in terms of a module represented by four q-linearized polynomials and
present our polynomial-time algorithm. We conclude this paper in Section 4.

2. Preliminaries

2.1. q-linearized polynomials

Let q be a prime power and let m be a positive integer. Denote the finite field with q elements by
Fq and denote a primitive element of the extension field Fqm by α. Since Fqm is isomorphic (as a vector
space) to the vector space Fmq , matrices over the base field Fq can be interpreted as vectors over the
extension field, i.e., we have the isomorphism Fm×nq ∼= Fnqm. In the sequel we denote the rank of a matrix
X over Fq by rankq(X).

For a vector (v1, . . . ,vn) ∈ Fnqm we denote the k ×n Moore matrix by

Mk(v1, . . . ,vn) :=




v1 v2 . . . vn
v
[1]
1 v

[1]
2 . . . v

[1]
n

...
v
[k−1]
1 v

[k−1]
2 . . . v

[k−1]
n


 , (1)

where [i] := qi. A q-linearized polynomial over Fqm is defined to be of the form

f(x) =

n∑
i=0

aix
[i] , ai ∈ Fqm,

where, assuming that an 6= 0, n is called the q-degree of f(x), denoted by qdeg(f). This class of
polynomials was studied in detail by Ore in [17]. One can easily check that f(x1 +x2) = f(x1)+f(x2) and
f(λx1) = λf(x1) for any x1,x2 ∈ Fqm and λ ∈ Fq, hence the name linearized. The set of all q-linearized
polynomials over Fqm is denoted by Lq(x,qm). This set is a non-commutative ring with the normal
addition + and with composition ◦ of polynomials. Because of the non-commutativity, products and
quotients of elements of Lq(x,qm) have to be specified as being “left" or “right". To not be mistaken with
the standard division, we call the inverse of the composition symbolic division. Thus f(x) is symbolically
divisible by g(x) with right quotient m(x) if

g(x) ◦m(x) = g(m(x)) = f(x).

30

http://orcid.org/0000-0003-2685-2343
http://orcid.org/0000-0001-9223-9550


A.-L. Horlemann-Trautmann, M. Kuijper / J. Algebra Comb. Discrete Appl. 5(1) (2018) 29–43

Efficient algorithms for all these operations (left and right symbolic multiplication and division) can be
found e.g. in [12].

Lemma 2.1 (cf. [15] Theorem 3.50). Let f(x) ∈Lq(x,qm) and let Fqs be the smallest extension field of
Fqm that contains all roots of f(x). Then the set of all roots of f(x) is a Fq-linear vector space in Fqs.

Definition 2.2. Let U be a Fq-linear subspace of Fqm. We call ΠU (x) :=
∏

g∈U (x−g) the q-annihilator
polynomial of U.

Lemma 2.3 ([15] Theorem 3.52). Let U be a Fq-linear subspace of Fqm. Then ΠU (x) is an element of
Lq(x,qm).

Note that, if g1, . . . ,gn is a basis of U, one can rewrite

ΠU (x) = λ det(Mn+1(g1, . . . ,gn,x))

for some constant λ ∈ Fqm; clearly its q-degree equals n.
The notion of q-Lagrange polynomial is as follows:

Definition 2.4. Let g = (g1, . . . ,gn) ∈ Fnqm, where g1,g2, . . . ,gn are Fq-linearly independent. Let r =
(r1, . . . ,rn) ∈ Fnqm. Define the matrix Di(g,x) as Mn(g1, . . . ,gn,x) without the i-th column. We define
the q-Lagrange polynomial corresponding to g and r as

Λg,r(x) :=

n∑
i=1

(−1)n−iri
det(Di(g,x))

det(Mn(g))
∈ Fqm [x].

It can be easily verified that the above polynomial is q-linearized and that Λg,r(gi) = ri for i =
1, . . . ,n.

Throughout the paper we use matrix composition, which is defined analogously to matrix multipli-
cation: [

a(x) b(x)
c(x) d(x)

]
◦
[
e(x) f(x)
g(x) h(x)

]
:=

[
a(e(x)) + b(g(x)) a(f(x)) + b(h(x))
c(e(x)) + d(g(x)) c(f(x)) + d(h(x))

]
.

Let g1, . . . ,gn ∈ Fqm be linearly independent over Fq; as before denote g := (g1, . . . ,gn). Throughout
the remainder of the paper we use the standard notation 〈g1, . . . ,gn〉 for the Fq-linear span of g1,g2, . . .gn.
Furthermore we abbreviate the notation Π〈g1,g2,...,gn〉(x) by Πg(x). We need the following fact for our
investigations in Section 3.

Lemma 2.5. Let g1, . . . ,gn ∈ Fqm be linearly independent over Fq and let L(x) ∈Lq(x,qm) be such that
L(gi) = 0 for all i. Then

∃H(x) ∈Lq(x,qm) : L(x) = H(x) ◦ Πg(x).

Proof. We know from Lemma 2.3 that Πg(x) ∈ Lq(x,qm). Moreover unique left and right division
in Lq(x,qm) holds, i.e. in this case there exist unique polynomials H(x),R(x) ∈ Lq(x,qm) such that
L(x) = H(x) ◦ Πg(x) + R(x) and qdeg(R(x)) < qdeg(Πg(x)) = n. Since any α ∈ 〈g1, . . . ,gn〉 is a root of
L(x) as well as Πg(x), they must also be a root of R(x). Hence we have qn distinct roots for R(x) and
deg(R) < qn, thus R(x) ≡ 0 and the statement follows.

2.2. Gabidulin codes

Let g1, . . . ,gn ∈ Fqm be linearly independent over Fq. A Gabidulin code C ⊆ Fnqm of dimension k
is defined as the linear block code with generator matrix Mk(g1, . . . ,gn), as defined in (1). Using the

31

http://orcid.org/0000-0003-2685-2343
http://orcid.org/0000-0001-9223-9550


A.-L. Horlemann-Trautmann, M. Kuijper / J. Algebra Comb. Discrete Appl. 5(1) (2018) 29–43

isomorphic matrix representation, we can interpret C as a matrix code in Fm×nq . The rank distance dR
on Fm×nq is defined by

dR(X,Y ) := rankq(X −Y ) , X,Y ∈ Fm×nq

and analogously for the isomorphic extension field representation. The code C has dimension k over Fqm
and minimum rank distance (over Fq) n−k + 1. In fact, an equivalent definition of the code is

C = {(m(g1), . . . ,m(gn)) ∈ Fnqm | m(x) ∈Lq(x,q
m)<k},

where Lq(x,qm)<k := {m(x) ∈ Lq(x,qm) | qdeg(m(x)) < k}. For more information on bounds and
constructions of rank-metric codes the interested reader is referred to [9].

Consider a received word r = (r1, . . . ,rn) ∈ Fnqm as the sum r = c + e, where c = (c1, . . . ,cn) ∈ C is
a codeword and e = (e1, . . . ,en) ∈ Fnqm is the error vector. We now recall the polynomial interpolation
setup from [16] via a more general formulation in the next theorem.

Theorem 2.6. Let m(x) ∈Lq(x,qm), qdeg(f(x)) < k and ci = m(gi) for i = 1, . . . ,n. Then dR(c,r) = t
if and only if there exists a D(x) ∈Lq(x,qm), such that qdeg(D(x)) = t and

D(ri) = D(m(gi)) ∀i ∈{1, . . . ,n}.

Proof. Let D(x) ∈ Lq(x,qm) be such that D(ri) = D(f(gi)) and qdeg(D(x)) = t. This implies that
D(ri −f(gi)) = 0 for all i. Define ei := ri −f(gi), then ei ∈ Fqm and every element of 〈e1, . . . ,en〉 is a
root of D(x) (see Lemma 2.1). Since D(x) is non-zero and has degree qt, it follows that the linear space
of roots has q-dimension t, which implies that (e1, . . . ,en) has rank t. This means that the rank distance
between (c1, . . . ,cn) and (r1, . . . ,rn) is equal to t. Thus, one direction is proven.

For the other direction let (c1, . . . ,cn), (r1, . . . ,rn) have rank distance t, i.e. (e1, . . . ,en) := (c1 −
r1, . . . ,cn − rn) has rank t. Then by Lemma 2.3 there exists a non-zero D(x) ∈ Lq(x,qm) of degree qt
such that D(ei) = 0 for all i. By linearity we get that D(ci) = D(ri) for i = 1, . . . ,n. Since ci = f(gi)
the statement follows.

Remark 2.7. Theorem 2.6 states that the set of roots of D(x) is a vector space of degree t which is equal
to the span of e1, . . . ,en (for this note that ei = m(gi) − ri). This is why D(x) is unique up to scalar
multiplication (for given codeword and received word) and is also called the error span polynomial (cf.
e.g. [22]). The analogy in the classical Hamming metric set-up is the error locator polynomial, whose
roots indicate the error locations.

2.3. Modules over Lq(x, qm)

As mentioned before, the set of q-linearized polynomials Lq(x,qm) is a ring with addition and
composition. Hence, for any positive integer `, the set Lq(x,qm)` is a (right or left) module. In this work
we will consider Lq(x,qm)` as a left module and investigate its (left) submodules.

In this section, we give some general definitions and results on Lq(x,qm)` and present the terminology
of the Predictable Leading Monomial property. All of these are analogous to the definitions and results for
modules over Fq[x] (equipped with normal polynomial multiplication) from [3], see also the early work by
Fitzpatrick [7] and the textbooks [2, 5]. Linearized polynomials belong to the class of skew polynomials,
for which the general theory of linear algebra and Gröbner bases is well established, see e.g. [1, 4, 11].

For reasons of clear exposition and self-containedness, we formulate the results that we need explicitly
in terms of rings with composition, in the language of linearized polynomials. Thus, compared to the
Fq[x]-case, multiplication is replaced by composition.

To avoid confusion, we denote polynomials by f(x), while vectors of polynomials are denoted by f.
If we need to index polynomials, we use the notation f1(x), . . . ,fs(x), while for vectors of polynomials
we use the notation f(1), . . . ,f(s).

32

http://orcid.org/0000-0003-2685-2343
http://orcid.org/0000-0001-9223-9550


A.-L. Horlemann-Trautmann, M. Kuijper / J. Algebra Comb. Discrete Appl. 5(1) (2018) 29–43

Elements of Lq(x,qm)` are of the form

f := [f1(x) . . . f`(x)] =
∑̀
i=1

fi(x)ei

where fi(x) =
∑

j fijx
[j] ∈ Lq(x,qm) and e1, . . . ,e` are the unit vectors of length `. Analogous to

polynomial multiplication on Fqm [x]` we define for h(x) ∈Lq(x,qm) the left operation

h(x) ◦f := [h(f1(x)) . . . h(f`(x))] =
∑̀
i=1

h(fi(x))ei.

The monomials of f are of the form x[k]ei for all k such that fik 6= 0.

Definition 2.8. A subset M ⊆ Lq(x,qm)` is a (left) submodule of Lq(x,qm)` if it is closed under
addition and composition with Lq(x,qm) on the left.

Definition 2.9. Consider the non-zero elements f(1), . . . ,f(s) ∈ Lq(x,qm)`. We say that f(1), . . . ,f(s)
are linearly independent if for any a1(x), . . . ,as(x) ∈Lq(x,qm)

s∑
i=1

ai(x) ◦f(i) = [ 0 . . . 0 ] =⇒ a1(x) = · · · = as(x) = 0.

A generating set of a submodule M ⊆ Lq(x,qm)` is called a basis of M if all its elements are linearly
independent.

One can easily see that

B = {xe1,xe2 . . . ,xe`}

is a basis of Lq(x,qm)`, thus Lq(x,qm)` is a free and finitely generated module.
We need the notion of monomial order for the subsequent results, which we will define in analogy to

[2, Definition 3.5.1].

Definition 2.10. A monomial order < on Lq(x,qm)` is a total order on Lq(x,qm)` that fulfills the
following two conditions:

• x[k]ei < x[j] ◦ (x[k]ei) for any monomial x[k]ei ∈Lq(x,qm)` and j ∈ N>0.

• If x[k]ei < x[k
′]ei′, then x[j]◦(x[k]ei) < x[j]◦(x[k

′]ei′ ) for any monomials x[k]ei,x[k
′]ei′ ∈Lq(x,qm)`

and j ∈ N0.

We have different choices for monomial orders, of which the following is of interest for our investiga-
tions.

Definition 2.11. The (k1, . . . ,k`)-weighted term-over-position monomial order is defined as

x[i1]ej1 <(k1,...,k`) x
[i2]ej2 : ⇐⇒ i1 + kj1 < i2 + kj2 or [i1 + kj1 = i2 + kj2 and j1 < j2].

Note that this monomial order for Lq(x,qm)` coincides with the weighted term-over-position mono-
mial order for Fqm [x], since one could replace the q-degrees with normal degrees and get the classical
cases.

We furthermore need the following definition in analogy to the weighted term-over-position monomial
order:

33

http://orcid.org/0000-0003-2685-2343
http://orcid.org/0000-0001-9223-9550


A.-L. Horlemann-Trautmann, M. Kuijper / J. Algebra Comb. Discrete Appl. 5(1) (2018) 29–43

Definition 2.12. The (k1, . . . ,k`)-weighted q-degree of [f1(x) . . . f`(x)] is defined as max{ki +
qdeg(fi(x)) | i = 1, . . . ,`}.

In the following we will not fix a monomial order. The results, if not noted differently, hold for any
chosen monomial order.

Definition 2.13. We can order all monomials of an element f ∈ Lq(x,qm)` in decreasing order with
respect to some monomial order. Rename them such that x[i1]ej1 > x

[i2]ej2 > ... . Then

1. the leading monomial lm(f) = x[i1]ej1 is the greatest monomial of f.

2. the leading position lpos(f) = j1 is the vector coordinate of the leading monomial.

3. the leading term lt(f) = fj1,i1x
[i1]ej1 is the complete term of the leading monomial.

In order to define minimality for submodule bases we need the following notion of reduction, in
analogy to [2, Definition 4.1.1].

Definition 2.14. Let f,h ∈ Lq(x,qm)` and let F = {f(1), . . . ,f(s)} be a set of non-zero elements of
Lq(x,qm)`. We say that f reduces to h modulo F (in one step) if and only if

h = f − ((b1x[a1]) ◦f(1) + · · · + (bkx[ak]) ◦f(k))

for some a1, . . . ,ak ∈ N0 and b1, . . . ,bk ∈ Fqm, where

lm(f) = x[ai] ◦ lm(f(i)), i = 1, . . . ,k, and

lt(f) = (b1x
[a1]) ◦ lt(f(1)) + · · · + (bkxa[k] ) ◦ lt(f(k)).

We say that f is minimal with respect to F if it cannot be reduced modulo F.

Definition 2.15. A module basis B is called minimal if all its elements b are minimal with respect to
B\{b}.

Proposition 2.16. Let B be a basis of a module M ⊆ Lq(x,qm)`. Then B is a minimal basis if and
only if all leading positions of the elements of B are distinct.

Proof. Let B be minimal. If two elements of B have the same leading position, the one with the
greater leading monomial can be reduced modulo the other element, which contradicts the minimality.
Hence, no two elements of a minimal basis can have the same leading position.

The other direction follows straight from the definition of reducibility and minimality of a basis,
since if the leading positions of all elements are different, none of them can be reduced modulo the other
elements.

The property outlined in the following theorem is well-established for minimal Gröbner bases for
modules in Fq[x]` with respect to multiplication. It extends to non-commutative Gröbner bases of solvable
type, see e.g. [11, Lemma 1.5]. As a result, it also holds over the ring of linearized polynomials. It was
labeled Predictable Leading Monomial (PLM) property in [13] to emphasize its closeness to Forney’s
Predictable Degree property [8]. It captures the exact property that is needed in subsequent proofs.

Note that in [13] minimal bases were addressed as minimal Gröbner bases. It can be shown that in
our current setting these are the same.

Theorem 2.17 (PLM property). Let M be a module in Lq(x,qm)` with minimal basis B =
{b(1), . . . ,b(L)}. Then for any 0 6= f ∈ M, written as

f = a1(x) ◦ b(1) + · · · + aL(x) ◦ b(L),

34

http://orcid.org/0000-0003-2685-2343
http://orcid.org/0000-0001-9223-9550


A.-L. Horlemann-Trautmann, M. Kuijper / J. Algebra Comb. Discrete Appl. 5(1) (2018) 29–43

where a1(x), . . . ,aL(x) ∈Lq(x,qm), we have

lm(f) = max
1≤i≤L;ai(x) 6=0

{lm(ai(x)) ◦ lm(b(i))}

where lm(ai(x)) is the term of ai(x) of highest q-degree.

Proof. Since B is minimal, all leading positions and thus also all leading monomials of its elements are
distinct (by Proposition 2.16). Without loss of generality assume that lm(b(1)) > lm(b(2)) > · · · > lm(b(L))
and that all ai(x) are non-zero. Since Lq(x,qm) contains no zero divisors, we have that lpos(ai(x)◦b(i)) =
lpos(b(i)) for 1 ≤ i ≤ L. As a result, all leading positions and therefore all leading monomials of the
ai(x) ◦ b(i)’s are distinct. Thus there exist j1, . . . ,jL such that

lm(aj1 (x) ◦ b
(j1)) > lm(aj2 (x) ◦ b

(j2)) > · · · > lm(ajL (x) ◦ b
(jL)).

It follows that

lm(f) = lm(aj1 (x) ◦ b
(j1)) = lm(aj1 (x)) ◦ lm(b

(j1)) = max
1≤i≤L

{lm(ai(x)) ◦ lm(b(i))}.

Proposition 2.18. The leading positions and weighted q-degrees of all elements of two distinct minimal
bases for the same module in Lq(x,qm)` have to be the same. This implies that the cardinality of both
bases are equal as well.

Proof. Let B1 = {b(i) | i = 1, . . . ,L} and B2 = {c(i) | i = 1, . . . ,L′} be two different minimal bases
of the same module in Lq(x,qm)`. Then b(j) must be a linear combination of the c(i) for j = 1, . . . ,L.
Similarly, c(i) must be a linear combination of the b(j) for i = 1, . . . ,L′. Hence, by the PLM property and
since all leading positions are different in the bases, there exist j′ ∈{1, . . . ,L′} and a(x),a′(x) ∈Lq(x,qm)
such that lm(a(x) ◦ c(j

′)) = lm(b(j)) and lm(a′(x) ◦ b(j)) = lm(c(j
′)). This implies on the one hand

that lpos(b(j)) = lpos(c(j
′)) and on the other that qdeg(a(x)) = qdeg(a′(x)) = 0, which implies that

qdeg(b(j)) = qdeg(c(j
′)).

3. Iterative decoding of Gabidulin codes

For the remainder of the paper let g1, . . . ,gn ∈ Fqm be linearly independent over Fq and let
Mk(g1, . . . ,gn) be the generator matrix of the Gabidulin code C ⊆ Fnqm. Denote g = (g1, . . . ,gn) and
let r = (r1, . . . ,rn) ∈ Fnqm be the received word. Throughout the remainder of this paper our monomial
order will be the (0,k − 1)-weighted term-over-position monomial order.

3.1. Parametrization

In the following we abbreviate the row span of a (polynomial) matrix A by rs(A).

Definition 3.1. The interpolation module M(r) for r is defined as the left submodule of Lq(x,qm)2,
given by

M(r) := rs

[
Πg(x) 0
−Λg,r(x) x

]
.

We identify any [f(x) g(x)] ∈ M(r) with the bivariate linearized q-polynomial Q(x,y) = f(x)+g(y).
The following theorem shows that the name interpolation module is justified for M(r):

35

http://orcid.org/0000-0003-2685-2343
http://orcid.org/0000-0001-9223-9550


A.-L. Horlemann-Trautmann, M. Kuijper / J. Algebra Comb. Discrete Appl. 5(1) (2018) 29–43

Theorem 3.2. M(r) consists exactly of all Q(x,y) = f(x) + g(y) with f(x),g(x) ∈Lq(x,qm), such that
Q(gi,ri) = 0 for i = 1, . . . ,n.

Proof. For the first direction let Q(x,y) = f(x) + g(y) be an element of M(r). Then there exist
β(x),γ(x) ∈Lq(x,qm) such that f(x) = β(x) ◦ Πg(x) −γ(x) ◦ Λg,r(x) and γ(x) = g(x), thus Q(gi,ri) =
β(Πg(gi)) −γ(Λg,r(gi)) + γ(ri) = 0 −γ(ri) + γ(ri) = 0.

For the other direction let f(x),g(x) ∈ Lq(x,qm) be such that Q(gi,ri) = f(gi) + g(ri) = 0 for
i = 1, . . . ,n. To show that Q(x,y) ∈ M(r) we need to find β(x),γ(x) ∈Lq(x,qm) such that

β(x) ◦ Πg(x) −γ(x) ◦ Λg,r(x) = f(x) and γ(x) = g(x).

We substitute the second into the first equation to get

β(x) ◦ Πg(x) = f(x) + g(x) ◦ Λg,r(x). (2)

By assumption, the equation f(gi) + g(Λg,r(gi)) = f(gi) + g(ri) = 0 holds for all i. Then, by Lemma 2.5,
it follows that f(x) + g(x)◦Λg,r(x) is symbolically divisible on the right by Πg(x) and hence there exists
β(x) ∈Lq(x,qm) such that (2) holds.

The above leads to the following characterization of codewords with distance t to the received word:

Theorem 3.3. The elements f = [N(x) −D(x)] of M(r) that fulfill

1. qdeg(N(x)) ≤ t + k − 1,

2. qdeg(D(x)) = t,

3. N(x) is symbolically divisible on the left by D(x), i.e. there exists m(x) ∈ Lq(x,qm) such that
D(m(x)) = N(x),

are in one-to-one correspondence with the codewords of rank distance t to the received word r.

Proof. To prove the first direction let c ∈ Fnqm be a codeword such that dR(c,r) = t with the corre-
sponding message polynomial m(x) ∈Lq(x,qm)<k. Then by Theorem 2.6 there exists D(x) ∈Lq(x,qm) of
q-degree t such that D(m(gi)) = D(ri) for i = 1, . . . ,n. By Theorem 3.2 we know that [D(m(x)) −D(x)]
is in M(r). It holds that qdeg(D(m(x))) ≤ t + k− 1 and that (D(m(x))) is symbolically divisible on the
left by D(x).

For the other direction let [N(x) − D(x)] ∈ M(r) fulfill conditions 1) − 3). Then the divisor
m(x) ∈ Lq(x,qm) has q-degree less than k and N(x) = D(m(x)). Since it is in M(r) it follows from
Theorem 3.2 that D(m(gi)) − D(ri) = 0 for all i. Define c := (m(g1), . . . ,m(gn)), then it follows from
Theorem 2.6 that dR(c,r) = t.

Note that conditions 1) and 2) of Theorem 3.3 can alternatively be formulated as the condition that
lpos(f) = 2 with (0,k − 1)-weighted q-degree of f being equal to t + k − 1.

It follows from Theorem 3.3 that decoding within rank radius t is equivalent to finding all elements
f = [N(x) −D(x)] in M(r) with (0,k−1)-weighted q-degree less than t+k and leading position 2, such
that N(x) is symbolically divisible on the left by D(x). The following theorem presents a parametrization
that is helpful in order to find such elements.

Theorem 3.4. (Parametrization) Let B = {b(1),b(2)} be a minimal basis of M(r) with respect to the
(0,k − 1)-weighted degree, with lpos(b(1)) = 1 and lpos(b(2)) = 2. Define `1 and `2 as the (0,k − 1)-
weighted q-degrees of b(1),b(2), respectively. Let t be a nonnegative integer. Then all elements f ∈ M(r)
with lpos(f) = 2 and (0,k − 1)-weighted q-degree equal to t + k − 1 are given by

f = β(x) ◦ b(1) + γ(x) ◦ b(2),

where β(x) is a q-linearized polynomial with qdeg(β(x)) ≤ t + k − 1 − `1 and γ(x) is a q-linearized
polynomial with qdeg(γ(x)) = t + k − 1 − `2.

36

http://orcid.org/0000-0003-2685-2343
http://orcid.org/0000-0001-9223-9550


A.-L. Horlemann-Trautmann, M. Kuijper / J. Algebra Comb. Discrete Appl. 5(1) (2018) 29–43

Proof. The parametrization follows straightforwardly from Theorem 2.17.

3.2. Construction of a minimal basis

We now present an iterative algorithm for the construction of a minimal basis for the interpolation
module. The algorithm is similar to the ones in[12, 16, 27]. Our main contribution is the recognition, via
Theorem 3.4, that such an algorithm essentially computes a minimal basis for the interpolation module
rather than just one solution corresponding to the received word. A preliminary version of this result is
the short conference paper [14].

We first need the following result:

Lemma 3.5. For i = 1, . . . ,n denote by Mi the interpolation module for (g1, . . . ,gi) and (r1, . . . ,ri).
Let [

P(x) −K(x)
N(x) −D(x)

]
be a basis for Mi−1 and

Γi := P(gi) −K(ri) , ∆i := N(gi) −D(ri).

If Γi 6= 0, then the set of row vectors of[
b(1)

b(2)

]
:=

[
xq − Γq−1i x 0

∆ix −Γix

]
◦
[
P(x) −K(x)
N(x) −D(x)

]
is a basis of Mi. If ∆i 6= 0, then the set of row vectors of[

∆ix −Γix
0 xq − ∆q−1i x

]
◦
[
P(x) −K(x)
N(x) −D(x)

]
is a basis of Mi.

Proof. We first consider the first case and show that both b(1) and b(2) are in Mi. From the assumptions
it follows that P(gj) = K(rj) and that N(gj) = D(rj) for 1 ≤ j < i. Moreover, the two entries of b(1)
are given by

(xq − Γq−1i x) ◦P(x) = P(x)
q − Γq−1i P(x),

(xq − Γq−1i x) ◦K(x) = K(x)
q − Γq−1i K(x),

thus P(gj)q − Γ
q−1
i P(gj) −K(rj)

q + Γ
q−1
i K(rj) = 0 for 1 ≤ j ≤ i. For b

(2) we get

∆iP(gj) − ΓiN(gj) − ∆iK(rj) + ΓiD(rj) =

∆i(P(gj) −K(rj)) − Γi(N(gj) −D(rj)) = ∆iΓi − Γi∆i = 0

for 1 ≤ j ≤ i. Thus, b(1) and b(2) are elements of Mi.
It remains to show that b(1) and b(2) span the entire interpolation module (and not just a submodule of

it). For this, it is sufficient to show that [ Πi−1(x) 0 ] and [ Λi−1(x) −x ] are linear combinations of b(1)
and b(2). Since [ P(x) −K(x) ] and [ N(x) −D(x) ] are a basis of Mi, there exist β̄(x), γ̄(x) ∈Lq(x,qm)
such that

β̄(x) ◦ [ P(x) −K(x) ] + γ̄(x) ◦ [ N(x) −D(x) ] = [ Πi−1(x) 0 ].

37

http://orcid.org/0000-0003-2685-2343
http://orcid.org/0000-0001-9223-9550


A.-L. Horlemann-Trautmann, M. Kuijper / J. Algebra Comb. Discrete Appl. 5(1) (2018) 29–43

Let β(x),γ(x) ∈Lq(x,qm) be such that

β(x) ◦ (xq − Γq−1i x) = (x
q − Πi−1(gi)q−1x) ◦

(
γ̄(

∆i
Γi
x) + β̄(x)

)
,

γ(x) = −(xq − Πi−1(gi)q−1x) ◦ γ̄(
1

Γi
x).

Note that it can easily be checked that Γi is a root of the right side of the previous equation, thus
β(x) is well-defined by Lemma 2.5 . Denote the first and second row of the new basis by b(1) and b(2),
respectively. Then

β(x) ◦ b(1)1 + γ(x) ◦ b
(2)
1 = β(x) ◦ (x

q − Γq−1i x) ◦P(x) + γ(x) ◦ (∆iP(x) − ΓiN(x))

= (xq − Πi−1(gi)q−1x) ◦
(
γ̄(

∆i
Γi
x) + β̄(x)

)
◦P(x) + γ(∆iP(x)) −γ(ΓiN(x))

=
(
(xq − Πi−1(gi)q−1x) ◦ β̄(x) −γ(∆ix)

)
◦P(x) + γ(∆iP(x)) −γ(ΓiN(x))

=
(
(xq − Πi−1(gi)q−1x) ◦ β̄(x)

)
◦P(x) + (xq − Πi−1(gi)q−1x) ◦ γ̄(N(x))

= (xq − Πi−1(gi)q−1x) ◦
(
β̄(P(x)) + γ̄(N(x))

)
= (xq − Πi−1(gi)q−1x) ◦ Πi−1(x) = Πi(x),

and

β(x) ◦ b(1)2 + γ(x) ◦ b
(2)
2 = −β(x) ◦ (x

q − Γq−1i x) ◦K(x) −γ(x) ◦ (∆iK(x) − ΓiD(x))

=
(
(xq − Πi−1(gi)q−1x) ◦ β̄(x) −γ(∆ix)

)
◦K(x) + γ(∆iK(x)) −γ(ΓiD(x))

= (xq − Πi−1(gi)q−1x) ◦
(
β̄(K(x)) + γ̄(D(x))

)
= 0.

Thus β(x)◦b(1) + γ(x)◦b(2) = [ Πi(x) 0 ], i.e. [ Πi(x) 0 ] is in the module spanned by the new basis.
Analogously, if we have that c̄(x) ◦ [ P(x) −K(x) ] + d̄(x) ◦ [ N(x) −D(x) ] = [ Λi−1(x) −x ]

and define c(x),d(x) ∈Lq(x,qm) such that

d(x) = −
(
d̄(x) +

Λi−1(gi) −ri
Πi−1(gi)

γ̄(x)

)
◦ (

1

Γi
x)

c(x) ◦ (xq − Γq−1i x) = c̄(x) +
Λi−1(gi) −ri

Πi−1(gi)
β̄(x) −d(∆ix)

we get

c(x) ◦ b(1) + d(x) ◦ b(2) = [ Λi(x) −x ].

Hence, we have shown that the new basis {b(1),b(2)} spans the entire interpolation module.
For the second case note that

rs

([
∆ix −Γix

0 xq − ∆q−1i x

]
◦
[
P(x) −K(x)
N(x) −D(x)

])

= rs

([
xq − ∆q−1i x 0

Γix −∆ix

]
◦
[
N(x) −D(x)
P(x) −K(x)

])
,

which corresponds to the first case after exchanging P(x) with N(x) and K(x) with D(x) (and vice
versa).

38

http://orcid.org/0000-0003-2685-2343
http://orcid.org/0000-0001-9223-9550


A.-L. Horlemann-Trautmann, M. Kuijper / J. Algebra Comb. Discrete Appl. 5(1) (2018) 29–43

Using Lemma 3.5 as our main ingredient, we now set out to design an iterative algorithm that
computes a minimal basis for Mi at each step i.

Algorithm 1 Iterative computation of a minimal basis of M(r).
Require: Positive integers k, n; g = (g1, . . . , gn) ∈ Fnqm, received word r = (r1, . . . , rn) ∈ Fnqm.

Initialize j := 0, B0 :=
[
x 0
0 x

]
.

We denote Bi :=
[
Pi(x) −Ki(x)
Ni(x) −Di(x)

]
.

for i from 1 to n do
Γi := Pi−1(gi) −Ki−1(ri) , ∆i := Ni−1(gi) −Di−1(ri).
if [qdeg(Pi−1(x)) ≤ qdeg(Di−1(x)) + k − 1 and Γi 6= 0] or ∆i = 0 then

Bi :=

[
xq − Γq−1i x 0

∆ix −Γix

]
◦Bi−1

else

Bi :=

[
∆ix −Γix

0 xq − ∆q−1i x

]
◦Bi−1

end if
end for
return Bn

Theorem 3.6. Algorithm 1 yields a minimal basis of the interpolation module M(r), where the leading
position of the first row equals 1 and the leading position of the second row equals 2.

Proof. Denote by M1 the matrix we multiply by on the left in the first IF statement and by M2 the
one in the ELSE statement of the algorithm. We know from Lemma 3.5 that at each step, Bi is a basis
for the interpolation module Mi. We now show that it is a minimal basis with respect to the (0,k − 1)-
weighted term-over-position monomial order via induction on i. Assume that at step i the first row has
leading position 1 and the second row has leading position 2, i.e. qdeg(Pi(x)) > qdeg(Ki(x)) + k−1 and
qdeg(Ni(x)) ≤ qdeg(Di(x)) + k − 1. If qdeg(Pi(x)) ≤ qdeg(Di(x)) + k − 1 we composite on the left by
M1. Hence,

qdeg(Pi+1(x)) = qdeg(Pi(x)) + 1

and

qdeg(Ki+1(x)) = qdeg(Ki(x)) + 1 < qdeg(Pi(x)) −k + 2 = qdeg(Pi+1(x)) −k + 1.

Thus, the leading position of the first row of Bi+1 is still 1. Moreover,

qdeg(Ni+1(x)) ≤ max{qdeg(Pi(x)), qdeg(Ni(x))}≤ qdeg(Di(x)) + k − 1

and, since the assumptions imply that qdeg(Ki(x)) < qdeg(Di(x)),

qdeg(Di+1(x)) = max{qdeg(Ki(x)), qdeg(Di(x))} = qdeg(Di(x)).

Thus the leading position of the second row is 2. Since the assumptions are true for B0 the statement
follows via induction.

Analogously one can prove that composition with M2 yields a basis of Mi with different leading
positions in the two rows. Thus at each step we get a basis of Mi with different leading positions, which
is by Proposition 2.16 a minimal basis. Thus, after n steps, Bn is a minimal basis for the interpolation
module M(r).

Remark 3.7. It can be verified that, due to the linear independence of g1, . . . ,gk, up to a constant, at step
k the algorithm has computed the q-annihilator polynomial and the q-Lagrange polynomial corresponding
to the data so far.

39

http://orcid.org/0000-0003-2685-2343
http://orcid.org/0000-0001-9223-9550


A.-L. Horlemann-Trautmann, M. Kuijper / J. Algebra Comb. Discrete Appl. 5(1) (2018) 29–43

Proposition 3.8. Algorithm 1 has computational complexity order Oqm (n2).

Proof. For the iterative computation of the minimal basis from Algorithm 1 we need n steps. In each
step we need

• four evaluations and differences of linearized polynomials of q-degree at most n (to compute ∆i and
Γi and in the update of Bi),

• two multiplications of a linearized polynomial of q-degree at most n by a scalar (in the update of
Bi),

• a composition of a linearized polynomial of q-degree at most n with (xq −gq−1i x) (for this note that
we compute a (q − 1)-th power of gi with a q-th power and one division).

All of these operations can be done with Oqm (n) operations. Overall we get an upper bound on the
complexity of Oqm (n2).

3.3. Decoding algorithm

We can now set up the decoding algorithm which will find the closest codeword(s) to a given received
word. For this we need the following lemma.

Lemma 3.9. Consider a Gabidulin code C ⊆ Fnqm of dimension k. Let M(r) be the interpolation module
of the received word r ∈ Fnqm with minimal basis B = {b(1),b(2)} where lpos(b(i)) = i for i = 1, 2. Denote
the (0,k − 1)-weighted q-degree of b(i) by `i for i = 1, 2. Then

`1 + `2 = n + k − 1. (3)

Proof. By Proposition 2.18 the q-degrees of any minimal basis of the interpolation module M(r) have
to add up to the same number, hence it is enough to show that they add up to n+k−1 for one particular
basis. Consider the iterative construction of a minimal basis from Algorithm 1. It is easy to see that
the initial basis has weighted q-degrees 0 and k − 1. Moreover, at each step the q-degree of one row
is increased by one, whereas the q-degree of the other row remains the same. Thus, the sum of the
two q-degrees is increased by 1 at each step. Since we get the desired basis of M(r) at the n-th step,
equation (3) follows.

In the following theorem we pay specific attention to the unique decoding case.

Theorem 3.10. Consider the setting of Theorem 3.4. If t = min{dR(c,r) | c ∈ C} and t ≤ (n−k)/2
then f = γ(x) ◦ b(2) with qdeg(γ(x)) = 0 and symbolic division on the two components of the vector b(2)
produces the message polynomial corresponding to the unique closest codeword to r.

Proof. Let m(x) ∈Lq(x,qm) be the message polynomial corresponding to the unique closest codeword
c. Then by Theorem 3.3, there exist D(x) ∈Lq(x,qm) of q-degree t such that f = [ D(m(x)) −D(x) ]
is an element of the interpolation module with leading position 2. Note that then the (0,k−1)-weighted
degree of f equals t + k − 1 ≤ (n + k − 2)/2. Theorem 2.17 now implies that lm(f) ≥ lm(b(2)), which
implies (since the leading positions of both elements are 2) that `2 ≤ (n + k − 2)/2. It now follows from
Lemma 3.9 that `1 ≥ (n + k)/2. Thus, in the parametrization we get β(x) ≡ 0, which means that there
exists γ(x) such that

f = γ(x) ◦ b(2).

But since γ(x) cancels out when we divide the right entry of f by the left, we can simply choose γ(x) = x
to recover the message polynomial. This also implies that qdeg(b(2)) = t + k− 1, and the last statement
of the theorem follows.

40

http://orcid.org/0000-0003-2685-2343
http://orcid.org/0000-0001-9223-9550


A.-L. Horlemann-Trautmann, M. Kuijper / J. Algebra Comb. Discrete Appl. 5(1) (2018) 29–43

Note that, if the received word is within the unique decoding radius, the main result of Loidreau’s
algorithm [16] is similar, namely the symbolic division on two components to produce the message poly-
nomial, as in the above theorem.

We present the general structure of the decoding algorithm in Algorithm 2 below. The outer IF loop
is based on Theorem 3.10, whereas the corresponding ELSE loop uses Theorems 3.3 and 3.4 to enumerate
all message polynomials corresponding to the codewords of distance t to the received word (for increasing
t).

Algorithm 2 Iterative decoding of a Gabidulin code C ⊆ Fnqm.
Require: Positive integers k, n; received word r ∈ Fnqm.
Use Algorithm 1 to compute a minimal basis Bn = {b(1), b(2)} of M(r).
Set `1 := qdeg(b(1)), `2 := qdeg(b(2)), list:= [ ], j := 0 .
if `2 ≤ (n + k − 2)/2 and b

(2)
1 is symbolically divisible by b

(2)
2 on the left then

add the symbolic quotient of b(2)1 and b
(2)
2 to list.

else
while list= [ ] do

for all a(x) ∈Lq(x, qm), qdeg(a(x)) ≤ `2 − `1 + j do
for all monic c(x) ∈Lq(x, qm), qdeg(b(x)) = j do

f := a(x) ◦ b(1) + c(x) ◦ b(2)
if f1(x) is symb. (right) divisible by f2(x) then

add the respective symb. quotient to list
end if

end for
end for
j := j + 1

end while
end if
return list

Remark 3.11. Algorithm 2 is an extension of Loidreau’s algorithm, in the sense that it has the same
performance in the unique decoding case, but it can also find all closest codewords if the received word is
beyond the unique decoding radius of the Gabidulin code. This is due to the parametrization derived in
Subsection 3.1 and the fact that Loidreau’s algorithm actually computes a minimal basis of the interpola-
tion module, as shown in Subsection 3.2.

We conclude this section with a final example.

Example 3.12. Consider the Gabidulin code in F23 ∼= F2[α] (with α3 = α + 1) of length n = 3 and
dimension k = 2 with generator matrix

G =

(
1 α α2

1 α2 α4

)
.

Thus g = (g1,g2,g3) = (1,α,α2). Suppose that the received word equals

r = ( α + 1 0 α ).

Using Algorithm 1, we iteratively compute

B1 =

[
x2 + x 0

(α + 1)x x

]
,

B2 =

[
x4 + (α2 + α + 1)x2 + (α2 + α)x 0

(α2 + α)x2 + (α2 + α + 1)x (α2 + α)x

]
,

41

http://orcid.org/0000-0003-2685-2343
http://orcid.org/0000-0001-9223-9550


A.-L. Horlemann-Trautmann, M. Kuijper / J. Algebra Comb. Discrete Appl. 5(1) (2018) 29–43

B3 =

[
α2x4 + α5x x

αx4 + α4x2 + x αx2 + α6x

]
.

B3 is a minimal (0, 1)-weighted basis of the interpolation module M(r). In the notation of Theorem 3.4,
we get `1 = `2 = 2. As a result, by Theorem 3.4, any monic f ∈ M(r) that has (0, 1)-weighted q-degree 2
and fulfills lpos(f) = 2 can be written as

f = β(x) ◦ b(1) + γ(x) ◦ b(2),

where β(x) is a q-linearized polynomial with qdeg(β(x)) ≤ 0 and γ(x) is a monic q-linearized polynomial
with qdeg(γ(x)) = 0. Thus

f = b0x◦ b(1) + x◦ b(2)

= b0b
(1) + b(2)

=
[

(b0α
2 + α)x4 + α4x2 + (b0α

5 + 1)x αx2 + (b0 + α
6)x

]
.

In fact, in this example we can use this basis to obtain a complete list of codewords of rank distance 1
away from r = ( α + 1 0 α ), as follows. It is easily checked that for b0 ∈ F23\{α6} we get divisibility.
Thus it follows from Theorem 3.3 that the complete list of all message polynomials & codewords of rank
distance 1 away from r = ( α + 1 0 α ) is given by

m1(x) = x
2 + αx c1 = ( α + 1 0 α

2 + 1),
m2(x) = α

5x2 + α2x c2 = ( α + 1 α α),
m3(x) = α

3x2 + α4x c3 = ( α
2 + 1 0 α2),

m4(x) = α
4x2 c4 = ( α

2 + α α2 + 1 α),
m5(x) = α

6x2 + α6x c5 = ( 0 α + 1 1),
m6(x) = α

2x2 + α3x c6 = ( α
2 + α + 1 0 α),

m7(x) = αx
2 + x c7 = ( α + 1 1 α + 1).

Note that the corresponding Hamming distances to r vary from 1 to 3.

4. Conclusions

We extended the Welch-Berlekamp type algorithm given in the pioneering work by Loidreau [16],
to be able to decode also beyond the unique decoding radius. For this we derived a parametrization of
all codewords within a given radius of the received words, based on a minimal basis of the interpolation
module. To compute such a minimal basis we presented a polynomial-time iterative algorithm with simple
update steps, similar to Loidreau’s algorithm. The main contribution of our paper is the recognition that
such algorithms actually compute a minimal basis of the interpolation module which can then be used
to provide a parametrization of all solutions corresponding to the received word.

In the Reed-Solomon case, Massey’s parametrization resulting from the Berlekamp-Massey algorithm
was used by Wu [26] as the foundation to his polynomial-time Reed-Solomon list decoding algorithm. This
was used in [3] as the foundation for a polynomial time Reed-Solomon list decoding method via Welch-
Berlekamp type interpolation. In this paper we strengthened the link between Reed-Solomon decoding
and Gabidulin decoding in providing a similar parametrization from a Welch-Berlekamp type algorithm
for Gabidulin decoding. Currently no polynomial-time list decoding algorithms exist for general Gabidulin
codes; on the contrary, it is shown that polynomial list sizes are not possible for certain parameter sets
(see e.g. [18, 24]). However, there are still many parameters for which it is an open question whether
polynomial-time list decoding of Gabidulin codes is possible. It is a topic of future research to build
on the results of this paper in extending the parametrization-based methods of [3, 26] to a possibly
polynomial-time Gabidulin list decoding algorithm.

42

http://orcid.org/0000-0003-2685-2343
http://orcid.org/0000-0001-9223-9550


A.-L. Horlemann-Trautmann, M. Kuijper / J. Algebra Comb. Discrete Appl. 5(1) (2018) 29–43

References

[1] S. Abramov, M. Bronstein, Linear algebra for skew–polynomial matrices, Technical Report INRIA,
RR–4420, 2002.

[2] W. W. Adams, P. Loustaunau, An Introduction to Gröbner Bases, volume 3 of Graduate Studies in
Mathematics, American Mathematical Society, Providence, RI, 1994.

[3] M. Ali, M. Kuijper, A parametric approach to list decoding of Reed–Solomon codes using interpola-
tion, IEEE Trans. Inform. Theory 57(10) (2011) 6718–6728.

[4] B. Beckermann, H. Cheng, G. Labahn, Fraction–free row reduction of matrices of Ore polynomials,
J. Symbolic Comput. 41(5) (2006) 513–543.

[5] D. A. Cox, J. Little, D. O’Shea, Using Algebraic Geometry, volume 185 of Graduate Texts in Math-
ematics, Springer, New York, second edition, 2005.

[6] P. Delsarte, Bilinear forms over a finite field, with applications to coding theory, J. Combin. Theory
Ser. A 25(3) (1978) 226–241.

[7] P. Fitzpatrick, On the key equation, IEEE Trans. Inform. Theory 41(5) (1995) 1290–1302.
[8] G. D. Forney, Jr., Minimal bases of rational vector spaces, with applications to multivariable linear

systems, SIAM J. Control 13(3) (1975) 493–520.
[9] E. M. Gabidulin, Theory of codes with maximum rank distance, Problemy Peredachi Informatsii,

21(1) (1985) 3–16.
[10] E. M. Gabidulin, A fast matrix decoding algorithm for rank–error–correcting codes, In Algebraic

coding (Paris, 1991), Lecture Notes in Computer Science, 573 (1992) 126–133.
[11] A. Kandri–Rody, V. Weispfenning, Noncommutative Gröbner bases in algebras of solvable type, J.

Symbolic Comput. 9(1) (1990) 1–26.
[12] R. Koetter, F. R. Kschischang, Coding for errors and erasures in random network coding, IEEE

Trans. Inform. Theory 54(8) (2008) 3579–3591.
[13] M. Kuijper, K. Schindelar, Minimal Gröbner bases and the predictable leading monomial property,

Linear Algebra Appl. 434(1) (2011) 104–116.
[14] M. Kuijper, A.–L. Trautmann, Iterative list–decoding of Gabidulin codes via Gröbner based inter-

polation, In IEEE Information Theory Workshop (ITW 2014), Hobart, TAS, 2014, 581–585.
[15] R. Lidl, H. Niederreiter, Finite Fields, Cambridge University Press, Second edition, Cambridge,

London, 1997.
[16] P. Loidreau, A Welch–Berlekamp like algorithm for decoding Gabidulin codes, In Coding and cryp-

tography, Lecture Notes in Computer Science 3969 (2006) 36–45.
[17] O. Ore, On a special class of polynomials, Trans. Amer. Math. Soc. 35(3) (1933) 559–584.
[18] N. Raviv, A. Wachter–Zeh, Some Gabidulin codes cannot be list decoded efficiently at any radius,

IEEE Trans. Inform. Theory 62(4) (2016) 1605–1615.
[19] G. Richter, S. Plass, Fast decoding of rank–codes with rank errors and column erasures, IEEE

International Symposium on Information Theory (ISIT) proceedings (2004) 398–398.
[20] N. Silberstein, A. S. Rawat, S. Vishwanath, Error resilience in distributed storage via rank–metric

codes, In Fiftieth Annual Allerton conference, UIUC, Illinois, USA, (2012) 1150–1157.
[21] D. Silva, F. R. Kschischang, Fast encoding and decoding of Gabidulin codes, IEEE International

Symposium on Information Theory (ISIT) proceedings (2009) 2858–2862.
[22] D. Silva, F. R. Kschischang, On metrics for error correction in network coding, IEEE Trans. Inform.

Theory 55(12) (2009) 5479–5490.
[23] D. Silva, F. R. Kschischang, R. Koetter, A rank–metric approach to error control in random network

coding, IEEE Trans. Inform. Theory 54(9) (2008) 3951 –3967.
[24] A. Wachter–Zeh, Bounds on list decoding of rank–metric codes, IEEE Trans. Inform. Theory 59(11)

(2013) 7268–7277.
[25] A. Wachter–Zeh, V. Afanassiev, V. Sidorenko, Fast decoding of Gabidulin codes, Des. Codes Cryp-

togr. 66(1–3) (2013) 57–73.
[26] Y. Wu, New list decoding algorithms for Reed–Solomon and BCH codes, IEEE Trans. Inform. Theory

54(8) (2008) 3611–3630.
[27] H. Xie, Z. Yan, B. W. Suter, General linearized polynomial interpolation and its applications, Inter-

national Symposium on Network Coding (NetCod) proceedings (2011) 1–4.

43

http://orcid.org/0000-0003-2685-2343
http://orcid.org/0000-0001-9223-9550
https://hal.inria.fr/file/index/docid/72168/filename/RR-4420.pdf
https://hal.inria.fr/file/index/docid/72168/filename/RR-4420.pdf
http://dx.doi.org/10.1090/gsm/003
http://dx.doi.org/10.1090/gsm/003
https://doi.org/10.1109/TIT.2011.2165803
https://doi.org/10.1109/TIT.2011.2165803
https://doi.org/10.1016/j.jsc.2005.10.002
https://doi.org/10.1016/j.jsc.2005.10.002
https://doi.org/10.1007/b138611
https://doi.org/10.1007/b138611
https://doi.org/10.1016/0097-3165(78)90015-8
https://doi.org/10.1016/0097-3165(78)90015-8
https://doi.org/10.1109/18.412677
https://doi.org/10.1137/0313029
https://doi.org/10.1137/0313029
http://www.ams.org/mathscinet-getitem?mr=791529
http://www.ams.org/mathscinet-getitem?mr=791529
https://doi.org/10.1007/BFb0034349
https://doi.org/10.1007/BFb0034349
https://doi.org/10.1016/S0747-7171(08)80003-X
https://doi.org/10.1016/S0747-7171(08)80003-X
https://doi.org/10.1109/TIT.2008.926449
https://doi.org/10.1109/TIT.2008.926449
https://doi.org/10.1016/j.laa.2010.08.030
https://doi.org/10.1016/j.laa.2010.08.030
https://doi.org/10.1109/ITW.2014.6970898
https://doi.org/10.1109/ITW.2014.6970898
https://doi.org/10.1007/11779360_4
https://doi.org/10.1007/11779360_4
https://doi.org/10.1090/S0002-9947-1933-1501703-0
https://doi.org/10.1109/TIT.2016.2532343
https://doi.org/10.1109/TIT.2016.2532343
https://doi.org/10.1109/ISIT.2004.1365435
https://doi.org/10.1109/ISIT.2004.1365435
https://doi.org/10.1109/Allerton.2012.6483348
https://doi.org/10.1109/Allerton.2012.6483348
https://doi.org/10.1109/ISIT.2009.5205272
https://doi.org/10.1109/ISIT.2009.5205272
https://doi.org/10.1109/TIT.2009.2032817
https://doi.org/10.1109/TIT.2009.2032817
https://doi.org/10.1109/TIT.2008.928291
https://doi.org/10.1109/TIT.2008.928291
https://doi.org/10.1109/TIT.2013.2274653
https://doi.org/10.1109/TIT.2013.2274653
https://doi.org/10.1007/s10623-012-9659-5
https://doi.org/10.1007/s10623-012-9659-5
https://doi.org/10.1109/TIT.2008.926355
https://doi.org/10.1109/TIT.2008.926355
https://doi.org/10.1109/ISNETCOD.2011.5978942
https://doi.org/10.1109/ISNETCOD.2011.5978942

	Introduction
	Preliminaries
	Iterative decoding of Gabidulin codes
	Conclusions
	References