Asymptotically MDS Array BP-XOR Codes
Şuayb Ş. Arslan

arXiv:1709.07949v1 [cs.IT] 22 Sep 2017

Department of Computer Engineering
MEF University
Maslak, Istanbul 34099
Email: arslans@mef.edu.tr

Abstract—Belief propagation or message passing on binary
erasure channels (BEC) is a low complexity decoding algorithm
that allows the recovery of message symbols based on bipartite
graph prunning process. Recently, array XOR codes have attracted attention for storage systems due to their burst error
recovery performance and easy arithmetic based on Exclusive
OR (XOR)-only logic operations. Array BP-XOR codes are a
subclass of array XOR codes that can be decoded using BP under
BEC. Requiring the capability of BP-decodability in addition
to Maximum Distance Separability (MDS) constraint on the
code construction process is observed to put an upper bound
on the maximum achievable code block length, which leads to
the code construction process to become a harder problem. In
this study, we introduce asymptotically MDS array BP-XOR
codes that are alternative to exact MDS array BP-XOR codes
to pave the way for easier code constructions while keeping
the decoding complexity low with an asymptotically vanishing
coding overhead. We finally provide and analyze a simple code
construction method that is based on discrete geometry to fulfill
the requirements of the class of asymptotically MDS array BPXOR codes.

I. I NTRODUCTION
Array codes are linear codes defined for two dimensional
data structures that are defined by both data and parity values
organized in a matrix form. These codes are quite attractive
candidates for burst error recovery in communication and
distributed storage systems [1] and provide data reliability
with optimal time/space consumption using Maximum Distance Separability (MDS) constraint in the code construction
process. Moreover, a great deal of work has been done and
many improvements have been proposed for these codes over
the years [2] to secure simpler math and low-complexity
computations while still maintain the MDS property.
Typically, any linear code can be represented using a
bipartite graph either using the parity check matrix or the
generator matrix of the code [3]. Using the generator matrix
representation, the corresponding bipartite graph has two types
of nodes: Nodes that are used to decode (check or coded
nodes) and nodes that are decoded (information nodes). Nodes
in bipartite graph representation are connected with edges to
represent node adjacency. The neighbors of node j (neighbor
set), denoted by Nj , is the set of all nodes connected to
node j. The cardinality of the neighbour set is called the
degree of node j. The Belief Propagation (BP) algorithm a.k.a.
message passing algorithm is an iterative process (updating
nodes and edges) to decode data from coded nodes over
symmetric erasure channels using the bipartite representation

of the code. At the onset of the BP algorithm, we begin by
setting all the contents of information nodes to NULL that
need to be decoded. Then, we look for a degree-one coded
node and copy the content to its neighbor information node
by replacing NULL. Next, we update all the coded nodes that
are connected to the this neighbor and eliminate the edges that
established neighborhood relationship. This completes the first
step, and in the next iteration we continue applying the same
methodology until there remains no information node with
NULL content. If algorithm stops prematurely during iteration,
we claim a decoding failure, otherwise we report a decoding
success.
Array codes have recently been studied under BP decoding
[9] and useful upper bounds are derived in [6] that theoretically
establishes the relationship between the block length (and
hence the rate of the code), decodability and sparsity of the
generator matrix i.e., the encoding/decoding complexity of
the code. In this study, we shall demonstrate by relaxing the
MDS constraint on the code construction process, we can also
dramatically relax the previously found bounds on the code
block length [6] while keeping low complexity BP algorithm
successfully decode the whole data block. Such an observation
shall yield easier and more powerful code constructions. For
instance, we shall consider one of the discrete geometry
based codes known as Mojette codes that are recently studied
within the context of low density parity check codes and
are shown to reduce the node repair complexity [10]. In our
study, we demonstrate an asymptotically MDS BP-XOR code
construction method based on Mojette geometry. By providing
and establishing an appropriate set of code parameters, we
explicitly construct codes that fulfills the desired theoretical
requirements.
The rest of the paper is organized as follows. In Section II,
we provide the basics of array MDS BP-XOR codes and give
some known results as well as state the main result of the paper. In Section III, we provide a discrete geometry construction
of an asymptotically-MDS array BP-XOR codes. In Section
IV, we validate our theoretical results by numerically plotting
rate, code block length for discrete geometry construction.
Finally, we conclude our paper in Section V.
II. A SYMPTOTICALLY MDS A RRAY BP-XOR C ODES
Before defining the class of asymptotically MDS array BPXOR codes, let us provide the conventional definition of MDS
BP-XOR codes using the notation of reference [6].

A. Background
Let l be the symbol size in bits and M = {0, 1}l be the
symbol set from which we select our information as well
as coded symbols. The fundamental operation we use is the
Exclusive OR (XOR) that is used to add symbols logically bit
by bit in binary domain. In our study, nodes represent blocks
of data that contains one or more symbols in it. Symbols are
the smallest data unit over which XOR operations are defined.
An [n, k, t, b] array BP-XOR code is a b×n two dimensional
rate r = k/n binary linear code C = [ai,j ]1≤i≤b,1≤j≤n in
which the coding symbol ai,j ∈ M is the XOR of a subset
of source symbols I = {v1 , . . . , vbk }, typically structured as
a b × k data matrix, and I can be reconstructed from any
n − t columns of the linear code C using BP algorithm for
an appropriate integer t ≤ n − k. The degree of a coded
symbol ai,j , denoted as σi,j , is the number of information
symbols that participate in logical XOR operation i.e., ai,j =
vz1 ⊕ · · · ⊕ vzσi,j such that vzs ∈ I for all s ∈ {1, . . . , σi,j }. A
t-erasure correcting array BP-XOR code is MDS if the source
symbols can be reconstructed from k = n − t columns of C.
For a given positive integer b0 satisfying b0 > b,
a [n, k, t, b, b0 ] asymptotically MDS array BP-XOR code
C a is a linear code with i-th column (yi,1 , . . . , yi,bi ) =
(x1 , . . . , xbk )Gi for a bk × bi P
generator matrix Gi , i ∈
{1, . . . , n} such that b0 = (1/n) P
i bi . Thus, the generator
matrix for C a is given by the bk × i bi matrix,
GC a = [G1 |G2 | . . . |Gn ].

(1)

What makes this code asymptotically MDS is that it is
possible to perfectly reconstruct user data matrix I from
any k column combinations of C a using BP decoding and
as b → ∞ we have b0 → b. Note that the raw source
data need not be in standard b × k form. For any positive
integer g satisfying b|g and k|g, the generator matrix GC a
should work fine for different arrangements of the data block
matrix such as b/g × kg. We finally note that the code C a
is not in two dimensional standard rectangle form as in C.
However, we introduced another parameter b0 to be able to
make asymptotically MDS array BP-XOR codes analogous to
standard MDS array codes defined over rectangle shape binary
matrices.
For a given fixed code rate r and n, let us define (b, n)
to be the maximum coding overhead1 of C a satisfying b0 =
(1 + (b, n))b. The asymptotically optimal overhead property
implies that as (b, n) → 0 we have b → ∞.
Letting σ denote the maximum check node degree of a given
array BP-XOR code, we note from [6] that if k = σ it is not
hard to show that
n

≤ kb + 1 + max{k − 3, 0}

(2)

the upper bound of which can be arbitrarily large (i.e., for b 
1) and allow any arbitrarily small r to be possible. However,
1 Since columns of C a may have different sizes, the overhead depends
on which k columns are used for reconstruction. Also note that the coding
overhead also depends on the number of columns n in the code, so called
array code blocklength.

for k > σ it is observed that the array code blocklength n is
upper bounded based on a specific choice of k [6]. In addition,
we observe from the same study that for b  1 and large
enough k i.e., k > σ 2 we have n ≤ k + σ − 1. This also
implies that for large enough information block length k, the
achievable rate will be close to 1, putting a constraint on the
code design rate.

B. Main Result
We begin with providing the following theorem that sets the
necessary condition/s on the parameters for the existence of
asymptotically MDS array BP-XOR codes.
Theorem 2.1. Let C a be a [n, k, t, b, b0 ] asymptotically MDS
array BP-XOR code such that the maximum coded node degree
satisfies 2 < σ < (bk − 1)/(b0 − 1). Then, we have
n ≤

k+σ−1+
(3)


0
0
b(k(σ − σ) + (σ − 1)σ ) − (σ − 1)(3σ/2 − 1)
b(k − σ 0 ) + σ − 1

where σ 0 = σ(1 + (b, n)) and (b, n) is the coding overhead.
Proof. Since the code is assumed to be MDS, i.e., able to
tolerate n−k column erasures of C a , each information symbol
vs ∈ I must appear in at least n − k + 1 columns, totaling up
to
kb(n − k + 1)

(4)

minimum appearances in C a . On the other hand, belief propagation decoding starts decoding from degree-one encoding
symbols. So we need at least n − k + 1 degree-one symbols
in distinct columns of C a (in the worst case of n − k column
erasures when each may comprise one degree-one symbol).
Similarly, we need at least one degree-two, one degree-three,
. . . , one degree-(σ − 1) coding symbols to make sure that BP
decoding continues. Although it is possible to have multiple
degree-two symbols and continue BP decoding, by this choice
we are trying to maximize the appearance of information symbols in C a . Note that if these symbols happen to be in distinct
unerased columns, the bound could be tightened, otherwise
the bound might still be loose for instance if σ > k + 1 which
is not usually typical. The rest of the b0 n − (n − k + σ − 1)
can have at most σ degree. Thus, C a can have at most
σ(b0 n − (n − k + σ − 1)) + n − k +

σ(σ − 1)
2

(5)

appearances of kb information symbols. So we have the
inequality (4) ≤ (5). We can rewrite (5) in a more compact
form as
σb0 n − (σ − 1)(n − k + σ/2)

(6)

Using equation (4), and assuming we have b(k − σ 0 ) + σ −
1 > 0, we can collect all terms that includes n and find an
upper bound on n as follows,


(kb + σ − 1)(k − 1) − (σ − 1)(σ/2 − 1)
n ≤
(7)
b(k − σ 0 ) + σ − 1
= k+σ−1+
(8)


b(k(σ 0 − σ) + (σ − 1)σ 0 ) − (σ − 1)(3σ/2 − 1)
b(k − σ 0 ) + σ − 1
where σ 0 = σ(1 + (b, n)).



Note that if b → ∞ we will have σ 0 → σ and hence equation
(7) becomes identical to equation (2) of [6] except the term
(σ − 1)(σ/2 − 1). This term is essentially what makes the
upper bound improved (tighter).
There are two cases that are interesting to consider for
understanding the asymptotical performance. First, if b tends
large we will have σ 0 → σ. Hence,


(σ − 1)σ
− 1(k−σ)|(σ−1)σ
n ≤ k+σ−1+
k−σ
where 1A is logical one if A is true, otherwise it is zero. This
indicator function is used due to the flooring operation and σ
only equals to σ 0 in the limit. Thus, if the code becomes array
MDS in the limit, there remains no dependence of n on b. On
the otherhand, if we let large but fixed b ≤ k, and if k gets
large, we shall have
n ≤
=

0

k+σ −1
k + σ(1 + (b, n)) − 1

(9)

which can be made arbitrarily large if we choose (b, n) → ∞
for a fixed b and large n. This essentially demonstrates that
as the array BP-XOR code becomes near-optimal in terms of
recovery performance, the upper bound on the number of code
columns n can dramatically be improved.
Although the desirable properties of the coding overhead are
found, we still need specific constructions to quantify or bound
the coding overhead and hence present tighter bounds on n
(and r) for a specific construction. Based on this observation,
we shall present a code construction method that uses the
result of Theorem 2.1 and has an appropriate (b, n) with the
properties as summarized below.
• For fixed k and rate r (i.e., fixed n), as b → ∞ we have
vanishing coding overhead, (b, n) → 0.
• For fixed b and rate r, as n → ∞ we have a diverging
coding overhead, (b, n) → ∞.
III. D ISCRETE G EOMETRY C ONSTRUCTIONS OF
A SYMPTOTICALLY-MDS ARRAY BP-XOR CODES
In this section, we will introduce a particular construction of
asymptotically MDS array BP-XOR codes based on discrete
geometry [5] and show that they can be regarded as a special
type of the class of asymptotically MDS BP-XOR codes.
The discrete geometry construction is known as Mojette
codes which are based on discrete version of Radon Transform

Fig. 1. A simple illustration of the projection concept and Mojette coding.

[4], and can be used to generate redundancy not just for rectangle two dimensional data grid but also for any convex data
grid. In our study, we consider matrix (rectangle) data and let
encoder compute a linear set of projections at angles specified
by a couple of coprime integers (p, q) from a b × k discrete
data structure f : (z, l) → N. Suppose that we generate n
projections with parameters {(pi , qi ), 0 ≤ i ≤ n − 1}. The
length of the projection i, denoted by bi , is a function of the
number of projections n, the angle parameters (pi , qi ) and the
data grid size b × k. It can be expressed in a closed form as
follows [5],
bi = |pi |(k − 1) + |qi |(b − 1) + 1

(10)

Note that in this construction, generated projections can be
treated as the columns of the asymptotically-MDS BP-XOR
code. An example code with parameters k = 3, b = 4 with n =
3 projections with parameters (−1, 1), (1, 0), (1, 1) is shown
in Fig. 1. Each bin or symbol of the i-th projection, based on
(pi , qi ), can be computed as given by the following compact
formulation
M(pi ,qi ) f (m + (b − 1)qi u(qi ) + (k − 1)pi u(pi ))
=

k−1
b−1 M
M

f (z, l)δm+zqi +lpi

(11)
(12)

z=0 l=0

for all m values satisfying the inequality,
−(b − 1)qi u(qi ) − (k − 1)pi u(pi )
≤m≤
bi − (b − 1)qi u(qi ) − (k − 1)pi u(pi ) − 1
L

where
stands for Boolean XOR operation, u(.) is the
discrete unit function and δi is Kronecker delta function which
are given by
(
(
1, if s > 0
0, if i 6= 0
u(s) =
, δi =
0, Otherwise
1, if i = 0
Mojette codes can be decoded using BP algorithm and the
exact reconstruction of user data matrix is possible if the projection parameters (pi , qi ) are selected judiciously according
to the following Katz criterion.

n−1
X
i=0

|pi | ≥ b or

n−1
X

|qi | ≥ k

(13)


Theorem 3.4. For the Mojette code with parameters as given
in Construction 3.3, for b  1, we have

i=0

Proof. The proof can be found in [7].

P

|qi | = k. If we use the coprime integers as given by
the Construction 3.3, we have qi never equal to zero and
σi = min{db/d(n − 1)/2e, k}. We note that we have σ = k
for b  1. We next quantify the coding overhead for this
particular construction and show the asymptotically optimal
property.

Theorem 3.1. For a given asymptotically-MDS BP-XOR code
defined by n projections with parameters (pi , qi ) on a b × k
data matrix, exact data reconstruction is possible using iterative BP if

According to Theorem 2.1, the maximum degree of the
coded symbols play key role in the attainable block length of
the BP-XOR codes. Thus, next we find the maximum degree
number in the case of Mojette transform codes and see that this
parameter can be adjusted based on the selection of projection
parameters (pi , qi ). The following theorem quantifies this
number.
Theorem 3.2. Let us use σi , i ∈ {1, 2, . . . , n} to denote
the maximum degree of the ith projection with parameters
(pi , qi ). We have σi = min{db/|pi |e, dk/|qi |e} and hence
σ = maxi {σi }.
Proof. Considering the equation (12) and the worst case
scenario, we would like to find the number of l and z values
such that zqi + lpi = −m. It is not hard to see that the
maximum number of z values that can satisfy this equation
is given by dk/|qi |e due to 0 ≤ z ≤ k − 1. Similarly, the
maximum number of l values that can satisfy this equation
is given by db/|pi |e due to 0 ≤ l ≤ b − 1. Since the
number of possibilities for z and l are also constrained by
the two dimensional rectangular shape, we have the maximum
encoding symbol degree equal to the minimum of the two i.e.,
σi = min{db/|pi |e, dk/|qi |e}. Thus, the maximum degree of
all the code symbols is given by the maximum degree of all
the projections i.e., σ = maxi {min{db/|pi |e, dk/|qi |e}}. 
Next, we quantify the coding overhead for Mojette transform based asymptotically MDS BP-XOR codes by considering k = σ and k > σ cases separately.
A. Case k = σ
First of all, note that depending on the choices of (pi , qi ),
the code overhead as well as the maximum degree of the code
can change. Although, there are multiple choices for k = σ,
we provide the typical choice below that also ensures block
length.
Construction 3.3. Let us consider the following choice of
coprime integers,



 
n−1
n−1
, . . . , −1, 0, 1, 2, . . . ,
qi = 1, pi ∈ T = −
2
2
(14)

(b, n) ≈

n(2 − r)(nr − 1)
4b

(15)

where r is the fixed rate of the array BP-XOR code.
Proof. See appendix A the proof of this theorem.



For fixed r and k (i.e., fixed n), if b → ∞ then it is
clear that (b, n) → 0 proving the asymptotical property. On
the other hand, for fixed r and b, if n → ∞ then we have
(b, n) → ∞. In fact, it is not hard to see that (b, n) = O(n2 ).
Therefore, due to these desirable properties of the overhead
and considering the inequality (9), we can make n arbitrarily
large. Particularly we can find the following lower bound on
n for k = rn = σ and r > 0.5,


n(2 − r)(nr − 1)
−1
(16)
n ≤ rn + rn 1 +
4b
which yields the inequality
n3 r2 (2 − r)
⇒n≥
n − 2nr ≤
4b

s

4b(1 − 2r)
r2 (2 − r)

(17)

This final lower bound shows that the value for the block
length n can be arbitrarily large for judiciously selected large
b. Note that the case k = σ has the least constraint on the
code block length for any MDS array BP-XOR code. The
case k > σ is more interesting for the class of asymptotically
MDS array BP-XOR codes.
B. Case k > σ
With classical array BP-XOR codes, the block length n is
constrained by the following upper bound for b  1,


σ(σ − 1)
n≤k+σ−1+
− 1(k−σ)|(σ−1)σ
(18)
k−σ

where T is known as canonical enumeration of integers [8]
that goes with the name A007306 and satisfies gcd(pi , qi ) = 1
for i = 0, . . . , n − 1.

which is the same for asymptotically MDS array BP-XOR
codes as mentioned in Section II. However, as the block length
gets large as well, we shall no longer have constraints on the
size of the block length for asyptotically MDS BP-XOR codes.
Next, we provide another set of parameters for Mojette code
that shall satisfy k > σ. The possibilities of the pair (pi , qi )
selection for making k > σ is not unique. We will consider
the typical class as given in construction 3.5.

Note that this construction satisfies the Katz criterion simply
because collecting any k projections will lead us to have

Construction 3.5. Let us consider the following choice of
coprime integers for n projections,

Existance of rate 5/6 MDS array BP-XOR Codes

4000

qi = qe > 0,
pi ∈ U = {d−n + 1eodd , . . . , −1, 1, 3, . . . , dn − 1eodd }
(19)

20
3000
10

where qe is a positive even number, and d.eodd rounds to the
next biggest odd integer of the argument, respectively.

2500

n

Note that using construction 3.5, it is easy to verify that
we have GCD(pi , qi ) = 1. Also, we have k > σ =
maxi {min{db/|pi |e, dk/|qi |e}} = dk/qe e. It is of interest to
quantify the coding overhead to be able to find the upper
bounds on the code block length.

20

30

2000

1000
500
0

(n, b) ≈
(20)




dk/qe e
dk/qe e
(k − 1) n −
+ (b − 1)qe + 1 − 1
kb
2

0

500

1000

k

1500

2000

Fig. 2. Upper bounds on n as a function of k for b = 10000.

where qe is a positive even number, and d.eodd rounds to the
next biggest odd integer of the argument, respectively.

Existance of rate 3/4 MDS Array BP-XOR Codes

4500



40

Upper bound on n (classical)
Upper bound on n (asym)
Required n

4000 30
3500 20
3000 10

10

20

30

2500

n

Note that as long as qe |k, we have  → 0 for large b
demonstrating the asymptotically optimal overhead property.
Similarly, for fixed r and b, if n → ∞ then we have
(n, b) → ∞ satisfying the second desirable property.
Finally, using equation (9) we can express the upper bound
on n as follows,




dk/qe e
σdk/qe e
n ≤ k+
(k − 1) n −
+ (b − 1)qe + 1 −1
kb
2
(21)
Since it is hard to see that with this result we improve the
upper bounds on the code block length, in the next section, we
provide some numerical results that compute the upper bounds
for comparison.

10

1500

Theorem 3.6. For the Mojette code with parameters as given
in construction 3.5, for b  1, we have

Proof. See appendix B for the proof of this theorem.

Upper bound on n (classical)
Upper bound on n (asym)
Required n

30

3500

2000
1500
1000
500
0

0

500

1000

k

1500

2000

IV. N UMERICAL R ESULTS

Fig. 3. Upper bounds on n as a function of k for b = 10000.

Let us consider qe = 2 and a large b value, such as
b = 10000 (this choice is completely arbitrary) and compare
the upper bounds on n with using classical MDS array BPXOR codes and their asymptotically optimal version proposed
in our study, abbreviated as AMDS. We present results in
Fig.1, Fig. 2 and Fig. 3 each corresponding to three different
rates 5/6, 3/4, 1/2, respectively as example use cases. These
results demonstrate that as the code rate decreases, classical
MDS array BP-XOR codes are only possible for very small
values of k. On the other hand, although the same is true
for asymptotically MDS BP-XOR codes for small k, it is
also observed that for large enough k our bounds are bigger
than the required n (fixed by the code rate), allowing possible
constructions to achieve the corresponding rate asymptotically
MDS array BP-XOR code such as Mojette construction we
have provided in previous sections. These figures also present
the upper bound behavior for small k on the left corner of

each plot. Plots include a curve “Required n” to denote the
required value for n for the corresponding rate r = k/n code.
In order to see clearly the range of rates that are possible
with both constructions, Fig. 5 depicts the minimum rate that
is possible as a function of the assumed rate. Note that with
asymtotically MDS array BP-XOR codes, the upper bound
on n depends on the coding overhead which is a function of
rate of the code. Thus, the minimum code rate changes as
the assumed code rate changes. For each assumed rate, we
calculate the upper bound and then compute the minimum
code rate possible. With respect to classical MDS BP-XOR
codes, since the upper bound does not change with varying
assumed rate (since the coding overhead is always zero), the
curves turns out to be flat.
According to Fig. 5, the region that lies above the curves

V. C ONCLUSION

Existance of rate 1/2 MDS Array BP-XOR Codes

18000

60

Upper bound on n (classical)
Upper bound on n (asym)
Required n

16000
40

Array BP-XOR codes are attractive data protection schemes
for low-complexity and optimal reliability. Their finite versions
are shown to have limitations on the maximum block length
when the coding symbol degree is particularly lower than the
data size. We have shown in this study, this limitation can
greatly be relaxed by extending the original optimal class
to asymptotically optimal class. We have also have shown
one particular code construction based on discrete geometry
that satisfies all the requirements of being asymptotically
MDS array BP-XOR codes. These codes can be encoded
and decoded in linear time with the block length and the
achievable bound on the block length is far from that of the
finite counterpart.

14000
20
12000

10

20

30

n

10000
8000
6000
4000
2000
0

0

500

1000

1500

k

2000

A PPENDIX A
P ROOF OF T HEOREM 2.4

Fig. 4. Upper bounds on n as a function of k for b = 10000.

Let us start by defining the following utility function,
ϕ(x) =

j x k j x k
2

2

+1



for x ≥ 0.

(22)

minimum rate possible (min_rate)

1

Also let It = {0, 1, . . . , t − 1}. Using these definitions, we
state the following lemma next.
Lemma
For the projection set given as in (14), we have
PA.1:
t−1
the sum i=0 |pi | that can be expressed in a closed form using
the utility function

0.8

0.6

0.4

X

0.2

0

i∈It

MDS array (k=10)
AMDS array (k=10)
MDS array (k=1000)
ass_rate = min_rate
AMDS array (k=1000)

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1

assumed rate (ass_rate)

Fig. 5. Upper bounds on n as a function of k for b = 10000.

are the possibilities of the code rate. However, there is no
guarantee each and every assumed rate would be achievable.
However, as can be seen as k gets large it becomes impossible
to construct classical MDS array BP-XOR codes with rate
smaller than 1. In contrast, by relaxing the exact MDS condition (such as adapting asymptotically MDS constructions),
we can improve the the region of possibilities for better
achievability. With this study, we have just provided one
simple construction based on discrete geometry (with judicious
selection of parameters) that helps improve the upper bounds
on the code block length n. Other constructions may help
improve the results presented in this subsection.

1
|pi | = (ϕ(t) + ϕ(t − 1)) =
2

(

t2 −1
4 ,
t2
4,

if t is odd
if t is even

This lemma can easily be proved by considering t odd and
even casesPusing induction, separately. Note that the integer
sequence i∈It |pi | is given by A002620 [8]. Using this result,
for a given pair of projections t2 and t1 satisfying t2 > t1 ,
(t ) (t )
with the associated projection parameters (pi 2 , qi 2 = 1)
(t1 ) (t1 )
and (pi , qi = 1) selected based on construction 2.2 (14),
we can deduce that
tX
tX
2 −1
1 −1
t22 − t21 − 1
t2 − t21 + 1
(t2 )
(t )
≤
|pi | −
|pj 1 | ≤ 2
(23)
4
4
i=0
j=0

Note that since qi = 1, it is sufficient to collect k projections
for perfect reconstruction. Thus, the upper/lower bounds given
in equation (23) are particularly useful if we set t2 = n and
t1 = n − k to be able find the contributions from the largest
k projections in the sum that appears in the worst case coding
(t )
(t )
overhead expression. Let i0 be the index such that pi0 2 = p0 1
and define the set
S = {i0 , i0 + 1, . . . , i0 + n − k − 1}

(24)

The worst case coding overhead in this case is given by the
following


1  X
|pi |(k − 1) + |qi |(b − 1) + k  − 1
(n, b) =
kb
i∈It \S

(25)
=

(b − 1)k +

k−1
2

(ϕ(n) + ϕ(n − 1))
kb
− k−1
(ϕ(n
−
k) + ϕ(n − k − 1)) + k
2
+
−1
kb

Now let us assume t to be even. For this particular assumption we can rewrite
T = U0 ∪ U1 ∪ {t}

(35)

Using this observation and the result of Lemma A.1, we can
express
P
X
X
|pi | − t
|pi | = i∈T
|pi | =
(36)
2
i∈U1
i∈U0


1 (2t + 1)2 − 1
t2
=
−t =
(37)
2
4
2

(26)
which completes the proof of the lemma.
k−1
P
(ϕ(n) + ϕ(n − 1) − ϕ(n − k) − ϕ(n − k − 1)) According to Theorem 3.1, we need to have t−1
=
i=0 |qi | =
2kb
(27) tqe ≥ k. This implies t = dk/qe e projections are sufficient for
perfect reconstruction. For a given pair of projections t2 and t1
where Equation (40) follows from the conjecture Lamma 1. satisfying t > t , with the associated projection parameters
2
1
Again, using conjecture Lamma 1 and Equation (23), and
(t ) (t )
(t ) (t )
(pi 2 , qi 2 = qe ) and (pi 1 , qi 1 = qe ) selected based on
through some algebra, we can bound the worst case coding
construction 3.6, we can deduce that
overhead as follows,
tX
tX
2 −1
1 −1
t22 − t21 + 1
t22 − t21 − 1
(t1 )
(t2 )


k−1
k−1
2
2
|p
|
≤
≤
|p
|
−
(38)
j
i
2kn − k − 1 ≤ (n, b) ≤
2kn − k + 1 (28)
2
2
4kb
4kb
j=0
i=0
which can be accurately approximated for b  1 as
 k−1
k−1
(n, b) ≈
2kn − k 2 =
(2n − k)
4kb
4b
from which the result follows.

(29)

A PPENDIX B
P ROOF OF T HM .

To be able find the contributions from the largest dk/qe e
projections, we set t2 = n and t1 = n − dk/qe e. Using similar
arguments to previous appendix, we can express the worst case
coding overhead in this case as follows


1  X
(n, b) =
|pi |(k − 1) + |qi |(b − 1) + dk/qe e − 1
kb
i∈It \S

Let us start by stating the following lemma.
Lemma B.1: For the projection
Pt−1set given as in (19) with t
projections, we have the sum i=0 |pi | that can be expressed
in a closed form using the utility function
( 2
t−1
t +1
X
, if t is odd
|pi | = t22
if t is even
2,
i=0

(39)
=

(b − 1)qe dk/qe e +
−

k−1
2

k−1
2

(ϕ(n) + ϕ(n − 1))

kb
(ϕ(n − dk/qe e) + ϕ(n − dk/qe e − 1))
kb

(40)

dk/qe e
−1
(41)
kb
Using equation (38) and b  1, we can accurately approximate the worst case coding overhead as,
Ua = {d−t + 1eodd − a, . . . , −1 − a, 1 − a, . . . , dt − 1eodd − a}
(30) (n, b) ≈
(42)




dk/qe e
dk/qe e
and notice that T = U0 ∪ U1 . Since these sets are disjoint, we
(k − 1) n −
+ (b − 1)qe + 1 − 1
kb
2
have
X
X
X
X
R EFERENCES
|pi | =
|pi | +
|pi | = 2
|pi | + 1
(31)
Proof: Let us consider the sum for even and odd t separately.
First we assume t to be odd. Let us define the set

i∈T

i∈U0

i∈U1

i∈U1

Using this relationship and the result of Lemma A.1, we can
express
X
X
|pi | =
|pi | + 1
(32)
i∈U0

i∈U1

P
=
=

|pi | − 1
+1
(33)
2
1
t2 + 1
2 (φ(2t) − φ(2t − 1)) − 1
+1=
(34)
.
2
2
i∈T

+

[1] P. G. Farrell, “A survey of array error control codes,” preprint, 1990.
[2] M. Blaum and R. M. Roth, “New Array Codes for Multiple Phased Burst
Correction”, IEEE Trans. on Information Theory, 339(1):66-77, 1993.
[3] S. Lin, and D. J. Costello, Jr., Error Control Coding: Fundamentals and
Applications. Prentice-Hall. 1983.
[4] Guedon, J., Barba, D., Burger, N. “Psychovisual image coding via an
exact discrete Radon transform.” In Wu, L., ed.: Proc. Visual Communications and Image Processing 1995 (VCIP95), Taipei, Taiwan, CORESA
(1995) 562572
[5] Guedon, J. P., and Normand, N., “The Mojette transform: The first
ten years.” In Discrete Geometry for Computer Imagery, E. Andres, G.
Damiand, and P. Lienhardt, Eds., vol. 3429 of Lecture Notes in Computer
Science. Springer Berlin Heidelberg, 2005, pp. 7991.

[6] M. Paterson, D. R. Stinson and Y. Wang, On Encoding Symbol Degrees
of Array BP-XOR Codes, Submitted for publication, 2013.
[7] M.B. Katz, “Questions of uniqueness and resolution in reconstruction
from projections” In: Levin, S. (Ed.), Lecture Notes in Biomathematics,
vol. 26. Springer-Verlag, New York.
[8] The On-Line Encyclopedia of Integer Sequences. Available online:
https://oeis.org/
[9] Wang, Y., “Array BP-XOR codes for reliable cloud storage systems,” In
Proc. of IEEE ISIT 2013, pages 326330. IEEE Press (2013).
[10] S. S. Arslan, B. Parrein and N. Normand, ”Mojette transform based
LDPC erasure correction codes for distributed storage systems,” 25th
Signal Processing and Communications Applications Conference (SIU),
Antalya, Turkey, May. 2017, pp. 1-4.

