Low-Density Parity-Check Codes
First proposed by Gallager in 1962 [127] and reexamined in [302, 303, 416, 417], low-density parity-check codes
have been shown to be a very promising coding technique for approaching the
channel capacity in AWGN channels. For example, a carefully constructed rate-½
irregular LDPC code with long block length has a bit-error probability of
10-6 just 0.04 dB away from the Shannon capacity of AWGN channels [82].
As the name suggests, an LDPC code is a linear block code
specified by a very sparse parity-check matrix as illustrated in Fig. 10.25. The parity-check matrix H of a regular
(N, K, s, t) LDPC code of rate R = K/N is an (N - K)
xN matrix, which has s 1s in each column and t >
s 1s in each row where s << N. Apart from these constraints, the 1s are typically
placed at random in the parity-check matrix. When the number of 1s in every
column is not the same, the code is known as an irregular LDPC code. It should be noted that the
parity-check matrix is not constructed in systematic form. Consequently, to
obtain the generator matrix G, we first
apply Gaussian elimination to reduce the parity-check matrix to a form H = [IN–K|PT],
where IN–K is an (N – K)
x (N – K) identity matrix. Then the generator
matrix is given by G = [P|IK]. In
contrast to P, the generator matrix G is dense. Consequently, the number of bit
operations required to encode is 
, which is larger than that for other
linear codes. Similar to turbo codes, LDPC codes can be efficiently decoded by a
suboptimal iterative belief propagation algorithm, which is explained in detail
in [127]. At the end
of each iteration, the parity check is performed. If the parity check is
correct, the decoding is terminated; otherwise, the decoding continues until it
reaches the maximum number of iterations (e.g., 30).
The code with parity-check matrix H can be represented by a bipartite graph which
consists of two types of nodes, variable nodes and check nodes. Each code bit is
a variable node, while each parity check or each row of the parity-check matrix
represents a check node. An edge in the graph is placed between variable node
i and check node j
if Hj,i = 1. That is, each check node is connected to
code bits whose sum modulo-2 should be zero. Irregular LDPC codes are specified
by two polynomials 
and 
, where
li is the
fraction of edges in the bipartite graph that are connected to variable nodes of
degree i, and pi is the
fraction of edges that are connected to check nodes of degree i. Equivalently, the degree profiles can also be
specified from the node perspective: two polynomials 
and 
where 
is the fraction of variable nodes of degree i and 
is the fraction of check nodes of
degree i. The parity-check matrix for an
irregular (7, 4) code and its associated bipartite graph is shown in Fig. 10.26 as an example. The degree
profiles for this code from the edge perspective are l(x) = 1/4 + ½x + ½x2 and
r(x) = x3. The
degree profiles from the node perspective are 
and 
Before we discuss the LDPC decoding algorithm, we first
establish the following notation. All extrinsic messages (information) are in
log-likelihood form, and the variable L is used
to refer to extrinsic messages. Superscript p is
used to denote quantities during the pth
iteration of LDPC decoding. A subscript b 
c or b 
c denotes quantities passed between the bit nodes and
the check nodes of the LDPC code. The variable (bit) nodes in the bipartite
graph of the LDPC code are numbered from 1 to N
and the check nodes from 1 to N – K (in any order). The degree of the ith bit node is denoted by 
and the
degree of the ith check node is denoted by Di. Denote by 
the set of edges connected to the ith bit node
and by 
the set of edges connected to the ith check node. That is, 
denotes
the kth edge connected to the ith bit node, and 
denotes
the kth edge connected to the ith check node. The particular edge or bit associated
with a piece of extrinsic information is denoted as the argument of L. For example, 
denotes
the extrinsic LLR passed from a bit node to a check node along the jth edge connected to the ith bit node, during the pth iteration within the LDPC decoder.
The LDPC decoding algorithm is summarized as follows.
Algorithm 10.4: [LDPC decoding
algorithm] Initially, all extrinsic messages are assumed
to be zeros 
Equation 10.79
-
- Check node update: For each of the
check nodes i = 1, 2, ..., N – K, for all edges that are connected to the check node, compute
the extrinsic message passed from the check node to the bit node, given
by
Equation 10.80
Equation 10.81
Sections
, block length 
