IEEE TRANSACTIONS ON COMMUNICATIONS

1

A Unified Form of EVENODD and RDP
Codes and Their Efficient Decoding
Hanxu Hou, Member, IEEE, Yunghsiang S. Han, Fellow, IEEE, Kenneth W.
Shum, Senior Member, IEEE and Hui Li Member, IEEE,

arXiv:1803.03508v1 [] 9 Mar 2018

Abstract
Array codes have been widely employed in storage systems, such as Redundant Arrays of Inexpensive Disks (RAID). The row-diagonal parity (RDP) codes and EVENODD codes are two popular doubleparity array codes. As the capacity of hard disks increases, better fault tolerance by using array codes
with three or more parity disks is needed. Although many extensions of RDP codes and EVENODD
codes have been proposed, the high decoding complexity is the main drawback of them. In this paper, we
present a new construction for all families of EVENODD codes and RDP codes, and propose a unified
form of them. Under this unified form, RDP codes can be treated as shortened codes of EVENODD
codes. Moreover, an efficient decoding algorithm based on an LU factorization of Vandermonde matrix
is proposed when the number of continuous surviving parity columns is no less than the number of
erased information columns. The new decoding algorithm is faster than the existing algorithms when
more than three information columns fail. The proposed efficient decoding algorithm is also applicable
to other Vandermonde array codes. Thus the proposed MDS array code is practically very meaningful
for storage systems that need higher reliability.

Index Terms
RAID, array codes, EVENODD, RDP, efficient decoding, LU factorization.

I. I NTRODUCTION
Array codes have been widely employed in storage systems, such as Redundant Arrays of
Inexpensive Disks (RAID) [1], [2], for the purpose of enhancing data reliability. In the current
Hanxu Hou is with the School of Electrical Engineering & Intelligentization, Dongguan University of Technology and with
the Shenzhen Key Lab of Information Theory & Future Internet Architecture, Peking University Shenzhen Graduate School (Email: houhanxu@163.com). Yunghsiang S. Han is with the School of Electrical Engineering & Intelligentization, Dongguan
University of Technology (E-mail: yunghsiangh@gmail.com). Kenneth W. Shum is with the Institute of Network Coding, The
Chinese University of Hong Kong (E-mail: wkshum@inc.cuhk.edu.hk). Hui Li is with the Shenzhen Key Lab of Information
Theory & Future Internet Architecture, Future Network PKU Lab of National Major Research Infrastructure, Peking University
Shenzhen Graduate School(E-mail: lih64@pkusz.edu.cn).

March 12, 2018

DRAFT

2

IEEE TRANSACTIONS ON COMMUNICATIONS

RAID-6 system, two disks are dedicated to the storage of parity-check bits, so that any two disk
failures can be tolerated. There are a lot of existing works on the design of array codes which
can recover any two disks failures, such as the EVENODD codes [3] and the row-diagonal parity
(RDP) codes [4].
As the capacities of hard disks are increasing in a much faster pace than the decreasing of
bit error rates, the protection offered by double parities will soon be inadequate [5]. The issue
of reliability is more pronounced in solid-state drives, which have significant wear-out rates
when the frequencies of disk writes are high. In order to tolerate three or more disk failures,
the EVENODD codes were extended in [6], and the RDP codes were extended in [7], [8]. All
of the above coding methods are binary array codes, whose codewords are m × n arrays with
each entry belonging to the binary field F2 , for some positive integers m and n. Binary array
codes enjoy the advantage that encoding and decoding can be done by Exclusive OR (XOR)
operations. The n disks are identified as n columns, and the m bits in each column are stored in
the corresponding disk. A binary array code is said to be systematic if, for some positive integer
r less than n, the right-most r columns store the parity bits, while the left-most k = n − r
columns store the uncoded data bits. If the array code can tolerate arbitrary r erasures, then it
is called a maximum-distance separable (MDS) array code. In other words, in an MDS array
code, the information bits can be recovered from any k columns.
A. Related Works
There are many follow-up studies on EVENODD codes [3] and RDP codes [4] along different
directions, such as the extensions of fault tolerance [6], [7], [9], the improvement of repair
problem [10], [11], [12], [13] and efficient decoding methods [14], [15], [16], [17] of their
extensions.
Huang and Xu [14] extended the EVENODD codes to be STAR codes with three parity
columns. The EVENODD codes were extended by Blaum, Bruck and Vardy [6], [9] for three
or more parity columns, with the additional assumption that the multiplicative order of 2 mod
p is equal to p − 1. A sufficient condition for the extended EVENODD codes to be MDS with
more than eight parity columns is given in [18]. Goel and Corbett [7] proposed the RTP codes
that extend the RDP codes to tolerate three disk failures. Blaum [8] generalized the RDP codes
that can correct more than three column erasures and showed that the extended EVENODD
codes and generalized RDP codes share the same MDS property condition. Blaum and Roth

DRAFT

March 12, 2018

SUBMITTED PAPER

3

[19] proposed Blaum-Roth codes, which are non-systematic MDS array codes constructed over
a Vandermonde matrix. Some efficient systematic encoding methods for Blaum-Roth codes are
given in [19], [20], [21]. We call the existing MDS array codes in [3], [4], [6], [7], [8], [9],
[14], [15], [16], [17], [19] as Vandermonde MDS array codes, as their constructions are based
on Vandermonde matrices.
Decoding complexity in this work is defined as the number of XORs required to recover
the erased no more than r columns (including information erasure and parity erasure) from
surviving k columns. There are many decoding methods for extended EVENODD codes [15]
and generalized RDP codes; however, most of them focus on r = 3. Jiang et al. [15] proposed
a decoding algorithm for extended EVENODD codes with r = 3. To further reduce decoding
complexity of the extended EVENODD codes with r = 3, Huang and Xu [14] invented STAR
codes. One extension of RDP codes with three parity columns is RTP codes, whose decoding has
been improved by Huang et al. [17]. Two efficient interpolation-based encoding algorithms for
Blaum-Roth codes were proposed in [20], [21]. However, the efficient algorithms in [20], [21]
are not applicable to the decoding of the extended EVENODD codes and generalized RDP codes.
An efficient erasure decoding method that solves Vandermonde linear system over a polynomial
ring was given in [19] for Blaum-Roth codes, and the decoding method is also applicable to
the erasure decoding of extended EVENODD codes if the number of information erasures is no
larger than the number of continuous surviving parity columns. There is no efficient decoding
method for arbitrary erasures and one needs to employ the traditional decoding method such as
Cramer’s rule to recover the erased columns.
B. Contributions
In this paper, we present a unified form of EVENODD codes and RDP codes that include
the existing RDP codes and their extensions in [4], [8], along with the existing EVENODD
codes and their extensions in [3], [6], [9]. Under this unified form, these two families of codes
are shown having a close relationship between each other. Based on this unified form, we also
propose a fast method for the recovery of failed columns. This method is based on a factorization
of Vandermonde matrix into very sparse lower and upper triangular matrices. Similar to the
decoding method in [19], the proposed fast decoding method can recover up to r erasures such
that the number of information erasure is no larger than the number of continuous surviving
parity columns. We then illustrate the methodology by applying it to EVENODD codes and

March 12, 2018

DRAFT

4

IEEE TRANSACTIONS ON COMMUNICATIONS

RDP codes. We compare the decoding complexity of the proposed method with those presented
in [19] for the extended EVENODD codes and generalized RDP codes. The proposed method
has lower decoding complexity than that of the decoding algorithm given in [19], and is also
applicable to other Vandermonde MDS array codes.
II. U NIFIED F ORM OF EVENODD C ODES AND RDP C ODES
In this section, we first present EVENODD codes and RDP codes. Then, we give a unified
form of them and illustrate that RDP codes are shortened EVENODD codes under this form.
The array codes considered in this paper contain p − 1 rows and k + r columns, where p is
an odd number. In the following, we let k and r be positive integers which are both no larger
than p. Let g(`) = (g(0), g(1), . . . , g(` − 1)) be an `-tuple consisting of ` distinct integers that
range from 0 to p − 1, where ` ≤ p. The i-th entry of column j are denoted as ai,j and bi,j for
EVENODD codes and RDP codes respectively. The subscripts are taken modulo p throughout
the paper, if it is not specified.
A. EVENODD Codes
For an odd p ≥ {k, r}, we define the EVENODD code as follows. It is a (p − 1) × (k + r)
array code, with the first k columns storing the information bits, and the last r columns storing
the parity bits. For j = 0, 1, . . . , k − 1, column j is called information column that stores the
information bits a0,j , a1,j , . . . , ap−2,j , and for j = k, k + 1, . . . , k + r − 1, column j is called
parity column that stores the parity bits a0,j , a1,j , . . . , ap−2,j .
Given the (p − 1) × k information array [ai,j ] for i = 0, 1, . . . , p − 2 and j = 0, 1, . . . , k − 1,
we add an extra imaginary row ap−1,j = 0, for j = 0, 1, . . . , k − 1, to this information array. The
parity bits in column k are computed by
ai,k =

k−1
X

ai,j for 0 ≤ i ≤ p − 2,

(1)

j=0

and the parity bits stored in column k + `, ` = 1, 2, . . . , r − 1, are computed by
ai,k+` = ap−1,k+` +

k−1
X

ai−`g(j),j for 0 ≤ i ≤ p − 2,

(2)

j=0

where
ap−1,k+` =

k−1
X

ap−1−`g(j),j .

(3)

j=0

DRAFT

March 12, 2018

SUBMITTED PAPER

5

TABLE I: Encoding of EVENODD(5, 3, 3; (0, 1, 4)). Note that, by (3), a4,4 = a3,1 + a0,2 and
a4,5 = a2,1 + a1,2 .
a0,0

a0,1

a0,2

a0,3 = a0,0 + a0,1 + a0,2

a0,4 = a0,0 + a1,2 + a4.4

a0,5 = a0,0 + a3,1 + a2,2 + a4,5

a1,0

a1,1

a1,2

a1,3 = a1,0 + a1,1 + a1,2

a1,4 = a1,0 + a0,1 + a2,2 + a4,4

a1,5 = a1,0 + a3,2 + a4,5

a2,0

a2,1

a2,2

a2,3 = a2,0 + a2,1 + a2,2

a2,4 = a2,0 + a1,1 + a3,2 + a4.4

a2,5 = a2,0 + a0,1 + a4,5

a3,0

a3,1

a3,2

a3,3 = a3,0 + a3,1 + a3,2

a3,4 = a3,0 + a2,1 + a4.4

a3,5 = a3,0 + a1,1 + a0,2 + a4,5

We denote the EVENODD codes defined in the above equations as EVENODD(p, k, r; g(k)).
The default values in g(k) are (0, 1, . . . , k − 1), and we simply write EVENODD(p, k, r) if the
values in g(k) are default. An example of EVENODD(5, 3, 3; (0, 1, 4)) is given in Table I. Under
the above definition, the EVENODD code in [3] is EVENODD(p, p, 2) with g(k) = (0, 1, . . . , k−
1), and the extended EVENODD code in [6] is EVENODD(p, p, r) with g(k) = (0, 1, . . . , k −1).

B. RDP Codes
RDP code is an array code of size (p − 1) × (k + r). Given the parameters k, r, p that satisfy
p ≥ max(k + 1, r), we add an extra imaginary row bp−1,0 = bp−1,1 = · · · = bp−1,k−1 = 0 to
the (p − 1) × k information array [bi,j ], for i = 0, 1, . . . , p − 2 and j = 0, 1, . . . , k − 1, as in
EVENODD(p, k, r). The parity bits of the RDP(p, k, r; g(k + 1)) are computed as follows:
bi,k =

k−1
X

bi,j for 0 ≤ i ≤ p − 2,

(4)

j=0

bi,k+` =

k
X

bi−`g(j),j for 0 ≤ i ≤ p − 2, 1 ≤ ` ≤ r − 1.

(5)

j=0

Like EVENODD(p, k, r), the default value of g(k + 1) are (0, 1, . . . , k). The first 4 rows in
Table II are the array of RDP(5, 3, 3; (0, 1, 4, 3)). The RDP code in [4] is RDP(p, p − 1, 2) with
g(p) = (0, 1, . . . , p − 1) and RDP(p, p − 1, r) is the extended RDP in [8].

C. Unified Form
There is a close relationship between RDP(p, k, r; g(k + 1)) and EVENODD(p, k, r; g(k))
when both array codes have the same number of parity columns. The relationship can be seen
by augmenting the arrays as follows. For RDP codes, we define the corresponding augmented

March 12, 2018

DRAFT

6

IEEE TRANSACTIONS ON COMMUNICATIONS

TABLE II: The augmented array of RDP(5, 3, 3; (0, 1, 4, 3)).
b0,0

b0,1

b0,2

b0,3 = b0,0 + b0,1 + b0,2

b0,4 = b0,0 + b1,2 + b2,3

b0,5 = b0,0 + b3,1 + b2,2

b1,0

b1,1

b1,2

b1,3 = b1,0 + b1,1 + b1,2

b1,4 = b1,0 + b0,1 + b2,2 + b3,3

b1,5 = b1,0 + b3,2 + b0,3

b2,0

b2,1

b2,2

b2,3 = b2,0 + b2,1 + b2,2

b2,4 = b2,0 + b1,1 + b3,2

b2,5 = b2,0 + b0,1 + b1,3

b3,0

b3,1

b3,2

b3,3 = b3,0 + b3,1 + b3,2

b3,4 = b3,0 + b2,1 + b0,3

b3,5 = b3,0 + b1,1 + b0,2 + b2,3

0

0

0

0

b4,4 = b3,1 + b0,2 + b1,3

b4,5 = b2,1 + b1,2 + b3,3

array as a p × (k + r) array with the top p − 1 rows the same as in RDP(p, k, r), and the last
row defined by bp−1,j = 0 for 0 ≤ j ≤ k and
bp−1,k+` =

k
X

bp−1−`g(j),j for 1 ≤ ` ≤ r − 1.

(6)

j=0

Note that (6) is the extension of (5) when i = p − 1. The auxiliary row in the augmented array
is defined such that the column sums of columns k + 1, k + 2, . . . , k + r − 1 are equal to zero.
The above claim is proved as follows.
Lemma 1. For 1 ≤ ` ≤ r − 1, we have

Pp−1
i=0

bi,k+` = 0.

Proof. The summation of all bits in column k + ` of the augmented array is the summation of
all bits in columns 0 to k. Since the summation of all bits in column k is the summation of all
bits in columns 0 to k − 1, we have that the summation of all bits in column k + ` is equal to
0.
By the above lemma, we can compute bp−1,k+` for ` = 1, 2, . . . , r − 1 as
bp−1,k+` = b0,k+` + b1,k+` + · · · + bp−2,k+` .
An example of the augmented array code of RDP(5, 3, 3; (0, 1, 4, 3)) is given in Table II.
Similarly, for an EVENODD(p, k, r; g(k)), the augmented array is a p × (k + r) array [a0i,j ]
defined as follows. The first k + 1 columns are the same as those of EVENODD(p, k, r; g(k)),
i.e., for j = 0, 1, . . . , k and i = 0, 1, . . . , p − 1, a0i,j = ai,j . For ` = 1, 2, . . . , r − 1, we define the
parity bits in column k + ` as
a0i,k+` :=

k−1
X

ai−`g(j),j for 0 ≤ i ≤ p − 1.

(7)

j=0

DRAFT

March 12, 2018

SUBMITTED PAPER

7

We note that a0p−1,k+` is the same as ap−1,k+` defined in (3). According to (2), the parity bits in
column k + ` of EVENODD(p, k, r; g(k)) can be obtained from the augmented array by
ai,k+` = a0i,k+` + a0p−1,k+` .
Lemma 2. The bits in column k + ` for ` = 1, 2, . . . , r − 1 of the augmented array can be
obtained from EVENODD(p, k, r, g(k)) by
a0p−1,k+`

p−2
X
(ai,k + ai,k+` ), and
=

(8)

i=0

a0i,k+`

= ai,k+` +

a0p−1,k+`

for i = 0, 1, . . . , p − 2.

(9)

Proof. Note that
p−2
X

(ai,k + ai,k+` ) =

p−2 k−1
p−2
k−1
X
X
X
X
(
ai,j ) +
(ap−1,k+` +
ai−`g(j),j )

i=0

=

=

p−2
X

i=0 j=0

ai,0 + · · · +

ai,k−1 +

p−2
X

j=0

ai−`g(0),0 + · · · +

p−2
X

i=0

i=0

i=0

i=0

p−1

p−1

p−2

p−2

X

ai,0 + · · · +

i=0

=

p−2
X

i=0

X

ai,k−1 +

i=0

X

ai−`g(0),0 + · · · +

i=0
p−1

p−2

X

X

X

ai−`g(0),0 + · · · +

ai−`g(k−1),k−1 +

i=0

X

ai−`g(k−1),k−1 + (ap−1,k+` + · · · + ap−1,k+` )
|
{z
}
p−1

ai−`g(k−1),k−1

(11)

i=0

p−1

i=0

(10)

ai−`g(0),0 + · · · +

i=0

p−2
X

ai−`g(k−1),k−1

(12)

i=0

= (ap−1−`g(0),0 + ap−1−`g(1),1 + · · · + ap−1−`g(k−1),k−1 )
= a0p−1,k+` ,
where (10) comes from (1) and (2), (11) comes from that ap−1,j = 0 for j = 0, 1, . . . , k − 1, and
(12) comes from the fact that
{−`g(j), 1 − `g(j), . . . , p − 1 − `g(j)} = {0, 1, . . . , p − 1} mod p
for 1 ≤ ` ≤ r − 1, 0 ≤ g(j) ≤ p − 1. Therefore, we can obtain the bit a0p−1,k+` by (8) and the
other bits in parity column k + ` by (9).
The augmented array of EVENODD(5, 3, 3; (0, 1, 4)) is given in Table III.
The augmented array of RDP(p, k, r; g(k+1)) can be obtained from shortening the augmented
array of EVENODD(p, k + 1, r; g(k + 1)) and we summarize this fact in the following.

March 12, 2018

DRAFT

8

IEEE TRANSACTIONS ON COMMUNICATIONS

TABLE III: The augmented array of EVENODD(5, 3, 3; (0, 1, 4)).
a0,0

a0,1

a0,2

a0,3 = a0,0 + a0,1 + a0,2

a0,4 = a0,0 + a1,2

a0,5 = a0,0 + a3,1 + a2,2

a1,0

a1,1

a1,2

a1,3 = a1,0 + a1,1 + a1,2

a1,4 = a1,0 + a0,1 + a2,2

a1,5 = a1,0 + a3,2

a2,0

a2,1

a2,2

a2,3 = a2,0 + a2,1 + a2,2

a2,4 = a2,0 + a1,1 + a3,2

a2,5 = a2,0 + a0,1

a3,0

a3,1

a3,2

a3,3 = a3,0 + a3,1 + a3,2

a3,4 = a3,0 + a2,1

a3,5 = a3,0 + a1,1 + a0,2

0

0

0

0

a4.4 = a3,1 + a0,2

a4,5 = a2,1 + a1,2

Proposition 3. Let g(k+1) of RDP(p, k, r; g(k+1)) be the same as g(k+1) of EVENODD(p, k+
1, r; g(k + 1)). The augmented array of RDP(p, k, r; g(k + 1)) can be obtained from shortening
the augmented array of EVENODD(p, k + 1, r; g(k + 1)) as follows: (i) imposing the following
additional constraint on the information bits
a0i,k = a0i,0 + a0i,1 + · · · + a0i,k−1

(13)

for i = 0, 1, . . . , p − 1; (ii) removing column k + 1 of the augmented array of EVENODD(p, k +
1, r; g(k + 1)).
Proof. Consider the augmented array of EVENODD(p, k + 1, r; g(k + 1)) and assume that the
information bits of column k satisfy (13). By (1), the parity bits in column k + 1 are all zeros.
After deleting column k + 1 from the augmented array of EVENODD(p, k + 1, r; g(k + 1)) and
reindexing the columns after this deleted column by reducing all indices by one, we have a new
array with k + r columns of a shortened EVENODD(p, k, r; g(k)). Let the augmented array of
RDP(p, k, r; g(k + 1)) with the k information columns being the same as the first k information
columns of the augmented array of EVENODD(p, k + 1, r; g(k + 1)) such that these columns are
the same as those of the array of the shortened EVENODD(p, k, r; g(k)). Then column k of the
augmented array of RDP(p, k, r; g(k + 1)) is the same as column k of the array of the shortened
EVENODD(p, k, r; g(k)) according to (13) and (4). Recall that the bit bi,k+` in column k + `,
i = 0, 1, . . . , p − 1 and ` = 2, 3, . . . , r − 1, of the augmented array of RDP(p, k, r; g(k + 1)) is
computed by (5) (or (6)). Since a0i,j = ai,j = bi,j for i = 0, 1, . . . , p − 1 and j = 0, 1, . . . , k, bi,k+`
is the same as a0i,k+` in the array of the shortened EVENODD(p, k, r; g(k)) that is defined by
(7). Therefore, we can obtain the augmented RDP(p, k, r; g(k +1)) by shortening the augmented
EVENODD(p, k + 1, r; g(k + 1)) by imposing the condition (13) and removing column k + 1,
and this completes the proof.

DRAFT

March 12, 2018

SUBMITTED PAPER

9

By Proposition 3, the unified form of RDP(p, k, r; g(k + 1)) and EVENODD(p, k, r; g(k))
is the augmented array of EVENODD(p, k + 1, r; g(k + 1)). In the following, we focus on
EVENODD(p, k, r; g(k)), as the augmented array of RDP(p, k, r; g(k + 1)) can be viewed as
the shorten augmented array of EVENODD(p, k + 1, r; g(k + 1)).

III. A LGEBRAIC R EPRESENTATION
Let F2 [x] be the ring of polynomials over binary field F2 , and Rp be the quotient ring F2 [x]/(1+
xp ). An element in Rp can be represented by a polynomial of degree strictly less than p with
coefficients in F2 , we will refer to an element of Rp as a polynomial in the sequel. Note that
the multiplication of two polynomials in Rp is performed under modulo 1 + xp .
The ring Rp has been discussed in [22], [23] and has been used in designing regenerating
codes with low computational complexity. Let
Mp (x) := 1 + x + · · · + xp−1 .
Rp is isomorphic to a direct sum of two finite fields F2 [x]/(1+x) and F2 [x]/Mp (x)1 if and only if
2 is a primitive element in Fp [24]. In [25], F2 [x]/Mp (x) was used for performing computations
in F2p−1 , when p is a prime such that 2 is a primitive element in Fp . In addition, Blaum et al. [6],
[9] discussed the rings F2 [x]/Mp (x) in detail.
We will represent each column in a augmented array of EVENODD(p, k, r; g(k)) by a polynomial in Rp , so that a p × n array is identified with an n-tuple
(a00 (x), a01 (x), · · · , a0k+r−1 (x))

(14)

in Rpk+r , where n = k+r. Under this representation, the augmented array of EVENODD(p, k, r; g(k))
can be defined in terms of a Vandermonde matrix.
In the p × (k + r) array, the p bits a00,j , a01,j , . . . , a0p−1,j in column j can be represented as a
polynomial
a0j (x) = a00,j + a01,j x + · · · + a0p−1,j xp−1
for j = 0, 1, . . . , k+r−1. The first k polynomials a00 (x), a01 (x), . . . , a0k−1 (x) are called information
polynomials, and the last r polynomials a0k (x), a0k+1 (x), . . . , a0k+r−1 (x) are the parity polynomials.
1

When 2 is a primitive element in Fp , F2 [x]/Mp (x) is a finite field.

March 12, 2018

DRAFT

10

IEEE TRANSACTIONS ON COMMUNICATIONS

The parity bit of augmented array of EVENODD(p, k, r; g(k)) defined in (7) is equivalent to
the following equation over the ring Rp
i h
h
0
0
ak (x) · · · ak+r−1 (x) = a00 (x) · · ·

a0k−1 (x)

where Vk×r (g(k)) is the k × r Vandermonde matrix

1 xg(0) · · ·

1 xg(1) · · ·

Vk×r (g(k)) :=  .
..
..
 ..
.
.

1 xg(k−1) · · ·

i

· Vk×r (g(k)),

x(r−1)g(0)



x(r−1)g(1)
..
.








(15)

(16)

x(r−1)g(k−1)

and additions and multiplications in the above calculations are performed in Rp . (15) can be
verified as follows:
a0k+` (x)

=

p−1
X

a0i,k+` xi

=

i=0

k−1
X

aj (x)x

`g(j)

=

p−1
k−1 X
X

a

i0 ,j

x

j=0 i0 =0

j=0

i0 +`g(j)

=

p−1 k−1
X
X

0

ai0 ,j xi +`g(j) .

(17)

i0 =0 j=0

Let i0 = i − `g(j), we have
a0i,k+`

=

k−1
X

ai−`g(j),j ,

j=0

which is the same as (7). In other words, each parity column in the augmented array of
EVENODD codes is obtained by adding some cyclically shifted version of the information
columns.
Recall that a0j (x) is a polynomial over Rp for j = 0, 1, . . . , k + r − 1. When we reduce a
polynomial a0j (x) modulo Mp (x), it means that we replace the coefficient a0i,j with a0i,j + a0p−1,j
for i = 0, 1, . . . , p − 2. When j = 0, 1, . . . , k, we have that a0p−1,j = 0. If we reduce a0j (x)
modulo Mp (x), we obtain a0j (x) itself, of which the coefficients are the bits of column j of
EVENODD(p, k, r; g(k)), for j = 0, 1, . . . , k. Recall that the coefficients of a0k+` (x) for ` =
1, 2, . . . , r − 1 are computed by (7). If we reduce a0k+` (x) modulo Mp (x), i.e., replace the
coefficients a0i,k+` for i = 0, 1, . . . , p − 2 by a0i,k+` + a0p−1,k+` , which are ai,k+` that are bits in
column k + ` of EVENODD(p, k, r; g(k)). In fact, we have shown how to convert augmented
array of EVENODD(p, k, r; g(k)) into original array of EVENODD(p, k, r; g(k)).
By Proposition 3, we can obtain the augmented array of RDP(p, k, r; g(k +1)) by multiplying
(b0 (x), · · · , bk−1 (x),

k−1
X

h
i
bj (x)) Ik+1 V(k+1)×r (g(k + 1)) ,

j=0

DRAFT

March 12, 2018

SUBMITTED PAPER

11

and removing the k + 2-th component, which is always equal to zero, in the resultant product.
If we arrange all coefficients in the polynomials with degree strictly less than p − 1, we get the
original (p − 1) × (k + r) array of RDP(p, k, r; g(k + 1)).
When 0 ≤ g(i) ≤ k−1 for i = 0, 1, . . . , k−1, the MDS property condition of EVENODD(p, k, r; g(k))
is the same as that of the extended EVENODD codes [6], and the MDS property condition of
r ≤ 8 and r ≥ 9 was given in [6] and [18], respectively. Note that the MDS property condition
depends on that 2 is a primitive element in Fp . This is the reason of the assumption of primitivity
of 2 in Fp . In the following of the paper, we assume that 0 ≤ g(i) ≤ k −1 with i = 0, 1, . . . , k −1
for EVENODD(p, k, r; g(k)) and 0 ≤ g(i) ≤ k with i = 0, 1, . . . , k for RDP(p, k, r; g(k + 1)),
and the proposed EVENODD(p, k, r; g(k)) and RDP(p, k, r; g(k + 1)) are MDS codes. We will
focus on the erasure decoding for these two codes.
When some columns of EVENODD(p, k, r; g(k)) are erased, we assume that the number of
erased information columns is no larger than the number of continuous surviving parity columns.
Note that one needs to recover the failure columns by downloading k surviving columns. First,
we represent the downloaded k columns by some information polynomials and continuous parity
polynomials. Then, we can subtract all the downloaded information polynomials from the parity
polynomials to obtain a Vandermonde linear system. Although EVENODD(p, k, r; g(k)) can be
described by the k ×r Vandermonde matrix given in (16) over F2 [x]/Mp (x) and we can solve the
Vandermonde linear system over F2 [x]/Mp (x) to recover the failure columns, it is more efficient
to solve the Vandermonde linear system over Rp . First, we will show in the next section that we
can first perform calculation over Rp and then reduce the results modulo Mp (x) in the decoding
process. An efficient decoding algorithm to solve Vandermonde linear system over Rp based on
LU factorization of Vandermonde matrix is then proposed in Section V.

IV. VANDERMONDE M ATRIX OVER Rp

Before we focus on the efficient decoding method of EVENODD(p, k, r; g(k)) and RDP(p, k, r; g(k+
1)), we first present some properties of Vandermonde matrix. As the decoding algorithm hinges
on a quick method in solving a Vandermonde system of equations over Rp , we discuss some
properties of the linear system of Vandermonde matrix over Rp in this section.
March 12, 2018

DRAFT

12

IEEE TRANSACTIONS ON COMMUNICATIONS

Let Vr×r (a) be an r × r Vandermonde matrix

1 xa1 · · ·

1 xa2 · · ·

Vr×r (a) :=  . .
...
 .. ..

1 xar · · ·

x(r−1)a1




x(r−1)a2 

,
.. 
. 

x(r−1)ar

(18)

where a1 , . . . , ar are distinct integers such that the difference of each pair of them is relatively
prime to p. The entries of Vr×r (a) are considered as polynomials in Rp . We investigate the
action of multiplication over Vr×r (a) by defining the function F : Rpr → Rpr :
F (u) := uVr×r (a)
for u = (u1 (x), . . . , ur (x)) ∈ Rpr . Obviously, F is a homomorphism of abelian group and we
have F (u + u0 ) = F (u) + F (u0 ) for u, u0 ∈ Rpr .
The function F is not surjective. If a vector v = (v1 (x), v2 (x), . . . , vr (x)) is equal to F (u)
for some u ∈ Rp , it is necessary that
v1 (1) = v2 (1) = · · · = vr (1).

(19)

This is due to the fact that each polynomial vj (x) is obtained by adding certain cyclically shifted
version of ui (x)’s. In other words, if v is in the image of F , then either there are even number of
nonzero terms in all vi (x), or there are odd number of nonzero terms in all vi (x) for 1 ≤ i ≤ r.
The function F is also not injective. We can see this by observing that if we add the polynomial
Mp (x) to a component of u, for example, adding Mp (x) to ui (x), then
F (u + (0, . . . , 0, Mp (x), 0, . . . , 0)) = F (u) + (Mp (x), . . . , Mp (x)).
| {z }
i−1

Hence, if we add Mp (x) to two distinct components of input vector u, then the value of F (u) does
not change. We need the following lemma before discussing the properties of the Vandermonde
linear system over Rp .
Lemma 4. [6, Lemma 2.1] Suppose that p is an odd number and d is relatively prime to p,
then 1 + xd and Mp (x) are coprime in F2 [x], and xi and Mp (x) are relatively prime in F2 [x]
for any positive integer i.
If the vector v satisfies (19), in the next theorem, we show that there are many vectors u such
that F (u) = v.

DRAFT

March 12, 2018

SUBMITTED PAPER

13

Theorem 5. Let a1 , a2 , . . . , ar be r integers such that the difference ai1 − ai2 is relatively prime
to p for all pair of distinct indices 1 ≤ i1 < i2 ≤ r. The image of F consists of all vectors
v ∈ Rpr that satisfy the condition (19). For all vectors u satisfying
mod 1 + xp ,

uVr×r (a) = v

(20)

they are congruent to each other modulo Mp (x).
Proof. Suppose that v1 (x), . . . , vr (x) are polynomials in Rp satisfying (19). We want to show
that the vector v = (v1 (x), . . . , vr (x)) is in the image of F . We first consider the case that
v1 (1) = v2 (1) = · · · = vr (1) = 0. Since 1 + x and Mp (x) are relatively prime polynomials, by
Chinese remainder theorem, we have an isomorphism
θ(f (x)) = (f (x) mod 1 + x, f (x) mod Mp (x))
defined for f (x) ∈ Rp . The inverse of θ is given by
θ−1 (a(x), b(x)) = Mp (x)a(x) + (1 + Mp (x))b(x) mod 1 + xp ,
where a(x) ∈ F2 [x]/(1 + x) and b(x) ∈ F2 [x]/Mp (x). We thus have a decomposition of the ring
Rp as a direct sum of F2 [x]/(1 + x) and F2 [x]/Mp (x). It suffices to investigate the action of
multiplication over Vr×r (a) by considering
uVr×r (a) = v
uVr×r (a) = v

mod 1 + x, and

(21)

mod Mp (x).

(22)

Note that (21) is equivalent to
(u mod (1 + x)) · (Vr×r (a) mod (1 + x)) = v mod (1 + x).
Also Vr×r (a) mod (1 + x) is an r × r all one matrix and v mod (1 + x) = 0 because vi (1) =
0, 1 ≤ i ≤ r. It is sufficient to find r components of solution u0 from binary field such that
their summation is zero. Therefore, there are many solutions u0 and each solution satisfies that
the number of one among all the components of u0 is an even number.
For (22), we need to show that the determinant of Vr×r (a) is invertible modulo Mp (x). Since
the determinant of Vr×r (a) is2
det(Vr×r (a)) =

Y

(xai1 + xai2 ),

i1 <i2

2

Since −1 is the same as 1 in F2 , we replace −1 with 1 in this work and addition is the same as subtraction.

March 12, 2018

DRAFT

14

IEEE TRANSACTIONS ON COMMUNICATIONS

we need to show that xai1 + xai2 and Mp (x) are relatively prime polynomials in F2 [x], for all
pairs of distinct (i1 , i2 ). We first factorize xai1 + xai2 in the form xai1 + xai2 = xai1 (1 + xd ), and
by assumption, d is an integer which is coprime with p. This problem now reduces to showing
that (i) 1 + xd and Mp (x) are relatively prime in F2 [x] whenever gcd(d, p) = 1, and (ii) x`
and Mp (x) are relatively prime in F2 [x] for all integer `. We can show this by Lemma 4. We
can thus solve the equation in (22), say, by Cramer’s rule, to obtain the unique solution u00 .
After obtaining the solutions u0i (x) ∈ F2 [x]/(1 + x) and u00i (x) ∈ F2 [x]/Mp (x) in (21) and (22)
respectively for all i, we can calculate the solution via the isomorphism θ−1
θ−1 (u0i (x), u00i (x)) = Mp (x)u0i (x) + (1 + Mp (x))u00i (x) mod 1 + xp .
Therefore, the solutions of u ∈ Rpr in (20) are
((1 + Mp (x))u001 (x) + 1 Mp (x), · · · , (1 + Mp (x))u00r (x) + r Mp (x)),

(23)

where i is equal to 0 or 1 for all i and the number of ones is an even number. That is to say,
there are many solutions in (20) and all the solutions after reducing modulo Mp (x) is unique
and is the solution in (22).
When v1 (1) = v2 (1) = · · · = vr (1) = 1, similar argument can be applied to find the solution.
The only difference between this solution and (23) is that the number of ones among all i in
this solution is odd. This completes the proof.
From the above theorem, whenever the vector v satisfies the condition (19), we can decode one
solution of u in (20). Recall that, for augmented array of EVENODD codes, every component
in u has been added zero coefficient of the term with degree p − 1. Hence, each component of
the real solution is with at most degree p − 2. By the theorem, reducing u modulo Mp (x) gives
us the final solution. Therefore, to solve u in (22), we can first solve u over Rp and then take
the modulo Mp (x) for every component of u. This will be demonstrated in next section.

V. E FFICIENT D ECODING OF VANDERMONDE S YSTEM OVER Rp
In this section, we will present an efficient decoding method of the Vandermonde system over
Rp based on LU factorization of the Vandermonde matrix.
DRAFT

March 12, 2018

SUBMITTED PAPER

15

A. Efficient Division by 1 + xd
We want to first present two decoding algorithms for performing division by 1 + xd which
will be used in the decoding process, where d is a positive integer that is coprime with p and
all operations are performed in the ring Rp = F2 [x]/(1 + xp ). Given the equation
(1 + xd )g(x) = f (x) mod 1 + xp ,

(24)

where d is a positive integer such that gcd(d, p) = 1 and f (x) has even number of nonzero terms.
One method to compute g(x) is given in Lemma 8 in [26], which is summarized as follows.
Lemma 6. [26, Lemma 8] The coefficients of g(x) in (24) can be computed by
gp−1 = 0, gp−d−1 = fp−1 , gd−1 = fd−1 ,
g(p−(i+1)d−1) = f(p−id−1) + g(p−id−1) for i = 1, . . . , p − 3,
where g(x) =

Pp−1
i=0

gi xi , f (x) =

Pp−1
i=0

f i xi .

Although computing the division in (24) by Lemma 6 only takes p−3 XORs, we do not know
whether the resulting polynomial g(x) has even number of nonzero terms or not. In solving the
Vandermonde linear system in the next subsection, we need to compute many divisions of the
form in (24). If we do not require that the solved polynomial g(x) should have even number
of nonzero terms, then we can employ Lemma 6 to solve the division. Otherwise, Lemma 6 is
not applicable to such division. Therefore, we need the following lemma that can compute the
division when g(x) is required to have even number of nonzero terms.
Lemma 7. [23, Lemma 13] Given the equation in (24), we can compute the coefficient g0 by
g0 = f2d + f4d + · · · + f(p−1)d ,

(25)

and the other coefficients of g(x) can be iteratively computed by
gd` = fd` + gd(`−1) for ` = 1, 2, . . . , p − 1.

(26)

Note that the subscripts in Lemma 7 are taken modulo p. As gcd(d, p) = 1, we have that
{0, d, 2d, · · · , (p − 1)d} = {0, 1, 2, · · · , p − 1} mod p.
Therefore, we can compute all the coefficients of g(x) by Lemma 7. The result in Lemma 7 has
been observed in [23], [27]. We can check that the computed polynomial g(x) satisfies g(1) = 0,

March 12, 2018

DRAFT

16

IEEE TRANSACTIONS ON COMMUNICATIONS

by adding the equation in (25) and the equations in (26) for ` = 2, 4, . . . , p − 1. The number of
XORs required in computing the division by Lemma 7 is (3p − 5)/2.
For the same parameters, the computed g(x) by Lemma 6 is equal to either the computed
g(x) by Lemma 7 or the summation of Mp (x) and the computed g(x) by Lemma 7, depending
on whether the computed g(x) by Lemma 6 has even number of nonzero terms or not. When
solving a division in (24), we prefer the method in Lemma 6 if there is no requirement that
the resulting polynomial g(x) should have even number of nonzero terms, as the method in
Lemma 6 involves less XORs.
B. LU Method of Vandermonde Systems over Rp
The next theorem is the core of the fast LU method for solving Vandermonde system of
equations v = uVr×r (a) which is based on the LU decomposition of a Vandermonde matrix
given in [28].
Theorem 8. [28] For positive integer r, the square Vandermonde matrix Vr×r (a) defined in
(18) can be factorized into
(2)
(r−1) (r−1) (r−2)
Vr×r (a) = L(1)
Ur
Ur
· · · U(1)
r Lr · · · Lr
r ,
(`)

where Ur is the upper triangular matrix

Ir−`−1






U(`)
:=

r






0

0
1 xa1


···

0

xa2 · · ·
..
...
.

0
..
.

0

0
..
.

1
..
.

0

0

0

···

1

0

0

0

···

0


0 


0 

.. 
. 


a` 
x 
1

(`)

and Lr is the lower triangular matrix

Ir−`−1












0



0

1

0

···

0

0

1
..
.

xar−`+1 + xar−`
..
.

···
..
.

0
..
.

0
..
.

0

0

···

xar−1 + xar−`

0

0

0

···

1

xar + xar−`












for ` = 1, 2, . . . , r − 1.

DRAFT

March 12, 2018

SUBMITTED PAPER

17

For example, the Vandermonde matrix V3×3 (1, x, x4 ) can be factorized as





0  1
0
0  1 1 0  1 0 0
1 0





(1) (2) (2) (1)
L3 L3 U3 U3 = 0 1
0  1 x + 1
0  0 1 x 0 1 1 .





0 1 x4 + x
0
1
x4 + 1
0 0 1
0 0 1
Based on the factorization in Theorem 8, we have a fast algorithm for solving a Vandermonde
system of linear equations. Given the matrix Vr×r (a) and a row vector v = (v1 (x), . . . , vr (x)),
we can solve the linear system uVr×r (a) = v in (20) by solving
(2)
(r−1) (r−1) (r−2)
uL(1)
Ur
Ur
· · · U(1)
r Lr · · · Lr
r = v.

(27)

As the inversion of each of the upper and lower triangular matrices can be done efficiently, we
can solve for u by inverting 2(r − 1) triangular matrices.
Algorithm 1 Solving a Vandermonde linear system.
Inputs:
positive integer r, odd integer p,

integers

a1 , a2 , . . . , ar ,

and

v

=

(v1 (x), v2 (x), . . . , vr (x)) ∈ Rpr .
u = (u1 (x), . . . , ur (x)) that satisfies uVr×r (a) = v.

Output:

Require: v1 (1) = v2 (1) = · · · = vr (1), and gcd(ai1 − ai2 , p) = 1 for all 1 ≤ i1 < i2 ≤ r.
1:

u ← v.

2:

for i from 1 to r − 1 do

3:
4:
5:
6:

for j from r − i + 1 to r do
uj (x) ← uj (x) + uj−1 (x)xai+j−r
for i from r − 1 down to 1 do
Solve g(x) from (xar + xar−i )g(x) = ur (x) by Lemma 7 or Lemma 6 (only when i = 1)
ur (x) ← g(x)

7:
8:

for j from r − 1 down to r − i + 1 do
Solve g(x) from (xaj + xar−i )g(x) = (uj (x) + uj+1 (x)) by Lemma 7 or Lemma 6 (only
when i + j = r + 1)
uj (x) ← g(x)

9:
10:

ur−i (x) ← ur−i (x) + ur−i+1 (x)
return u = (u1 (x), . . . , ur (x))

The procedure of solving a Vandermonde system of linear equations is given in Algorithm 1. In
Algorithm 1, steps 2 to 4 are forward additions that require r(r − 1)/2 additions and r(r − 1)/2

March 12, 2018

DRAFT

18

IEEE TRANSACTIONS ON COMMUNICATIONS

multiplications. Steps 5 to 9 are backward additions, and require r(r − 1)/2 additions and
r(r−1)/2 divisions by factors of the form xaj +xar−i . Division by xaj +xar−i is done by invoking
the method in Lemma 6 or Lemma 7. We may compute all the divisions by Lemma 7. However,
some of the division can be computed by Lemma 6, where the computational complexity can
be reduced.
Theorem 9. Algorithm 1 outputs u that is one of the solution to uVr×r (a) = v over Rp .
Furthermore, g(x) in step 6 when i = 1, and in step 8 when i+j = r+1 and i ∈ {2, 3, . . . , r−1}
can be computed by Lemma 6 to reduce computation complexity.
Proof. First, we want to show that Algorithm 1 implements precisely the matrix multiplications
(i)

in (27). Consider the linear equations uUr = v for i = 1, 2, . . . , r − 1. According to the upper
(i)

triangular matrix Ur in Theorem 8, we can obtain the relation between u and v as
uj (x) = vj (x) for j = 1, . . . , r − i,
xai+j−r uj−1 (x) + uj (x) = vj (x) for j = r − i + 1, . . . , r.
(r−1)

We can observe from Algorithm 1 that steps 1 to 4 solve u from uUr

(r−2)

Ur

(1)

· · · Ur = v,

and we denote the solved r polynomials as v0 = (v10 (x), . . . , vr0 (x)). Consider the equations
(i)

(i)

uLr = v0 . According to the lower triangular matrix Lr in Theorem 8, the relation between u
and v0 is as follows:
uj (x) = vj0 (x) for j = 1, . . . , r − i − 1,
0
ur−i (x) + ur−i+1 (x) = vr−i
(x),

(28)

(xaj + xar−i )uj (x) + uj+1 (x) = vj0 (x) for j = r − i + 1, . . . , r − 1,

(29)

(xar + xar−i )ur (x) = vr0 (x).

(30)

It is easy to see that step 6, step 8 and step 9 solves ur (x) from (30), uj (x) from (29) and ur−i (x)
(1)

(2)

(r−1)

from (28) respectively. We thus obtain that steps 5 to 9 solve u from uLr Lr · · · Lr

= v0 .

Therefore, Algorithm 1 precisely computes u from the matrix multiplication in (27).
Note that we need to compute r(r−1)/2 divisions (solving g(x)) in steps 6 and 8 in Algorithm
1, and all divisions can be solved by Lemma 6 or Lemma 7. To solve all divisions by Lemma
6 or Lemma 7, all polynomials ur (x) and uj (x) + uj+1 (x) in steps 6 and 8 must have even
number of nonzero terms, which is a requirement in computing the divisions. That is ur (1) = 0
DRAFT

March 12, 2018

SUBMITTED PAPER

19

and uj (1) + uj+1 (1) = 0 when we calculate g(x) in these steps. Next we show this requirement
is ensured during the process of the algorithm.
Consider two cases: vi (1) = 0 for all i and vi (1) = 1 for all i. If vi (1) = 0 for all i, then we
have ui (1) = 0 for all i after the double for loops between steps 2 to 4. Hence ur (1) = 0 in step
6 when i = r − 1. In step 6, we need to ensure that all ur (x) produced satisfy ur (1) = 0. Since
all g(x), hence ur (x), generated by Lemma 7 have such property, we only need to consider the
case that g(x) is generated by Lemma 6, i.e., when i = 1. When i = 1, the ur (x) assigned by
g(x) will not be invoked in computing the division in steps 7 and 8 as r − i + 1 = r which is
larger than the initial value r − 1 of the loop in step 7. Hence, there is no need to run the for
loop in step 7 to step 8.
Similarly, we need to ensure that uj (1) − uj+1 (1) = 0 for j = r − 1, r − 2, . . . , r − i − 1. It
is sufficient to ensure that uj (1) = 0 and uj+1 (1) = 0. Since all g(x), hence uj (x), generated
by Lemma 7 already have had such property, in step 8, we only need to consider the case that
g(x) is generated by Lemma 6, i.e., when i + j = r + 1. Next, we prove that when i + j = r + 1,
the uj (x) assigned by g(x) in step 8 are not used again to solve the division in step 8. Let i = t
(i = r − 1, . . . , 2). Note that, when i + j = r + 1, the algorithm is in the final iteration of the for
loop in step 7. Hence, we need to prove that uj (x) = ur−t+1 (x) will not be used in the iterations
i < t. When i < t in step 7, the last iteration j = r − i + 1 > r − t + 1 such that ur−t+1 (x) will
not be used in the calculation involving uj (x) and uj+1 (x) in step 8.
If vi (1) = 1 for all i, then after the double for loops between steps 2 to 4, we have
u1 (1) = 1, and u2 (1) = u3 (1) = · · · = ur (1) = 0.
In this case, we only need to show that u1 (x) has never been used in the calculation of g(x) in
step 8. Note that, in the last iteration of step 7, j = r − i + 1 has never gone down to 1 since
i ≤ r − 1. Hence, u1 (x) has never been used in step 8.
The next theorem shows the computational complexity in Algorithm 1.
Theorem 10. The computation complexity in Algorithm 1 is at most
r(r − 1)p + (r − 1)(p − 3) + (r − 1)(r − 2)(3p − 5)/4.

(31)

Proof. In Algorithm 1, there are r(r − 1) additions that require r(r − 1)p XORs, r(r − 1)/2
multiplications that require no XORs (only cyclic shift applied) and r(r − 1)/2 divisions that

March 12, 2018

DRAFT

20

IEEE TRANSACTIONS ON COMMUNICATIONS

require (r − 1)(p − 3) + (r − 1)(r − 2)(3p − 5)/4 XORs (r − 1 divisions are computed by
Lemma 6 and the other divisions are computed by Lemma 7). Therefore, the total computation
of Algorithm 1 is at most (31).
According to Theorem 5, we can solve the Vandermonde system over F2 [x]/Mp (x) by first
solving the Vandermonde system over Rp and then reducing the r resulting polynomials by
modulo Mp (x). By Theorem 9, we can solve the Vandermonde system over Rp by using the
factorization method in Theorem 8.
Remark. Since in Algorithm 1, when i = 1, the output ur (x) is computed from the division
in step 6 which is solved by Lemma 6, we have that the last coefficient of ur (x), gp−1 , is zero.
For i = 1, 2, . . . , r − 1, the output ur−i (x) is a summation of ur−i (x) and ur−i+1 (x), where
ur−i+1 (x) is computed in the last iteration in step 7 for i = r − 1, r − 2, . . . , 2, and ur−i (x) is
computed in the last iteration in step 7 for i + 1 = r − 1, r − 2, . . . , 2. Note that the last iteration
for each i is solved by Lemma 6. Thus the last coefficient of ui (x) is zero for i = 2, 3, . . . , r − 1.
The output u1 (x) is the summation of u1 (x) and u2 (x) by step 9, where u1 (x) = v1 (x) and
u2 (x) is computed from the division in step 8 when i = r − 1, which is solved by Lemma 6.
Therefore, if the last coefficient of v1 (x) is zero, then the last coefficient of the output u1 (x)
is zero. Otherwise, the last coefficient of the output u1 (x) is one. We thus have that the last
coefficient of each of the last r − 1 resulting polynomials is zero. Therefore, it is not necessary
to reduce the last r − 1 resulting polynomials by modulo Mp (x) and we only need to reduce
the first resulting polynomial by modulo Mp (x). In the example of EVENODD(5, 3, 3; (0, 1, 4)),
the three components of the returned u are exactly equal to the three information polynomials
of EVENODD(5, 3, 3; (0, 1, 4)), as the last coefficient of v1 (x) is zero.
Although the LU decoding method of the r × r Vandermonde linear systems over Rp is also
discussed in Theorem 14 of [23], the complexity of the algorithm provided is 47 r(r − 1)p which
is larger than (31). The reason of computation reduction given in (31) is as follows. There are
r − 1 divisions in Algorithm 1 that are solved with p − 3 XORs involved for each division, while
all r(r − 1) divisions are solved with (3p − 5)/2 XORs involved for each division in [23].
VI. E RASURE D ECODING OF EVENODD(p, k, r) AND RDP(p, k, r)
The efficient decoding method of the Vandermonde linear systems over Rp proposed in
Section V is applicable to the information column failure and some particular cases with both
information failure and parity failure of EVENODD(p, k, r; g(k)), RDP(p, k, r; g(k + 1)) and

DRAFT

March 12, 2018

SUBMITTED PAPER

21

Vandermonde array codes such as Blaum-Roth code [19]. We first consider the decoding method
for EVENODD(p, k, r; g(k)).
A. Erasures Decoding of EVENODD(p, k, r)
Suppose that γ information columns e1 , . . . , eγ and δ parity columns f1 , . . . , fδ are erased
with 0 ≤ e1 < . . . < eγ ≤ k − 1 and k + 1 ≤ f1 < . . . < fδ ≤ k + r − 1, where k ≥ γ ≥ 0,
r − 1 ≥ δ ≥ 0 and γ + δ = ρ ≤ r. Let f0 = k − 1 and fδ+1 = k + r − 1, we assume that there
exist λ ∈ {0, 1, . . . , δ} such that fλ+1 − fλ ≥ γ + 1. We have that the columns fλ + 1, . . . , fλ + γ
are not erased. Let
A := {0, 1, . . . , k − 1} \ {e1 , e2 , . . . , eγ }
be a set of indices of the available information columns. We want to first recover the lost
information columns by reading k − γ information columns with indices i1 , i2 , . . . , ik−γ ∈ A,
and γ parity columns with indices fλ + 1, fλ + 2, . . . , fλ + γ, and then recover the failure parity
column by re-encoding the failure parity bits according to (2) for ` = f1 − k, . . . , fδ − k.
First, we compute the bits of the γ parity columns fλ + 1, fλ + 2, . . . , fλ + γ of the augmented
array according to (8) and (9) in Lemma 2. This can be done since column k is not failed.
Then, we represent the k − γ information columns and γ parity columns by k − γ information
polynomials a0i (x) as
a0i (x) := a0,i + a1,i x + · · · + ap−2,i xp−2

(32)

for i ∈ A and γ parity polynomials a0fλ +j (x)
a0fλ +j (x) := a00,fλ +j + a01,fλ +j x + · · · + a0p−1,fλ +j xp−1

(33)

for j = 1, 2, . . . , γ. Then, we subtract k − γ information polynomials a0i (x) in (32), i ∈ A from
the γ parity polynomials a0fλ +1 (x), . . . , a0fλ +γ (x) in (33), to obtain γ syndrome polynomial āh (x)
over Rp as
āh (x) = a0fλ +h (x) +

X

a0i (x)xg(i)·(fλ +h−k) ,

(34)

i∈A

for h = 1, 2, . . . , γ. Therefore, we can establish the relation between the syndrome polynomials
and the erased information polynomials as follows

xg(e1 )(fλ +1−k) xg(e1 )(fλ +2−k) · · ·

h
i h
i xg(e2 )(fλ +1−k) xg(e2 )(fλ +2−k) · · ·

ā1 (x) · · · āγ (x) = a0e1 (x) · · · a0eγ (x) · 
..
..
..

.
.
.

xg(eγ )(fλ +1−k) xg(eγ )(fλ +2−k) · · ·

March 12, 2018

xg(e1 )(fλ +γ−k)




xg(e2 )(fλ +γ−k) 

.
..

.

g(eγ )(fλ +γ−k)
x

DRAFT

22

IEEE TRANSACTIONS ON COMMUNICATIONS

The right-hand side of the above equations can be reformulated as
h
i
g(e1 )(fλ +1−k) 0
g(eγ )(fλ +1−k) 0
x
ae1 (x) · · · x
aeγ (x) Vγ×γ (e),
where Vγ×γ (e) is a Vandermonde matrix

1 xg(e1 ) · · ·

1 xg(e2 ) · · ·

Vγ×γ (e) :=  .
..
...
 ..
.

1 xg(eγ ) · · ·
By (17), we have that a0fλ +h (1) =
āh (1) =

Pk−1
j=0

a0fλ +h (1)

+

xg(e1 )(γ−1)




xg(e2 )(γ−1) 

.
..

.

xg(eγ )(γ−1)

a0j (1) and we thus have
X
i∈A

a0i (1)

=

k−1
X
j=0

a0j (1) +

X

a0i (1),

i∈A

which is independent on h. Thus, we obtain that ā1 (1) = · · · = ār (1). We can then obtain the
erased information polynomials by first solving the Vandermonde linear systems over Rp by
Algorithm 1, cyclic-left-shifting the solved polynomials xg(ei )(fλ +1−k) a0ei (x) by g(ei )(fλ + 1 − k)
positions for i = 1, 2, . . . , γ, and then reduce a0e1 (x) modulo Mp (x) when λ > 0 according to
the remark at the end of Section V-B. If λ = 0, we have fλ + 1 − k = 0 and the last coefficient
of ā1 (x) is zero, then we do not need to reduce a0e1 (x) modulo Mp (x) according to the remark at
the end of Section V-B. The parity bits in the δ erased parity columns can be recovered by (2).
Note that column k is assumed to be non-failure, as column k is needed to compute the bits
of the augmented array by (8) and (9).
B. Erasure Decoding of RDP(p, k, r)
Similar to the decoding for EVENODD(p, k, r), we assume that γ information columns
indexed by e1 , . . . , eγ and δ parity columns f1 , . . . , fδ of RDP(p, k, r) are erased with 0 ≤
e1 < . . . < eγ ≤ k − 1 and k + 1 ≤ f1 < . . . < fδ ≤ k + r − 1, where k ≥ γ ≥ 0,
r − 1 ≥ δ ≥ 0 and γ + δ = ρ ≤ r. Let f0 = k − 1 and fδ+1 = k + r − 1 and assume that there
exist λ ∈ {0, 1, . . . , δ} such that fλ+1 − fλ ≥ γ + 1. The decoding procedure can be divided into
two cases: λ ≥ 1 and λ = 0.
(i) λ ≥ 1. First, we formulate k − γ surviving information polynomials bi (x) for i ∈ A as
bi (x) := b0,i + b1,i x + · · · + bp−2,i xp−2 ,
DRAFT

March 12, 2018

SUBMITTED PAPER

23

and γ + 1 parity polynomials as
bk (x) := b0,k + b1,k x + · · · + bp−2,k xp−2 ,
bfλ +j (x) := b0,fλ +j + · · · + bp−2,fλ +j x

p−2

+(

p−2
X

bi,fλ +j )xp−1 ,

i=0

where j = 1, 2, . . . , γ. Then, we compute γ syndrome polynomials b̄1 (x), b̄2 (x), . . . , b̄γ (x) by
b̄h (x) = bfλ +h (x) + bk (x)xg(k)(fλ +h−k) +

X

bi (x)xg(i)(fλ +h−k) ,

i∈A

for h = 1, 2, . . . , γ. It is easy to check that b̄1 (1) = · · · = b̄γ (1). By the remark at the end of
Section V-B, the erased information polynomials can be computed by first solving the following
Vandermonde system of linear equations
h
i h
b̄1 (x) · · · b̄γ (x) = xg(e1 )(fλ +1−k) be1 (x) · · ·

x

g(eγ )(fλ +1−k)

i
beγ (x) Vr×r (e),

over Rp by Algorithm 1, cyclic-left-shifting the resultant xg(ei )(fλ +1−k) bei (x) by g(ei )(fλ + 1 − k)
positions for i = 1, 2, . . . , γ, and then reducing be1 (x) modulo Mp (x).
(ii) λ = 0. We have that columns k, k + 1, . . . , k + γ are not erased. We can obtain γ syndrome
polynomials b̄1 (x), b̄2 (x), . . . , b̄γ (x) by
b̄1 (x) = bk (x) +

X

bi (x),

i∈A

and
b̄h (x) = bk+h (x) + bk (x)xg(k)·(h−1) +

X

bi (x)xg(i)·(h−1) ,

i∈A

for h = 2, 3, . . . , γ. The erased information polynomials can be computed by solving the
following Vandermonde linear system
h
i h
b̄1 (x) · · · b̄γ (x) = be1 (x) · · ·

i
beγ (x) · Vr×r (e).

We do not need to reduce be1 (x) modulo Mp (x) according to the remark at the end of Section
V-B, as the last coefficient of b̄1 (x) is zero. Lastly, we can recover the δ parity columns by (5)
for i = 0, 1, . . . , p − 2 and ` = f1 − k, . . . , fδ − k.
Note that we need column k to obtain the syndrome polynomials in the decoding procedure,
so column k is assumed to be non-failure column.
Remark. In the erasure decoding, the assumption that there exist λ ∈ {0, 1, . . . , δ} such that
fλ+1 − fλ ≥ γ + 1 is necessary; otherwise, we cannot obtain the Vandermonde linear system and
March 12, 2018

DRAFT

24

IEEE TRANSACTIONS ON COMMUNICATIONS

Algorithm 1 is not applicable. The traditional decoding method, such as Cramer’s rule, can be
used to recover the failures if the assumption is not satisfied. In the next section, we consider
the decoding complexity for two codes when the assumption is satisfied.
VII. D ECODING C OMPLEXITY
In this section, we evaluate the decoding complexity for EVENODD(p, k, r) and RDP(p, k, r).
We determine the normalized decoding complexity as the ratio of the decoding complexity to
the number of information bits.
When r = 3, some specific decoding methods [7], [14], [15], [16], [17] are proposed to
optimize the decoding complexity of three information erasures, such as the decoding method
for STAR [14] and the decoding method for Triple-Star [16]. However, all those decoding
methods [7], [14], [15], [16], [17] only focus on the specific codes with r = 3 and cannot be
generalized for r ≥ 4. In the following, we evaluate the decoding complexity for more than
three information erasures.
Theorem 11. Suppose that γ information columns and δ parity columns f1 , . . . , fδ are erased.
Let f0 = k − 1 and fδ+1 = k + r − 1, we assume that there exist λ ∈ {0, 1, . . . , δ} such
that fλ+1 − fλ ≥ γ + 1. We employ Algorithm 1 to recover the γ information erasures and
recover the failure parity columns by re-encoding the parity bits. The decoding complexity of
EVENODD(p, k, r) is
p(γk +

γ 2 5γ 5
3γ 2 γ 5
− + ) − γk −
−
− + δ(kp − k − 1) when λ > 0,
4
4 2
4
4
2

(35)

p(γk +

3γ 2 γ 1
γ 2 5γ 1
− − ) − γk −
−
+ + δ(kp − k − 1) when λ = 0.
4
4 2
4
4
2

(36)

The decoding complexity of RDP(p, k, r) is
3γ 2 γ 3
γ 2 9γ 1
− + ) − γk −
−
− + δk(p − 2) when λ > 0,
p(γk +
4
4 2
4
4
2

(37)

3γ 2 γ 3
γ 2 9γ 7
− − ) − γk −
−
+ + δk(p − 2) when λ = 0.
4
4 2
4
4
2

(38)

p(γk +

Proof. Consider the decoding process of EVENODD(p, k, r). When λ > 0, we compute the
bits a0i,k+` of the augmented array from EVENODD(p, k, r) by (8) and (9) for ` = fλ + 1 −
Pp−2
k, . . . , fλ + γ − k. We first compute i=0
ai,k , and then compute a0p−1,k+` by (8) and a0i,k+` by
DRAFT

March 12, 2018

SUBMITTED PAPER

25

(9). Thus, the total number of XORs involved in computing the bits a0i,k+` is 2(p − 1)γ + (p − 2).
We now obtain k − γ information polynomials in (32) and γ parity polynomials in (33). Next,
we subtract k − γ surviving information polynomials from the γ parity polynomials to obtain γ
syndrome polynomials by (34) that takes γ(k − γ)(p − 1) XORs. The γ information polynomials
are obtained by solving the Vandermonde system of equations by using Algorithm 1, of which
the computational complexity is
γ(γ − 1)p + (γ − 1)(p − 3) + (γ − 1)(γ − 2)(3p − 5)/4
according to Theorem 10. Since the last γ − 1 output polynomials of Algorithm 1 are exactly
the last γ − 1 information polynomials of EVENODD(p, k, r), we only need to reduce the first
polynomial modulo Mp (x), which takes at most p − 1 XORs. The erased δ parity columns can
be recovered by (2) and the complexity is δ(kp − k − 1). Therefore, the decoding complexity
of EVENODD(p, k, r) is (35) when λ > 0.
When λ = 0, there are two differences compared with the case of λ > 0. First, we only
need to compute the bits of the augmented array for γ − 1 parity columns and the complexity
is 2(p − 1)(γ − 1) + (p − 2), as the bits in the first parity column of the augmented array are
the same as those of the first parity column of EVENODD(p, k, r), Second, we do not need
to reduce the first polynomial modulo Mp (x) after solving the Vandermonde system. Therefore,
the decoding complexity of λ = 0 has 3p − 3 XORs reduction and results in (36).
In RDP(p, k, r), computing r syndrome polynomials takes
γ(p − 2) + γ(k − γ + 1)(p − 1)
XORs when λ ≥ 1 and
(γ − 1)(p − 2) + (k − γ)(p − 1) + (γ − 1)(k − γ + 1)(p − 1)
XORs when λ = 0. Similar to EVENODD(p, k, r), the Vandermonde linear system can be
solved by Algorithm 1 with complexity
γ(γ − 1)p + (γ − 1)(p − 3) + (γ − 1)(γ − 2)(3p − 5)/4
XORs. Reducing one polynomial modulo Mp (x) takes at most p − 1 XORs when λ > 0. The δ
parity columns are recovered by (5) and its complexity is δk(p − 2). Therefore, the total number
of XORs involved in the decoding process results in (37) for λ ≥ 1 and (38) for λ = 0.

March 12, 2018

DRAFT

26

IEEE TRANSACTIONS ON COMMUNICATIONS

Blaum-Roth decoding method [19] proposed for decoding Blaum-Roth codes is also applicable
to the decoding of EVENODD(p, k, r). Suppose that γ information columns and δ parity columns
f1 , . . . , fδ are erased with the assumption that there exist λ ∈ {0, 1, . . . , δ} such that fλ+1 − fλ ≥
γ + 1. If one employs the Blaum-Roth decoding method to recover the information erasures and
recover the failure parity columns by re-encoding the parity bits, the decoding complexity of
EVENODD(p, k, r) is [29]
γ(k + γ)p + (3γ 2 + 0.5γ)p + γ 2 − 0.5γ + δ(kp − k − 1).
The Blaum-Roth decoding method cannot be directly employed on the erasure decoding for
RDP(p, k, r). However, one can first transform λ parity columns of RDP(p, k, r) into the form
of EVENODD(p, k, r) and then recover the erased information columns by the decoding method
of EVENODD(p, k, r). Let ai,j = bi,j for i = 0, 1, . . . , p − 2 and j = 0, 1, . . . , k − 1. That is, the
information bits of RDP(p, k, r) and EVENODD(p, k, r) are the same. We then have ai,k = bi,k
by (1) and (4) and
p−2
X

bi,k+` + bp−1−`g(k),k =

i=0
k
XX

bi−`g(j),j +

i=0 j=0

=

k
X

bi−`g(j),j + bp−1−`g(k),k

(39)

i=0 j=0

p−1

=

p−2 k
X
X

k
X

bp−1−`g(j),j + bp−1−`g(k),k

j=0

bp−1−`g(j),j + bp−1−`g(k),k

(40)

j=0

=

k−1
X
j=0

bp−1−`g(j),j =

k−1
X

ap−1−`g(j),j = ap−1,k+` ,

j=0

where (39) comes from (5), (40) comes from (4) and
{−`g(j), 1 − `g(j), · · · , p − 1 − `g(j)} = {0, 1, · · · , p − 1} mod p.
Therefore, when λ > 0, we can transform λ parity columns of RDP(p, k, r) into the form of
EVENODD(p, k, r) by
ap−1,k+` =

p−2
X

bi,k+` + bp−1−`g(k),k

i=0

and
ai,k+` = bi,k+` + bi−`g(k),k + ap−1,k+`
DRAFT

March 12, 2018

SUBMITTED PAPER

27

for ` = fλ +1−k, . . . , fλ +γ −k and i = 0, 1, . . . , p−2. When λ = 0, we only need to transform
the bits for ` = 1, . . . , γ − 1 and i = 0, 1, . . . , p − 2, as column k of EVENODD(p, k, r) is the
same as column k of RDP(p, k, r). Then we employ the Blaum-Roth decoding method to obtain
the erased γ information columns of EVENODD(p, k, r). Lastly, we recover δ parity columns
by (5). The decoding complexity is then
γ(k + γ)p + (3γ 2 + 3.5γ)p + γ 2 − 0.5γ + δ(kp − 2k) − 3 for λ > 0,
γ(k + γ)p + (3γ 2 + 3.5γ − 3)p + γ 2 − 3.5γ + δ(kp − 2k) + 3 for λ = 0.
Note that we can recover the erased parity columns by encoding the parity bits according
to the definition for both EVENODD(p, k, r) and RDP(p, k, r) after recovering all the erased
information bits. Therefore, the main difference of the decoding complexity between the proposed
LU decoding method and the Blaum-Roth decoding method lies in the complexity of decoding the
Vandermonde linear system, i.e., the erasure decoding of information failures. In the following,
we consider a special case where δ = 0. We evaluate the decoding complexity of γ information

30

# of XORs/information bits

# of XORs/information bits

erasures for the proposed LU decoding method and the Blaum-Roth decoding method.

RDP(p,p−1,4) (Blaum−Roth method)
EVENODD(p,p,4) (Blaum−Roth method)
RDP(p,p−1,4) (Algorithm 1)
EVENODD(p,p,4) (Algorithm 1)

25
20
15
10
5
10

20

30
40
Parameter p

50

(a) r = 4 and p ranges from 5 to 59.

60

40

RDP(p,p−1,5) (Blaum−Roth method)
EVENODD(p,p,5) (Blaum−Roth method)
RDP(p,p−1,5) (Algorithm 1)
EVENODD(p,p,5) (Algorithm 1)

30
20
10
10

20

30
40
Parameter p

50

60

(b) r = 5 and p ranges from 5 to 59.

Fig. 1: The normalized decoding complexity of γ = r information erasures EVENODD(p, p, r)
and RDP(p, p − 1, r) by Algorithm 1 and by Blaum-Roth decoding method for r = 4, 5.
For fair comparison, we let k = p for EVENODD(p, k, r) and k = p−1 for RDP(p, k, r). According to Lemma 11, the decoding complexity of γ information erasures of EVENODD(p, p, r)
and RDP(p, p − 1, r) by Algorithm 1 is
p(γp +

March 12, 2018

γ 2 5γ 1
3γ 2 5γ 1
−
− )−
−
+ , and
4
4
2
4
4
2
DRAFT

28

IEEE TRANSACTIONS ON COMMUNICATIONS

p(γ(p − 1) +

3γ 2 5γ 3
γ 2 5γ 7
−
− )−
−
+ ,
4
4
2
4
4
2

respectively.
When r = 4 and 5, the normalized decoding complexity of γ = r information erasures of
EVENODD(p, p, r) and RDP(p, p−1, r) by Algorithm 1 and by Blaum-Roth decoding method is
shown in Fig. 1. One can observe that EVENODD(p, p, r) and RDP(p, p − 1, r) decoded by LU
decoding method is more efficient than by the Blaum-Roth decoding method. When r = 4 and
p ranges from 5 to 59, the decoding complexity of EVENODD(p, p, 4) and RDP(p, p − 1, 4)
by Algorithm 1 has 20.1% to 71.3% and 22.7% to 77.7% reduction on that by the BlaumRoth decoding method, respectively. When r = 5, the complexity reduction is 20.4% to 68.5%
and 25.7% to 78.5% for EVENODD(p, p, 5) and RDP(p, p − 1, 5), respectively. The reduction
increases when p is small and r is large. For example, RDP(p, p − 1, r) decoded by Algorithm 1
has 78.5% less decoding complexity than that by the Blaum-Roth decoding method when p = 5
and r = 5.
The reasons that the decoding complexity of EVENODD(p, p, r) and RDP(p, p − 1, r) by the
LU decoding method is less than that by the Blaum-Roth decoding method are summarized as
follows. First, the Blaum-Roth decoding method is operated over the ring F2 [x]/Mp (x); however,
we show that the Vandermonde linear systems over F2 [x]/Mp (x) can be computed by first solving
the Vandermonde linear systems over Rp and then reducing the results by Mp (x) modulus.3 The
operation of multiplication and division over Rp is more efficient than that over F2 [x]/Mp (x).
Second, the proposed LU decoding method is more efficient than the Blaum-Roth decoding
method.
VIII. D ISCUSSION AND C ONCLUSIONS
In this paper, we present a unified construction of EVENODD codes and RDP codes, which
can be viewed as a generalization of extended EVENODD codes and generalized RDP codes.
Moreover, an efficient LU decoding method is proposed for EVENODD codes and RDP codes,
and we show that the LU decoding method requires less XOR operations than the existing
algorithm when more than three information columns are failure.
In most existing Vandermonde array codes, the parity bits are computed along some straight
lines in the array, while the parity bits of the proposed EVENODD codes and RDP codes are
3

When there are only information erasures, modulo Mp (x) is not needed in the decoding procedure.

DRAFT

March 12, 2018

SUBMITTED PAPER

29

computed along some polygonal lines in the array. By this generalization, EVENODD codes
and RDP codes may have more design space for decoding algorithm when there is a failure
column. For example, assume that the first column of EVENODD(5, 3, 3; (0, 1, 4)) in Table I
is erased, we want to recover the erased column by downloading some bits from other four
surviving columns. We can recover bits a0,0 , a2,0 by
a0,0 = a0,1 + a0,2 + a0,3 , a2,0 = a2,1 + a2,2 + a2,3 ,
and bits a1,0 , a3,0 by
a1,0 = a0,1 + a2,2 + a4,4 + a1,4 , a3,0 = a2,1 + a4,4 + a3,4 ,
where a4,4 can be computed as a4,4 = a3,1 + a0,2 . In total, 9 bits are downloaded to recover
the first column. For original EVENODD codes, an erased information column is covered by
downloading at least 0.75(p−1) bits from each of the helped k +1 columns [10]. Hence, the total
number of bits to be downloaded to recover the first column of original EVENODD codes is at
least 12. Therefore, one may design a decoding algorithm for an information failure such that
the number of bits downloaded is less than that of the original EVENODD codes. Designing an
algorithm to recover a failure column for general parameters is then an interesting future work.
R EFERENCES
[1] D. A. Patterson, P. Chen, G. Gibson, and R. H. Katz, “Introduction to Redundant Arrays of Inexpensive Disks (RAID),”
in Proc. IEEE COMPCON, vol. 89, 1989, pp. 112–117.
[2] P. M. Chen, E. K. Lee, G. A. Gibson, R. H. Katz, and D. A. Patterson, “RAID: high-performance, reliable secondary
storage,” University of California at Berkeley, Berkeley, Tech. Rep. CSD 03-778, 1993.
[3] M. Blaum, J. Brady, J. Bruck, and J. Menon, “EVENODD: An efficient scheme for tolerating double disk failures in RAID
architectures,” IEEE Trans. Computers, vol. 44, no. 2, pp. 192–202, 1995.
[4] P. Corbett, B. English, A. Goel, T. Grcanac, S. Kleiman, J. Leong, and S. Sankar, “Row-diagonal parity for double disk
failure correction,” in Proc. of the 3rd USENIX Conf. on File and Storage Technologies (FAST), 2004, pp. 1–14.
[5] A. H. Leventhal, “Triple-parity RAID and beyond,” Comm. of the ACM, vol. 53, no. 1, pp. 58–63, January 2010.
[6] M. Blaum, J. Bruck, and A. Vardy, “MDS array codes with independent parity symbols,” IEEE Trans. Information Theory,
vol. 42, no. 2, pp. 529–542, 1996.
[7] A. Goel and P. Corbett, “RAID triple parity,” in ACM SIGOPS Operating Systems Review, vol. 36, no. 3, December 2012,
pp. 41–49.
[8] M. Blaum, “A family of MDS array codes with minimal number of encoding operations,” in IEEE Int. Symp. on Inf.
Theory, 2006, pp. 2784–2788.
[9] M. Blaum, J. Brady, J. Bruck, J. Menon, and A. Vardy, “The EVENODD code and its generalization: An effcient scheme for
tolerating multiple disk failures in RAID architectures,” in High Performance Mass Storage and Parallel I/O. Wiley-IEEE
Press, 2002, ch. 8, pp. 187–208.

March 12, 2018

DRAFT

30

IEEE TRANSACTIONS ON COMMUNICATIONS

[10] Z. Wang, A. G. Dimakis, and J. Bruck, “Rebuilding for array codes in distributed storage systems,” in IEEE GLOBECOM
Workshops (GC Wkshps), 2010, pp. 1905–1909.
[11] L. Xiang, Y. Xu, J. Lui, and Q. Chang, “Optimal recovery of single disk failure in RDP code storage systems,” in ACM
SIGMETRICS Performance Evaluation Rev., vol. 38, no. 1.

ACM, 2010, pp. 119–130.

[12] L. Xiang, Y. Xu, J. C. S. Lui, Q. Chang, Y. Pan, and R. Li, “A hybrid approach of failed disk recovery using RAID-6
codes: Algorithms and performance evaluation,” ACM Trans. on Storage, vol. 7, no. 3, pp. 1–34, October 2011.
[13] Y. Zhu, P. P. C. Lee, Y. Xu, Y. Hu, and L. Xiang, “On the speedup of recovery in large-scale erasure-coded storage
systems,” IEEE Transactions on Parallel & Distributed Systems, vol. 25, no. 7, pp. 1830–1840, 2014.
[14] C. Huang and L. Xu, “STAR: An efficient coding scheme for correcting triple storage node failures,” IEEE Trans.
Computers, vol. 57, no. 7, pp. 889–901, 2008.
[15] H. Jiang, M. Fan, Y. Xiao, X. Wang, and Y. Wu, “Improved decoding algorithm for the generalized EVENODD array
code,” in International Conference on Computer Science and Network Technology, 2013, pp. 2216–2219.
[16] Y. Wang, G. Li, and X. Zhong, “Triple-Star: A coding scheme with optimal encoding complexity for tolerating triple disk
failures in RAID,” International Journal of innovative Computing, Information and Control, vol. 3, pp. 1731–1472, 2012.
[17] Z. Huang, H. Jiang, and K. Zhou, “An improved decoding algorithm for generalized RDP codes,” IEEE Communications
Letters, vol. 20, no. 4, pp. 632–635, 2016.
[18] H. Hou, K. W. Shum, and H. Li, “On the MDS condition of Blaum-Bruck-Vardy codes with large number parity columns,”
IEEE Communications Letters, vol. 20, no. 4, pp. 644–647, 2016.
[19] M. Blaum and R. M. Roth, “New array codes for multiple phased burst correction,” IEEE Trans. Information Theory,
vol. 39, no. 1, pp. 66–77, January 1993.
[20] Q. Guo and H. Kan, “On systematic encoding for Blaum-Roth codes,” Development, vol. 42, no. 4, pp. 2353–2357, 2011.
[21] ——, “An efficient interpolation-based systematic encoder for low-rate Blaum-Roth codes,” in IEEE Int. Symp. on Inf.
Theory, 2013, pp. 2384–2388.
[22] K. W. Shum, H. Hou, M. Chen, H. Xu, and H. Li, “Regenerating codes over a binary cyclic code,” in Proc. IEEE Int.
Symp. Inf. Theory, Honolulu, July 2014, pp. 1046–1050.
[23] H. Hou, K. W. Shum, M. Chen, and H. Li, “BASIC codes: Low-complexity regenerating codes for distributed storage
systems,” IEEE Transactions on Information Theory, vol. 62, no. 6, pp. 3053–3069, 2016.
[24] S. T. J. Fenn, M. G. Parker, M. Benaissa, and D. Taylor, “Bit-serial multiplication in GF(2m ) using irreducible all-one
polynomials,” IEEE Proceedings on Computers and Digital Techniques, vol. 144, no. 6, pp. 391–393, 1997.
[25] J. H. Silverman, “Fast multiplication in finite fields GF(2n ),” in International Workshop on Cryptographic Hardware and
Embedded Systems, 1999, pp. 122–134.
[26] H. Hou and Y. S. Han, “A new construction and an efficient decoding method for Rabin-Like codes,” IEEE Transactions
on Communications, pp. 1–1, 2017.
[27] H. Hou, K. W. Shum, M. Chen, and H. Li, “New MDS array code correcting multiple disk failures,” in Global
Communications Conference, 2014, pp. 2369–2374.
[28] S.-L. Yang, “On the LU factorization of the Vandermonde matrix,” Discrete applied mathematics, vol. 146, no. 1, pp.
102–105, 2005.
[29] P. Subedi and X. He, “A comprehensive analysis of XOR-based erasure codes tolerating 3 or more concurrent failures,”
in IEEE 27th International Parallel and Distributed Processing Symposium Workshops & PhD Forum (IPDPSW), 2013,
pp. 1528–1537.

DRAFT

March 12, 2018

