Low Complexity Progressive Edge-Growth
algorithm based on Chinese Remainder Theorem
Xueqin Jiang, Papa Ousmance Thiaw Diagne, Moon Ho Lee, Senior Member, IEEE and Wujun Xu
Abstract—Progr essive edge-growth (PEG) algorithm construc-
tion builds the Tanner graph for an LDPC code by establishing
edges between the symbol nodes and the check nodes in an
edge-by-edge manner and maximizing the local girth in a
greedy fashion. This approach is simple but the computational
complexity of the PEG algorithm scale as O(),where is the
number of symbol nodes and is the number of check nodes.
We deal with this problem by first construct a base LDPC code of
length
1
with the PEG algorithm and then extend this LDPC
code into an LDPC code of length ,where À
1
,viathe
the chinese remainder theorem (CR T). This method increase the
code length of an LDPC code generated with the PEG algorithm,
without decreasing its girth. Due to the code length reducing in
the PEG construction step, the computational complexity of the
whole code construction process is reduced. Furthermore, the
proposed algorithm have a potential advantage by storing a small
parity-check matrix of a base code and extending it “on-the-fly”
in hardware.
Index Terms—LDPC codes, Progressive Edge-Growth (PEG)
algorithm, Chinese Remainder Theorem (CRT), girth.
I. I
NTRODUCTION
C
HINESE remainder theorem (CRT) [1][2][3] tells that a
positive integer can be uniquely reconstructed from its
remainders modulo positive integers,
1
2
,if
lcm{
1
2
} where lcm stands for the least common
multiple, and furthermore it provides a simple reconstruction
formula if all moduli
are co-prime.
Low-density parity-check (LDPC) codes, first proposed
in the early 1960’s [4] and re-discovered in 1996 [5],
have recently attracted much attention due to their capacity-
approaching performance. LDPC codes belong to the class of
linear block codes, whose performance improves as the code
length becomes very large [8][9]. Based on the methods of
construction, LDPC codes can be classified into two general
categories: 1) structured codes; and 2) random (or random-
like) codes. A method to extend the code length of quasi-
cyclic (QC) LDPC codes, which is a class of structured LDPC
codes via CRT was proposed in [10]. Codes result from this
method have flexible code lengths, flexible code rates and,
most importantly, large girths. Among the existing methods
for the construction of random-like LDPC codes, one of the
most successful approaches is progressive-edge-growth (PEG)
algorithm proposed in [6][7]. The PEG algorithm is simple
but not efficient. In the case of long codes, the construction of
LDPC codes with this approach requires long time consump-
tion. In the worst case, the computational complexity of the
PEG algorithm scale as O().
In this paper, motivated by the high computational complex-
ity problem of the PEG algorithm and the simplicity of the ex-
tending method for QC LDPC codes via CRT, we combine the
CRT with the PEG algorithm in the construction of random-
like LDPC codes. Note that our proposed algorithm is not
just extending the method used earlier in the construction of
QC LDPC code to the random-like LDPC code. The proposed
method extend a short base LDPC code, constructed by PEG
algorithm, via CRT without reducing its girth. The simulation
results show that the extended codes perform better than the
base PEG LDPC codes and perform similar to long PEG
LDPC codes of the same length with much less computational
complexity.
The remainder of this paper is organized as follows. Section
II reviews the PEG algorithm and the CRT. Section III
proposes a method to combine the PEG algorithm and CRT.
Lower bound on the girth of the PEG-CRT LDPC codes is
also derived in this section. Section IV introduce an improved
PEG-CRT algorithm. Section V presents examples of PEG-
CRT LDPC codes and improved PEG-CRT LDPC codes and
demonstrates their error-correcting performances. The com-
plexity of the proposed algorithm is analysis in Section VI.
Finally, Section VII concludes the paper.
II. P
RELIMINARIES
A. Progressive Edge-Growth Algorithm
Let denote a sparse parity-check matrix having dimension
× and let
= {
0
1
−1
} denote the set of
check nodes and
= {
0
1
−1
} denotes the set of
symbol notes. is the set of edges such that ⊆
×
,
with edge (
) ∈ if and only if
6=0,where
denotes the entry of at the -th row and -th column,
0 ≤ ≤ − 1, 0 ≤ ≤ − 1. In this algorithm, both
symbol nodes and check nodes are ordered according to their
degrees in nondecreasing order.
is the degree of symbol
node
,and
and
¯
denote the set of all check nodes
reached by a tree spreading from symbol node
with in
depth , and its complement, respectively [6]. PEG algorithm
constructs Tanner graphs having large girths and the lower
bound on the girth
is proved to be
≥ 2
⎛
⎝
⎢
⎢
⎢
⎣
log(
−
− +1)
log[(
− 1)(
− 1)]
− 1
⎥
⎥
⎥
⎦
+2
⎞
⎠
(1)
where
and
are the maximum degrees of the check
nodes and symbol nodes, respectively.
978-1-4673-1881-5/12/$31.00 ©2012 IEEE