18-08-2012, 03:08 PM
Fast Decoding Algorithm for Low-Density Parity-Check Codes
Fast dec_LDPC.pdf (Size: 140.3 KB / Downloads: 63)
SUMMARY
A fast decoding algorithm for low-density
parity-check codes is presented based on graph decomposition
and two-way message passing schedule. Simulations show that
the convergence speed of the proposed algorithm is about twice
that of the conventional belief propagation algorithm.
key words: LDPC code turbo-type two-way algorithm
1. Introduction
The belief propagation algorithm (BPA) is considered
to be a standard decoding technique for low-density
parity-check (LDPC) codes[1-3]. The conventional
BPA is based on the °ooding schedule[2] (we will re-
fer to this type of BPA as the °ood algorithm (FA)
for convenience in this paper), in which all the vari-
able nodes and, successively, all the check nodes pass
new messages to their neighbors in a decoding iteration.
In this algorithm, the messages from each node only af-
fect the state of its immediate neighbors,which can lead
to a slow convergence speed when serial processors are
involved. In order to improve the convergence speed,
a turbo-type two-way algorithm (TTWA) is presented
here for decoding a general LDPC code. This new algo-
rithm is developed from a two-way schedule technique
for local decoding combined with a turbo mechanism
for global decoding. A pre-processing stage is involved
to decompose the general LDPC code into several tree-
structured component codes so that the LDPC code
can then be viewed as a concatenated tree (CT) code
[4], TTWA can then be used to accomplish the decod-
ing task. The proposed method is particularly suited to
the numerical evaluation of LDPC codes since modern
computers are still mainly based on serial processors.
2. Two-Way Schedule
This technique is suitable for decoding tree code, that
is, a code whose Tanner graph contains no loops. In
this schedule, messages are only passed once in each di-
rection along each edge in the tree during the whole de-
coding process to achieve optimal performance[2]. The
yThe author is with the State Key Lab of ISN, Xidian
University, Xi'an, Shaanxi, China
yyThe author is with Department of Electronic Engi-
neering, City University of Hong Kong, TatChee Avenue,
Kowloon, Hong Kong
yyyThe author is with IBM Zurich Research Laboratory,
Saumerstrasse 4, CH-8803, Rueschlikon, Switzerland
two-way schedule is more e±cient than the °ooding
schedule when decoding a tree code using a serial pro-
cessor (detailed discussions can be found in[2]). How-
ever it cannot be directly applied to a code containing
loops.
3. CT codes and Turbo-Type decoder
CT codes are formed from the parallel concatenation
of several tree codes[4], and can be decoded by a serial
Turbo-type algorithm. Suppose that there are M local
decoders and each is responsible for one component tree
code. The main decoding process is:
1. At the ¯rst iteration, an initial a priori LLR vector
for code bits is fed into the ¯rst local decoder.
2. The local decoders run successively on the turbo
principle [5]. LetL(m) denote the a posteriori LLR
vector of the mth component code and E(m)
last the ex-
trinsic LLR vector generated in the last iteration.
Firstly, E(m)
last is initialized to 0 for all m. With
~L
(m) = L(m) ¡E(m)
last as its input, the mth local de-
coder performs a posteriori probability decoding
and then outputs L(m) for the next decoder. Fi-
nally, the Mth (last) local decoder L(M) feeds into
the 1st (¯rst) local decoder for the next iteration.
3. The process iterates until some termination condi-
tion is satis¯ed.
With this algorithm, CT codes combine the advantages
of LDPC codes and Turbo codes and can achieve good
performance with low decoding cost. In the following,
we will show that this mechanism can be applied to
general LDPC codes to improve convergence speed.
4. TTWA and Graph Decomposition
TTWA, as the name indicates, uses the turbo mech-
anism in the global decoder and the two-way sched-
ule in the local decoders. If properly used, this algo-
rithm can provide fast convergence when a serial pro-
cessor is involved. Before it can be applied to a gen-
eral LDPC code, we need to decompose the code into
several trees by graph decomposition. Many meth-
ods can be employed for this purpose. One approach
is as follows. Given a Tanner graphT with variable
nodesº1; º2; : : : ; ºNand check nodes c1; c2; : : : ; cM (N
and M are the number of variable nodes and check
nodes respectively), we initially construct the ¯rst sub
treeT1by taking all of the variable nodes (and without
2
IEICE TRANS. COMMUN., VOL.Exx{?, NO.xx XX 200x
any check nodes). Next, we test each check node ck one
by one. If adding ck intoT1 results in loops, it will not
be acceptable; otherwise, we can add ck into T1. After
testing all the check nodes, the process of constructing
T1 is completed. In the same way, we construct T2
from the check nodes that were not added to T1. The
process is repeated to build sub trees T3;T4; : : : until no
check nodes are left. The above decomposing process
is illustrated by Fig.1, where Fig.1.a is a Tanner graph
with loops while Fig.1.b gives its two sub trees. After
the decomposition, the LDPC code can be viewed as a
CT code, and so the TTWA can be used for decoding.
code1 (solid line) and subcode2 (dot line)
5. Complexity
The proposed TTWA and the conventional FA involve
almost the same number of operations at each iteration,
i.e. about 6N¸ multiplications and 5N¸ additions each
iteration, where ¸is the average variable node degree.
6. Numerical Results
Fig.2 shows the performance of two irregular LDPC
codes (code length=1008 and 5000 respectively) de-
coded using the TTWA and FA methods. In the graphs,
solid lines mark the TTWA results and dashed lines the
FA performance; the iteration number can also be read
from the ¯gures. The LDPC codes used in the simula-
tion are constructed by the PEG algorithm [5] with the
following degree distributions:
¸(x) = 0:238687x1 + 0:209597x2 + 0:0035803x3
+ 0:135505x1 + 0:380408x14 (1)
½(x) = 0:017401x6 + 0:982599x7 (2)
Evidently, the TTWA converges faster than the FA.
This is due to the fact that the TTWA can achieve
locally optimal solution for a component tree code
within one iteration (this property does not hold for
the FA).Experimentally, we observed that di®erent de-
compositions of an LDPC code make little di®erence
to the convergence speed and performance. We also
observed that FA requires about twice the number of
iterations to achieve the same BER as TTWA.
1 1.5 2 2.5 3
10-5
10-4
10-3
10-2
10-1
Eb/N0(dB)
BER
0.5 0.75 1 1.25 1.5
10-5
10-4
10-3
10-2
10-1
Eb/N0(dB)
BER
TTWA
FA
TTWA
FA
NFA=2
NTTWA=2
NTTWA=16,32
NTTWA=8
NTTWA=4
NFA=32
NFA=16
NFA=8
NFA=4
NFA=4
NTTWA=4
NFA=8
NTTWA=8
NFA=16
NFA=32
NTTWA=16
NTTWA=32,50
NFA=50
Fig. 2 Comparison of convergence speed of TTWA and FA
Rate = 1/2 length =1008(left)length = 5000 (right)
7. Conclusion
We have presented a TTWA algorithm for decoding
general LDPC codes using a serial processor. Simu-
lation results show that the new algorithm converges
twice as fast as the conventional FA algorithm with
almost the same computational complexity and can
achieve the nearly same decoding performance. Thus
it can explore full advantage of the Turbo mechanism
and two-way schedule.