1

ML and Near-ML Decoding of LDPC Codes Over
the BEC: Bounds and Decoding Algorithms
Irina E. Bocharova, Senior Member, IEEE, Boris D. Kudryashov, Senior Member, IEEE,
Vitaly Skachek, Member, IEEE, Eirik Rosnes, Senior Member, IEEE,
and Øyvind Ytrehus, Senior Member, IEEE

arXiv:1709.01455v1 [] 5 Sep 2017

Abstract
The performance of maximum-likelihood (ML) decoding on the binary erasure channel for finite-length low-density paritycheck (LDPC) codes from two random ensembles is studied. The theoretical average spectrum of the Gallager ensemble is
computed by using a recurrent procedure and compared to the empirically found average spectrum for the same ensemble as well
as to the empirical average spectrum of the Richardson-Urbanke ensemble and spectra of selected codes from both ensembles.
Distance properties of the random codes from the Gallager ensemble are discussed. A tightened union-type upper bound on the
ML decoding error probability based on the precise coefficients of the average spectrum is presented. A new upper bound on the
ML decoding performance of LDPC codes from the Gallager ensemble based on computing the rank of submatrices of the code
parity-check matrix is derived. A new low-complexity near-ML decoding algorithm for quasi-cyclic LDPC codes is proposed and
simulated. Its performance is compared to the upper bounds on the ML decoding performance.

I. I NTRODUCTION
The binary erasure channel (BEC) is one of the simplest for analysis and consequently a well-studied communication channel
model. In spite of its simplicity, during the last decades the BEC has started to play a more important role due to the emergence
of new applications. For example, in communication networks virtually all errors occurring at the physical level can be detected
using a rather small redundancy. Data packets with detected errors can be viewed as symbol erasures.
As already mentioned, an important reason for the popularity of the BEC is that analysis of decoding performance is simpler
than for other channel models. On the other hand, it is expected that ideas and findings for the BEC might be useful for
constructing codes and developing decoding algorithms for other important communication channels, such as, for example, the
binary symmetric channel (BSC) or the additive white Gaussian noise (AWGN) channel.
A remarkable property of the BEC is that maximum-likelihood (ML) decoding of any linear code over this channel is reduced
to solving a system of linear equations. This means that ML decoding of an [n, k] low-density parity-check (LDPC) code (where
n is the code length and k is the number of information symbols) with ν erasures can be performed by Gaussian elimination
with time complexity at most O(ν 3 ). Exploiting the sparsity of the parity-check matrix of the LDPC codes can lower the
complexity to approximately O(ν 2 ) (see overview and analysis in [3] and references therein). Practically feasible algorithms
with a thorough complexity analysis can be found in [4]–[6]. This makes ML-decoded LDPC codes strong competitors for
scenarios with strong restrictions on the decoding delay. It is worth noting that ML decoding allows for achieving low error
probability at rates strictly above the so-called belief propagation (BP) decoding threshold [7]. However, ML decoding of long
LDPC codes of lengths of a few thousand bits over the BEC is still considered impractical.
Low-complexity suboptimal decoding techniques for LDPC codes over the BEC are based on the following two approaches.
The first approach consists of adding redundant rows to the original code parity-check matrix (see, for example, [8]–[10]). The
second approach applies post-processing in case of BP decoding failure [11]–[14]. In [11], [14], a post-processing step based on
the concept of guessing bits is proposed. Applying bit guessing based algorithms to the decoding of LDPC codes improves the
performance of BP decoding, but does not provide near-ML performance. A new low-complexity near-ML decoding algorithm
is presented in this paper.
A commonly used approach to the analysis of decoding algorithms is to study the performance of the algorithm applied to
random linear codes over a given channel model. Two of the most studied code ensembles are the classical Gallager ensemble
[15] and the more general ensemble presented in [7]. The Gallager ensemble is historically the first thoroughly studied ensemble
of regular LDPC codes. The ensemble in [7] can be described by random Tanner graphs with given parity-check and symbol
I. Bocharova and B. Kudryashov are with Dept. of Information Systems, St.-Petersburg University of Information Technologies, Mechanics and Optics,
St.-Petersburg, 197101, Russia (e-mail: {iebocharova, bdkudryashov}@corp.ifmo.ru).
I. Bocharova and V. Skachek are with Institute of Computer Science, University of Tartu (e-mail: {irinaboc, vitaly}@ut.ee).
E. Rosnes is with Simula@UiB, and Ø. Ytrehus is with Simula@UiB and with Dept. of Informatics, University of Bergen (e-mail: {eirik, oyvind}@ii.uib.no).
This paper was presented in part at the 9th International Symposium on Turbo Codes and Iterative Information Processing, Brest, France, September
2016 [1], and at the IEEE International Symposium on Information Theory, Aachen, Germany, June 2017 [2].
This work is supported in part by the Norwegian-Estonian Research Cooperation Programme under the grant EMP133, and by the Estonian Research
Council under the grant PUT405.
Copyright c 2017 IEEE

2

node degree distributions. We will refer to this ensemble and the LDPC codes contained in it as the Richardson-Urbanke (RU)
ensemble and RU LDPC codes, respectively. Several ensembles of regular LDPC codes are described and analyzed in [16].
It is shown in [15, Appendix B] that the asymptotic weight enumerator of random (J, K)-regular LDPC codes approaches
the asymptotic weight enumerator of random linear codes when J and K grow. In [16], it is confirmed that other ensembles of
regular LDPC codes display a similar behavior. Thus, regular ensembles are good enough to achieve near-optimal performance.
On the other hand, it is well known that both asymptotically [7] and in a finite-length regime irregular LDPC codes outperform
their regular counterparts and more often are recommended for real-life applications [17], [18]. Finite-length analysis of RU
LDPC codes under BP and (to a lesser degree) under ML decoding was performed in [19]. In this paper, we extend the analysis
of the ML decoding case for regular codes. In particular, new error probability bounds for regular codes are presented. For
general linear codes, detailed overviews of lower and upper bounds for the AWGN channel and the BSC were presented by
Sason and Shamai in their tutorial paper [20], and for the AWGN channel, the BSC, and the BEC by Polyanskiy et al. in [21]
and by Di et al. in [19].
For computing upper bounds on the error probability for LDPC codes there exist two approaches. One approach is based on
a union-type bound and requires knowledge of the code weight enumerator or its estimate. The second approach used in [19]
implies estimating the rank of submatrices of the LDPC code parity-check matrix. Notice that for infinitely long codes, the
bit error rate performance of BP decoding can be analyzed through density evolution (see e.g. [7], [22]). However, the density
evolution technique is not suitable for analysis of finite-length codes, since dependencies caused by cycles in the Tanner graph
associated with the code are not taken into account.
In this paper, first we consider a tightened union-type bound based on precise average spectra of random finite-length LDPC
codes. The difference between our approach and other techniques is the way of calculating the bound. Instead of manipulating
with hardly computable coefficients of series expansions of generating functions, we compute the spectra by using efficient
recurrent procedures. This allows for obtaining precise average weight enumerators with complexity growing linearly with the
code length. New bounds, based on computing the rank of submatrices, are derived for the RU and the Gallager ensemble of
regular LDPC codes.
As mentioned above, in this paper, we propose a decoding algorithm which provides near-ML decoding of long quasi-cyclic
(QC) LDPC block codes. The decoding complexity is polynomial in the window length, but it is linear in the code length.
It is well known that a QC LDPC block code can be represented as a tail-biting (TB) parent convolutional LDPC code.
Thereby, decoding techniques developed for TB codes are applicable to QC LDPC codes. The proposed algorithm resembles a
wrap-around suboptimal decoding of TB convolutional codes [23], [24]. Decoding of a TB code requires identification of the
correct starting state, and thus ML decoding must apply the Viterbi algorithm once for each possible starting state. In contrast,
wrap-around decoding applies the Viterbi algorithm once to the wrapped-around trellis diagram with all starting state metrics
initialized to zero. This decoding approach yields near-ML performance at a typical complexity of a few times the complexity
of the Viterbi algorithm.
The new algorithm is based on a combination of BP decoding of the QC LDPC code followed by so-called “quasi-cyclic
sliding-window” ML decoding. The latter technique is applied “quasi-cyclically” to a relatively short sliding window, where
the decoder performs ML decoding of a zero-tail terminated (ZT) LDPC convolutional code. Notice that unlike sliding-window
near-ML (SWML) decoding of convolutional codes considered in [25], the suggested algorithm working on the parent LDPC
convolutional code has significantly lower computational complexity due to the sparsity of the code parity-check matrix [26].
On the other hand, it preserves almost all advantages of the convolutional structure in the sense of erasure correcting capability.
The remainder of the paper is organized as follows. Preliminaries are given in Section II. A recurrent algorithm for computing
the average spectrum for the Gallager ensemble of binary LDPC codes is presented in Section III. Empirical average spectra
for the Gallager and RU ensembles are computed and compared to the theoretical average spectra as well as to the spectra of
selected codes in the same section. Distance properties of the Gallager ensemble are discussed in Appendix A. In Section IV,
two upper bounds on the error probability of ML decoding over the BEC are considered. The corresponding proofs are given
in Appendices B and C for the RU and the Gallager ensemble, respectively. A new algorithm for near-ML decoding for
long QC LDPC codes based on the interpretation of these codes as TB convolutional codes and using wrap-around slidingwindow decoding is proposed in Section V. Simulation results confirm the efficiency of the algorithm and are presented
in Section VI, while asymptotic density evolution thresholds which stem from the derived rank bounds are computed in
Section VII. Conclusions are presented in Section VIII.
II. P RELIMINARIES
For a binary linear [n, k] code C of rate R = k/n, let r = n−k be the code redundancy. Denote by {An,w }, w = 0, 1, . . . , n,
the code weight enumerator, where An,w is the number of codewords of weight w. By some abuse of notation, we use An,w
for both the weight enumerator of a specific code and for random weight enumerators in code ensembles.
We denote by H an r × n parity-check matrix which determines C. Random matrices H of size r × n do not necessarily
have full rank ρ = r which means that the “true” dimension of the code is equal to k 0 = n − ρ ≥ k. Following a commonly
accepted assumption we ignore the difference between k 0 and k when deriving bounds on the error probability, but we take it
into account when considering code examples.

3

Two ensembles of random regular LDPC codes are studied below. The first ensemble is the Gallager ensemble [15] of
(J, K)-regular LDPC codes. Codes of this ensemble are determined by random parity-check matrices H which consist of
strips Hi of width M = r/J rows each, i = 1, 2, . . . , J. All strips are random column permutations of the strip where the
j-th row contains K ones in positions (j − 1)K + 1, (j − 1)K + 2, . . . , jK, for j = 1, 2, . . . , n/K.
The second ensemble is a special case of the ensemble described in [7, Definition 3.15]. Notice that the Gallager ensemble
and the RU ensemble are denoted by B and H, respectively, in [16].
For a ∈ {1, 2, . . . } denote by am the sequence (a, a, . . . , a) of m identical symbols a. In order to construct an r × n
parity-check matrix H of an LDPC code from the RU ensemble one does the following.
J
J
J
• Construct the sequence a = (1 , 2 , . . . , n ); and
• apply a random permutation b = π(a) to obtain a sequence b = (b1 , . . . , bN ), where N = Kr = Jn. The elements
b1 , . . . , bK show the locations of the nonzero elements of the first row of H, elements bK+1 , . . . , b2K show the locations
of the nonzero elements of the second row of H, etc.
A code from the RU ensemble is (J, K)-regular if for a given permutation π all elements of subsequences (biK−K+1 , . . . , biK )
are different for all i = 1, . . . , r, otherwise it is irregular. The regular RU codes belong to the ensemble A in [16] which is
defined by equiprobable parity-check matrices with row weight K and column weight J. It is shown in [16] that the three
ensembles A, B, and H have the same asymptotic average weight enumerators.
It is known (see [16, Theorem 3]) that for large n the total number of (J, K)-regular [n, n − r] codes (ensemble A in [16])
is equal to



(K − 1)(J − 1)
(Jn)!
1 + o(n−1+δ ) ,
exp −
(K!)r (J!)n
2
where δ > 0 and o(x) → 0 when x → 0. At the same time the number of different codes from the RU ensemble constructed
as described above is
(Jn)!
.
(K!)r (J!)n
Thus, the portion of (J, K)-regular LDPC codes in the RU ensemble is



(K − 1)(J − 1)
1 + o(n−1+δ ) ,
exp −
2
that is, most of the “(J, K)-regular” RU codes are indeed irregular. In the following, a code from the RU ensemble with
parameters J and K will sometimes be referred to as a (J, K)-RU code or simply as a (J, K)-regular code even if it is not
strictly (J, K)-regular. Also, with some abuse of language a (J, K)-regular code from the Gallager ensemble will be referred
to as a (J, K)-Gallager code.
As a performance measure we use word (block, frame) error rate (FER) Pe , which for the BEC is defined as the probability
that the decoder cannot recover the information of a received word uniquely.
Consider ML decoding over the BEC, where ε > 0 denotes the channel symbol erasure probability. Assume that a codeword
x = (x1 , . . . , xn ) is transmitted and that ν erasures occurred. Then, we denote by I the set of indices of the erased positions,
that is, I = {i1 , . . . , iν } ⊆ {1, 2, . . . , n}, |I| = ν, and by xI = (xi1 , . . . , xiν ) a vector of unknowns corresponding to the
erased positions. Let I c = {1, 2, . . . , n} \ I and xI c be the set of indices of unerased positions and the vector of unerased
values of x, respectively. Also, let HI be the submatrix of H consisting of the columns indexed by I. From xH T = 0, where
(·)T denotes the transpose of its argument, it follows that
xI HIT = xI c HITc , s ,

(1)

yI HIT = 0 ,

(2)

where s is the syndrome vector or, equivalently,
where y = x + x0 is a codeword. If the solution of (2) is not unique, that is,
rank (HI ) < |I| ,
then the corresponding set of erasures cannot be (uniquely) corrected. Otherwise, the set of erasures I is correctable. Thus,
the ML decoding error probability (for the BEC) is the probability of such a set I, that is,
Pe = Pr (rank (HI ) < |I|) .

(3)

4

III. AVERAGE SPECTRA FOR ENSEMBLES OF REGULAR LDPC CODES
A. Weight enumerator generating functions
In this section, we study average weight enumerators for different ensembles of LDPC codes. The weight distribution of
any linear code can be represented in terms of its weight generating function
Gn (s) =

n
X

An,w sw ,

w=0

where An,w is the random variable representing the number of binary codewords of weight w and length n, and s is a formal
variable. Our goal is to find E{An,w }, where E{·} denotes the expected value over the code ensemble. In general, computing
the coefficients An,w is a rather difficult task. If a generating function can be represented as a degree of another generating
function (or expressed via a degree of such a function) then for numerical computations we can use the following simple
recursion.
P
Lemma 1: Let f (s) = l≥0 fl sl be a generating function. Then, the coefficients in the series expansion of the generating
P
L
function FL (s) = [f (s)] = l≥0 Fl,L sl satisfy the following recurrent equation

fl ,
L=1
Pl
Fl,L =
.
(4)
f
F
,
L>1
i=0 i l−i,L−1
B. General linear codes
For completeness, we present the average spectrum for the ensemble of random linear codes determined by equiprobable
r × n parity-check matrices, where r = n − k, and k and n are the code dimension and length, respectively. The weight
generating function of all binary sequences of length n is Gn (s) = (1 + s)n . Then, the average spectrum coefficients are
 
n −r
E{An,w } =
2 , w>0,
(5)
w
where 2−r is the probability that a binary sequence x of length n and weight w > 0 satisfies xH T = 0.
If a random linear code contains only codewords of even weight, then its generating function has the form
X n
(1 + s)n + (1 − s)n
,
Gn (s) =
sw =
2
w
w even
and the average spectrum coefficients are

E{An,w } =

2−r+1
0,

n
w



,

w > 0 and even
w odd

.

(6)

C. The Gallager binary (J, K)-regular random LDPC codes
The generating function of the number of sequences satisfying the nonzero part of one parity check is given by
X K 

1
si =
g(s) =
(1 + s)K + (1 − s)K .
i
2
i even
The generating function for the strip is
GJ,K (s) = g(s)M =

n
X

Nn,w sw ,

(7)

(8)

w=0

where Nn,w denotes the total number of binary sequences of weight w satisfying xH1T = 0. Due to Lemma 1 we can compute
Nn,w precisely. The probability that xH1T = 0 is valid for a random binary x of weight w is equal to
p1 (w) =

Nn,w
 .
n
w

Since the submatrices Hj , j = 1,
 . . . , J, are obtained by independent random column permutations of H1 , the expected
n
number of codewords among all w
sequences of weight w is
 
 1−J
n
n
J
E{An,w } =
p1 (w)J =
Nn,w
,
(9)
w
w
where Nn,w is computed recursively using Lemma 1.

5

log2(Weight enumerator)

25

20

15

10
(48,24), d=12 code
Gallager bound
Random even−distance code
Average (3,6) Gallager code
Random (3,6) Gallager codes

5

0

0

5

10

15

20

weight

Fig. 1. The theoretical and empirical spectra of (3, 6)-regular Gallager codes of length n = 48. The Gallager bound and the random coding bound are
defined by (9) and (6), respectively.

D. The empirical and theoretical average spectra for the Gallager and the Richardson-Urbanke ensemble
In this section, we compare the theoretical average spectra computed according to (6) and (9) with the empirically obtained
average spectra for the Gallager and the RU ensemble. Furthermore, we compare the average spectra with the spectra of both
randomly generated and constructed LDPC and linear block codes.
We remark that there is a weakness in the proof of Theorem 2.4 in [15] by Gallager, which is similar to the one in the
derivations (7)–(9) above. Formula (2.17) in [15] (and (9) in this paper) states that the average number of weight-w binary

n
sequences which satisfy the parity checks of all J strips simultaneously is obtained by computing the J-th degree of Nn,w / w
,
that is, the probability of weight-w sequences satisfying the parity checks of the first strip. This formula relies on the assumption
that parity checks of strips are statistically independent. Strictly speaking, this statement is not true because they are always
linearly dependent (the sum of the parity checks of any two strips is equal to the all-zero sequence). The detailed discussion
and examples can be found in Appendix A.
In our derivations of the bounds on the error probability in Section IV we rely on the same assumption. Hence, it is important
to compare the empirical and the theoretical average spectra. Moreover, as it is shown in Appendix A, in the Gallager ensemble
there is no code whose spectrum coincides with the average spectrum. Thus, estimating the deviation of the spectrum of a
particular code from the average spectrum is an interesting issue.
One more question that we try to answer in this section is how close are the average spectra for the Gallager and RU
ensembles. It is known [16] that the Gallager and RU ensembles have the same asymptotic average spectrum. However, their
relation for finite lengths is unknown.
In Figs. 1–4, the distance spectra of 100 randomly selected rate R = 12 codes of length n = 48 (“Random codes” in the
legends) and their empirical average spectrum (“Average” in the legends) are compared with the theoretical average spectra.
We take into account that all codewords of a (J, K)-regular LDPC code from the Gallager ensemble have even weight. If
K is even, then the all-one codeword belongs to any code from the ensemble. It is easy to see that in this case the weight
enumerators An,w are symmetric functions of w, that is, An,w = An,n−w , and hence we show only half of the spectra in these
figures.
In Figs. 1 and 2, we present the average spectra for the Gallager ensembles and the average spectrum for the ensemble
of random linear codes with only even-weight codewords, computed by using formulas from Section III-B, spectra of 100
random codes from the Gallager ensemble, and the empirical average spectrum computed over 100 random codes from the
same ensemble. The spectrum of a quasi-perfect [48, 24] linear code with minimum distance d = 12 is presented in the same
figures as well. In Figs. 3 and 4, the average spectrum for the Gallager ensemble and the average spectrum for the ensemble
of random linear codes are compared with the spectra of 100 random codes from the RU ensemble and the empirical average
spectrum computed over 100 random codes from the RU ensemble.
Observations regarding the Gallager codes:
• For the Gallager (3, 6) and (4, 8)-regular LDPC codes their empirical average spectra perfectly match with the theoretical
average spectra computed for the corresponding ensembles.

6

log2(Weight enumerator)

25

20

15

10
(48,24), d=12 code
Gallager bound
Random even−distance code
Average (4,8) Gallager code
Random (4,8) Gallager codes

5

0
0

5

10

15

20

weight

Fig. 2. The theoretical and empirical spectra of (4, 8)-regular Gallager codes of length n = 48. The Gallager bound and the random coding bound are
defined by (9) and (6), respectively.

25

log 2 (Weight enumerator)

20

15

10

5
(48,24), d=12 code
Gallager bound
Random linear code
Average (3,6) RU code
Random (3,6) RU codes

0

-5
0

5

10

15

20

weight

Fig. 3. The theoretical spectrum of (3, 6)-regular Gallager codes and the empirical spectra of (3, 6)-RU LDPC codes of length n = 48. The Gallager bound
and the random coding bound are defined by (9) and (5), respectively.

For all codes from the Gallager ensemble the number of high-weight codewords is perfectly predicted by the theoretical
average spectrum.
• The number of low-weight codewords has large variation.
Remarks about the RU codes:
• Most of the RU LDPC codes are irregular and have codewords of both even and odd weight.
• Typically, parity-check matrices of random codes from the RU ensemble have full rank, and these codes have lower rate
than LDPC codes from the Gallager ensemble. For this reason, the empirical average spectrum of the RU ensemble lies
below the theoretical average spectrum computed for the Gallager ensemble.
• The average distance properties of the RU codes are better than those of the Gallager codes.
• The variation of the number of low-weight codewords is even larger than that for the Gallager codes.
Since for all considered ensembles low-weight codewords have a much larger probability than for general linear codes, we
expect to observe a higher error floor.
•

7

25

log 2 (Weight enumerator)

20

15

10

5
(48,24), d=12 code
Gallager bound
Random linear code
Average (4,8) RU code
Random (4,8) RU codes

0

-5
0

5

10

15

20

weight

Fig. 4. The theoretical spectrum of (4, 8)-regular Gallager codes and the empirical spectra of (4, 8)-RU LDPC codes of length n = 48. The Gallager bound
and the random coding bound are defined by (9) and (5), respectively.

IV. E RROR PROBABILITY BOUNDS ON THE BEC
A. Lower bounds
In this section, we consider bounds on the ML decoding error probability. We start with a simple lower bound which is true
for any linear code.
Theorem 1:
Pe ≥ Pe (n, k, ε) ,

 
n
X
n i
ε (1 − ε)n−i .
i
i=r+1

(10)

Remark: [21, Theorem 38] gives a lower bound on the error probability of ML decoding. It differs from (10) by a multiplier
which is close to 1. This difference appears because of different definitions of the frame error event in this paper and in [21,
Theorem 38].
Proof. It readily follows from the definition of the decoding error probability and from the condition in (3) that if the number
of erasures ν > r ≥ rank (H), then the decoding error probability is equal to one.
The bound (10) ignores erasure combinations of weight less than or equal to r. Such combinations lead to an error if they
cover all nonzero elements of a codeword.
Theorem 2: Let the code minimum distance be dmin ≤ d0 . Then,

r 
X
n − d0 w
Pe ≥ Pe (n, k, ε) +
ε (1 − ε)n−w .
w − d0

(11)

w=d0

Proof. There is at least one nonzero codeword c0 of weight at most d0 in the code. Each erasure combination of weight
w ≥ d0 which covers the nonzero positions of c0 leads to additional decoder failures taken into account as the sum in the
right-hand side (RHS) of (11).
We remark that upper bounds on the minimum distance of linear codes with given n ≤ 256 and k can be found in [27].
The lower bounds (10) and (11) are plotted in Figs. 5, 6, 7, and 13 for some code examples, and discussed in Section VI.
B. Upper bounds for general linear codes
Next, we consider the ensemble-average ML decoding block error probability E{Pe } over the BEC with erasure probability
ε > 0. This average decoding error probability can be interpreted as an upper bound on the achievable error probability for
codes from the ensemble. In other words, there exists at least one code in the ensemble whose ML decoding error probability

8

is upperbounded by E{Pe }. For the ease of notation, in the sequel we use Pe for the ensemble-average error probability. For
the ensemble of random binary [n, n − r] linear codes
 
n
X
n ν
Pe =
ε (1 − ε)n−ν
ν
ν=r+1
r  
X
n ν
+
ε (1 − ε)n−ν Pe|ν ,
(12)
ν
ν=1
where Pe|ν denotes the conditional ensemble-average error probability given that ν erasures occurred.
By using the approach based on estimating the rank of submatrices of random matrices [28], the following expression for
Pe|ν was obtained in [19], [29], [30]
Pe|ν = Pr (rank(HI ) < ν) = 1 −

ν−1
Y


1 − 2j−r ≤ 2ν−r ,

(13)

j=0

where HI is an r × ν submatrix of a random r × n parity-check matrix H.
The bound obtained by combining (12) and (13) is used as a benchmark to compare the FER performance of ML decoding
of LDPC codes to the FER performance of general linear codes in Figs. 5–16.
An alternative upper bound for a specific linear code with known weight enumerator has the form [29]
(  i

)
n
X
n X
n−w
Pe ≤
min
,
An,w
εi (1 − ε)n−i .
(14)
i
i−w
i=d

w=d

In particular, this bound can be applied to random ensembles of codes with known average spectra (see Section III). We refer
to this bound as the S-bound. It is presented for several ensembles in Figs. 5–16 and discussed in Section VI.
C. Random coding upper bounds for (J, K)-regular LDPC codes
In this subsection, we derive an upper bound on the ensemble-average error probability of ML decoding for the RU and
Gallager ensembles of (J, K)-regular LDPC codes. Similarly to the approach in [19], we estimate the rank of the submatrix
HI .
Theorem 3: The (J, K)-RU ensemble-average ML decoding error probability for [n, n − r] codes, n = M K, r = M J, and
M  1, is upperbounded by
 
n
X
n ν
Pe ≤
ε (1 − ε)n−ν
ν
ν=r+1
 !r  
r
n−ν
X
n ν

ε (1 − ε)n−ν .
(15)
+
2ν−r 1 + K
n
ν
K
ν=1
Proof. See Appendix B.
The same technique leads to the following bound for the Gallager ensemble of random LDPC codes.
Theorem 4: The (J, K)-Gallager ensemble-average ML decoding error probability for [n, n − r] codes, n = M K, r = M J,
and M  1, is upperbounded by
( 

J 
µK )  
r J(n−ν)/K
X
X
 µ+ν−r
µ+J −1
M
n−ν
n ν
Pe ≤
min 1, 2
min 1,
ε (1 − ε)n−ν
J
−
1
µ/J
n
ν
ν=1
µ=0
 
n
X
n ν
+
ε (1 − ε)n−ν .
(16)
ν
ν=r+1
Proof. See Appendix C.
We refer to the bounds (15) and (16) as R-bounds, since they are based on estimating the rank of submatrices of H.
Computations show that while for rates close to the capacity these bounds are rather tight, for small ε (or for rates significantly
lower than the capacity) these bounds are weak. The reason for the bound untightness is related to the Gallager ensemble
properties discussed in detail in Appendix A.

9

V. S LIDING - WINDOW NEAR -ML DECODING FOR QC LDPC CODES
A binary QC LDPC block code can be considered as a TB parent convolutional code determined by a polynomial parity-check
matrix whose entries are monomials or zeros.
A rate R = b/c parent LDPC convolutional code can be determined by its polynomial parity-check matrix


h11 (D)
h12 (D) . . . h1c (D)
 h21 (D)
h22 (D) . . . h2c (D) 


(17)
H(D) = 
 ,
..
..
..
..


.
.
.
.
h(c−b)1 (D) h(c−b)2 (D) . . . h(c−b)c (D)
where D is a formal variable, hij (D) is either zero or a monomial entry, that is, hij (D) ∈ {0, Dwij } with wij being a
nonnegative integer, and µ = maxi,j {wij } is the syndrome memory.
The polynomial matrix (17) determines an [M0 c, M0 b] QC LDPC block code using a set of polynomials modulo DM0 − 1.
If M0 → ∞ we obtain an LDPC convolutional code which is considered as a parent convolutional code with respect to the
QC LDPC block code for any finite M0 . By tailbiting the parent convolutional code to length M0 > µ, we obtain the binary
parity-check matrix


H0 H1 . . . Hµ−1 Hµ
0 ...
0


 0 H0 H1 . . . Hµ−1 Hµ . . .
0 


..
..
.. . .

 ..
..

 .
.
.
.
.
.

HTB = 
H 0 . . .
0
H0 H1 . . . Hµ−1 

 µ
 . .
..
..
..
..
..
.. 

 .
.
. .
.
.
.
.
. 
 .
H1 . . . Hµ
0
...
0 . . . H0
of an equivalent (in the sense of column permutation) TB code (all matrices Hi including HTB should have a transpose
operator to get the exact TB code [31]), where Hi , i = 0, 1, . . . , µ, are the binary (c − b) × c matrices in the series expansion
H(D) = H0 + H1 D + · · · + Hµ Dµ .
If every column and row of H(D) contains J and K nonzero entries, respectively, we call C a (J, K)-regular QC LDPC
code and irregular otherwise.
Notice that by zero-tail termination [31] of (17) at length W > µ, we can obtain a parity-check matrix of a [W c, (W − µ)b]
ZT QC LDPC code.
Consider a BEC with erasure probability ε > 0. Let H be an M0 (c − b) × M0 c parity-check matrix of a binary [n =
M0 c, k = M0 b, dmin ] QC LDPC block code, where dmin is the minimum Hamming distance of the code. An ML decoder
corrects any pattern of ν erasures if ν ≤ dmin − 1. If dmin ≤ ν ≤ n − k, then a unique correct decision can be obtained for
some erasure patterns. The number of such correctable patterns depends on the code structure.
As explained in Section II, ML decoding over the BEC is reduced to solving (1). Its complexity for sparse parity-check
matrices is of order ν 2 , ν = |I|, that is, still computationally intractable for LDPC codes of large lengths.
In order to reduce decoding complexity, we apply a sliding-window decoding algorithm which is modified for QC LDPC
block codes. This decoder is determined by a binary parity-check matrix


H0 . . . Hµ 0
0 ... 0
 0 H0 . . . Hµ 0 . . . 0 



.. 
..
..
HW =  ... . . . . . .
(18)
.
.
. 


 0 . . . 0 H0 . . . Hµ 0 
0
0 . . . 0 H0 . . . Hµ
of size (W − µ)(c − b) × W c, where W ≥ 2µ + 1 denotes the size of the decoding window in blocks. The matrix (18)
determines a ZT LDPC parent convolutional code. We start decoding with BP decoding applied to the original QC LDPC
block code of length n = M0 c, and then apply ML decoding to the ZT LDPC parent convolutional code determined by the
parity-check matrix (18). It implies solving a system of linear equations
T
xI,W HI,W
= sW ,

where xI,W = (xI,W,i , xI,W,i+1 mod n , . . . , xI,W,i+W c−1 mod n ), i = 0, s, 2s, . . . mod n is a subvector of xI corresponding
to the chosen window, s denotes the size of the window shift, and sW and HI,W are the corresponding subvector of s
and submatrix of HI , respectively. The final decision is made after αn/s steps, where α denotes the number of passes of
sliding-window decoding. The formal description of the decoding procedure is given below as Algorithms 1 and 2.
Notice that the choice of s affects both the performance and the complexity. By increasing s we can speed up the decoding
procedure at the cost of some performance loss. In the sequel, we use s = c bits that corresponds to the lowest possible FER.

10

Algorithm 1 BP-BEC
while there exist parity checks with only one erased symbol do
Assign to the erased symbol the modulo-2 sum of all nonerased symbols participating in the same parity check.
end while
Algorithm 2 Wrap-around algorithm for near-ML decoding of QC LDPC codes over the BEC
Input: BEC output y.
Perform BP decoding for y.
wstart ← 0;
wend ← W − 1;
corrected ← 1;
while corrected > 0 do
corrected ← 0;
Apply ML decoding to the window (ywstart , . . . , ywend );
wstart ← wstart + s mod n;
wend ← wend + s mod n;
if wstart = 0 then
corrected ← number of corrected erasures after a full round;
end if
end while
return y

VI. N UMERICAL RESULTS AND SIMULATIONS
A. Short codes
In Figs. 5 and 6, we compare upper and lower bounds on the error probability of ML decoding for short codes on the
BEC. First, notice that the lower bounds in Theorems 1 and 2 (sphere packing and the tightened sphere packing bound) almost
coincide with each other near the channel capacity. However, the new bound is significantly tighter than the known one in the
low erasure probability region. For further comparisons we use the new bound whenever information on the code minimum
distance is available. The upper bounds in Theorems 3 and 4 are also presented in Figs. 5 and 6. These two bounds are
indistinguishable at high symbol erasure probabilities but the difference between them is visible in the low ε region where all
bounds are rather weak. Notice that for high ε random coding bounds for LDPC codes are close to those of random linear
codes. For (J, K)-regular LDPC codes with J = 4 the random bound is almost as good as the random bound for general
linear codes of the same length and dimension in a wide range of ε values. In Figs. 5 and 6, as well as in subsequent figures,
S-bounds (14) are computed based on the spectra of the corresponding code ensembles.
In Fig. 7, we compare upper bounds on the ML decoding FER performance for the RU ensemble of (J, K)-regular LDPC

100

10-2

FER

10-4

10-6
S-bound for (3,6) LDPC code
R-bound for (3,6) RU code
R-bound for (3,6) Gallager code
Random linear codes
Tightened sphere packing
Sphere packing

-8

10

10-10
0.1

0.15

0.2

0.25

0.3

0.35

0.4

0.45

0.5

Symbol erasure probability

Fig. 5. Bounds for binary (3, 6)-regular LDPC codes of length n = 96 and rate R = 1/2. The S-bound is defined by (14), and R-bounds for RU and
Gallager codes are defined by (15) and (16), respectively. The random coding bound is computed by (12)–(13), while the sphere packing bound and the
tightened sphere packing bound are computed according (10) and (11), respectively.

11

100

10-2

FER

10-4

10-6
S-bound for (4,8) LDPC code
R-bound for (4,8) RU code
R-bound for (4,8) Gallager code
Random linear codes
Tightened sphere packing
Sphere packing

10-8

10-10
0.1

0.15

0.2

0.25

0.3

0.35

0.4

0.45

0.5

Symbol erasure probability

Fig. 6. Bounds for binary (4, 8)-regular LDPC codes of length n = 96 and rate R = 1/2. The S-bound is defined by (14), and R-bounds for RU and
Gallager codes are defined by (15) and (16), respectively. The random coding bound is computed by (12)–(13), while the sphere packing bound and the
tightened sphere packing bound are computed according to (10) and (11), respectively.

100

10-1
R=1/3,
n=108,
1 - (4,6)
2 - (6,9)
3 - (8,12)

FER

10-2

R=1/2,
n=96,
1 - (3,6)
2 - (4,8)
3 - (6,12)

10-3

10-4

0.15

R=2/3,
n=108,
1 - (3,9)
2 - (4,12)
3 - (6,18)

0.2

0.25

0.3

0.35

0.4

Lower bound
Average FER for linear codes
R-bound for 1st LDPC code
R-bound for 2nd LDPC code
R-bound for 3d LDPC code
S-bound for 1st LDPC code
S-bound for 2nd LDPC code
S-bound for 3d LDPC code

0.45

0.5

0.55

0.6

0.65

Symbol erasure probability

Fig. 7. Error probability bounds for binary (J, K)-regular LDPC codes of length n ≈ 100. The S- and R-bounds are defined by (14) and (15), respectively.
The average ML decoding FER performance for random linear codes is computed by (12)–(13). The lower bound is (11).

codes with different pairs (J, K) to the upper bounds for general linear codes of different code rates. Interestingly, the
convergence rate of the bounds for LDPC codes to the bounds for linear codes depends on the code rate. For rate R = 1/3,
even for rather sparse codes with column weight J = 4, their FER performance under ML decoding is very close to the FER
performance of general linear codes.
Next, we present simulation results for two ensembles of LDPC codes. The first ensemble is the Gallager ensemble.
In Figs. 8 and 9, we present the FER performance of ML decoding simulated for 10 randomly selected (3, 6) and (4, 8)regular Gallager codes of length n = 96. The FER performance for these codes has large variation and most of the FER
performance curves are located between the R-bound and the S-bound.
In Figs. 10 and 11, we present the FER performance of ML decoding simulated for 10 randomly selected (3, 6) and (4, 8)RU codes of length n = 96. The FER performance variation in both cases is smaller than for the Gallager codes and the
performance of (4, 8)-RU codes is concentrated around the R-bound.
There are two reasons for better behavior of the RU codes. First, the code rate for the RU codes is typically equal to R = 1/2,
whereas for the Gallager codes the rate is R ≥ 52/96 = 0.5417. A second reason to the difference in the FER performance is
the approximation discussed in Appendix A. In our derivations we used the Gallager approximation for estimating the number
of non-full-rank submatrices of size r × ν, where ν denotes the number of erasures. For decreasing values of ν, the number of

12

100

10-1

FER

10-2

10-3

S-bound
R-bound
Average FER for linear codes
Random (3,6) Gallager LDPC codes

10-4

0.25

0.3

0.35

0.4

Symbol erasure probability

Fig. 8. Error probability bounds and simulation results for (3, 6)-regular Gallager codes of length n = 96. S- and R-bounds are defined by (14) and (16),
respectively. The average ML decoding FER performance for random linear codes is computed by (12)–(13).

100

10-1

FER

10-2

10-3

S-bound
R-bound
Average FER for linear codes
Random (4,8) Gallager LDPC codes

10-4

0.25

0.3

0.35

0.4

Symbol erasure probability

Fig. 9. Error probability bounds and simulation results for (4, 8)-regular Gallager codes of length n = 96. S- and R-bounds are defined by (14) and (16),
respectively. The average ML decoding FER performance for random linear codes is computed by (12)–(13).

100

10-1

FER

10-2

10-3

S-bound
R-bound
Average FER for linear codes
Random (3,6) RU LDPC codes

10-4

0.2

0.22 0.24 0.26 0.28

0.3

0.32 0.34 0.36 0.38

0.4

Symbol erasure probability

Fig. 10. Error probability bounds and simulation results for (3, 6)-RU codes of length n = 96. S- and R-bounds are defined by (14) and (15), respectively.
The average ML decoding FER performance for random linear codes is computed
. by (12)–(13)

13

100

10-1

FER

10-2

10-3

10-4

0.2

S-bound
R-bound
Average FER for linear codes
Random (4,8) RU LDPC codes
0.22 0.24 0.26 0.28

0.3

0.32 0.34 0.36 0.38

0.4

Symbol erasure probability

Fig. 11. Error probability bounds and simulation results for (4, 8)-RU codes of length n = 96. S- and R-bounds are defined by (14) and (15), respectively.
The average ML decoding FER performance for random linear codes is computed by (12)–(13).

100

10-1

FER

10-2

10-3

Linear codes
R-bound (3,6) RU
R-bound (3,6) Gallager
Simulations (3,6) Gallager
Simulations (3,6) RU
R-bound (4,8) RU
R-bound (4,8) Gallager
Simulations (4,8) Gallager
Simulations (4,8) RU

10-4

0.25

0.3

0.35

0.4

Symbol erasure probability

Fig. 12. Simulation results for (3, 6)-regular and (4, 8)-regular codes of length n = 96 from the Gallager and RU ensembles. The S-bound is defined by
(14), and R-bounds for RU and Gallager codes are defined by (15) and (16), respectively. The average ML decoding FER performance for random linear
codes is computed by (12)–(13).

independent parity checks in “independent” strips decreases, and, therefore, the bound becomes loose. Since the parity-check
matrix for the RU codes is not split into strips, the inter-row dependencies for this submatrix are weaker than for the Gallager
codes.
In Fig. 12, we compare the best code among 10 randomly selected (3, 6)-regular LDPC codes and the best code among 10
randomly selected (4, 8)-regular LDPC codes of the two ensembles. As predicted by bounds, the ML decoding performance
of the (4, 8)-regular codes is much better than that of the (3, 6)-regular codes in both ensembles. Due to the rate bias and
imperfectness of the Gallager approximation, codes from the Gallager ensemble are weaker than the RU codes with the same
parameters. The performance of the RU codes perfectly matches the R-bound. Moreover, the best (4, 8)-RU code shows even
better FER performance than the average FER performance of general linear codes in the high erasure probability region.
B. Codes of moderate length
The FER performance for relatively long codes of length n = 1008 is shown in Fig. 13. Notice that the difference between
the lower and upper bounds for general linear codes, which was noticeable for short codes becomes very small for n = 1008.
Since the lower bound (10) is simply the probability of more than r erasures, the fact that the upper and the lower bounds
almost coincide leads us to the conclusion that even for rather low channel erasure probabilities ε, achieving ML decoding
performance requires correcting almost all combinations of erasures of weight close to the code redundancy r. Notice that
according to the S-bounds in Fig. 13, error floors are expected in the low erasure probability region. The error-floor level
strongly depends on J and K, and rapidly decreases with increasing J.

14

100

10-1
R=1/3
1 - (4,6)
2 - (6,9)
3 - (8,12)

10-2
R=1/2
1 - (3,6)
2 - (4,8)
3 - (6,12)

FER

10-3

10-4

-5

10

10-6

10-7
0.2

Lower bound
Average FER for linear codes
R-bound for 1st LDPC code
R-bound for 2nd LDPC code
R-bound for 3d LDPC code
S-bound for 1st LDPC code
S-bound for 2nd LDPC code
S-bound for 3d LDPC code

R=2/3
1 - (3,9)
2 - (4,12)
3 - (6,18)

0.3

0.4

0.5

0.6

0.7

0.8

Symbol erasure probability

Fig. 13. Error probability bounds for binary (J, K)-regular LDPC codes of length n = 1008. S- and R-bounds are defined by (14) and Theorem 3,
respectively. The average ML decoding FER performance for random linear codes is computed by (12)–(13). The lower bound is (11).

100

FER

10-2

10-4

S-bound
R-bound RU codes
R-bound Gallager codes
BP decoding
Irregular
Random (3,6)-Gallager codes
Random (3,6)-RU codes

-6

10

10-8
0.38

0.4

0.42

0.44

0.46

0.48

0.5

Symbol erasure probability

Fig. 14. Error probability bounds and simulation results for (3, 6)-regular LDPC codes of length n = 1008. The S-bound is defined by (14), and R-bounds
for the RU and Gallager codes are defined by (15) and (16), respectively.

In Figs. 14 and 15, we show simulation results for 5 randomly selected (3, 6)-regular and (4, 8)-regular codes of length n =
1008, respectively, from the Gallager and RU ensembles. In the same plots the rank and spectral bounds for the corresponding
ensembles are shown. We observe that for rates close to the capacity, the rank and spectral bounds demonstrate approximately
the same behavior as the average simulated FER. For low channel erasure probabilities the spectral bound predicts error floors.
As expected, the spectral bound is weak for rates far below the channel capacity. Since all 10 codes (5 for the Gallager
ensemble and 5 for the RU ensemble) show identical FER performance, we present only one of the BP decoding FER curves
in each plot. Finally, we show the FER performance of ML decoding for 2 non-random codes. The first code is an irregular
QC LDPC code with a base matrix of size 12 × 24 optimized for the BEC using the approach in [32]. The second code is
the (4, 8)-regular so-called double-Hamming code from [33]. Simulations show that the irregular code has better ML decoding
FER performance than any randomly generated code and almost everywhere outperforms the double-Hamming code. The
double-Hamming code is better than the randomly generated RU and Gallager codes, but it mimics their error-floor behavior.
C. Sliding-window near-ML decoding for QC LDPC codes
Simulation results for the irregular rate-12/24 LDPC code and for the double-Hamming regular LDPC code are presented
in Fig. 16. Parameters of the codes and the SWML decoder are summarized in Table I.

15

100

10-1

FER

10-2

10-3
S-bound
R-bound RU codes
R-bound Gallager codes
BP decoding
Double Hamming
Random (4,8)-Gallager codes
Random (4,8)-RU codes

10-4

0.42

0.43

0.44

0.45

0.46

0.47

0.48

0.49

0.5

Symbol erasure probability

Fig. 15. Error probability bounds and simulation results for (4, 8)-regular LDPC codes of length n = 1008. The S-bound is defined by (14), and R-bounds
for the RU and Gallager codes are defined by (15) and (16), respectively.

100

10-1

10-2

FER

10-3

10-4

10-5

Irregular, BP
Irregular, ML
Double Hamming, BP
Double Hamming, ML
S-bound for (3,6)-codes
S-bound for (4,8)-codes
R-bound for (3,6)-codes
R-bound for (4,8)-codes
Random linear codes

10-6

10-7

10-8
0.34

0.36

0.38

0.4

0.42

0.44

0.46

0.48

0.5

Symbol erasure probability

Fig. 16. Error probability bounds and the simulated FER performance of SWML decoding for QC LDPC codes of length n = 4800. S- and R-bounds are
defined by (14) and (15), respectively. The average FER performance of ML decoding for random linear codes is computed by (12)–(13).

The SWML decoding FER performance of the double-Hamming code is very close to the theoretical bounds, despite very
low decoding complexity. In contrast, the FER performance of BP decoding for this code is extremely poor. For the irregular
code, BP decoding performs much better than for the double-Hamming code, but its SWML decoding FER performance is
worse than that for the double-Hamming code. In general, both codes show very good error-correcting performance.
VII. T HRESHOLDS
In order to obtain an asymptotic upper bound on the error probability for (J, K)-regular LDPC codes, we use the following
inequality:
 
K
n−ν
n−ν
K
≤
.
(19)
n
n
K

16

TABLE I
E XAMPLE PARAMETERS OF SWML DECODERS FOR CODES OF LENGTH n = 4800.
Code and decoder

Codes

parameters

Irregular

Double-Hamming

Base matrix size

12 × 24

8 × 16

Lifting degree

24

32

Decoding window size

51

68

Window shift

24

16

Overall TB length

200

300

Maximum number of passes

15

15

For the RU ensemble, it follows from (15) that
Pe

n
X

 
n ν
≤
min {1, Bν }
ε (1 − ε)n−ν
ν
ν=1
n
o
≤ n · exp − min {max {T1 , T1 − log Bν }} ,
ν

where
 !r

Bν = 2ν−r
T1 = − log

1+

n−ν
K
n
K

,

 
n
− ν log ε − (n − ν) log(1 − ε) .
ν

Denote by α = ν/n the normalized number of erasures. The asymptotic error probability exponent can be written as


log Pe
E(ε) = lim −
n→∞
n
≥ min {max {F1 (α, ε) , F2 (α, ε)}} ,
(20)
α∈[0,1]

where
F1 (α, ε) = −h(α) − α log ε − (1 − α) log(1 − ε) ,

(21)

F2 (α, ε) = F1 (α, ε) − F3 (α) ,



J
J 
F3 (α) =
α−
log 2 +
log 1 + (1 − α)K ,
K
K
h(α) = −α log α − (1 − α) log(1 − α) .

(22)
(23)
(24)

In (20)–(24) all logarithms are to the base of e. The asymptotic decoding threshold is defined as the maximum ε providing
E(ε) > 0, or as the minimum ε providing E(ε) = 0. It is easy to see that F1 (α, ε) is always positive except at the point
α = ε where F1 (α, ε) = 0, F2 (α, ε) > 0 for α < ε, and F2 (α, ε) = 0 at α = ε if F3 (α) = F3 (ε) = 0. In other words, a lower
bound on the ML decoding threshold can be found as the unique solution of the equation
"
#
log 1 + (1 − ε)K
J
1−
.
(25)
ε=
K
log 2
Notice that increasing K leads to the simple expression
J
=1−R
K
for the threshold, which corresponds to the capacity of the BEC. Numerical values for the lower bound from (25) on the ML
decoding threshold for different code rates and different column weights are shown in Table II.
Surprisingly, the new lower bounds on the threshold marked by asterisk in Table II are essentially identical to the upper
bounds on the ML decoding threshold in [34, Eq. (37), Table 1], although the analytical expressions for the bounds are different.
This confirms the tightness of the bound in Theorem 3 and the bounds in [34] for rates near the channel capacity.
ε −−−−→
K→∞

17

TABLE II
A SYMPTOTIC LOWER BOUNDS ON THE ML DECODING THRESHOLD FOR BINARY (J, K)- REGULAR LDPC CODES ON THE BEC.
J

R
3

4

5

6

1/4

0.746930∗

8

9

—

—

1/3

—

0.665737∗

—

0.749989

—

0.750000

0.666633

0.666665

1/2

0.491422∗

—

0.497987

2/3

0.323598

0.330648

0.499507

0.499878

0.499992

0.499998

0.332560

0.333106

0.333314

0.333327

3/4

0.241029

0.247364

0.249191

0.249747

0.249975

0.249992

VIII. C ONCLUSION
Both a finite-length and an asymptotic analysis of ML decoding performance for LDPC codes on the BEC have been
presented. The obtained bounds are very useful since unlike other channel models, for the BEC, ML decoding can be
implemented for rather long codes. Moreover, an efficient sliding-window decoding algorithm which provides near-ML decoding
of very long codes is developed. Comparison of the presented bounds with empirical estimates of the average error probability
over sets of randomly constructed codes has shown that the new bounds are rather tight at rates close to the channel capacity
even for short codes. For code length n > 1000, the bounds are rather tight for a wide range of parameters. The new bounds
lead to a simple analytical lower bound on the ML decoding threshold on the BEC for regular LDPC codes.
A PPENDIX A
There is a weakness in the proof of Theorem 2.4 in [15] by Gallager, analogous to the one in the derivations (7)–(9) above.
Formula (2.17) in [15] and (9) in this paper state that the average number of weight-w binary sequences which simultaneously
satisfy all parity checks in J strips is
#J
 "
n
Nn,w

,
(26)
E{An,w } =
n
w
w
where Nn,w is the number of weight-w sequences satisfying the parity checks of the first strip H1 . This formula relies on the
assumption that parity checks of strips are independent. It is known that this assumption is incorrect because the strips of the
parity-check matrix are always linearly dependent (the sum of the parity checks of any two strips is the all-zero sequence)
and, as a consequence, the actual rate of the corresponding (J, K)-regular codes is higher than 1 − J/K. The fact that we
intensively use the strip-independence hypothesis in our derivations motivated us to study deeper the influence of the strip
independence assumption both on the conclusions in [15] and on the derivations done in this paper.
In order to verify how this assumption influences the precision of estimates, consider the following simple example.
Example 1: Consider a (3, 3)-regular code with M = 2. The first strip is


1 1 1 0 0 0
.
0 0 0 1 1 1
The other two strips are obtained by random permutations of the columns of this strip. In total there exist (6!)2 LDPC codes,
but most of the codes are equivalent. By taking into account that the first row in each strip determines the second row, we
obtain that the choice of each code is determined by the choice of the third and fifth rows of the parity-check matrix. Thus,
2
there are at most 63 = 400 equiprobable classes of equivalent codes. We compute the average spectra over codes with a
certain code dimension and the average spectrum over all codes. The obtained results are presented in Table III.
TABLE III
S PECTRA OF (3, 3)- REGULAR LDPC CODES OF LENGTH 6.
Dimension

Number of codes

2

288

1

Average spectrum
0

3

108

1

4

4

1

1
2

0

5
2

0

2

0

5

0

0

6

0

9

0

0


0

0

0

Average parameters over the ensemble
2.29

—

1

0

24
25

0

81
25

0


0

18

Notice that the lower bound on the code rate R ≥ 1 − J/K = 0, but since there exist at least two rows that are linearly
dependent on other rows, a tightened lower bound on the code rate is R ≥ 1 − 4/6 = 1/3. Let us compare these empirical
estimates with the Gallager bound. The generating function for the first strip is
g(s) = 1 + N6,2 s2 + N6,4 s4 = 1 + 6s2 + 9s4 .
According to (26)
 
6
E{A6,2 } =
2
 
6
E{A6,4 } =
4

6

6

!3
=

24
,
25

=

81
,
25

2

9

6

!3

4

which matches with the empirical average over all codes presented in Table III.
These computations lead us to the following conclusions:
• In the ensemble of (J, K)-regular LDPC codes there are codes of different dimensions. The average spectra depend on
the dimension of the code and differ from the average spectrum over all codes of the ensemble.
• The average over all codes may coincide with the Gallager estimate, but does not correspond to any particular linear code.
Moreover, the estimated number of codewords (sum of all spectrum components) is not necessarily equal to a power of
2.
Notice that if M is large enough, then the influence of strip dependence on the precision of the obtained spectrum estimate
is negligible. However, if ν  M , that is, in the low ε region, the assumption of strip independence should be used with
caution.
A PPENDIX B
Proof of Theorem 3
Assume that the number of erasures is ν > 0. The error probability of ML decoding over the BEC is estimated as the
probability that ν columns of the random parity-check matrix H from the RU ensemble corresponding to the erased positions
are linearly dependent, ν ≤ r.
Let HI be the submatrix consisting of the columns determined by the set I of the erased positions, |I| = ν. We can write
X
Pr (rank(HI ) < ν| ν) ≤
Pr xI HIT = 0 ν) .
(27)
xI 6=0

Consider a random vector s =
the all-zero vector is

xI HIT .

Denote by

sji

the subvector (si , . . . , sj ) of the vector s. The probability of s being

p(s = 0|ν) = p(s1 = 0|ν)

r
Y

p(si = 0|si−1
= 0, ν) .
1

(28)

i=2

Next, we prove that p(s1 = 0|ν) ≥ p(si = 0|si−1
= 0, ν), i = 2, 3 . . . , r. We denote by νi the number of erasures in nonzero
1
positions of the i-th parity check. For the choice of a random vector x and a random parity-check matrix from the RU ensemble
the probability of a zero syndrom component si is

1, νi = 0
p(si = 0|νi ) =
.
(29)
1
2 , νi > 0
First, we observe that for all i
p(si = 0|ν) = p(si = 0|νi = 0, ν)p(νi = 0|ν) + p(si = 0|νi > 0, ν)p(νi > 0|ν)
1
= 1 · p(νi = 0|ν) + · (1 − p(νi = 0|ν))
2
1 + p(νi = 0|ν)
=
.
(30)
2
For all i 6= j, let K 0 denote the number of row positions in which the corresponding elements either in row j or in row i of
H are nonzero. Since K 0 ≥ K the following inequality holds:

n−K 0
ν
p(νj = 0|νi = 0, ν) =
n
≤

ν

n−K
ν
n
ν

= p(νj = 0|ν) .

(31)

19

For the second parity check, by using arguments similar to those in (30), we obtain
1
(1 + p(ν2 = 0|s1 = 0, ν)) .
2
The conditional probability in the RHS can be estimated as
p(s2 = 0|s1 = 0, ν) =

(32)

min{K,ν}

p(ν2 = 0|s1 = 0, ν) =

X

p(ν2 = 0|s1 = 0, ν1 , ν)p(ν1 |s1 = 0, ν)

ν1 =0
(a)

=

K
X

p(ν2 = 0|ν1 , ν)

ν1 =0

p(s1 = 0|ν1 , ν)p(ν1 |ν)
,
p(s1 = 0|ν)

(33)

where equality (a) follows from the fact that p(ν2 = 0|s1 = 0, ν1 , ν) = p(ν2 = 0|ν1 , ν). By substituting (29) into (33), we get
p(ν2 = 0|s1 = 0, ν)
p(ν2 = 0|ν1 = 0, ν)p(ν1 = 0|ν)
=
+
p(s1 = 0|ν)

Pmin{K,ν}
ν1 =1

p(ν2 = 0|ν1 , ν)p(ν1 |ν)
2p(s1 = 0|ν)

Pmin{K,ν}
p(ν2 = 0|ν1 = 0, ν)p(ν1 = 0|ν) + ν1 =0
p(ν2 = 0|ν1 , ν)p(ν1 |ν)
=
.
2p(s1 = 0|ν)
The second term in the nominator is equal to p(ν2 = 0|ν), and p(νi = 0|ν) does not depend on i. Thus, we obtain
p(ν2 = 0|ν1 = 0, ν) + 1
2p(s1 = 0|ν)
(a)
p(ν2 = 0|ν) + 1
≤ p(ν2 = 0|ν)
2p(s1 = 0|ν)

p(ν2 = 0|s1 = 0, ν) = p(ν2 = 0|ν)

(b)

= p(ν2 = 0|ν) ,

(34)

where inequality (a) follows from (31) and equality (b) follows from (30). From (30), (32), and (34) we conclude that
p(s2 = 0|s1 = 0, ν) ≤ p(s2 = 0|ν) .
Consecutively applying these derivations for i = 3, 4, . . . , r we can prove that
p(si = 0|si−1
= 0, ν) ≤ p(si = 0|ν) ,
1
and then from (28) it follows that
p(s = 0|ν) ≤ p(s1 = 0|ν)r .
The probability that the i-th row in HI has only zeros can be bounded from above by

n−ν
K
p(νi = 0|ν) = n ,
K

and the probability that the entire sequence of length ν is a codeword (all r components of the syndrome vector are equal to
zero) is
 !r
n−ν
−r
K
p(s = 0|ν) ≤ 2
1+ n
.
(35)
K

By substituting (35) into (27), we obtain
 !r

Pe|ν = Pr (rank(HI ) < ν| ν) ≤ 2ν−r
and the statement of Theorem 3 follows from (12).

1+

n−ν
K
n
K

,

20

A PPENDIX C
Proof of Theorem 4
Assume that the number of erasures is ν > 0. Let HI be the submatrix consisting of the columns numbered by the set I
of the erased positions, |I| = ν. In Section IV it is shown that the problem of estimating the FER of ML decoding can be
reduced to the problem of estimating the rank of the submatrix HI . Let Hj,I denote the j-th strip of HI , j = 1, 2, . . . , J.
Denote by µi the number of all-zero rows in Hi,I , and define µ = (µ1 , . . . , µJ ).
Assume that the vector x is chosen uniformly at random from the set of binary vectors of length n, and let xI be the
subvector of x consisting of the elements numbered by the set I. Then,
X

T
Pr (rank(HI ) < ν|ν) ≤
Pr xI : xI Hj,I
= 0 for all j and xI 6= 0|ν, µ p(µ|ν) .
(36)
µ

For the Gallager ensemble the conditional probability for the vector µ given that the number of erasures is ν is
p(µ|ν) =

=

J
Y

p(µi |ν)

i=1
J 
Y
i=1

M
µi



n−µi K
ν
n
ν


=


J 
Y
M
i=1

µi

n−ν
µi K

n
µi K


,

where we take into account that the strips are obtained by independent random permutations. By using the inequality in (19),
we can bound this distribution from above as
" J  # " J 
#
Y M
Y n − ν µi K
p(µ|ν) ≤
(37)
µi
n
i=1
i=1
J 
J 
PJi=1 µi K 
µK

n−ν
M
n−ν
M
=
,
(38)
≤
µ/J
µ/J
n
n
PJ
where µ = i=1 µi , and the second inequality follows from the fact that the maximum of the first product in (37) is achieved
when µ1 = µ2 = · · · = µJ = µ/J.
According to (29) each of the M −µi nonzero rows of the i-th strip produces a zero syndrome component with probability 12 .
PJ
For a given µ, where i=1 µi = µ, 0 ≤ µ ≤ r, the probability of having a zero syndrome vector can be upperbounded using
a union bound argument as


 X



T
T
Pr xI : xI Hj,I
= 0 for all j and xI 6= 0|ν, µ ≤ min 1,
Pr xI Hj,I
= 0 for all j|ν, µ


xI 6=0


J


Y
2−M +µj
≤ min 1, (2ν − 1)


j=1
n
o
PJ

≤ min 1, 2ν−M J+ j=1 µj = min 1, 2ν−r+µ .
(39)
From (36) it follows that
Pr (rank(HI ) < ν| ν) ≤

r
X
µ=0


min 1, 2ν+µ−r

X

p(µ|ν) .


The total number of different µ with a given sum µ is equal to µ+J−1
J−1 . From (38) we obtain


J 
µK
X
µ+J −1
M
n−ν
p(µ|ν) ≤
.
J −1
µ/J
n
PJ
µ:

j=1

(40)

P
µ: J
j=1 µj =µ

(41)

µj =µ

Next, we use (12), where for the conditional probability Pe|ν = Pr (rank(HI ) < ν|ν) we apply estimates (40) and (41).
Each of the ν erasures belongs to J rows, and the total number Jν of nonzero elements are located in at least Jν/K rows.
Thus, the number of zero rows never exceeds r − Jν/K = J(n − ν)/K, which explains the upper summation limit in the
second sum of (16). Thereby, we prove (16) of Theorem 4.

21

R EFERENCES
[1] I. E. Bocharova, B. D. Kudryashov, E. Rosnes, V. Skachek, and Ø. Ytrehus, “Wrap-around sliding-window near-ML decoding of binary LDPC codes
over the BEC,” in Proc. 9th Int. Symp. Turbo Codes Iterative Inf. Processing (ISTC), 2016, pp. 16–20.
[2] I. E. Bocharova, B. D. Kudryashov, and V. Skachek, “Performance of ML decoding for ensembles of binary and nonbinary regular LDPC codes of finite
lengths,” in Proc. IEEE Int. Symp. Inf. Theory (ISIT), 2017, pp. 794–798.
[3] D. Burshtein and G. Miller, “An efficient maximum-likelihood decoding of LDPC codes over the binary erasure channel,” IEEE Trans. Inf. Theory,
vol. 50, no. 11, pp. 2837–2844, 2004.
[4] E. Paolini, G. Liva, B. Matuz, and M. Chiani, “Maximum likelihood erasure decoding of LDPC codes: Pivoting algorithms and code design,” IEEE
Trans. Comm., vol. 60, no. 11, pp. 3209–3220, 2012.
[5] M. Cunche, V. Savin, and V. Roca, “Analysis of quasi-cyclic LDPC codes under ML decoding over the erasure channel,” in Proc. Int. Symp. Inf. Theory
Appl. (ISITA), 2010, pp. 861–866.
[6] S. Kim, S. Lee, and S.-Y. Chung, “An efficient algorithm for ML decoding of raptor codes over the binary erasure channel,” IEEE Commun. Lett.,
vol. 12, no. 8, 2008.
[7] T. Richardson and R. Urbanke, Modern coding theory. Cambridge University Press, 2008.
[8] S. Sankaranarayanan and B. Vasic, “Iterative decoding of linear block codes: A parity-check orthogonalization approach,” IEEE Trans. Inf. Theory,
vol. 51, no. 9, pp. 3347–3353, 2005.
[9] N. Kobayashi, T. Matsushima, and S. Hirasawa, “Transformation of a parity-check matrix for a message-passing algorithm over the BEC,” IEICE Trans.
Fundamentals, vol. 89, no. 5, pp. 1299–1306, 2006.
[10] I. E. Bocharova, B. D. Kudryashov, V. Skachek, and Y. Yakimenka, “Distance properties of short LDPC codes and their impact on the BP, ML and
near-ML decoding performance,” in Proc. 5th Int. Castle Meeting Coding Theory Appl., 2017, pp. x–y.
[11] H. Pishro-Nik and F. Fekri, “On decoding of low-density parity-check codes over the binary erasure channel,” IEEE Trans. Inf. Theory, vol. 50, no. 3,
pp. 439–454, 2004.
[12] G. Hosoya, T. Matsushima, and S. Hirasawa, “A decoding method of low-density parity-check codes over the binary erasure channel,” in Proc. Int.
Symp. Inf. Theory Appl. (ISITA), 2004, pp. 263–266.
[13] P. M. Olmos, J. J. Murillo-Fuentes, and F. Pérez-Cruz, “Tree-structure expectation propagation for decoding LDPC codes over binary erasure channels,”
in Proc. IEEE Int. Symp. Inf. Theory (ISIT), 2010, pp. 799–803.
[14] B. N. Vellambi and F. Fekri, “Results on the improved decoding algorithm for low-density parity-check codes over the binary erasure channel,” IEEE
Trans. Inf. Theory, vol. 53, no. 4, pp. 1510–1520, 2007.
[15] R. G. Gallager, Low-density parity-check codes. M.I.T. Press: Cambridge, MA, 1963.
[16] S. Litsyn and V. Shevelev, “On ensembles of low-density parity-check codes: Asymptotic distance distributions,” IEEE Trans. Inf. Theory, vol. 48, no. 4,
pp. 887–908, 2002.
[17] Air Interface for Fixed and Mobile Broadband Wireless Access Systems, IEEE P802.16e/D12 Draft, Oct. 2005.
[18] Digital Video Broadcasting (DVB), European Telecommunications Standards Institute ETSI EN 302 307, Rev. 1.2.1, Aug. 2009.
[19] C. Di, D. Proietti, I. E. Telatar, T. J. Richardson, and R. L. Urbanke, “Finite-length analysis of low-density parity-check codes on the binary erasure
channel,” IEEE Trans. Inf. Theory, vol. 48, no. 6, pp. 1570–1579, 2002.
[20] I. Sason and S. Shamai, Performance analysis of linear codes under maximum-likelihood decoding: A tutorial. Now Publishers Inc, 2006.
[21] Y. Polyanskiy, H. V. Poor, and S. Verdú, “Channel coding rate in the finite blocklength regime,” IEEE Trans. Inf. Theory, vol. 56, no. 5, pp. 2307–2359,
2010.
[22] M. G. Luby, M. Mitzenmacher, M. A. Shokrollahi, and D. A. Spielman, “Efficient erasure correcting codes,” IEEE Trans. Inf. Theory, vol. 47, no. 2,
pp. 569–584, 2001.
[23] B. D. Kudryashov, “Decoding of block codes obtained from convolutional codes,” Problemy Peredachi Informatsii, vol. 26, no. 2, pp. 18–26, 1990.
[24] R. Y. Shao, S. Lin, and M. P. Fossorier, “Two decoding algorithms for tailbiting codes,” IEEE Trans. Comm., vol. 51, no. 10, pp. 1658–1665, 2003.
[25] V. Tomás, J. Rosenthal, and R. Smarandache, “Decoding of convolutional codes over the erasure channel,” IEEE Trans. Inf. Theory, vol. 58, no. 1, pp.
90–108, 2012.
[26] I. E. Bocharova, B. D. Kudryashov, V. Skachek, and Y. Yakimenka, “Low complexity algorithm approaching the ML decoding of binary LDPC codes,”
in Proc. IEEE Int. Symp. Inf. Theory (ISIT), 2016, pp. 2704–2708.
[27] M. Grassl, “Bounds on the minimum distance of linear codes and quantum codes,” Online available at http://www.codetables.de, 2007, accessed on
2017-01-06.
[28] G. Landsberg, “Ueber eine anzahlbestimmung und eine damit zusammenhängende reihe.” Journal für die reine und angewandte Mathematik, vol. 111,
pp. 87–88, 1893.
[29] E. R. Berlekamp, “The technology of error-correcting codes,” Proceedings of the IEEE, vol. 68, no. 5, pp. 564–593, 1980.
[30] S. J. MacMullan and O. M. Collins, “A comparison of known codes, random codes, and the best codes,” IEEE Trans. Inf. Theory, vol. 44, no. 7, pp.
3009–3022, 1998.
[31] R. Johannesson and K. S. Zigangirov, Fundamentals of convolutional coding, 2nd ed. John Wiley & Sons, 2015.
[32] I. Bocharova, B. Kudryashov, and R. Johannesson, “Searching for binary and nonbinary block and convolutional LDPC codes,” IEEE Trans. Inf. Theory,
vol. 62, no. 1, pp. 163–183, 2016.
[33] I. E. Bocharova, F. Hug, R. Johannesson, and B. D. Kudryashov, “Double-Hamming based QC LDPC codes with large minimum distance,” in Proc.
IEEE Int. Symp. Inf. Theory (ISIT), 2011, pp. 923–927.
[34] I. Sason and R. Urbanke, “Parity-check density versus performance of binary linear block codes over memoryless symmetric channels,” IEEE Trans.
Inf. Theory, vol. 49, no. 7, pp. 1611–1635, 2003.

