Random Construction of Partial MDS Codes

arXiv:1801.05848v1 [cs.IT] 17 Jan 2018

Alessandro Neri and Anna-Lena Horlemann-Trautmann
Abstract
This work deals with partial MDS (PMDS) codes, a special class of
locally repairable codes, used for distributed storage system. We first
show that a known construction of these codes, using Gabidulin codes,
can be extended to use any maximum rank distance code. Then we define a standard form for the generator matrices of PMDS codes and use
this form to give an algebraic description of PMDS generator matrices.
This implies that over a sufficiently large finite field a randomly chosen
generator matrix in PMDS standard form generates a PMDS code with
high probability. This also provides sufficient conditions on the field size
for the existence of PMDS codes.

1

Introduction

In a distributed storage system a file x ∈ Fkq (where Fq denotes the finite field
of cardinality q), is encoded and stored as some codeword c ∈ Fnq , over several
storage nodes. Each of these nodes is assumed, for simplicity, to store exactly
one coordinate of c. In case some of the nodes fail, we want to be able to recover
the lost information using as little effort as possible. The locality of a code plays
an important role in this context, and it denotes the number of nodes one has to
contact for repairing a lost node. We call the set of nodes one has to contact if a
given node fails, the locality group of that node. For this work we assume that
the locality groups are distinct. Partial MDS codes are maximally recoverable
codes in this setting, i.e., any erasure pattern that is information theoretically
correctable is correctable with such a code.
It is known that maximally recoverable codes in general, and PMDS codes in
particular, exist for any locality configuration if the field size is large enough [1].
Furthermore, some constructions of PMDS codes are known, e.g. [2–6].
In this paper we describe a random construction of PMDS codes, by prescribing a generator matrix of the respective code in a specific form, which we
will call PMDS standard form. If we fill the non-prescribed coordinates of this
generator matrix with random values, by high probability, the resulting code is
PMDS, if the underlying field size is large enough. We derive a lower bound on
this probability (depending on the field size). This gives rise to a lower bound on
the necessary field size for PMDS codes to exist. With some final adjustments
on the random construction we get a lower bound that improves the one of [1].

1

2

Preliminaries

2.1

PMDS codes

Consider a distributed storage system with m disjoint locality groups, where the
i-th group is of size ni (i = 1, . . . , m) and can correct any ri erasures. First we
set the locality for the code to be ℓ ∈ N. We can divide the coordinates of the
code into blocks of length n1 , . . . , nm , where ni = ℓ + ri , such that each block
represents a locality group.
We denote an MDS code of length n and dimension k by [n, k]-MDS code.
We use the definition of PMDS codes given in [7], which generalizes the definition
of [2].
Pm
Definition 1. Let ℓ, m, r1 , . . . , rm ∈ N. Define n :=
i=1 (ri + ℓ) and let
C ⊆ Fnq be a linear code of dimension k < n with generator matrix
G = (B1 | · · · | Bm ) ∈ Fqk×n

(1)

k×(r +ℓ)

such that Bi ∈ Fq i . Then C is a [n, k, ℓ; r1 , . . . , rm ]-partial-MDS (PMDS)
code (with locality ℓ) if
• for i ∈ {1, . . . , m} the row space of Bi is a [ri + ℓ, ℓ]-MDS code, and
• for any ri erasures in the i-th block (i = 1, . . . , m), the remaining code
(after puncturing the coordinates of the erasures) is a [mℓ, k]-MDS code.
The erasure correction capability of PMDS codes is as follows:
Lemma 2. [7, Lemma 3] A [n, k, ℓ; r1 , . . . , rm ]-PMDS code can correct any ri
erasures in the i-th block (simultaneously) plus s := mℓ − k additional erasures
anywhere in the code.
We can see that the definition of PMDS codes given makes sense only for
k ≥ ℓ. In case of equality, or in the case that m = 1 there exist only trivial
PMDS codes, i.e. the only PMDS codes are MDS codes.
It was shown in [7] that a code is a [n, k, ℓ; r1 , . . . , rm ]-PMDS code if and only
if it is maximally recoverable (for the respective locality group configuration).
The same results had previously been shown in [6, Lemma 4] for the case r1 =
r2 = · · · = rm .
Now we give a summary on known results about PMDS codes.
Proposition 3. [1] Maximally recoverable (MR) codes of length n and dimen
sion k exist for any locality configuration over any finite field of size q > n−1
k−1 .

MR codes are PMDS codes for disjoint locality blocks. Therefore, Proposition 3 implies that PMDS codes exist for any set of parameters when the field
size is large enough.
A construction of PMDS codes based on rank-metric and MDS codes was
given in [8], when r1 = r2 = · · · = rm . This gives the following existence result:
Proposition 4. [8] [n, k, ℓ; r, . . . , r]-PMDS codes with m locality blocks of the
same length exist over a finite field of size q n−mr .

2

Furthermore, some specific constructions of PMDS codes, for particular values of s or of the ri , are given in [2–4, 6].
In particular, a general construction for PMDS codes with s = 1 was given
in [7]. This construction is based on the concatenation of several MDS codes as
building blocks.
Proposition 5. [7, Corollary 14]
1. For any integers m ≥ 2 and ℓ, r1 , . . . , rm ≥ 1 there exists a [n, k = mℓ −
1, ℓ; r1 , . . . , rm ]-PMDS code over any field Fq with q ≥ maxi {ri } + ℓ.
2. If there exists h ∈ N such that ℓ ∈ {3, 2h − 1} and maxi {ri } + ℓ = 2h + 1,
then there exists a [n, k = mℓ − 1, ℓ; r1 , . . . , rm ]-PMDS code over Fq with
q = 2h = maxi {ri } + ℓ − 1.
In [7] the authors also show that this construction is basically the only one
possible, i.e., every PMDS with s = 1 is of this form, giving thus a characterization for this set of parameters. However, for s ≥ 2 there is no characterization
yet for PMDS codes.

2.2

Zarisky topology over finite fields

Let F be a field, and F[x1 , . . . , xN ] be the polynomial ring over F. Denote by F̄
the algebraic closure of F. For a subset S ⊆ F[x1 , . . . , xN ] we define the algebraic
set
V (S) := {α ∈ F̄rq | f (α) = 0, ∀f ∈ S}.
The Zariski topology on F̄N is defined as the topology whose closed sets
are the algebraic sets, while the complements of the Zariski-closed sets are the
Zariski-open sets [9, Ch. I, Sec. 1].
Definition 6. A subset A ⊂ F̄N is called a generic set if A contains a non-empty
Zariski-open set.
In classical geometry one studies the Zariski topology over the complex numbers. In this framework, a generic set inside CN is dense and its complement is
contained in an algebraic set of dimension at most N − 1.
If one wants to consider generic sets restricted to a finite field Fq , the situation is slightly different. Here, for a subset T ⊆ FN
q one can always find a set
of polynomials S ⊆ Fq [x1 , . . . , xN ] such that
T = {α ∈ FN
q | f (α) = 0, ∀f ∈ S}.
and therefore the Zariski topology restricted to FN
q is the discrete topology. This
means that it is not useful to extend the notion of generic sets to finite fields
since it would not give any information.
However, given a set of polynomials S ⊆ Fq [x1 , . . . , xN ], we can define the
set of Fq -rational points as
V (S; Fq ) := {α ∈ FN
q | f (α) = 0, ∀f ∈ S}.
In this setting the Schwartz-Zippel Lemma implies an analog result to the one
of generic sets, as explained in the following.

3

Lemma 7 (Schwartz-Zippel). [10, Lemma 1.1] Let f ∈ Fq [x1 , . . . , xN ] be a
non-zero polynomial of total degree d ≥ 0. Let T ⊆ F̄ be a finite set and let
α1 , . . . , αN be selected at random independently and uniformly from T . Then

d
Pr f (α1 , . . . , αN ) = 0 ≤
.
|T |
As a consequence of this result we have that, in case the size of S and the
total degrees of the polynomials in S do not depend on the finite field, the
proportion between the cardinality of V (S; Fq ) and the cardinality of the whole
space FN
q goes to 0 as q grows. Vice versa, for growing q the probability that a
random point is in the complement of V (S; Fq ) tends to 1. This result will be
crucial in Section 5 for our random construction of PMDS codes.

2.3

Rank-metric codes

We now give some known facts about rank-metric codes. Recall that FqN is
n ∼
isomorphic to FN
q as an Fq - vector space. From this it easily follows that FqN =
×n
FN
. Then we can give the following definition.
q
×n
Definition 8. The rank distance dR on FN
is defined by
q

dR (U, V ) := rank(U − V ),

×n
U, V ∈ FN
.
q

Analogously, if u, v ∈ FnqN , then dR (u, v) is the rank of the difference of the
×n
respective matrix representations in FN
.
q
Observe that the definition of rank distance in the case of vectors in FnqN
does not depend on the choice of the basis. Moreover it can be shown that the
function dR : FnqN × FnqN → R≥0 is a metric.
Definition 9. An FqN -linear rank-metric code C of length n and dimension
k is a k-dimensional subspace of FnqN equipped with the rank distance. The
minimum distance of C is defined as
dR (C) := min {dR (u, v) | u, v ∈ C, u 6= v} .
Theorem 10 (Singleton-like Bound). [11, Theorem 1] Let C ⊆ FnqN be an
FqN -linear rank-metric code of dimension k. Then
dR (C) ≤ n − k + 1.
Definition 11. Codes attaining the Singleton-like bound are called Maximum
Rank Distance (MRD) Codes.
A necessary and sufficient condition for the existence of MRD codes is that
n ≤ N . In this framework, a characterization for FqN -linear MRD codes in
terms of their generator matrices was given in [12, Corollary 2.12], which in
turn is based on a result given in [13]. For this we define the set

Eq (k, n) := E ∈ Fqk×n | rank(E) = k .

Proposition 12 (MRD criterion). Let G ∈ Fqk×n
be a generator matrix of a
m
rank-metric code C ⊆ Fnqm . Then C is an MRD code if and only if
rank(GE T ) = k
for all E ∈ Eq (k, n).
4

3

General construction using rank metric codes

In this section we generalize the construction given in [8]. In that work the
authors use Gabidulin codes in order to build [n, k, ℓ, r, . . . , r]-PMDS codes. We
will show that this construction also works for different ri , and that Gabidulin
codes can be replaced by any linear MRD codes.
e ∈ Fk×mℓ
Fix n, k, ℓ, r1 , . . . , rm , and let G
be the generator matrix of a MRD
qN
code. For the existence of an MRD code we need N ≥ mℓ. Moreover, for every
i = 1, . . . , m, we consider a [ℓ + ri , ℓ]-MDS code over Fq with generator matrix
Mi , and define


M1
0 ...
0
 0 M2 . . .
0 


mℓ×n
M :=  .
.
(2)
..  ∈ Fq
..
 ..
.
. 
0

...

0

Mm

We can now formulate our PMDS construction.
e ∈ Fk×mℓ
Theorem 13. Let G
be the generator matrix of a MRD code and let
qN
e is a generator matrix for
M be the matrix defined in (2). Then the matrix GM
a [n, k, ℓ, r1 , . . . , rm ]-PMDS code over FqN .
e and let S ∈ Tk,ℓ (G) be the submatrix obtained by selecting
Proof. Let G := GM
columns h1 , . . . , hkj from the jth block for j = 1, . . . , m, where ki ≤ ℓ and
eM
f, where
k1 + . . . + km = k. S is equal to G


N1 0 . . .
0
 0 N2 . . .
0 

f=
M
 ..
..  ,
.
..
 .
. 
0 . . . 0 Nm
and Nj is the ℓ×kj submatrix of Mj obtained by the respective selected columns.
Since Mi generates an [ℓ + ri , ℓ]-MDS code, any ℓ columns of Mi are linearly
f) = k1 + . . . + km = k. By
independent. Thus, rank(Ni ) = ki and rank(M
e
f
Proposition 12 we have that det(GM ) 6= 0, and we conclude the proof using
Proposition 16.
Corollary 14. Let m ≥ 2 and ℓ, r1 , . . . , rm ≥ 1, k ≥ ℓ be positive integers.
Then, for every prime p and every positive integer L ≥ n0 mℓ there exists a
[n, k, ℓ, r1 , . . . , rm ]-PMDS code over FpL , where
n0 = min{j ∈ N | pj ≥ ℓ + ri − 1, for i = 1, . . . , m}.
Proof. A MRD code in Fmℓ
qN exists if N ≥ mℓ. Suitable MDS codes over Fq
for the matrix in (2) exist if q ≥ max{ℓ + ri − 1}. The statement follows from
Theorem 13 with q = pn0 and L = n0 N .

4

Algebraic description of PMDS codes

We will now define a standard form for generator matrices of PMDS codes. This
standard form is the main tool for the random construction of PMDS codes.
5

Theorem 15 (PMDS standard form). Let m ≥ 2 and s, ℓ, r1 , . . . , rm ≥ 1 and
let C be a [n, k = mℓ − s, ℓ; r1 , . . . , rm ]-PMDS code over a field Fq . Then C has
a generator matrix of the form
G = (B1 | · · · | Bm ) ,

(3)

where
• Bi = (Ci | Di ), Ci ∈ Fqk×ℓ and Di ∈ Fqk×ri for i = 1, . . . , m, and
• the submatrix GC = (C1 | · · · | Cm ) is of the form
GC = [Ik | A] ,
with A being superregular.
e be a generator matrix for C of the form (1), i.e.
Proof. Let G


e= B
e1 | · · · | B
em .
G

ei in the last ri columns, we get that the submatrix G
eC
Puncturing every block B
is the generator matrix of a [mℓ, k]-MDS code. Operating on the rows of such a
submatrix we can transform it to a matrix GC = [Ik | A], with A superregular.
e C = [Ik | A],
I.e., there exists an invertible matrix P ∈ GLk (Fq ) such that P G
e
and therefore the matrix G := P G is a generator matrix of C of the required
form.
We now consider the entries aw,z of A as variables xw,z for w = 1, . . . , k amd
z = 1, . . . , s. We know that the column space of Di is inside the column space of
Ci , by the parameters of the block MDS codes. This means that every column
(j)
in Di is a linear combination of the columns of Ci . If we denote by Di the jth
column of Di , then
ℓ
X
(t)
(j)
(4)
yt,i,j Ci
Di =
t=1

for some yt,i,j , which we also consider variable. This way we can consider a
k × n generator matrix as a matrix in Fq [xw,z , yt,i,j ]k×n (where Fq [xw,z , yt,i,j ]
denotes the polynomial
ring in all xw,z , yt,i,j ).
Pm
Let R = i=1 ri . We denote α := (αw,z )w,z ∈ Fsk
q and β := (βt,i,j )t,i,j ∈
FℓR
.
If
we
replace
the
variables
x
,
y
described
above
in a matrix in PMDS
w,z t,i,j
q
standard form by the values αw,z , βt,i,j , we denote the corresponding generator
matrix by
G(α, β).
Analogously we will denote the variable form by G(x, y).
However, a general matrix of this form is not necessarily a generator matrix
of a PMDS code for any values α, β. The following proposition shows what
needs to be fulfilled to generate a PMDS code:
Proposition 16. A matrix G ∈ Fqk×n generates a [n, k = mℓ − s, ℓ; r1 , . . . , rm ]PMDS code if and only if, every submatrix in the set


S is a submatrix of G with
Tk,ℓ (G) := S ∈ Fk×k |
at most ℓ columns per block Bi
has non-zero determinant.
6

Proof. This follows from the definition of PMDS, cf. also [7].
The above results give an algebraic description of the generator matrix of a
[n, k = mℓ − s, ℓ; r1 , . . . , rm ]-PMDS code over Fq , as follows. If we consider the
variable form of a generator matrix G as above, and the polynomial
p(x, y) := lcm{det S | S ∈ Tk,ℓ (G)} ∈ Fq [xw,z , yt,i,j ],

(5)

then, we have that G(α, β) generates a [n, k = mℓ − s, ℓ; r1 , . . . , rm ]-PMDS code
over Fq if and only if p(α, β) is non-zero.

5

Topological and probability results

In this section we first deal with the algebraic description of the generator matrix
of a PMDS code in the algebraic closure of the finite field where we want our code
to be built. After that, we analyze the probability that a code whose generator
matrix is of the form G(α, β) is PMDS. Moreover, we also study the
Pmexistence of
PMDS codes for given parameters n, k, ℓ, s, r1 , . . . , rm and R = i=1 ri , giving
sufficient conditions on the field size. Although for s = 1 this problem was
completely solved in [7], for s ≥ 2 this is still an open problem.
We denote the set of valid entries for PMDS generator matrices over the
algebraic closure of the finite field Fq by
n
o
ℓR
APMDS := (α, β) ∈ F̄sk
q × F̄q | rowspace(G(α, β)) is PMDS ,

Then the following result holds.
Theorem 17. APMDS is a generic set.
Proof. By Proposition 16 we have that

ℓR
APMDS := (α, β) ∈ F̄sk
q × F̄q | p(α, β) 6= 0 ,

and therefore APMDS is a Zariski open set.
Concerning the non-emptiness, let q = pt0 . From Corollary 14 there exists
a [n, k, ℓ, r1 , . . . , rm ]-PMDS code C over FpL , for some L multiple of t0 . By
Theorem 15, C has a generator matrix of the form G(α, β), therefore (α, β) ∈
APMDS .
This means that over the algebraic closure, by probability 1, for randomly
chosen α, β the matrix G(α, β) generates a PMDS code. For underlying finite
fields, this implies that for growing field size this probability will tend to 1. We
now derive a probability formula depending on the field size.
We can easily observe that the entries of G(x, y) are polynomials of total
degree 0, 1 or 2. In particular, if t := ⌈ sℓ ⌉ and we write G(x, y) as in (3), then the
entries of the blocks Di are polynomials of degree at most 1 for i = 1, . . . , m − t,
and of degree at most 2 for the last t blocks.
To estimate the degree of p(x, y) we need the following lemma.
Lemma 18 (Derivation of Vandermonde’s identity).
 



r
X
m
n
m+n−1
(r − j)
=n
.
j
r−j
r−1
j=0
7

Lemma 19. The total degree of the polynomial p(x, y), defined as in (5), satisfies the inequality


n−1
deg p(x, y) ≤ 2(n − k)
.
k−1
Proof. It holds that
Tk,ℓ (G) ⊂ Mk (G) := {S ∈ Fqk×k | S is a submatrix of G},
hence the polynomial p(x, y) divides the polynomial
q(x, y) := lcm{det S | S ∈ Mk (G)}.
Observe that the entries of the first k columns of the submatrix GC have degree
0. Let t := ⌈ sℓ ⌉. Then the entries of the columns corresponding to the blocks Di
for i = 1, . . . , m − t have degree at most 1, as well as the last mℓ − k columns of
GC . Finally, the columns of the blocks Di for i = m − t + 1, . . . , m, have degree
at most 2. In particular, all the entries of the blocks Di and the last mℓ − k
columns of GC have degree at most 2. Therefore,
X
deg det S
deg q(x, y) ≤
S∈Mk (G)

 

k
n−k
2(k − j0 )
≤
j0
k − j0
j0 =0


n−1
= 2(n − k)
k−1
k
X

where the last equality follows from Lemma 18. Since deg p(x, y) ≤ deg q(x, y)
we conclude the proof.
We can now formulate a lower bound for the probability that a randomly
chosen generator matrix in PMDS standard form generates a PMDS code over
a finite field Fq :
Theorem 20. Let the entries of α and β be uniformly and independently chosen
at random in Fq . Then

2(n − k) n−1
k−1
Pr{rowspace(G(α, β)) is PMDS } ≥ 1 −
.
q
Proof. We have
Pr{rowspace(G(α, β)) is PMDS }
=Pr{(α, β) ∈
/ V (p(x, y); Fq )}
=1 − Pr{p(α, β) = 0}
2(n − k)
deg p(x, y)
≥1 −
≥1−
q
q



n−1
k−1

,

where the last two inequalities follow from Lemmas 7 and 19, respectively.

8

From this we can deduce an existence result for PMDS codes over finite fields
of a given minimal size.

Corollary 21. If q > 2(n−k) n−1
k−1 then there exists a [n, k, ℓ, r1 , . . . , rm ]-PMDS
code over the finite field Fq .
One notices that this is not an improvement over the known existence result
from Proposition 3.
However, we can improve the above result, considering a step-by-step construction. We will again consider a generator matrix in PMDS standard form
as in (3). We start with an [mℓ, k]-MDS code over a finite field Fq and write
its generator matrix as (C1 | · · · | Cm ). For this purpose it is sufficient that
(1)
q ≥ mℓ − 1. Then we construct the first column D1 of the block D1 as in (4).
Every entry will be a degree 1 polynomial in the variables yt,1,1 for t = 1, . . . , ℓ.
Imposing that every k × k minor of


(1)
G′ := C1 | D1 | C2 | . . . | Cm
is non-zero, we get the condition p′ (yt,1,1 ) 6= 0, where
p′ (yt,1,1 ) = lcm{det S | S ∈ Tk,ℓ (G′ )}.
Using Lemma 7, we obtain
deg p′
.
q


mℓ
mℓ
In this situation deg p′ ≤ k−1
, therefore for q > k−1
we have that there exists
at least one evaluation of p′ that is non-zero and such that G′ (βt,1,1 ) generates
a [n, k, ℓ, 1, 0, . . . , 0]-PMDS code.
Repeating this construction step by step, we get a [n, k, ℓ, r1 , . . . , rm−1 , rm −
(r )
1]-PMDS code. From that code we build the last column Dmm of the block
Dm again as in (4):
ℓ
X
(t)
(rm )
.
Dm =
yt,m,rm Cm
Pr{p′ (βt,1,1 ) = 0} ≤

t=1

In the end we get the matrix
G(yt,m,rm ) = (C1 | D1 | . . . | Cm | Dm ),

(6)

where the matrix G(yt,m,rm ) without the last column generates a [n, k, ℓ, r1 , . . . , rm−1 , rm −
1]-PMDS code, and the entries of the last column are polynomials of total degree
at most 1 in the variables yt,m,rm , for t = 1, . . . , ℓ.
Definition
22. Let m, n, k, n1 , . . . , n
m , f1 , . . . , fm be positive integers such that
P
P
i
n =
n
.
Let
N
:=
0,
N
:=
0
i
j=1 nj and Ji = {Ni−1 + 1, . . . , Ni } for
i i
i = 1, . . . , m − 1. We define the set
M(k; n1 . . . , nm ; f1 , . . . , fm ) = {I ⊂ {1, . . . , n} | |I| = k, |I ∩ Ji | ≤ fi }
and M (k; n1 . . . , nm ; f1 , . . . , fm ) as its cardinality.

9

Proposition 23. Let G(yt,m,rm ) be as in (6). The total degree of the polynomial
p̃(yt,m,rm ) := lcm{det S | S ∈ Tk,ℓ (G(yt,m,rm ))}
is less or equal to
M (k − 1; ℓ + r1 . . . , ℓ + rm−1 , ℓ + rm − 1; ℓ, . . . , ℓ, ℓ − 1) =: M ∗ .
P
deg det S. By
Proof. The polynomial p̃(yt,m,rm ) has degree less or equal to
assumption all the determinants det S for S not containing the last column are
non zero elements in Fq . The only polynomials with degree 1 are the determinants of k × k submatrices involving the last column, and they are exactly M ∗
many.
Corollary 24. If q > M ∗ then there exists a [n, k, ℓ, r1 , . . . , rm ]-PMDS code
over the finite field Fq .
To our knowledge there is no closed formula for M ∗ . However, it is easy to
see that M ∗ ≤ n−1
k−1 and that the inequality is strict if any of the conditions
|I ∩ Ji | ≤ fi is non-empty. Hence, Corollary 24 improves upon Proposition 3.

6

Conclusion

We gave a generalization of a known PMDS code construction based on rankmetric codes. Furthermore, we investigated a random construction of PMDS
codes by prescribing a PMDS standard form. We derived a lower bound on the
probability that a randomly filled matrix in PMDS standard form generates a
PMDS code. This probability implies a lower bound on the field size needed for
such codes to exist. In the end we gave a step-by-step construction of such a
generator matrix to improve this lower bound on the necessary field size.

References
[1] M. Chen, C. Huang, and J. Li, “On the maximally recoverable property for
multi-protection group codes,” in 2007 IEEE International Symposium on
Information Theory, June 2007, pp. 486–490.
[2] M. Blaum, J. L. Hafner, and S. Hetzler, “Partial-MDS codes and their application to RAID type of architectures,” IEEE Transactions on Information
Theory, vol. 59, no. 7, pp. 4510–4519, July 2013.
[3] M. Blaum, J. S. Plank, M. Schwartz, and E. Yaakobi, “Partial MDS
(PMDS) and sector-disk (SD) codes that tolerate the erasure of two random
sectors,” in 2014 IEEE International Symposium on Information Theory,
June 2014, pp. 1792–1796.
[4] ——, “Construction of partial MDS and sector-disk codes with two global
parity symbols,” IEEE Transactions on Information Theory, vol. 62, no. 5,
pp. 2673–2681, May 2016.
[5] J. Chen, K. W. Shum, Q. Yu, and C. W. Sung, “Sector-disk codes and
partial MDS codes with up to three global parities,” in 2015 IEEE International Symposium on Information Theory (ISIT), June 2015, pp. 1876–
1880.
10

[6] P. Gopalan, C. Huang, B. Jenkins, and S. Yekhanin, “Explicit maximally
recoverable codes with locality,” IEEE Transactions on Information Theory, vol. 60, no. 9, pp. 5245–5256, September 2014.
[7] A.-L. Horlemann-Trautmann and A. Neri, “A complete classification of
partial-MDS (maximally recoverable) codes with one global parity,” arXiv
preprint arXiv:1707.00847, 2017.
[8] G. Calis and O. O. Koyluoglu, “A general construction for PMDS codes,”
IEEE Communications Letters, vol. 21, no. 3, pp. 452–455, March 2017.
[9] R. Hartshorne, Algebraic geometry.
2013, vol. 52.

Springer Science & Business Media,

[10] D. Lewin and S. Vadhan, “Checking polynomial identities over any field:
Towards a derandomization?” in Proceedings of the thirtieth annual ACM
symposium on Theory of computing. ACM, 1998, pp. 438–447.
[11] R. Roth, “Maximum-rank array codes and their application to crisscross
error correction,” IEEE Transactions on Information Theory, vol. 37, no. 2,
pp. 328 –336, mar 1991.
[12] A.-L. Horlemann-Trautmann and K. Marshall, “New criteria for MRD and
Gabidulin codes and some rank-metric code constructions,” Adv. in Math.
of Comm., vol. 11, no. 3, pp. 533–548, 2017.
[13] E. M. Gabidulin, “Theory of codes with maximum rank distance,” Problemy
Peredachi Informatsii, vol. 21, no. 1, pp. 3–16, 1985.

11

