1

Protograph LDPC Codes with Block
Thresholds: Extension to Degree-1 and

arXiv:1710.09651v1 [] 26 Oct 2017

Generalized Nodes
Asit Kumar Pradhan and Andrew Thangaraj
Department of Electrical Engineering
Indian Institute of Technology Madras, Chennai 600036, India
Email: asit.pradhan,andrew@ee.iitm.ac.in

Abstract
Protograph low-density-parity-check (LDPC) are considered to design near-capacity lowrate codes over the binary erasure channel (BEC) and binary additive white Gaussian noise
(BIAWGN) channel. For protographs with degree-one variable nodes and doubly-generalized
LDPC (DGLDPC) codes, conditions are derived to ensure equality of bit-error threshold and
block-error threshold. Using this condition, low-rate codes with block-error threshold close to
capacity are designed and shown to have better error rate performance than other existing codes.

I. I NTRODUCTION
Low-density-parity-check (LDPC) codes [1], introduced by Gallager in 1960s, became popular
in 1990s, because of their excellent performance under iterative message-passing decoding [2].
Several applications including security applications like wiretap coding [3] need code sequences
with provable block-error threshold, i.e for any channel parameter below capacity, block-error rate
should provably approach zero as blocklength goes to infinity. Two early efforts in block- error
threshold for LDPC codes include consideration of ML decoding [1] and a weight enumeration
analysis [4]. In [5], authors have shown that block-error and bit-error thresholds are same under
message-passing decoder for codes having minimum variable node degree greater than two.

October 27, 2017

DRAFT

2

In our earlier work [6], we have extended the block-error condition in [5] allowing degreetwo nodes in protograph LDPC ensembles under the condition that the degree-two subgraph
of the protograph is a tree. In [6], we have also designed high rate codes (rate ≥ 1/2) with
block-error threshold close to capacity using differential evolution. However, computer search
shows that low-rate codes (rate ≤ 1/3) satisfying block-error threshold condition derived in [6]
have threshold away from capacity. For example, a 7 × 8 optimized protograph defining a rate1/8 code has a gap of 0.3 between block-error threshold and capacity over the Binary Erasure
Channel (BEC). Low rate codes with bit-error threshold close to capacity have a large fraction
of degree-one bit nodes [7] [8], which are not allowed by the block-error threshold condition
in [6]. In this work, we extend the block-error threshold condition in [6] to allow degree-one
bit nodes, which play an important role in designing low-rate codes with threshold close to
capacity. Using the new block-error threshold condition, we have designed low-rate codes with
block-error threshold close to capacity. For example, we have designed a rate-1/8 protograph
LDPC code for BEC with a block-error threshold of 0.866 (gap of 0.009 from capacity). For the
binary additive white Gaussian noise (BIAWGN) channel, we have designed a code of rate-1/4
and blocklength-64800 which has better BER/FER performance than the rate-1/4 code in the
DVBS2 standard [9].
We also extend the block-error threshold condition to protograph Doubly Generalized LDPC
(DGLDPC) codes, introduced in [10]–[12] and studied in [13]–[16]. Block-error condition for
protograph DGLDPC ensembles allows cycles of degree-2 nodes and enables better optimization
of codes.
Rest of the paper is organized as follows. Section II introduces definition and notation for
protograph DGLDPC codes and describes density evolution over BEC and BIAWGN channel.
Section III derives conditions on protograph and component codes under which block-error
threshold equals density evolution threshold for large-girth ensembles. Optimization of protograph DGLDPC code is described in Section IV.

II. D EFINITIONS

AND

P RELIMINARIES

A general block-error threshold condition will be derived for doubly-generalized low density
parity check (DGLDPC) codes. We will first define these codes formally and introduce notation
for protograph DGLDPC codes.

DRAFT

October 27, 2017

3

A. Protograph DGLDPC codes
Protograph LDPC codes are defined by Tanner graphs that are created from a small base
graph, called protograph, by a copy-permute operation. Protograph DGLDPC codes are defined
in a similar way by allowing the variable and check nodes of the protograph to enforce arbitrary
linear codes as component codes. The copy-permute operation for lifting the protograph remains
the same.
Fig. 1 is an example of a protograph that expands to a DGLDPC code. The variable node v4
v1 ev1 ,1

ec1 ,1
ec1 ,2
c1

v2

v3
ev4 ,1

ec2 ,2
ev4 ,2

ec2 ,1
c2

v4

Fig. 1: Example of a protograph for DGLDPC codes. Double line for a node indicates that its
component code is generalized.
and the check node c1 have a (5,2) linear code as component code. All other component codes
are standard. In the copy operation, all copies of v4 and c1 will retain the respective component
codes.
A protograph is denoted G = (V ∪ C, E), where V and C are the set of variable and check
nodes, respectively, and E is the set of undirected edges. Multiple parallel edges are allowed
between a variable node and a check node in a protograph. The edges connected to a variable
node vi or a check node cj are denoted by evi ,m and ecj ,n , respectively, where m ∈ {1, 2 · · · dvi }
and n ∈ {1, 2 · · · dcj }. If vi is connected to cj , then evi ,m = ecj ,n for some m, n.
The lifted or expanded graph is obtained by the copy-permute operation, and is specified by
the number of copies and a permutation for each edge type. The design rate of the lifted graph
is the same as that of the protograph. For the lifted graph, the sequence of component codes
and edge types in the computation graph is completely determined by the protograph G. This
makes protograph density evolution analysis on girth-g liftings accurate up to iteration g2 .
October 27, 2017

DRAFT

4

Iterative message-passing decoding of DGLDPC codes is a generalized version of iterative
decoding used for standard LDPC codes. At variable node vi enforcing a (dvi , kvi ) component
code with generator matrix G, channel information for kvi bits is combined with incoming
messages from check nodes in the previous iteration by extrinsic Maximum A Posteriori (MAP)
processing on the extended component code with generator matrix [G|Ikvi ], where Ikvi is the
kvi × kvi identity matrix. At check node cj , extrinsic MAP processing is performed using the
enforced (dcj , kcj ) component code.

B. Density evolution over BEC
Consider iterative message passing decoding on the lifted Tanner graph G′ derived from a
DGLDPC protograph G = (V ∪ C, E) after transmission over a BEC with erasure probability
ǫ. In iteration t, let xtvi ,m denote the probability that an edge of type evi ,m carries an erasure
from variable node to check node. Since the lifted graph has |E| edge types, density evolution
is a vector recursion that proceeds by computing xt+1
vi ,m for, 1 ≤ i ≤ |V |, 1 ≤ m ≤ dvi , from the
vector {xtvi ,m }. Let yctj ,n denote the probability that an edge of type ecj ,n carries an erasure from
check node to variable node in the t-th iteration.
Since MAP processing is done with the component code at check and variable nodes, the
evolution of xt and y t will depend on the extrinsic messages generated by MAP decoders of
the component codes. For obtaining an explicit expression for the probability of erasure of an
extrinsic message generated by the MAP decoder of a linear code, a method based on the support
weights and information functions of the linear code is used as described and discussed in [17].
An example of a (5, 2) linear code, worked out in [17], is reproduced here and used later in an
illustrative example of density evolution.
Example 1. Consider the (5,2) linear code with codewords {00000, 01011, 10101, 11110}. Let
xi , i = 1, 2, . . . , 5, denote the independent input erasure probabilities of the 5 bits. Let hi (x∼i ),
where x∼i = {x1 , . . . , x5 } \ {xi } is the list of all variables except xi , denote the output erasure
probability of bit i. From [17], hi can be explicitly written in terms of xi . For example, h1 and
h3 are as follows:
h1 (x2 , x3 , x4 , x5 ) = x3 x5 + x2 x3 x4 − x3 x4 x5 x2 ,
h3 (x1 , x2 , x4 , x5 ) = x1 x5 + x1 x2 x4 − x1 x4 x5 x2 .

DRAFT

(1)

October 27, 2017

5

To proceed further, we assume that the extrinsic message-erasure probabilities from MAP
processing at m-th edge of node vi and n-th edge of node cj have been derived, and these are
denoted as hvi ,m (·) and hcj ,n (·), respectively. With this notation, the protograph density evolution
recursion is given by the following equations for 1 ≤ i ≤ |V |, 1 ≤ m ≤ dvi , 1 ≤ j ≤ |C|,
1 ≤ n ≤ dcj :
x0vi ,m = hvi ,m (1dvi −1 , ǫ1ki ),


t
yct+1
=
h
x
cj ,n
cj ,∼n ,
j ,n

t
xt+1
vi ,m = hvi ,m yvi ,∼m , ǫ1ki .

(2)
(3)
(4)

where xtcj ,∼n = {xtcj ,1 , · · · , xtcj ,n−1 , xtcj ,n+1 , · · · , xtcj ,dc },
j

yvt i ,∼m

=

{yvt i ,1 , · · ·

, yvt i ,m−1 , yvt i ,m+1 , · · ·

, yvt i ,dv }and
i

1k is the length-k all-ones vector. In the

first iteration, shown in (2), the probability that an incoming message from a check node is an
erasure is set as 1. Erasure probability from the channel is set to be ǫ.
Example 2. In Fig. 1, let the component codes at the variable node v4 and check node c1 be
the (5, 2) code considered in Example 1. All other variable and check nodes enforce repetition
codes and SPC codes, respectively. As mentioned earlier, at v4 MAP decoding is done over
the extended version of the (5, 2) code with codewords {0000000, 0101101, 1010110, 1111011}.
Before starting recursion, assign yv0i ,m = 1 for 1 ≤ i ≤ |V | and 1 ≤ m ≤ dvi . The evolution for
a few edges is shown below:
t
xt+1
v1 ,1 = ǫyv1 ,2 ,

t
xt+1
v1 ,2 = ǫyv1 ,1 ,

t
t
2 t
t
t
2 t
t
t
t
xt+1
v4 ,1 = ǫyv4 ,3 yv4 ,5 + ǫ yv4 ,2 yv4 ,3 yv4 ,4 − ǫ yv4 ,2 yv4 ,3 yv4 ,4 yv4 ,5 ,

yct1,1 = xtc1 ,3 xtc1 ,5 + xtc4 ,2 xtc1 ,3 xtc1 ,4 − xtc1 ,2 xtc1 ,3 xtc1 ,4 xtc1 ,5 .
III. B LOCK -E RROR T HRESHOLD E XTENSIONS
In this section, we generalize block-error threshold conditions for protograph LDPC codes to
protograph with degree-1 variable nodes and to DGLDPC codes. The density evolution threshold,
denoted ǫth , for the protograph ensemble is defined as the supremum of the set of ǫ for which
erasure probability on each edge tends to zero as iterations tend to infinity, i.e
ǫth = sup{ǫ : max xt (e) → 0}.
e∈E

October 27, 2017

DRAFT

6

e1

v1
e2
c1
e3 e4 e5
v2
v3
v4

Fig. 2: Computation graph with degree one node

Let us define xt as follows:
xt = sup xt (e).
e∈E

In [6], sufficient conditions for block-error threshold being equal to bit-error threshold have been
derived using the following two steps:
1. In first step, it has been shown that xt falls double exponentially with t, i.e.
xt = O(exp(−β2αt ))
with α > 0, β > 0, when the degree-two subgraph of the protograph is a tree and ǫ ≤ ǫth .
2. Under the assumption that girth, denoted by g, of the lifted code of blocklength n is
O(log n) and t < g/2, it has been shown that block-error threshold is same as bit-error
threshold by upper bounding probability of block error, denoted by PB , with nxt and using
double-exponential fall property of xt as follows:
PB ≤ nxt = O(n exp(−β2αt )) = O(n exp(−βnα )).
The basic idea in the proof of step one is the following: When the degree-two subgraph of a
protograph is a tree, variable node with degree greater than two is traversed in every |V | (number
of variable nodes) iterations of density evolution, resulting in squaring of xt , which is sufficient
to show double exponential fall of xt as described in [6]. Let us consider the computation graph

DRAFT

October 27, 2017

7

in Fig. 2 with a degree-one variable node v2 and a degree-2 variable node v1 . In iteration t, we
have
xte1 = ǫyet 2
t−1
t−1
= ǫ(1 − (1 − xt−1
e3 )(1 − xe4 )(1 − xe5 ))
2
≥ ǫ(1 − (1 − xt−1
e3 )) = ǫ .

(5)

By using similar argument as above, it can also be shown that y t corresponding to e4 and e5 is
less than ǫ. This shows that the argument for double exponential fall as described in [6] does
not carry over directly when the protograph has degree-one variable nodes even for edges that
are not directly connected to degree-1 variable nodes.
A. Protograph LDPC code with degree-1 variable nodes
We say a function f (t) falls double exponentially with t if f (t) = O(exp(−β2αt )) for sufficiently large t, with α and β being positive constants. The property of block-error threshold being
equal to bit-error threshold does not require xte and yet for all e ∈ E to fall double exponentially.
It is enough to show that probability of bit-error Pb corresponding to information bits falls
double exponentially with iteration. Let Pb (v) be the probability of bit error corresponding to
a variable node v. We observe that Pb (v) falls double exponentially if yet corresponding to at
least one of incoming edges from a check node connected to v falls double exponentially. If xte
falls double exponentially with t, then the edge e might help in the double exponential fall of
y t corresponding to other edges of protograph. To find out the set of variable nodes for which
Pb (v) falls double exponentially with t, we need to find out set of edges for which xte and/or yet
fall double exponentially with t.
Consider a protograph G(V ∪ C, E). Let V1 ⊂ V be the set of degree-one variable nodes and
E1 ⊂ E be the set of edges incident on them. Define C1 = {c : c is connected to v ∈ V1 }.
Let G2 be the subgraph of G induced by degree-two variable nodes. Let E2 ⊂ E be the set
b Vb ∪ C,
b E)
b of the protograph G, similarly define
of edges of cycles in G2 . For a subgraph G(
c1 , G
b2 and E
b2 . For v ∈ Vb , let Ev and E
bv denotes the set of edges connected to v in
Vb1 , C
b respectively. Similarly, define Ec and E
bc for c ∈ C.
b Define
protograph G and its subgraph G,

Dy = {e : yet falls double exponentially with t}, Dx = {e : xte falls double exponentially with
t}, D x = E \ Dx , Dy = E \ Dy , Dxy = Dx ∩ Dy , Dxy = E \ Dxy . In the following two lemmas,
we describe edges which are in D x , D y and D xy .
October 27, 2017

DRAFT

8

Lemma 1. In the notation introduced above, the following are true:
1) E1 ⊆ Dx .
2) For e ∈ E1 and e′ ∈ Ece \ e, {Ece \ e} ⊆ D y .
3) E2 ⊆ Dxy .
4) If e ∈ E2 , then Ece ⊆ D y .
Proof.

1) Consider e ∈ E1 . From (4), it follows that xte = ǫ

∀t. So, E1 ⊆ Dx .

2) Consider e ∈ E1 . Observe that for each e′ ∈ {Ece \ e}, e ∈ {Ece′ \ e′ }. From (3), it follows
that for each e′ ∈ {Ece \ e}
Y

yet ′ = 1 −

(1 − xt−1
ē )

ē∈Ece′ \e′

≥ xt−1
e .
Since e ∈ E1 , we know from Part 1, xt−1
= ǫ. So, yet ′ ≥ ǫ and e′ ∈ D y .
e
3) Consider a cycle L = e1 e2 · · · el e1 , with vei = vei+1 . From (2)-(3), it follows that
xe(t+l)
= ǫye(t+l)
i
i+1
≥ ǫxe(t+l−1)
.
i+2
(t+l)

By applying (2) and (3) l/2 times alternatively, it can be shown that xei
(t+l)

1 ≤ i ≤ l. Similarly, it can be shown that yei

l

≥ ǫ 2 (xtei ) for

l

≥ ǫ 2 (yet i ). So, ei ∈ D xy .

4) Consider e ∈ E2 . For each e′ ∈ Ece , observe that {Ece′ \e′ }∩E2 6= ∅. Let ẽ ∈ {Ece′ \e′ }∩E2 .
From (2), it follows that for each e′ ∈ Ece
yet ′ = 1 −

Y

(1 − xt−1
e′′ )

e′′ ∈Ece′ \e′

≥ xẽt−1 .
Since ẽ ∈ E2 , we know from Part 3 of Lemma 1 that xẽt−1 does not fall double exponentially
with t. So, yet ′ , for e ∈ E2 and e′ ∈ Ece , does not fall double exponentially with t.

b = E − {E1 ∪ E2 }. Let G(
b Vb ∪ C)
b be the subgraph of G induced by edges in E.
b In
Define E
b1 and E
b2 behave in same way as E1 and E2 , which will be
context of double exponential fall, E
shown in the following lemma.

DRAFT

October 27, 2017

9

Lemma 2. In the notation defined above
b1 ⊆ Dx .
1) E

b1 , then {Ece \ e} ⊆ D y .
2) If e ∈ E
b2 ⊆ Dxy .
3) E

b2 , Ece ⊆ Dy .
4) If e ∈ E

Proof.

b1 . We will use the fact that xt falls double exponentially iff y t ′
1) Consider e ∈ E
e
e

corresponding to at least one edge e′ ∈ Ece \ e falls double exponentially. We have
xte = ǫ

Y

yet ′

e′ ∈Eve \e

=ǫ
Define Ate =

Y

bve }
e′ ∈{Eve \E

Q

Y

yet ′

yet ′ .

bve \e}
e′ ∈{E

yet ′ . From Lemma 1, it can be deduced that Ate does not fall double

bce
e′ ∈Ece \E

b E
bce \ e = ∅.
exponentially with t. Since e is incident on a degree-one variable node of G,
So, xte = ǫAte and it does not fall double exponentially with t.

2) Similar to the proof of Part 2 of Lemma 1.
b = e1 e2 · · · el e1 with ve = ve .
3) Consider a cycle L
i
i+1
xt+l
ei = ǫ

Y

yet+l

e∈Evei \ei

=ǫ

Y

bve }
e∈{Evei \E
i

yet+l

Y

yet+l

bve \ei
e∈E
i

t+l
= At+l
e yei+1
t+l−1
≥ At+l
e xei+2 ,

where At+l
=
e
At+l
e

Q

bve }
e∈{Evei \E
i

bve \ ei . From Lemma 1, it can be deduced that
yet+l and ei+1 = E
i

does not fall double exponentially. By applying above l/2 times we can show that
t
t
xt+l
ei ≥ Ae1 xei .

Since Ate1 does not fall double exponentially, xtei does not fall double exponentially with t.
4) Similar to the proof of Part 4 of Lemma 1.

October 27, 2017

DRAFT

10

1) Subgraph RED(G): The following algorithm finds a subgraph, denoted by RED(G),
such that edges of RED(G) are in Dxy . This is done by recursively removing edges in E1 and
E2 using Lemmas 1 and 2.

b = G(V ∪ C, E).
1) G
b Vb ∪ C,
b E)
b has variable nodes of degree-one, or the subgraph induced by degree-two
while G(
variable nodes is not a tree do
b2 (Vb2 ∪ C
b2 , E
b2 ): Subgraph induced by degree-two variable node in G.
b V ′ = {v ∈ Vb2 : v
2) G
2
′
′
b
b
belongs to a cycle in G2 }, C = {c ∈ C : c is connected to some v ∈ V }
2

2

b=G
b − {V ′ , C ′ }.
3) G
2
2
′
b : c is connected to some v ∈ V ′ }.
4) V1 = {v ∈ Vb : deg(v) = 1}, C1′ = {c ∈ C
1
′
′
b=G
b − {V , C } (delete nodes and edges connected to them).
5) G
1

1

end while

b
6) RED(G) = G.

2) Double Exponential Fall: We will now show that xt and y t corresponding to each edge
e ∈ RED(G) fall double exponentially in the density evolution analysis of protograph G. For
an edge e ∈ ERED(G) , observe that Ece ⊂ ERED(G) . So, from (3), it is easy to see that if xte
falls double exponentially for all e ∈ ERED(G) , then yet will fall double exponentially for all
e ∈ ERED(G) . So, it is enough to show xte for all e ∈ RED(G) falls double exponentially with
t.
Theorem 1. Let ERED(G) denote edges of RED(G). Let xt =

max

e∈ERED(G)

xt (e), where xt (e) is

the erasure probability along edge e in the density evolution recursion of G. Let ǫth denote the
density evolution threshold of G. If RED(G) is non-empty, then ERED(G) ⊂ Dxy .
Proof. The proof follows the proof of [6, Theorem 1] very closely. We will briefly sketch the
proof here.
First observe that ERED(G) ⊂ E. Let us consider e ∈ ERED(G) . From the density evolution
DRAFT

October 27, 2017

11

recursions in (2)-(4), we know
yct+1
≤ C2 (xt ),
j ,n

t+1
xvi ,m ≤ C1 ǫ
max

m∈{1,··· ,dvi }

≤ C1 ǫ



max

m∈{1,··· ,dvi }

(6)
yvt+1
i ,m

dvi (G)−1

yvt+1
i ,m

dvi (RED(G))−1

,

(7)
,

(8)

where C1 and C2 are positive constants, dvi (G) and dvi (RED(G)) are degree of the variable
node vi in G and RED(G), respectively. By combining (6) and (8), we get
xt+1 ≤ {C2 }dvi (RED(G))−1 C1 {(xt )}dvi (RED(G))−1 .

(9)

Let v2 be the number of degree-two variable nodes in RED(G). Now, a squaring term appears
in the RHS of the bound above at least once in every 2v2 + 1 iterations because in every edge
traversal on RED(G) with 2v2 + 1 steps there is at least one variable node with degree at least
3. Since ǫ ≤ ǫth , t can be chosen sufficiently large to make the constant term in the expression
of xt to be smaller than one. This can be formally shown using the same argument as in [6].
Therefore, we have proved that there exists R such that
xt+2v2 +1 ≤ A(xt )2 ,
where A is constant and Axt ≤ 1 for t > R. By applying the above repeatedly, we can show
that
i

xR+i(2v2 +1) ≤ A−1 (AxR )2 ,

(10)

for every positive integer i, which implies ERED(G) ⊂ Dxy and the proof of the theorem is
complete.
In Theorem 1, we have shown that ERED(G) ⊂ Dxy . If e ∈ Dxy , then xte′ corresponding to
edge e′ ∈ {Eve \ e} falls double exponentially. So, {Eve \ e} ⊂ Dx for each e ∈ ERED(G) . Now
consider an edge e ∈
/ ERED(G) . We have
yet = 1 −

Y

(1 − xt−1
e′ ).

e′ ∈Ece \e

If {Ece \ e} ⊂ Dx , then e ∈ Dy . Using the above two steps, we will find Dy and Dx from
ERED(G) by using a message passing algorithm. Let ret and ste denote messages on edge e in
October 27, 2017

DRAFT

12

1) If e ∈ ERED(G) , then initialize re0 = 1, otherwise re0 = 0.
2) For e ∈ E, if ∃e′ ∈ {Eve \ e} such that ret ′ = 1, then ste = 1.
3) For e ∈ E, if ste′ = 1 ∀e′ ∈ {Ece \ e}, then ret+1 = 1.
4) Continue 2 and 3 till ret = ret−1 . and ste = st−1
e .
5) Dx = {e ∈ E : ste = 1} and Dy = {e ∈ E : ret = 1}.

v1

c1

v2

(a) Protograph G.

c4

v4

c3

v3

v2

c4

v4

c4

c3

v3

v4

b after first iteration of Algorithm (c) G.
b after second iteration.
(b) G

??.

Fig. 3: RED(G) : Empty.

t-th iteration from check node to variable node and variable node to check node, respectively.
Algorithm ?? and ?? are illustrated through the following examples.
Example 3. Consider the rate-1/4 LDPC protograph G in Fig. 3a. G has a degree-one variable
node v1 . After removing v1 , and the check node c1 connected to v1 from G, we get the reduced
protograph shown in Fig. 3b. Removal of edges connected to v1 and c1 reduces degree of
variable node v2 to one. Removal of newly introduced degree-one variable node v2 and check
node connected to it introduces a cycle v4 c4 formed by degree-two variable nodes. Removal of
loop v4 c4 from Fig. 3c results in a empty RED(G). So, Dxy = Dy = Dx = ∅.
Example 4. Consider the rate-1/4 protograph (G) in Fig. 4a. After removal of degree-one
variable node v1 and its neighboring check node c1 , we get Fig. 4b. Removal of v1 and c1
introduces a degree-one variable node v2 in Fig. 4b. After removal of v2 , we get Fig. 4c, which
does not have a variable node with degree ≤ 2. Hence, xt and y t for all edges in Fig. 4c have
double exponential fall property in density evolution analysis of G. Algorithm ?? is illustrated
through Fig. 5. Algorithm ?? starts by assigning re0 = 1 for e ∈ ERED(G) and re0 = 0 for
e ∈ E \ERED(G) . In Fig. 5, edges are labeled with messages carried by them. Arrow indicates the
direction of message in an edge. After end of Algorithm ??, we get Dy = {ERED(G) , v2 c2 , v1 c1 }.
DRAFT

October 27, 2017

13

v4

c3

v3

v4

c3

v4

v3

c3
v1

c1

v2

c2

v2

v3

c2

b after first iteration of Algorithm ??.
(b) G.

(a) Protograph G.

(c) RED(G).

Fig. 4: RED(G): Non empty.

v4

1

c3

1

v3

1

v4

1

c3

v3

0
v1

0 c
1

0

v2

0

1

c3

1

c2

0

0 c
1

v1

0

v2

v1

1

v2

0

v3

c2

(d) s1e for iteration 1.

c2

(b) s0e for iteration 0.
v4

1

c3

1

c3

1

v3

0
v1

0 c
1

0

v2

1

c2

(c) re1 for iteration 1.

v3

1
0 c
1

1

1

(a) re0 for iteration 0.
v4

v4

0
v1

1 c
1

0

v2

1

c2

(e) re2 for iteration 2.

Fig. 5: Illustration of Algorithm ??.

3) Extension to DGLDPC protograph: For an edge e in a DGLDPC protograph G, let
hce and hve denote the extrinsic message erasure probabilities at the check node and variable
node, respectively. Note that hce and hve are polynomials in multiple variables denoting erasure
probabilities of edges in Ece \ e and Eve \ e, respectively (see (2)-(4)). Let dce and dve denote
the least sum degree of terms in hce and hve , respectively. In a standard protograph, edges from
degree-1 variable nodes and edges in loops formed by degree-2 variable nodes do not have
double exponential fall in erasure probabilities. In a DGLDPC protograph, the corresponding
edges are as follows. Let E1 = {e : dve = 0 or dce = 0}, i.e E1 is the set of edges with a
constant term in their corresponding hce or hve . Let G2 be the subgraph induced by edges in
{e : dce = 1 or dve = 1}. A cycle {e1 e2 · · · e2l e1 } is said to be non-DEX(does not have double
exponential fall property) if the 2l multivariate polynomials hce1 , hve2 , hce3 , hve4 , · · · , hce2l−1 , hve2l
share at least one degree-1 term. Let E2 be the set of edges in non-DEX cycles of G2 .
Algorithm ?? is run with the above generalized definition of E1 and E2 to find RED(G)
for a DGLDPC protograph G. Another modification is as follows: after removing an edge, the

October 27, 2017

DRAFT

14

message erasure probability of all edges are updated by replacing the message corresponding to
the removed edge by 1. Algorithm ?? is extended with no significant modification.
4) Block-error threshold: We now use Theorem 1 and its generalized version to a sequence
of large girth liftings of a DGLDPC protograph G and state conditions for block-error threshold
property. Let us denote the set of variable nodes of G for which Pb (v) falls double exponentially
by DEX(V ). Let G be the code lifted from protograph G with blocklength n and message length
k. Let us define Pb as Pb = maxv∈VI Pb (v), where VI is a set of variable nodes corresponding
to message bits. Probability of block error can be bounded as PB < kPb . Let VD be the variable
nodes in G corresponding to DEX(V ).
Theorem 2. In the notation introduced above, if VI ⊂ VD , and girth of G is at least c log n,
then
PB ≤ kO(exp(−βnα )),
where α, β, c are positive constants.
Proof. We know that Pb (v) corresponding to v ∈ DEX(V ) fall double exponentially in density
evolution of G, i.e.,
Pb (v) = O(exp(−β2αt ))
for v ∈ DEX(V ) with α, β being positive constants. Since VI ⊂ VD , Pb (v) = O(exp(−β2αt ))
for v ∈ VI . So, probability of block error of G, denoted by PB , can be bounded as follows:
PB ≤ kO(exp(−β2αt ))
for ǫ ≤ ǫth . Assuming t < g/2 and putting t = c log n, we get
PB ≤ kO(exp(−βnα )).

From above theorem, if ǫ < ǫth , we can deduce that PB → 0 as n → ∞. The rate-1/4
protograph in Fig. 4a has one information bit and it satisfies the block-error threshold condition,
because Pb corresponding to degree-three variable node of G fall double exponentially as
described in Example 3. So, block-error threshold and bit-error threshold can be made equal for
appropriate lifting size using Theorem 2. Protographs can be lifted to have large girth (O(c log n))
by using the large girth construction in [6]. Similarly, the rate-1/4 protograph in Fig. 3a has

DRAFT

October 27, 2017

15

one information bit. However, for this protograph, block-error threshold cannot be made equal
to bit-error threshold by using Theorem 2, because Pb corresponding to any variable nodes of
G does not fall double exponentially.
The block-error threshold condition for BIAWGN channel is same as block-error threshold
condition for BEC and can be proved using a Bhattacharya parameter argument as in [6, Theorem
3] and [18, Theorem 2].
IV. O PTIMIZED DGLDPC P ROTOGRAPHS
In this section, we design capacity-approaching protographs with block-error threshold by
using the condition derived in Section III. Let G be a protograph of size |V | × |C|, where V
and C denote the set of variable and check nodes. We divide variable nodes in V into two sets
- standard variable nodes denoted Vs , and generalized variable nodes denoted Vg . Cs and Cg are
similar notations for check nodes. We use repetition code and SPC code at standard variable
nodes and check nodes, respectively. At a generalized node v, we choose a (dv , kv ) linear code
as component code. To design a rate-r code, we choose component codes at generalized nodes
in such a way that r = 1 −

P|C|

i=1 (dci −kci )
P|V |
i=1 kvi

. At standard variable node v and check node c, we

have kv = 1 and dc − kc = 1. We maximize the threshold of protograph over the connections
of protograph, degree of standard nodes, and label of edges connected to generalized nodes by
using differential evolution [19].

A. Differential Evolution
Different steps of differential evolution are elaborated as follows. The details of optimizing
labels of edges at generalized nodes is skipped for brevity.
1) Initialization is done as follows
• Start with |C||V | base matrices Bk,0 , 0 ≤ k ≤ |C||V |, each of size |C| × |V |. To
restrict the search space, entries of base matrices are chosen randomly from the set
{1, 2, · · · , 8}. Enforce variable and check node degree constraint at generalized nodes,
P|V |
P
i.e. |C|
j=1 Bk,0 (i, j) = dci , ci ∈ Cg .
i=1 Bk,0 (i, j) = dvj , for vj ∈ Vg ,

If Bk,0 does not satisfy block-error threshold condition derived in Theorem 2, add an edge
between degree-1 or degree-2 standard variable node and standard check node, chosen
randomly. Continue adding such edges till the block-error threshold condition is satisfied.

October 27, 2017

DRAFT

16

2) Mutation: Protographs of generation G (G = 0, 1, · · · ) are interpolated as follows.
Mk,G = [Br1 ,G + 0.5(Br2 ,G − Br3 ,G )],

(11)

where r1 , r2 , r3 are randomly-chosen distinct values, and [x] denotes the absolute value of
x rounded to the nearest integer.
′
3) Crossover: The (i, j)-th entry of a candidate protograph Bk,G
is set as the (i, j)-th entry of

Mk,G with probability pc , or as the (i, j)-th entry of Bk,G with probability 1 − pc . We use
pc = 0.88 in our optimization runs.
′
4) Selection: If the threshold of Bk,G is greater than that of Bk,G
and it satisfies block-error
′
threshold condition in Theorem 2, set Bk,G+1 = Bk,G ; else, set Bk,G+1 = Bk,G
.

5) Termination: Steps 2–4 are run for several generations (we run up to G = 6000) and the
protograph that gives the best threshold is chosen as the optimized protograph.
We compute thresholds of protographs for the BEC by using the density evolution described in
Section II-B. We compute thresholds of protograph for AWGN channel using the EXIT function
method described in [20].

B. Lifting Protographs
A |v| × |c| protograph G is lifted to a LDPC code of length n as follows:
1. Let m denote the maximum element of the corresponding |V | × |C| base matrix B. Replace
B(i, j) with a random m × m binary matrix M with row and column sum equal to B(i, j).
If B(i, j) = 0, replace by an m × m zero matrix. Denote the new |V |m × |C|m binary
matrix as B ′ .
2. We assume m|V | divides n. Replace each nonzero entry of B ′ with a

n
× |Vn|m ,
|V |m

randomly

generated, circular shift permutation matrix.
There can be more sophisticated liftings. However, we use the above simple method in all
simulations and do not attempt to optimize the lifting further.

C. Optimized protographs for BEC
For BEC, optimized LDPC protographs (base matrices) of rate 1/10 and 1/8 with block-error
thresholds within 0.01 of capacity are given in (14) and (15), respectively, in the Appendix. It
is observed that optimized protographs have significant fraction of degree-one variable nodes.

DRAFT

October 27, 2017

17

Thresholds of LDPC protographs with degree-one nodes, LDPC protographs without degreeone nodes, GLDPC protographs with degree-one nodes and AR4A protograph [21] for BEC
have been compared in Table I. We see that optimized protographs have better thresholds when
degree-one nodes are allowed in optimization. For example, an optimized, rate-1/8, Protograph
with degree-one bit nodes in (15) has threshold 0.866 over BEC, while optimized, rate-1/8
protograph without degree-one nodes has a threshold 0.85. From Table I, it is also observed
that use of a generalized component code does not improve the threshold. However, generalized
nodes are useful in designing smaller protographs with block-error threshold reasonably close
to capacity. For example, an optimized 8 × 10, rate-1/8 DGLDPC protograph has block-error
threshold 0.86 which is quite close to 0.866 achieved with a 21 × 24 LDPC protograph.
Optimized protographs in Table I are lifted to codes of blocklength 5000 using the method
in Section IV-B and their BER/FER are simulated using the standard message-passing decoder.
The plots are shown in Fig 6a. For comparison, AR3A/AR4A [7] protographs are lifted to the
same blocklength of 5000 using the method in Section IV-B and their BER/FER are plotted in
Fig. 6a. We see that the BER and FER of optimized codes are better than that of AR4A codes
of same rate.
D. Optimized Protographs For AWGN
Observations similar to the BEC case hold for AWGN channel as well. Fig. 6(b) compares
BER/FER of optimized rate-1/3 and rate-1/4 codes with codes of same rate from DVBS2
standard [9] and AR4A family. The blocklength for all codes are fixed to 64800. Parity check
matrix corresponding to optimized protographs and AR4A protographs are obtained by method
described in Section IV-B. BER and FER performance of optimized codes are better than the
corresponding DVBS2/AR4A codes. BER/FER performance of optimized codes can be further
improved by using more optimized liftings.
In summary, we designed low-rate codes with block-error threshold close to capacity. From
simulation, we observe that optimized codes have better FER performance than comparable
protographs of same rate.
R EFERENCES
[1] R. Gallager, “Low-density parity-check codes,” Ph.D. dissertation, Massachusetts Institute of Technology, 1963.
[2] D. Mackay and N. Neal, “Near Shannon limit performance of low density parity check codes,” IEEE Electron. Letter,
vol. 2, pp. 1645–1646, 1996.

October 27, 2017

DRAFT

18

100

Error Rates

10−1
r=

1
8

r=

1
8

10−2

10−3

r=

10−4

1
8

r=

1
10

r=

Proposed
AR4A

1
10

0.82 0.83 0.84 0.85 0.86 0.87 0.88 0.89 0.9
ǫ
(a) Performance of codes over BEC, length=5000.

100
r=

Error Rates

10−1

1
4

10−2
10

r=

−3

10−4

1
3
Proposed
DVBS2
AR4A

r=
−5

1
3

r=
−4.5

1
3

r=
r=

−4
−3.5
SNR in dB

1
4

1
4

−3

(b) Performance of codes over AWGN, length=64800.

Fig. 6: BER:Solid, FER:Dashed.

DRAFT

October 27, 2017

19

Rate

1/10

Size of

Types of

DE

Block

Protograph

Protograph

Threshold

Threshold

0.894

Yes

0.868

No

0.892

Yes

0.877

Yes

0.866

Yes

0.846

No

0.866

Yes

0.85

Yes

0.86

Yes

27 × 30 in (14)
10 × 11

LDPC with
degree-1
AR4JA

in [7, Fig. 12]
17 × 23
27 × 30

1/8

21 × 24 in (15)
8×9

GLDPC with
degree-1
LDPC w/o
degree-1
LDPC with
degree-1
AR4JA

in [7, Fig. 11]
13 × 19
14 × 16 [6]
8 × 10

GLDPC with
degree-1
LDPC w/o
degree-1
DGLDPC w/o
degree-1

TABLE I: Optimized protographs and thresholds for BEC.

[3] A. Subramanian, A. Suresh, S. Raj, A. Thangaraj, M. Bloch, and S. McLaughlin, “Strong and weak secrecy in wiretap
channels,” in Turbo Codes and Iterative Information Processing (ISTC), 2010 6th International Symposium on, Sep. 2010,
pp. 30 –34.
[4] D. Divsalar, C. Jones, S. Dolinar, and J. Thorpe, “Protograph based LDPC codes with minimum distance linearly growing
with block size,” in GLOBECOM ’05. IEEE Global Telecommunications Conference, 2005., vol. 3, Nov 2005.
[5] M. Lentmaier, D. Truhachev, K. Zigangirov, and D. Costello, “An analysis of the block error probability performance of
iterative decoding,” IEEE Trans. Inf. Theory, vol. 51, no. 11, pp. 3834 –3855, Nov. 2005.
[6] A. Pradhan, A. Thangaraj, and A. Subramanian, “Construction of near-capacity protograph LDPC code sequences with
block-error thresholds,” IEEE Trans. Commun., vol. 64, no. 1, pp. 27–37, Jan 2016.
[7] D. Divsalar, S. Dolinar, and C. Jones, “Low-rate LDPC codes with simple protograph structure,” in Information Theory,
2005. ISIT 2005. Proceedings. International Symposium on, Sept 2005, pp. 1622–1626.
[8] T. Richardson and R. Urbanke, “Multi-edge type LDPC codes,” Apr. 2004, unpublished. [Online]. Available:
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.106.7310
[9] “Digital video broadcasting; second generation framing structure, channel coding and modulation systems for broadcasting,
interactive services, news gathering,” EN 302 307 V1.1.1, 2004, [online] Available: http://www.etsi.org.
[10] R. Tanner, “A recursive approach to low complexity codes,” Information Theory, IEEE Transactions on, vol. 27, no. 5, pp.
533–547, Sep 1981.

October 27, 2017

DRAFT

20

Rate

1/4

Size of

Types of

DE

Block

Protograph

Protograph

Threshold

Threshold

-0.630

Yes

DVBS2

-0.35

No

AR4A

-0.522

No

-0.330

Yes

DVBS2

-0.1

No

AR4A

-0.130

No

30 × 40 in (13)

4 × 5 in [7, Fig.8]
1/3

30 × 45 in (12)

3 × 4 in [7, Fig.7]

LDPC with
degree-1

LDPC with
degree-1

TABLE II: Optimized protographs and thresholds for AWGN.

[11] M. Lentmaier and K. Zigangirov, “On generalized low-density parity-check codes based on Hamming component codes,”
Communications Letters, IEEE, vol. 3, no. 8, pp. 248–250, Aug 1999.
[12] J. Boutros, O. Pothier, and G. Zemor, “Generalized low density (Tanner) codes,” in Communications, 1999. ICC ’99. 1999
IEEE International Conference on, vol. 1, 1999, pp. 441–445 vol.1.
[13] E. Paolini, M. Fossorier, and M. Chiani, “Doubly-generalized LDPC codes: Stability bound over the BEC,” Information
Theory, IEEE Transactions on, vol. 55, no. 3, pp. 1027–1046, March 2009.
[14] Y. Wang and M. Fossorier, “Doubly generalized LDPC codes over the AWGN channel,” Communications, IEEE
Transactions on, vol. 57, no. 5, pp. 1312–1319, May 2009.
[15] E. Paolini, M. Fossorier, and M. Chiani, “Generalized and doubly generalized LDPC codes with random component codes
for the binary erasure channel,” Information Theory, IEEE Transactions on, vol. 56, no. 4, pp. 1651–1672, April 2010.
[16] S. Abu-Surra, D. Divsalar, and W. Ryan, “Enumerators for protograph-based ensembles of LDPC and generalized LDPC
codes,” Information Theory, IEEE Transactions on, vol. 57, no. 2, pp. 858–886, Feb 2011.
[17] M. Lentmaier, M. Tavares, and G. Fettweis, “Exact erasure channel density evolution for protograph-based generalized
LDPC codes,” in Information Theory, 2009. ISIT 2009. IEEE International Symposium on, June 2009, pp. 566–570.
[18] A. K. Pradhan and A. Thangaraj, “Near-capacity protograph doubly-generalized LDPC codes with block thresholds,” in
2016 IEEE International Symposium on Information Theory (ISIT), July 2016, pp. 2534–2538.
[19] A. Shokrollahi and R. Storn, “Design of efficient erasure codes with differential evolution,” in Information Theory, 2000.
Proceedings. IEEE International Symposium on, 2000, p. 5.
[20] E. Sharon, A. Ashikhmin, and S. Litsyn, “EXIT functions for binary input memoryless symmetric channels,” IEEE
Transactions on Communications, vol. 54, no. 7, pp. 1207–1214, July 2006.

DRAFT

October 27, 2017

21

[21] D. Divsalar, S. Dolinar, C. Jones, and K. Andrews, “Capacity-approaching protograph codes,” IEEE J. Sel. Areas Commun.,
vol. 27, no. 6, pp. 876 –888, Aug. 2009.

A PPENDIX A
O PTIMIZED C ODES

Non zero entries of optimized base matrices corresponding to different rates are given below.
Non zero entries of the i-th row of a base matrix is listed next to i :. Superscript denotes the
element at that location. If superscript is not mentioned, then non-zero element at that location
is 1.

1 : 3, 10, 152, 32, 37, 39.

2 :82 , 11, 12, 14, 25.

5 : 2, 4, 6, 8, 11, 26, 29,

6 :6, 8, 13, 15, 22, 25.

31, 40, 43, 45.
10 : 3, 6, 82 , 15, 20, 29.
12 : 1, 8, 10, 12, 25,
26, 27.

8 :11, 14, 18, 22, 23,
25, 37.
13 :8, 132, 14, 23, 25,
27, 42.

16 : 5, 6, 8, 9, 15, 25, 40. 17 :5, 8, 23, 25, 43.
20 : 1, 6, 7, 9, 14, 26,
41.
25 : 3, 6, 8, 112, 15, 19,
23, 24, 26, 33.
29 : 5, 7, 10, 13, 14, 33,
37.

October 27, 2017

21 :2, 8, 12, 13, 25, 28,
32, 41, 45.
26 :3, 6, 8, 21, 23,
25, 27.
30 :6, 8, 252, 30.

3 :8, 10, 12, 13, 25, 29,
33.
9 :3, 5, 9, 10, 19, 36,
42, 44.
14 :82 , 10, 13, 15, 34,
25, 27, 31, 42.
18 :2, 7, 8, 9, 15, 19,
28, 37.
23 :5, 8, 19, 23, 25, 37,
44.
28 :5, 8, 9, 19, 25, 38,

4 :5, 82 , 25, 39.
7 :1, 82 , 10, 12, 32,
33, 35, 42, 43.
11 :6, 8, 23, 25.
15 :3, 6, 8, 10, 11, 14,
27, 31, 42.
19 :4, 5, 6, 8, 14, 25.
22 :52 , 6, 17, 25, 43.
24 :3, 6, 8, 11, 19.
27 :6, 8, 12, 16, 19,
23, 42.

44.
(12)

DRAFT

22

1 : 2, 12, 14, 20, 30.

2 :2, 11, 17, 202.

3 :2, 11, 14, 20, 26, 29.

5 : 22 , 7, 18, 23, 32,

6 :11, 12, 14, 20, 24.

7 :2, 14, 20, 36.

8 :6, 9, 202, 35.

9 :2, 6, 20, 23, 35, 40.

35.
11 : 9, 14, 35, 37, 39,

12 :2, 3, 11, 122, 19,

10 :11, 14, 18, 20, 37.
14 :14, 202, 28, 33.

20, 21, 332, 34.

15 :3, 15, 20, 30, 35.

16 :5, 11, 14, 20.

352 , 38, 39.

18 :2, 8, 12, 28, 30, 35.

19 :2, 11, 14, 20.

20 :2, 10, 12, 14, 20.

21 :2, 4, 20, 30, 35, 38.

22 :2, 142, 31, 32, 35.

17 : 4, 11, 16, 20, 25,

23 : 2, 3, 21, 26, 35.

35.

13 :2, 3, 4, 12, 25, 35.

40

35.

4 :13, 22, 27, 28, 30.

24 :9, 11, 122, 27, 28. 25 :2, 14, 19, 20, 25.

27 : 9, 19, 21, 33, 352. 28 :22, 23, 352.

26 :2, 7, 11, 12, 23, 34.

29 :4, 14, 20, 30, 31, 39. 30 :1, 9, 12, 20, 22. (13)

1 : 3, 21, 29.

2 :10, 21, 24.

3 :11, 12, 14, 21.

4 :6, 12, 21, 30.

6 : 8, 20, 212, 23.

7 :7, 9, 11.

8 :3, 8, 21, 28, 30.

9 :162 , 18.

11 : 4, 11, 25.

12 :11, 25, 29.

13 :5, 11, 25.

16 : 11, 252 .

17 :1, 3, 14, 18, 212. 18 :8, 9, 17, 21.

21 : 11, 15, 22.

22 :3, 9, 13, 30.

26 : 8, 11, 21.

27 :15, 25, 29.

23 :19, 212.

5 :18, 21, 29.
10 :10, 21, 25, 26.

14 :2, 16, 21, 24. 15 :21, 24, 27.
19 :7, 14, 21, 25. 20 :11, 24, 25, 30.
24 :8, 11, 20.

25 :32 , 7, 13, 14,
19, 24, 25, 30.
(14)

1 : 2, 5, 9, 12, 13,
17, 23.

2 :13, 15, 18, 23.

3 :6, 10, 12, 13.

4 :8, 10, 13, 17.

5 :7, 13, 15.

6 :13, 15, 17.

7 :6, 7, 11, 15,

8 :4, 7, 13, 18.

9 :7, 14, 15, 17.

10 : 72 , 12, 21.

11 :3, 72 .

14 : 72 , 17, 20.

15 :2, 7, 12.

19 : 72 , 12.

20 :7, 11, 18, 222, 21 :1, 7, 12, 15.
24.

DRAFT

18.

12 :7, 13, 15, 19. 13 :7, 13, 182, 24.

16 :72 , 9, 13, 22. 17 :9, 132, 152 ,

18 :6, 7, 9, 13.

16, 17.
(15)

October 27, 2017

