Efficient Implementations of the Sum-Product Algorithm for Decoding LDPC
Codes
Xiao–Yu Hu, Evangelos Eleftheriou, Dieter–Michael Arnold, and Ajay Dholakia
IBM Research, Zurich Research Laboratory, CH-8803 R¨uschlikon, Switzerland
Abstract— Efficient implementations of the sum-product algorithm
(SPA) for decoding low-density parity-check (LDPC) codes using log-
likelihood ratios (LLR) as messages between symbol and parity-check
nodes are presented. Various reduced-complexity derivatives of the LLR-
SPA are proposed. Both serial and parallel implementations are investi-
gated, leading to trellis and tree topologies, respectively. Furthermore, by
exploiting the inherent robustness of LLRs, it is shown, via simulations,
that coarse quantization tables are sufficient to implement complex core
operations with negligible or no loss in performance. The unified treat-
ment of decodingtechniques for LDPC codes presented here provides flex-
ibility in selecting the appropriate design point in high-speed applications
from a performance, latency, and computational complexity perspective.
I. INTRODUCTION
Iterative decoding of binary low-density parity-check
(LDPC) codes using the sum-product algorithm (SPA) has re-
cently been shown to approach the capacity of the additive
white Gaussian noise (AWGN) channel within 0.0045 dB [1-
3]. Efficient hardware implementation of the SPA has become
a topic of increasing interest. The direct implementation of the
original form of SPA has been shown to be sensitive to quanti-
zation effects [4]. In addition, using likelihood ratios can sub-
stantially reduce the required quantization levels [4]. A simpli-
fication of the SPA that reduces the complexity of the parity-
check update at the cost of some loss in performance was pro-
posed in [5]. This simplification has been derived by operat-
ing in the log-likelihood domain. Recently, a new reduced-
complexity decoding algorithm that also operates entirely in
the log-likelihood domain was presented [6]. It bridges the gap
in performance between the optimal SPA and the simplified ap-
proach in [5]. Finally, low complexity software and hardware
implementations of an iterative decoder for LDPC codes suit-
able for multiple access applications were presented in [7].
Here we present efficient implementations of the SPA and
describe new reduced-complexity derivatives thereof. In our
approach, log-likelihood ratios (LLR) are used as messages be-
tween symbol and parity-check nodes. It is known that in prac-
tical systems, using LLRs offers implementation advantages
over using probabilities or likelihood ratios, because multipli-
cations are replaced by additions and the normalization step
is eliminated. The family of LDPC decoding algorithms pre-
sented here is called LLR-SPA.
The unified treatment of decoding techniques for LDPC
codes presented here provides flexibility in selecting the appro-
priate design point in high-speed applications from a perfor-
mance, latency, and computational complexity perspective. In
particular, serial and parallel implementations are investigated,
leading to trellis and tree topologies, respectively. In both
cases, specific core operations similar to the special operations
defined in the log-likelihood algebra of [8] are used. This for-
mulation not only leads to reduced complexity LDPC decoding
algorithms that can be implemented with simple comparators
and adders but also provides the ability to compensate the loss
in performance by using simple look-up tables or constant cor-
rection terms.
The remainder of the paper is organized as follows. In Sec-
tion II, the SPA in the log-likelihood domain is described, and
the issues associated with a brute-force implementation are
discussed. In Section III, a trellis topology for carrying out
the parity-check updates is derived. The core operation on this
trellis is the LLR of the exclusive OR (XOR) function of two
binary independent random variables [8], rather than the hy-
perbolic tangent operation used in the brute-force implemen-
tation. This core operation can either be implemented very
accurately by using the
operation [9] or approximately
by using the so-called sign-
operation. In either case, the
check-node updates can be efficiently implemented on the trel-
lis by the well-known forward–backward algorithm. Section
IV is devoted to parallel processing, and a simple tree topol-
ogy with a new core operation is proposed. It is shown that
such an implementation offers smaller latency compared to the
serial implementation. In practice, this core operation can be
realized by employing a simple eight-segment piecewise linear
function. In Section V, simulation results are presented, com-
paring the performance of the various alternative implementa-
tions of the LLR-SPA. Finally, Section VI contains a summary
of the results and conclusions.
II. SPA
IN THE LOG-LIKELIHOOD DOMAIN
A binary
LDPC code [1, 2] is a linear block code
described by a sparse
parity-check matrix
, i.e.,
has a low density of 1s. The parity-check matrix
can be
viewed as a bipartite graph with two kinds of nodes:
symbol
nodes corresponding to the encoded symbols, and
parity-
check nodes corresponding to the parity checks represented by
the rows of the matrix
. The connectivity of the bipartite
graph is such that the parity-check matrix
is its incidence
matrix. For regular LDPC codes, each symbol is connected to
parity-check nodes and each parity-check node is connected
to
symbol nodes. For irregular LDPC codes,
and/or
are not constant.
Following a notation similar to [2, 5], let
denote the
set of check nodes connected to symbol node
, i.e., the po-
sitions of 1s in the
-th column of the parity-check matrix
, and let
!"#
denote the set of symbol nodes that partic-
ipate in the
#
-th parity-check equation, i.e., the positions of
1s in the
#
-th row of
. Furthermore,
!"#$%
represents
the set
!"#
, excluding the
-th symbol node, and similarly,
0-7803-7206-9/01/$17.00 © 2001 IEEE
1036
评论1