1

Asymptotic Average Number of Different
Categories of Trapping Sets, Absorbing Sets

arXiv:1705.06798v1 [] 18 May 2017

and Stopping Sets in Random Regular and
Irregular LDPC Code Ensembles
Ali Dehghan and Amir H. Banihashemi, Senior Member, IEEE
Department of Systems and Computer Engineering, Carleton University, Ottawa, Ontario, Canada

Abstract
The performance of low-density parity-check (LDPC) codes in the error floor region is closely
related to some combinatorial structures of the code’s Tanner graph, collectively referred to as trapping
sets (TSs). In this paper, we study the asymptotic average number of different types of trapping sets
such as elementary TSs (ETS), leafless ETSs (LETS), absorbing sets (ABS), elementary ABSs (EABS),
and stopping sets (SS), in random variable-regular and irregular LDPC code ensembles. We demonstrate
that, regardless of the type of the TS, as the code’s length tends to infinity, the average number of a
given structure tends to infinity, to a positive constant, or to zero, if the structure contains no cycle, only
one cycle, or more than one cycle, respectively. For the case where the structure contains a single cycle,
we obtain an estimate of the expected number of the structure through the available approximations for
the average number of its constituent cycle. These estimates, which are independent of the block length
and only depend on the code’s degree distributions, are shown to be accurate even for finite-length
codes.
Index Terms: Low-density parity-check (LDPC) codes, random LDPC codes, trapping sets (TS),
elementary trapping sets (ETS), leafless elementary trapping sets (LETS), absorbing sets (ABS),
elementary absorbing sets (EABS), stopping sets (SS).

I.

INTRODUCTION

The performance of low-density parity-check (LDPC) codes in the error floor region is closely
related to some combinatorial structures of the code’s Tanner graph, here referred to collectively
as trapping sets (TS). A trapping set S is often identified by its number of variable nodes

2

a, and the number of unsatisfied check nodes b in its subgraph. In this case, the set S is
said to belong to the (a, b) class. For a given LDPC code, the harmful trapping sets would
depend on the degree distribution of the code, the channel model, the decoding algorithm, the
quantization scheme, and the structure of the code’s Tanner graph. Some categorizations of
TSs include stopping sets (SS), elementary TSs (ETS), leafless ETSs (LETS), absorbing sets
(ABS), and elementary ABSs (EABS). Stopping sets are known to be the problematic structures
of the belief propagation algorithm over the binary erasure channel (BEC) [1]. Leafless ETSs
are relevant for soft-decision iterative decoding of variable-regular LDPC codes over the additive
white Gaussian noise (AWGN) channel [2], [3], [4]. The broader category of ETSs are harmful
sets for irregular codes over the AWGN channel [2], [5]. Absorbing sets are the fixed points
of bit-flipping decoding algorithms [6], [7], and are also shown to be relevant in the context of
quantized decoders over the AWGN channel [7].
Regardless of the type of the TS, the problem of counting and/or enumerating trapping sets in
a given code is a hard problem. It was shown in [8] that for a given a, finding an (a, b) TS with
the smallest b is an NP-hard problem. Also, finding an (a, b) ETS with the smallest a for a given
b is a hard problem [8]. Furthermore, it was proved in [9] that for a given Tanner graph G and a
positive integer t, determining whether G has a stopping set of size t is NP-complete. Despite the
intrinsic difficulty of such combinatorial problems, many advances are made on characterization
of trapping sets and the development of efficient search algorithms to find them [10], [11], [12],
[13], [14], [2], [15], [3], [16], [4], [5].
More related to the work presented in this paper, asymptotic results on the distribution of
trapping sets in different ensembles of LDPC codes were established in [17], [18], [19], [20].
The distribution of stopping sets in Tanner graph ensembles was first studied in [17]. In [18],
using tedious combinatorial methods, Orlitsky et al. studied the asymptotic average distribution
of stopping sets and the stopping number (the size of the smallest nonempty stopping set in
a code) in regular and irregular LDPC code ensembles, as the code’s block length n tends to
infinity. In particular, they proved that for almost all codes with smallest variable degree greater
than two, stopping number increases linearly with n. Milenkovic et al. [19] used random matrix
enumeration techniques and large deviations theory to study the asymptotic distribution of SSs
and TSs of size constant and linear in n, in random regular and irregular LDPC code ensembles.
Specifically, for regular ensembles with variable degree dv , they demonstrated that as n tends
to infinity, for constant a and b values, the average number of ETSs in the (a, b) class tends

3

to cna+

b−adv
2

, where c is a constant with respect to n, but depends on a, b, and dv . Using a

technique similar to that of [19], Amiri et al. [20] studied the asymptotic distribution of ABSs
and fully ABSs (FABSs) of size linear in n, in random regular LDPC code ensembles. They
also derived simplified formulas for enumerating the asymptotic average number of EABSs, and
FEABSs in regular LDPC code ensembles with variable degrees 3 and 4.
In this paper, we focus on the case where a and b are constant values (with respect to n). This
case is of particular practical interest, as in practice, the size of the most harmful trapping sets
may not necessarily increase with the code’s block length. For the scenario of constant a and b
values, all the existing results on the asymptotic average number of trapping sets, as discussed in
the previous paragraph, are consistent with the results of our analysis. In addition, for constant
a and b values, our analysis extends some of the results in the literature. For example, while
the results in [19] are limited to TSs and ETSs, in this work, we also cover LETSs, ABSs
and elementary ABSs. Moreover, compared to the existing literature [18], [19], [20], one major
difference is that rather than focusing on a class of trapping sets, we focus on individual nonisomorphic structures within a class. We show that such structures, although in the same class,
may demonstrate completely different asymptotic behavior. For example, the average number of
one structure may tend to a constant as n tends to infinity, while that of another structure, within
the same class, may tend to infinity. Or the asymptotic average number of one structure may
be zero, while that of another structure may be a non-zero constant. If one only considers the
behavior of the whole class, in the former case, the average number tends to infinity and in the
latter, to a constant. The granularity of our analysis is important since it is known that, in general,
different non-isomorphic trapping sets in the same class can differ in their harmfulness [21]. It
is thus important to know the average number of individual non-isomorphic TS structures within
a code ensemble. Finally, although the analysis in [18], [19], [20], may be conceptually easy
to understand, but the derivations are tedious and the final formulas are often complicated. In
contrast, at the core of our analysis is a simple, yet general, asymptotic result that the expected
number of an structure S is equal to Θ(n|V (S)|−|E(S)| ),1 where |V (S)| and |E(S)| are the number
of nodes and the number of edges of S, respectively. This result is then easily translated to an
asymptotic result on the average multiplicity of the structure based on the number of cycles
1

We use the notation f (x) = Θ(g(x)), if for sufficiently large values of x, we have a × g(x) ≤ f (x) ≤ b × g(x), for some

positive a and b values.

4

TABLE I
T HE ASYMPTOTIC AVERAGE NUMBER OF DIFFERENT TRAPPING SET STRUCTURES WITHIN (a, b) CLASSES OF
VARIABLE - REGULAR LDPC CODE ENSEMBLES WITH VARIABLE DEGREE dv .

TS Type

b/a < dv − 2
dv ≥ 2

b/a = dv − 2
dv = 2

dv = 3

b/a > dv − 2
dv ≥ 4

dv ≥ 2

ETSs

0

Θ(1)

∞

LETSs

0

∼ N2a

–

EASs

0

SSs

0

∼ N2a
∼ N2a

–
–

–
–

in the structure. For the number of cycles equal to zero, one, or more than one, the average
multiplicity tends to infinity, a non-zero constant, or zero, respectively.
In an ensemble E of LDPC codes, for given a and b values, we say that the (a, b) class has a
consistent behavior in E, if all the structures within the class demonstrate the same asymptotic
behavior in E, i.e., the average number of every non-isomorphic structure in the class tends to
the same value (zero, infinity or a non-zero constant) in E, as n tends to infinity. Otherwise, we
say that the class has an inconsistent behavior in E. As an example of our results, we prove
that in random variable-regular LDPC codes, every class of ETSs and every class of LETSs
has a consistent behavior. In irregular LDPC codes, however, classes of ETSs and LETSs have
inconsistent behavior. Another consequence of our analysis is to provide approximations for
the average number of TS structures that contain only one cycle. By definition, such a cycle
must be chordless (simple). We use asymptotic results on the multiplicity of cycles in random
regular and irregular Tanner graphs [22] to approximate the average number of simple cycles and
thus the average number of corresponding structures in the ensemble. We demonstrate that these
approximations are rather accurate even for individual codes selected randomly from finite-length
ensembles.
In Table I, we have summarized our results on the asymptotic average number of (a, b) TSs
in variable-regular ensembles of LDPC codes with variable degree dv , for different types of
trapping sets, and for different values of a, b and dv . In Table I, the notation N2a denotes the
asymptotic average number of cycles of length 2a in the Tanner graphs of the codes. The entry
“–” in the table is used to indicate that it is impossible to have trapping sets of a particular type
in the corresponding classes.

5

The organization of the rest of the paper is as follows: In Section II, we present some definitions
and notation. This is followed in Section III by our main result on the asymptotic average number
of an arbitrary local structure in the Tanner graph of random LDPC codes. This is followed by
the application of the general result to different types of trapping sets including ETSs, LETSs,
ABSs, EABSs and SSs, for both variable-regular and irregular LDPC code ensembles. Section IV
is devoted to numerical results. The paper is concluded with some remarks in Section V.
II. D EFINITIONS

AND NOTATIONS

For a graph G, we denote the node set and the edge set of G by V (G) and E(G), respectively.
In this work, we consider graphs with no loop or parallel edges. For v ∈ V (G) and S ⊆ V (G),
notations N(v) and N(S) are used to denote the neighbor set of v, and the set of nodes of G
which has a neighbor in S, respectively. A path of length c in G is a sequence of distinct nodes
v1 , v2 , . . . , vc+1 in V (G), such that {vi , vi+1 } ∈ E(G), for 1 ≤ i ≤ c. A cycle of length c is a
sequence of distinct nodes v1 , v2 , . . . , vc in V (G) such that v1 , v2 , . . . , vc form a path of length
c − 1, and {vc , v1 } ∈ E(G). We may refer to a path or a cycle by the set of their nodes, or by
the set of their edges, or by both. A chordless or simple cycle in a graph is a cycle such that
no two nodes of the cycle are connected by an edge that does not itself belong to the cycle.
A graph G = (V, E) is called bipartite, if the node set V (G) can be partitioned into two
disjoint subsets U and W (i.e., V (G) = U ∪ W and U ∩ W = ∅), such that every edge in E
connects a node from U to a node from W . The Tanner graph of a low-density parity-check
(LDPC) code is a bipartite graph, in which U and W are referred to as variable nodes and
check nodes, respectively. Parameters n and n′ in this case are used to denote |U| and |W |,
respectively. Parameter n is the length of the code, and the code rate R satisfies R ≥ 1 − (n′ /n).
The number of edges incident to a node v is called the degree of v, and is denoted by dv
or deg(v). Also, we denote the maximum degree and the minimum degree of G by ∆(G) and
δ(G), respectively. A bipartite graph G = (U ∪ W, E) is called bi-regular, if all the nodes on
the same side of the given bipartition have the same degree, i.e., if all the nodes in U have the
same degree du and all the nodes in W have the same degree dw . It is clear that, for a bi-regular
graph, |U|du = |W |dw = |E(G)|. A bipartite graph that is not bi-regular is called irregular. A
Tanner graph G = (U ∪ W, E) is called variable-regular with variable degree dv , if for each
variable node ui ∈ U, dui = dv . Also, a (dv , dc )-regular Tanner graph is a variable-regular
graph with variable degree dv , in which for each check node wi ∈ W , dwi = dc . The variable

6

and check node degree distributions of irregular LDPC codes are represented by polynomials
Pdvmax
Pdcmax
λ(x) = i=d
λi xi−1 and ρ(x) = i=d
ρi xi−1 , where λi and ρi denote the fraction of
v
c
min

min

the edges in the Tanner graph connected to degree-i variable and check nodes, respectively, and
dvmin , dvmax , dcmin and dcmax are the minimum and maximum variable and check node degrees
in the Tanner graph, respectively.

In a Tanner graph G = (U ∪ W, E), for a subset S of U, the induced subgraph of S in G,
denoted by G(S), is the graph with the set of nodes S ∪ N(S), and the set of edges {{ui , wj } :
{ui , wj } ∈ E(G), ui ∈ S, wj ∈ N(S)}. The set of check nodes with odd and even degrees in
G(S) are denoted by No (S) and Ne (S), respectively. Also, the terms unsatisfied check nodes
and satisfied check nodes are used to refer to the check nodes in No (S) and Ne (S), respectively.
Throughout this paper, the size of an induced subgraph G(S) is defined to be the number of its
variable nodes (i.e., |S|).
For a given Tanner graph G, a set S ⊂ U, is said to be an (a, b) trapping set (TS) if |S| = a
and |No (S)| = b. Alternatively, set S is said to belong to the class of (a, b) TSs. A stopping set
(SS) S is a TS for which the degree of each check node in G(S) is at least two. An elementary
trapping set (ETS) is a TS for which all the check nodes in G(S) have degree one or two. A
leafless ETS (LETS) S is an ETS for which each variable node in S is connected to at least
two satisfied check nodes in G(S). An absorbing set (ABS) S is a TS for which all the variable
nodes in S are connected to more nodes in Ne (S) than in No (S). Also, an elementary absorbing
set (EABS) S is an ABS for which all the check nodes in G(S) have degree one or two. A fully
absorbing set (FABS) is an ABS with the extra constraint that each variable node in the Tanner
graph has strictly fewer unsatisfied check nodes than satisfied check nodes in its neighborhood.
Also, an elementary fully absorbing set (EFABS) S is an FABS such that each check node in
G(S) has degree one or two.
In the asymptotic analysis presented in this work, for a given ensemble of LDPC codes (Tanner
graphs), identified by certain degree distributions and the block length n, we tend n to infinity.
In such an asymptotic scenario, we say that an structure S is local in a Tanner graph G, if the
definition of S depends on a constant number (with respect to n) of nodes in G. In particular,
as we are interested in subgraphs S = G(S) induced in G by a set of variable nodes S, if such
subgraphs are local, we refer to them as being locally induced subgraphs. For example, if one
considers a constant positive integer a, and Tanner graphs whose maximum variable degree is
a constant in n, then (a, b) ETSs, (a, b) LETSs, (a, b) ABSs, (a, b) EABSs, and (a, b) SSs are

7

all local structures. (Note that such sets can only exist for b ≤ a × dvmax , and thus b is also a
constant in n.) On the other hand, the definition of FABSs depends on all the variable nodes in
the Tanner graph, and thus FABSs are not local structures. In this work, our focus is on (a, b)
TSs with a and b being constants in n. We also consider Tanner graphs whose maximum variable
and check node degrees are constant. Thus, in this work, all ETSs, LETSs, ABSs, EABSs and
SSs are local structures.
We conclude this section with the definition of k-permutations that will be used in the proof
of our main result. The k-permutations of n objects are the different ordered arrangements of
k-element subsets of the n objects. The number of such permutations is equal to P (n, k) =
n(n − 1) · · · (n − k + 1).
III. A SYMPTOTIC AVERAGE N UMBER

OF AN

A RBITRARY L OCAL S TRUCTURE

IN

LDPC

C ODE (TANNER G RAPH ) E NSEMBLES
A. Main Result
In this subsection, we find a lower and an upper bound on the average number of a locally
induced subgraph of a random Tanner graph with a given degree distribution, in the asymptotic
regime where the size of the graph tends to infinity.
Theorem 1. Let ∆ be a fixed natural number, such that ∆ ≥ d1 ≥ d2 ≥ . . . ≥ dn , and
P
P ′
∆ ≥ d′1 ≥ d′2 ≥ . . . ≥ d′n′ , and that ni=1 di = ni=1 d′i = η. Consider the probability space G of
all Tanner graphs with node set (U, W ), where U = {u1, u2 , . . . , un }, W = {w1 , w2 , . . . , wn′ },

the degree of the node ui is di , and the degree of the node wi is d′i . Suppose that the degree
sets {di } and {d′i } follow the distributions λ(x) and ρ(x), respectively, and that the graphs in
G are selected uniformly at random. For G ∈ G, denote by XS (G) the number of subgraphs
S, induced by a constant number of variable nodes, in G. Then, in the asymptotic regime of
n → ∞, we have
E(XS ) = Θ(n|V (S)|−|E(S)| ) ,

(1)

where E(XS ) is the expected value of XS (G), and |V (S)| and |E(S)| are the number of nodes
and edges of S, respectively.
Proof. First, we introduce the method that we use to construct a random Tanner graph. Suppose
that the variable nodes are labeled as {u1 , u2, . . . , un }, and check nodes as {w1 , w2 , . . . , wn′ }.

8

For each node z with degree d(z), we assign a bin that contains d(z) cells, and consider a
random perfect matching (bijection) to pair the cells on one side of the graph to the cells on
the other side. From each matching, we construct a Tanner graph such that if there is an edge
between two bins, then we place an edge between the corresponding nodes in the Tanner graph.
The resulted Tanner graphs are thus represented as images of the so-called configurations that
are obtained from the random perfect matchings. There are N(η) = η! configurations, where
η is the number of edges in the graph. Also, note that given a set of ℓ fixed edges, there are
Nℓ (η) = (η −ℓ)! configurations containing those edges. Since each bipartite graph (which has no
parallel edges) corresponds to (d1 !)(d2 !) . . . (dn !)(d′1 !)(d′2 !) . . . (d′n′ !) matchings, a bipartite graph
can be chosen uniformly at random by choosing a matching uniformly at random and rejecting
the result if it has parallel edges. We thus consider perfect matchings with no parallel edges
in their image that are selected uniformly at random. Given a set of ℓ fixed edges, we use the
notation Mℓ (η) for the number of such configurations containing those edges. We then have:
Mℓ (η)/M0 (η) ∼ Nℓ (η)/N(η). (See, e.g., Corollary 2.18 of [23].)
Now, consider a bipartite structure of interest S = (X ∪Y, E ′ ), such that X = {x1 , x2 , . . . , xr },
Y = {y1 , y2, . . . , yr′ }, and r + r ′ = |V (S)|. We say there is a copy of S in a configuration
corresponding to a Tanner graph G = (U ∪ W, E), if there is a set of |E(S)| = |E ′ | edges in the
configuration, whose image in G corresponds to a subgraph which is isomorphic to S (X ⊂ U,
Y ⊂ W ). We denote the number of copies of S in a configuration by CS . We then have
E(XS ) = CS

N|E(S)| (η)
M|E(S)| (η)
(η − |E(S)|)!
CS
∼ CS
= CS
∼ |E(S)| ,
M0 (η)
N(η)
η!
η

(2)

where, the last equation is valid asymptotically since |E(S)| is a constant in n, and thus in the
number of edges η of the Tanner graph. In the following, we derive upper and lower bounds on
CS , and subsequently on E(XS ).
Upper bound on CS : To form a copy of the structure S, we choose an r-permutation of the n bins
from U and an r ′ -permutation of the n′ bins from W (note that some of the permutations may
result in the same copy of S. By considering all possible r-permutations and r ′ -permutations,
we obtain an upper bound on CS ). Next, after fixing the r-permutation and the r ′ -permutation,
for each i, 1 ≤ i ≤ r, for the ith bin in the r-permutation, we select d(xi ) cells in order. We
note that if the number of cells in the ith bin is not equal to d(xi ), then a copy of S cannot be
formed (by definition, the degree of a variable node in a subgraph induced by a set of variable
nodes must be equal to the degree of that variable node in the Tanner graph). On the check side,

9

for each i, 1 ≤ i ≤ r ′ , for the ith bin in the r ′ -permutation, we select d(yi ) cells in order. If the
number of cells in the ith bin is less than d(yi ), then a copy of S cannot be formed. (Note that
by considering all possible orderings for d(xi ) cells and d(yi ) cells, we find an upper bound on
CS , since some of those orderings may result in the same copy of S). The number of possible
Q Qd(x )−1
choices of the cells on the variable side is thus upper bounded by rj=1 i=0j (d(xj ) − i), that
can be further bounded from above by ∆|E(S)| . Similarly, the number of choices of the cells on
the check side is upper bounded by ∆|E(S)| . We therefore have

CS ≤ ∆2|E(S)| × P (n, r) × P (n, r ′)
≤ ∆2|E(S)| × nr × nr

′

= ∆2|E(S)| × n|V (S)| .

(3)

Lower bound on CS : If any of the variable degrees of S is missing in the variable degree
distribution λ(x) of the Tanner graph G, then, no copy of S can exist in G. Otherwise, assume
that there are α different variable degrees d1 , . . . , dα , in S, and denote the number of variable
nodes with degree di by ri . We thus have r1 +· · ·+rα = r. Denote by Ui the set of variable nodes
in G with degree di , i = 1, . . . , α. By the construction of the ensemble, we have |Ui | ≥ ci × n,
for some constant values ci , i = 1, . . . , α. On the check side, denote the set of all check nodes
with degree at least equal to the largest check degree in S by W ′ . Here also, |W ′| ≥ c′ × n, for
some constant c′ . It is then easy to establish the following lower bound on CS :





|Uα | |W ′|
|U1 |
,
···
CS ≥
r′
rα
r1

(4)

a
b

= a!/(b!(a − b)!). Using the linear lower bounds on |Ui |, i = 1, . . . , α, and |W ′|,

a
followed by the well-known lower bound ab ≥ ( )b , we obtain
b

where



 c n rα  c′ n r′
 c n  r1
α
1
···
r1
rα
r′
′
′
min{c1 , . . . , cα }r nr c′r nr
≥
× ′r′
rr
r
|V (S)|
(c × n)
,
≥
|V (S)||V (S)|

CS ≥

where c = min{c′ , c1 , . . . , cα } is a constant, and we have used r + r ′ = |V (S)|.

(5)

10

The proof is then completed by combining (3) and (5) with (2), and noting that dvmin × n ≤
η ≤ ∆ × n, where dvmin is the minimum variable degree in λ(x).
Theorem 1 shows that depending on the relative values of |V (S)| and |E(S)|, the expected
number of a structure S can tend to zero, infinity or a non-zero constant, as n tends to infinity.
The following lemma establishes a connection between the number of cycles in S, and the value
of |V (S)| − |E(S)|.
Lemma 1. Consider a graph S with the set of nodes V (S), and the set of edges E(S). If
|V (S)| > |E(S)|, then S does not contain any cycle. Else, if |V (S)| < |E(S)|, then S contains
at least two cycles, and if |V (S)| = |E(S)|, then S contains only one (simple) cycle.
Based on Theorem 1 and Lemma 1, we have the following corollary.
Corollary 1. Consider a random ensemble of Tanner graphs and a given subgraph S induced by
a constant number of variable nodes in such Tanner graphs. Depending on whether S contains at
least two cycles, only one cycle, or no cycle, the average number of structure S in the ensemble
tends to zero, to a positive constant, or to infinity, as the size of the graphs (length of the code)
tends to infinity.
In the following subsections, we apply the results of this subsection to different categories of
trapping sets, i.e., ETSs, LETSs, ABSs, EABSs and SSs, respectively.
B. Elementary Trapping Sets (ETS)
In this subsection, based on the general result of Theorem 1, we study the asymptotic behavior
of ETSs in both regular and irregular LDPC code ensembles.
The following results show that every (a, b) class of ETSs has a consistent behavior in variableregular LDPC codes, and that the behavior is fully determined by the ratio b/a and the variable
degree dv .
Proposition 1. Consider an (a, b) ETS S in a variable-regular Tanner graph with variable
degree dv . We then have
|V (S)| − |E(S)| = a +

b − adv
.
2

(6)

11

Proof. Suppose that S is induced in a Tanner graph G by the set of variable nodes S. By
counting the number of edges in S = G(S) from the variable side, we have |E(S)| = a × dv .
We also have
|V (S)| = |S| + |No (S)| + |Ne (S)| = a + b +

adv + b
adv − b
=a+
,
2
2

(7)

where the second equality follows from the fact that all the satisfied and unsatisfied check nodes
have degree two and one, in the ETS, respectively. The proof is then completed by subtracting
|E(S)| = a × dv from (7).
The next theorem is resulted from Theorem 1 and proposition 1, and describes the asymptotic
expected number of ETSs in different (a, b) classes of variable-regular LDPC code ensembles.
Theorem 2. Consider a random variable-regular LDPC code C with variable degree dv and
ET S
length n. Denote by Na,b
the number of (a, b) elementary trapping sets in C. Then, for a being

a constant in n, in the asymptotic regime where n → ∞, we have:
ET S
E(Na,b
) = Θ(na+

b−adv
2

).

Thus, depending on whether b/a > dv − 2, b/a < dv − 2, or b/a = dv − 2, the expected value
ET S
E(Na,b
) tends to infinity, zero, or a positive constant value in n.

Example 1. Figure 1 shows three ETS structures in variable-regular Tanner graphs with dv = 3,
each satisfying one of the conditions in Theorem 2. (Variable nodes, satisfied and unsatisfied
check nodes are shown by full circles, empty and full squares, respectively.)
Unlike variable-regular Tanner graphs, in irregular Tanner graphs, classes of ETSs demonstrate
an inconsistent behavior, i.e., in general, in an (a, b) class, one can find at least two structures
whose expected numbers tend to different values (infinity, zero or a non-zero constant), as
n → ∞. This is explained in the following example for the (4, 2) class.
Example 2. Figure 2 shows three ETS structures, all in the (4, 2) class, but each with a different
asymptotic behavior. While the asymptotic expected values of the leftmost and the rightmost
structures are infinity and zero, respectively, for the middle structure, the asymptotic expected
value is a positive constant (see, Corollary 1).

12

(a)

(b)

(c)

Fig. 1. Three ETS structures in variable-regular Tanner graphs with dv = 3, each satisfying one of the three conditions of
Theorem 2: (a) A (2, 4) ETS satisfying b/a > dv − 2, (b) A (4, 2) ETS satisfying b/a < dv − 2, and (c) A (2, 2) ETS satisfying
b/a = dv − 2.

Fig. 2. Three (4, 2) ETS structures in irregular Tanner graphs.

C. Leafless Elementary Trapping Sets (LETS)
A LETS is a special case of an ETS, and thus the general results presented in Proposition 1
and Theorem 2 are also applicable to LETS structures of random variable-regular Tanner graphs.
For LETSs, however, from the three scenarios of b/a > dv − 2, b/a < dv − 2, and b/a = dv − 2,
only the last two can happen. This is proved in the following lemma.
Lemma 2. For any LETS structure in the (a, b) class of a variable-regular LDPC code with
variable degree dv , we have b/a ≤ dv − 2.
Proof. Consider an (a, b) LETS structure induced by the set of variable nodes S. Counting the
number of edges in the subgraph G(S) from the two sides of the graph, we have a × dv =
b + 2|Ne (S)|. Since G(S) is a LETS structure, each variable node is connected to at least 2
satisfied check nodes. This implies 2|Ne (S)| ≥ 2a, which together with the previous equation
complete the proof.

13

Theorem 3. Consider a random variable-regular LDPC code C with variable degree dv and
LET S
length n. Denote by Na,b
the number of (a, b) leafless elementary trapping sets in C. Then,

for a being a constant in n, in the asymptotic regime where n → ∞, we have:
LET S
E(Na,b
) = Θ(na+

b−adv
2

).

LET S
Thus, depending on whether b/a < dv − 2, or b/a = dv − 2, the expected value E(Na,b
) tends

to zero, or a positive constant value in n.
Based on Theorem 3, it is clear that, in the asymptotic regime, only the LETS classes with
b/a = dv − 2 are non-empty. All the structures in such classes contain only one cycle, and we
thus have the following result.
Corollary 2. In random variable-regular LDPC codes with variable degree dv and length n, as
n → ∞, the only non-empty classes of local (a, b) LETS structures are those with b/a = dv − 2.
For each such class, all structures within the class correspond to a simple (chordless) cycle of
length 2a.
For irregular LDPC codes, the following result is in parallel with Lemma 2.
Lemma 3. For any LETS structure S in irregular LDPC codes, we have |V (S)| ≤ |E(S)|.
Proof. To prove the lemma, we show that any LETS structure S has a cycle. In S, each variable
node is connected to at least two satisfied check nodes. On the other hand, the degree of each
satisfied check node is two. Now, if we consider the subgraph formed by variable nodes, satisfied
check nodes and the edges in between, we have a graph with minimum degree two. It is wellknown that a graph with the minimum degree two has at least one cycle.
Based on Lemma 3, for irregular LDPC codes also, the asymptotic expected number of LETS
structures is either zero or a constant non-zero value. The classes of LETS structures in irregular
codes also demonstrate an inconsistent behavior, and among all the structures within an (a, b)
class, only those that correspond to simple cycles of length 2a have an asymptotically non-zero
expected value for their multiplicity. We thus have the following result.
Proposition 2. Consider random irregular LDPC codes with dvmin ≥ 2, and length n. As n → ∞,
for a constant value of a, the sum of the expected number of LETS structures in all the (a, b)

14

classes, for different values of b, tends to the expected value of the number of simple cycles of
length 2a in the code.
The cycle structure of random regular and irregular Tanner graphs was studied in [22]. In
particular, it was shown in [22] that the asymptotic expected value of the number of cycles of
′

length c in irregular graphs with variable degrees {di }ni=1 and check node degrees {d′i }ni=1 , as
the size of the graph tends to infinity, is given by
n  
n′  
 2X
2 X d′i c/2
di
(
)(
)
η i=1 2
η i=1 2
,
(8)
E(Nc ) ∼
c
P ′
P
where η = ni=1 di = ni=1 d′i is the number of edges in the graph. This result for variableregular graphs with variable degree dv reduces to

E(Nc ) ∼

n′  

2 X d′i c/2
)
(dv − 1)(
η i=1 2

c

,

(9)

and for (dv , dc ) bi-regular graphs to
E(Nc ) ∼


c/2
(dv − 1)(dc − 1)
c

.

(10)

Considering that in the asymptotic regime of n → ∞, by Corollary 1, the expected number of
cycles with chords tends to zero, one can use the above approximations for chordless cycles, and
use them along with Corollary 2 and Proposition 2, to obtain asymptotic estimates on the average
number of LETS structures in different classes of regular and irregular graphs, respectively.
D. Absorbing Sets (ABS)
The following result relates the number of nodes and edges of an ABS.
Lemma 4. For any ABS structure S within a Tanner graph with dvmin ≥ 2, we have |V (S)| ≤
|E(S)|.
Proof. Let S = G(S) be the ABS induced in the Tanner graph G by the set of variable nodes
S. By the definition of an ABS, each variable node in S is connected to more nodes in Ne (S)
than in No (S). Each node in S has thus at least two neighbors in Ne (S). On the other hand, the
degree of each node in Ne (S) within G(S) is at least two. Thus, if we consider the subgraph of

15

G(S) containing the nodes in S and Ne (S), and the edges in between, we obtain a graph with
minimum degree two. Such a graph, thus, has a cycle. This completes the proof.
Based on Theorem 1 and Lemma 4, it is clear that the average number of any ABS structure
tends to either zero or a positive constant (not to infinity) as the block length tends to infinity.
The following theorem distinguishes between the two cases depending on the variable degrees
of the Tanner graph.
Theorem 4. Consider random Tanner graphs with variable degree distribution λ(x). If dvmin ≥ 4,
then all the classes of local ABSs have zero multiplicity asymptotically. Otherwise, if dvmin =
3, then all the local (a, b) classes of ABSs with a ≥ 2 and b 6= a, have zero multiplicity
asymptotically. In this case (dvmin = 3), the structures in the local (a, a) class with asymptotically
non-zero multiplicity all correspond to simple cycles of length 2a consisting only of degree-3
variable nodes. Finally, if dvmin = 2, then only the local ABS structures whose variable degrees
are only 2 or 3 can have non-zero multiplicity asymptotically. In the (a, b) classes with a given
a and different values of b ≤ a, such structures are all simple cycles of length 2a.
Proof. If dvmin ≥ 4, then each variable node in the ABS must be connected to at least three
satisfied check nodes. Now, consider the subgraph that consists of the variable nodes of the
ABS, its satisfied check nodes and the edges in between. This subgraph has minimum degree
two, and a node of degree at least three, and thus contains at least two cycles. This means that
the ABS itself contains at least two cycles and thus, based on Corollary 1, its multiplicity is
zero asymptotically. The same argument applies to any ABS structure that has at least one node
with degree greater than or equal to four (for the cases with dvmin = 3 or 2).
If dvmin = 3, thus, all ABS structures have asymptotically zero multiplicity, except those whose
variable nodes, all, have degree three. In this case, by the definition of an ABS, we must have
b ≤ a, as each degree-3 variable node must be connected to at least two satisfied check nodes.
Now consider the case where a ≥ 2 and b < a. For this case, we consider two scenarios and
show that for both scenarios the ABS structures will have more than one cycle and thus their
multiplicity is zero asymptotically: (1) all unsatisfied check nodes have degree one, (2) at least
one unsatisfied check node c has degree 3 or larger. In the first scenario, since b < a, there must
exist a variable node v in the ABS that has no connection to unsatisfied check nodes. Node v
is thus connected to three satisfied check nodes, and with the same argument presented before,

16

(a)

(b)

Fig. 3. Two (4, 4) ABS structures with different asymptotic behaviors in Tanner graphs with dvmin = 3.

the ABS will have more than one cycle. In the second scenario, consider the subgraph of the
ABS consisting of variable nodes, satisfied check nodes and the unsatisfied check node c plus
all the edges in between. This subgraph has minimum degree 2 and a node with degree at least
3, and thus has more than one cycle. Therefore, for the case of dvmin = 3, the only classes of
ABSs with asymptotically non-zero multiplicity are (a, a) classes. The only elements within the
(a, a) class whose multiplicity is non-zero asymptotically are simple cycles consisting of only
degree-3 variable nodes, where each variable node is connected to one unsatisfied check node
of degree one, and the degree of all satisfied check nodes are two.
For graphs with dvmin = 2, the proof of the statement of the proposition is similar. In this
case, the only structures whose average multiplicity tends to a constant are those with variable
degrees only 2 or 3, that contain only a simple cycle.
From Theorem 4, it can be seen that any class of ABSs has a consistent behavior in any
ensemble of variable-regular or irregular LDPC codes with dvmin ≥ 4. The same applies to any
class of (a, b) ABSs with a 6= b in any ensemble of LDPC codes with dvmin = 3. One can,
however, easily provide examples where two ABS structures within the same (a, a) class have
different asymptotic behavior in an ensemble with dvmin = 3. This is demonstrated in Fig. 3
for the (4, 4) class. While the structure in Fig. 3(a) has only one cycle and thus has an average
multiplicity tending to a non-zero constant, the structure in Fig. 3(b) contains more than one
cycle and thus its multiplicity is zero asymptotically. For ensembles with dvmin = 2, it can be
seen that, in general, an (a, b) class of ABSs with a ≥ 2 and b ≤ a, has an inconsistent behavior

17

Fig. 4. Two (4, 1) ABS structures with different asymptotic behaviors in Tanner graphs with dvmin = 2.

(see Fig. 4, for two structures with different asymptotic behaviors in the (4, 1) class).
E. Elementary Absorbing Sets (EABS)
Elementary ABSs are a special case of ABSs. All the results presented in the previous
subsection are thus applicable to EABSs as well. On the other hand, EABSs, for codes with
dvmin ≥ 2, are a special case of LETSs. Therefore, the results presented in Subsection III-C are
also applicable to EABSs. In fact, for the variable-regular graphs with dv = 2 or dv = 3, or
irregular graphs with variable degrees only 2 and 3, the sets of EABSs and LETSs are identical.
In addition to the asymptotic results of Theorem 4, the following finite-length result applies to
EABSs of variable-regular LDPC codes with dv ≥ 4.
Lemma 5. There is no (a, b) EABS structure with b/a = dv − 2, in a variable-regular Tanner
graph with variable degree dv ≥ 4.
Proof. We note that for an EABS S, the condition b/a = dv −2, is equivalent to |V (S)| = |E(S)|,
which in turn means that S contains only a simple cycle. The condition b/a = dv −2 thus implies
that every variable node in S is connected to two satisfied and dv −2 unsatisfied check nodes. By
the definition of an ABS, however, each variable node in S must be connected to more satisfied
than unsatisfied check nodes. This implies that dv − 2 < 2 or dv < 4.
In the asymptotic regime of n → ∞, for variable-regular Tanner graphs with dv ≥ 4, using
either Lemma 5 or Theorem 4, one can see that all (a, b) EABS classes are empty. For the cases
of dv = 2 and dv = 3, based of Corollary 2, the only non-empty classes (asymptotically) are
those with b/a = dv −2, whose members are simple cycles of length 2a. The average multiplicity
of such classes can then be approximated by (9) or (10).

18

In general, for an irregular Tanner graph, the following result shows that among ABS structures, only those that are elementary can possibly have non–zero multiplicity in the asymptotic
regime of n → ∞. This implies that for graphs with dvmin ≥ 2, the asymptotic results presented
in Theorem 4, related to ABS structures with constant average multiplicity, applies directly to
EABSs.
Proposition 3. Any non-elementary local ABS structure S in a Tanner graph with dvmin ≥ 2
contains more than one cycle. The multiplicity of S in a random Tanner graph thus tends to
zero as the size of the graph tends to infinity.
Proof. The non-elementary ABS structure S has either (a) a satisfied check node with degree 4
or larger, or (b) an unsatisfied check node of degree 3 or larger. In addition, each variable node
in S is connected to at least two satisfied check nodes. For Case (a), consider the subgraph of S
consisting of all the variable nodes in S, all the satisfied check nodes and the edges in between.
This subgraph has minimum degree 2 and has a node with degree 4 or larger. It thus contains
more than one cycle, and so does the ABS structure S, itself. For Case (b), consider the subgraph
of S containing all the variable nodes, all the satisfied check nodes and the unsatisfied check
node with degree 3 or larger, as well as all the edges in between. This subgraph has minimum
degree 2 and has a node with degree 3 or larger, and thus contains more than one cycle.
F. Stopping sets (SS)
In stopping sets, each check node is connected to at least two variable nodes. For Tanner
graphs with dvmin ≥ 2, therefore, any SS structure has a minimum degree at least 2, and as a
result, contains at least one cycle. If we, however, further limit the degree distribution of Tanner
graphs to dvmin ≥ 3, any SS structure will have a minimum degree of two and at least one node
with degree 3 or larger. This implies that the SS structure will contain more than one cycle.
Lemma 6. Any SS structure in a Tanner graph with dvmin ≥ 2 contains at least one cycle, i.e.,
|V (S)| ≤ |E(S)|. For Tanner graphs with dvmin ≥ 3, however, any SS structure contains more
than one cycle, i.e., |V (S)| < |E(S)|.
It is easy to see that, in general, the only SS structures that contain only one cycle are those
with all variable nodes having degree 2. For such stopping sets, we have the following result.

19

Fig. 5. Two (4, 0) SS structures, consisting of only degree-2 variable nodes, with different asymptotic behavior.

Lemma 7. Consider a stopping set that belongs to the (a, b) class, and in which all the variable
nodes have degree 2. We then have b < a. Moreover, among all such SS structures, only those
with b = 0 can contain only one cycle. Those in other classes all have more than one cycle.
Proof. Since in an SS, each check node has degree at least 2, the number of check nodes in
the SS (with all variable nodes having degree 2) must be less than or equal to the number of
variable nodes and thus b ≤ a. If b = a, however, since the degree of an unsatisfied check node
in the SS is at least 3, then there will be 3b edges connected to unsatisfied check nodes. This,
alone, will be larger than the total number of edges connected to variable nodes. Thus, we must
have b < a. For the second part of the lemma, we notice that any SS with b > 0 has at least
one check node of degree 3 or larger, and thus contains more than one cycle.
Based on Lemma 7, the only SS structures with only one cycle are codewords (b = 0). In
such structures, the number of variable and check nodes is the same, and all variable nodes and
check nodes have degree 2. In fact, these structures are all simple cycles of length 2a formed
by degree-2 variable nodes.
Theorem 5. Any (a, b) class of local stopping sets has a consistent behavior in any ensemble of
LDPC codes with dvmin ≥ 3, with the asymptotic multiplicity equal to zero. Moreover, the same
result applies to LDPC codes with dvmin = 2 and stopping set classes with b > 0. In ensembles
with dvmin = 2, (a, 0) classes, in general, however, do not demonstrate a consistent behavior.
The only stopping set structures in these classes whose average multiplicity tends to a non-zero
constant by increasing the block length are simple cycles of length 2a consisting of a degree-2
variable nodes. All the remaining structures have an asymptotic multiplicity of zero.
Fig. 5 shows two stopping sets, both having only variable nodes with degree 2, and both in
the (4, 0) class, but with different asymptotic behavior.

20

IV. N UMERICAL

RESULTS

In this section, we present some numerical results in relation to the theoretical results presented
in previous sections. In particular, we provide the multiplicities of different trapping set structures
within randomly constructed LDPC codes and compare the results to the average values predicted
by the asymptotic analysis. We focus on LETS structures, and use the exhaustive search algorithm
of [4] to find the multiplicity of LETS structures within different classes.
TABLE II
B I - REGULAR LDPC C ODES FROM [24] U SED IN THE F IRST E XPERIMENT

Code

C1

C2

C3

C4

C5

C6

C7

C8

C9

n

816

1008

4000

20000

50000

4000

8000

10000

20000

R

0.5

0.5

0.5

0.5

0.5

0.5

0.5

0.5

0.5

dv

3

3

3

3

3

4

4

4

4

For the first experiment, we consider random bi-regular (3, 6) and (4, 8) LDPC codes with
different block lengths as listed in Table II. The multiplicities of LETS structures in different (a, b)
classes with a ≤ 12, b ≤ 5, for the (3, 6) codes, and with a ≤ 10, b ≤ 10, for the (4, 8) codes,
are listed in Tables III and IV, respectively. In both tables, we have also listed the asymptotic
average number of LETS structures within each class obtained based on Corollary 2. For (3, 6)
and (4, 8) codes, the asymptotic average value is non-zero only for classes with b/a = 1 and
b/a = 2, respectively. For these cases, the asymptotic average multiplicity of (a, a) and (a, 2a)
classes is approximated by (10) as 10a /(2a) and 21a /(2a), respectively.
The results of Tables III and IV show that the non-zero expected values provide a good approximation for the multiplicity of LETSs in (a, a) and (a, 2a) classes, for (3, 6) and (4, 8) codes,
respectively, even at relatively short block lengths. The results also show that the multiplicity of
other classes decrease with increasing n (and tend asymptotically to zero). The rate of decrease,
however, depends on the class and is faster for some classes than others.
In the second experiment, we consider irregular LDPC codes with degree distributions λ(x) =
0.4286x2 + 0.5714x3 , and ρ(x) = x6 , and construct random codes of block lengths n =
500, 1000, 4000, 10000, and 20000. All the codes have rate 0.5 and girth 6. Based on Proposition 2, the sum of the asymptotic expected values of LETSs of a given size a tends to the
average number of simple cycles of length 2a. We have used the approximation (8) for the latter

21

TABLE III
M ULTIPLICITIES OF (a, b) LETS S WITHIN THE RANGE a ≤ 12, b ≤ 5,

FOR

(3, 6) REGULAR LDPC CODES OF TABLE II, IN

COMPARISON WITH THE ASYMPTOTIC EXPECTED VALUES OF

Code

C OROLLARY 2

C1

C2

C3

C4

C5

Expected value

(3,3)

132

165

171

161

178

166

(4,4)

1491

1252

1219

1260

1268

1250

(5,5)

9169

10019

9935

10046

10231

10000

(a, a)

(a, b), b 6= a
(4,2)

3

6

1

0

0

0

(5,3)

90

100

21

2

1

0

(6,2)

2

5

0

0

0

0

(6,4)

2463

1885

476

95

52

0

(7,3)

110

116

10

0

1

0

(7,5)

33406

29736

7661

1540

640

0

(8,2)

1

3

0

0

0

0

(8,4)

4199

2961

183

4

1

0

(9,3)

195

169

4

0

0

0

(9,5)

84378

63787

4001

167

21

0

(10,2)

15

4

0

0

0

0

(10,4)

7965

4869

74

1

0

0

(11,3)

290

219

1

0

0

0

(11,5)

211273

134236

2278

8

2

0

(12,2)

15

6

0

0

0

0

(12,4)

17838

9041

36

0

0

0

(i.e., 15.42a /(2a)), and have provided the values for different values of a = 3, 4, 5, and 6, in the
last column of Table V. The actual sum of the multiplicities of LETSs of a given size a for the
five random codes are also provided in the table. The comparison shows a good match between
the theoretical asymptotic value and the finite-length numerical results even at relatively short
block lengths.
V. C ONCLUSION
In this paper, we studied the asymptotic behavior of local structures within the Tanner graph
of randomly constructed regular or irregular LDPC codes, as the code’s block length tends to
infinity. Examples of such structures are different categories of trapping sets, such as stopping

22

TABLE IV
M ULTIPLICITIES OF (a, b) LETS S WITHIN THE RANGE a ≤ 12, b ≤ 10,

FOR

(4, 8) REGULAR LDPC CODES OF TABLE II, IN

COMPARISON WITH THE ASYMPTOTIC EXPECTED VALUES OF

Code

C OROLLARY 2

C6

C7

C8

C9

Expected value

(3,6)

1563

1620

1598

1531

1543

(4,8)

24269

24107

24241

24368

24310

(5,10)

402513

406289

406754

407743

408410

(a, 2a)

(a, b), b 6= 2a
(4,6)

91

55

33

17

0

(5,6)

2

2

1

0

0

(5,8)

4640

2303

1910

934

0

(6,8)

588

196

107

22

0

(6,10)

185544

96525

76621

37075

0

(7,8)

53

10

7

0

0

(7,10)

39794

10698

6649

1682

0

(8,8)

5

0

0

0

0

(8,10)

7006

1116

567

60

0

(9,8)

1

0

0

0

0

(9,10)

1145

101

53

0

0

(10,10)

185

13

4

0

0

sets, elementary trapping sets, or absorbing sets, that are harmful in the error floor region of
LDPC codes. We derived a simple asymptotic relationship for the expected number of such
structures based on the difference between the number of nodes and the number of edges of the
structure. This was then related to the number of cycles in the structure, where we demonstrated
that depending on the structure having, zero, one, or more than one cycle, the asymptotic expected
value is infinity, a constant non-zero value, or zero, respectively. This general result was then
applied to different categories of trapping sets to derive more specific results on the asymptotic
expected values of different structures and classes of structures. In particular, for the case where
the asymptotic expected value of a structure is a constant, we used the asymptotic results on
the average number of cycles to estimate the constant value. We also demonstrated through
numerical results that such estimates are rather accurate even at finite block lengths.
An important aspect of this work was to demonstrate that different (non-isomorphic) structures

23

TABLE V
T OTAL MULTIPLICITIES OF LETS S OF SIZE a FOR RANDOM IRREGULAR LDPC CODES WITH DEGREE DISTRIBUTIONS
λ(x) = 0.4286x2 + 0.5714x3 , ρ(x) = x6 , AND

DIFFERENT BLOCK LENGTHS IN COMPARISON WITH THE EXPECTED VALUES
FROM

a

P ROPOSITION 2

Block Length

Expected values

500

1000

4000

10000

20000

from Proposition 2

3

651

598

617

604

600

611

4

7373

7173

7056

7055

7169

7067

5

90134

89720

87564

87637

87630

87181

6

1157736

1150665

1130815

1127524

1124863

1120275

within the same class of trapping sets can, in general, behave differently, in the asymptotic regime
of infinite block length. This was not investigated in previous studies where the focus had been
on the asymptotic behavior of the whole class rather than its individual members.
R EFERENCES
[1] 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, Jun. 2002.
[2] M. Karimi and A. H. Banihashemi, “Efficient algorithm for finding dominant trapping sets of LDPC codes,” IEEE Trans.
Inf. Theory, vol. 58, no. 11, pp. 6942–6958, Nov. 2012.
[3] M. Karimi and A. H. Banihashemi, “On characterization of elementary trapping sets of variable-regular LDPC codes,”
IEEE Trans. Inf. Theory, vol. 60, no. 9, pp. 5188–5203, Sept. 2014.
[4] Y. Hashemi and A. H. Banihashemi, “New characterization and efficient exhaustive search algorithm for leafless elementary
trapping sets of variable-regular LDPC codes,” IEEE Trans. Inf. Theory, vol. 62, no. 12, pp. 6713 – 6736, Dec. 2016.
[5] Y. Hashemi and A. H. Banihashemi, “Characterization and efficient exhaustive search algorithm for elementary
trapping sets of irregular LDPC codes,” submitted to IEEE Trans. Inf. Theory, Oct. 2016, available online at:
http://arxiv.org/abs/1611.10014.
[6] H. Xiao and A. H. Banihashemi, “Estimation of bit and frame error rates of finite-length low-density parity-check codes
on binary symmetric channels,” IEEE Trans. Commun., vol. 55, no. 12, pp. 2234–2239, Dec. 2007.
[7] L. Dolecek, Z. Zhang, V. Anantharam, M. J. Wainwright, and B. Nikolic, “Analysis of absorbing sets and fully absorbing
sets of array-based LDPC codes,” IEEE Trans. Inf. Theory, vol. 56, no. 1, pp. 181–201, Jan. 2010.
[8] A. McGregor and O. Milenkovic, “On the hardness of approximating stopping and trapping sets,” IEEE Trans. Inf. Theory,
vol. 56, no. 4, pp. 1640–1650, Apr. 2010.
[9] M. K. Krishnan and P. Shankar, “Computing the stopping distance of a Tanner graph is NP-hard,” IEEE Trans. Inf. Theory,
vol. 53, no. 6, pp. 2278–2280, May. 2007.
[10] E. Rosnes and Ø. Ytrehus, “An efficient algorithm to find all small-size stopping sets of low-density parity-check matrices,”
IEEE Trans. Inf. Theory, vol. 55, no. 9, pp. 4167–4178, Sep. 2009.

24

[11] E. Rosnes and Ø. Ytrehus, “An efficient algorithm to find all small-size stopping sets of low-density parity-check matrices,”
IEEE Trans. Inf. Theory, vol. 55, no. 9, pp. 4167–4178, Sep. 2009.
[12] X. Zhang and P. H. Siegel, “Efficient algorithms to find all small error-prone substructures in LDPC codes,” in Proc.
Global Telecommun. Conf., Houston, TX, USA, Dec. 2011, pp. 1–6.
[13] E. Rosnes, Ø. Ytrehus, M. A. Ambroze, and M. Tomlinson, “Addendum to an efficient algorithm to find all small-size
stopping sets of low-density parity-check matrices,” IEEE Trans. Inf. Theory, vol. 58, no. 1, pp. 164–171, Jan. 2012.
[14] G. B. Kyung and C.-C. Wang, “Finding the exhaustive list of small fully absorbing sets and designing the corresponding
low error-floor decoder,” IEEE Trans. Commun., vol. 60, no. 6, pp. 1487–1498, Jun. 2012.
[15] E. Rosnes, M. A. Ambroze, and M. Tomlinson, “On the minimum/stopping distance of array low-density parity-check
codes,” IEEE Trans. Inf. Theory, vol. 60, no. 9, pp. 5204–5214, Sep. 2014.
[16] Y. Hashemi and A. H. Banihashemi, “On characterization and efficient exhaustive search of elementary trapping sets of
variable-regular LDPC codes,” IEEE Comm. Lett., vol. 19, no. 3, pp. 323–326, Mar. 2015.
[17] D. Burshtein and G. Miller, “Asymptotic enumeration methods for analyzing LDPC codes,” IEEE Trans. Inf. Theory,
vol. 50, no. 6, pp. 1115–1131, Jun. 2004.
[18] A. Orlitsky, K. Viswanathan, and J. Zhang, “Stopping set distribution of LDPC code ensembles,” IEEE Trans. Inf. Theory,
vol. 51, no. 3, pp. 929–953, March. 2005.
[19] O. Milenkovic, E. Soljanin, and P. Whiting, “Asymptotic spectra of trapping sets in regular and irregular LDPC code
ensembles,” IEEE Trans. Inf. Theory, vol. 53, no. 1, pp. 39–55, Jan. 2007.
[20] B. Amiri, C.-W. Lin, and L. Dolecek, “Asymptotic distribution of absorbing sets and fully absorbing sets for regular sparse
code ensembles,” IEEE Trans. Inf. Theory, vol. 61, no. 2, pp. 455–464, Feb. 2013.
[21] B. K. Butler and P. H. Siegel, “Error floor approximation for LDPC codes in the AWGN channel,” IEEE Trans. Inf. Theory,
vol. 60, no. 12, pp. 7416–7441, Dec. 2014.
[22] A. Dehghan and A. H. Banihashemi, “On the Tanner graph cycle distribution of random LDPC, random protographbased LDPC, and random quasi-cyclic LDPC code ensembles,” Submitted to IEEE Trans. Inf. Theory, available online at:
http://arxiv.org/abs/1701.02379.
[23] B. Bollobás, Random graphs. Cambridge University Press, Cambridge, second ed., 2001.
[24] D. J. MacKay, “Encyclopedia of sparse graph codes,” accessed on Sep. 28, 2016. [Online]. Available:
http://www.inference.phy.cam.ac.uk/mackay/codes/data.html.

