JOURNAL OF COMMUNICATIONS SOFTWARE AND SYSTEMS, VOL. 2, NO. 3, SEPTEMBER 2006
`
`191
`
`Design of LDPC Codes: A Survey and New Results
`
`Gianluigi Liva, Shumei Song, Lan Lan, Yifei Zhang, Shu Lin, and William E. Ryan
`
`Abstract— This survey paper provides fundamentals in the
`design of LDPC codes. To provide a target for the code designer,
`we first summarize the EXIT chart technique for determining
`(near-)optimal degree distributions for LDPC code ensembles.
`We also demonstrate the simplicity of representing codes by
`protographs and how this naturally leads to quasi-cyclic LDPC
`codes. The EXIT chart
`technique is then extended to the
`special case of protograph-based LDPC codes. Next, we present
`several design approaches for LDPC codes which incorporate
`one or more accumulators, including quasi-cyclic accumulator-
`based codes. The second half the paper then surveys several
`algebraic LDPC code design techniques. First, codes based on
`finite geometries are discussed and then codes whose designs
`are based on Reed-Solomon codes are covered. The algebraic
`designs lead to cyclic, quasi-cyclic, and structured codes. The
`masking technique for converting regular quasi-cyclic LDPC
`codes to irregular codes is also presented. Some of these results
`and codes have not been presented elsewhere. The paper focuses
`on the binary-input AWGN channel (BI-AWGNC). However,
`as discussed in the paper, good BI-AWGNC codes tend to be
`universally good across many channels. Alternatively, the reader
`may treat this paper as a starting point for extensions to more
`advanced channels. The paper concludes with a brief discussion
`of open problems.
`
`I. INTRODUCTION
`The class of low-density parity-check (LDPC) codes repre-
`sents the leading edge in modern channel coding. They have
`held the attention of coding theorists and practitioners in the
`past decade because of their near-capacity performance on a
`large variety of data transmission and storage channels and
`because their decoders can be implemented with manageable
`complexity. They were invented by Gallager in his 1960
`doctoral dissertation [1] and were scarcely considered in the
`35 years that followed. One notable exception is Tanner, who
`wrote an important paper in 1981 [2] which generalized LDPC
`codes and introduced a graphical representation of LDPC
`codes, now called Tanner graphs. Apparently independent of
`Gallager’s work, LDPC codes were re-invented in the mid-
`1990’s by MacKay, Luby, and others [3][4][5][6] who noticed
`the advantages of linear block codes which possess sparse
`(low-density) parity-check matrices.
`in LDPC code
`This papers surveys the state-of-the-art
`design for binary-input channels while including a few new
`
`results as well. While it is tutorial in some aspects, it is not
`entirely a tutorial paper, and the reader is expected to be fairly
`versed on the topic of LDPC codes. Tutorial coverages of
`LDPC codes can be found in [7][8]. The purpose of this paper
`is to give the reader a detailed overview of various LDPC code
`design approaches and also to point the reader to the literature.
`While our emphasis is on code design for the binary-input
`AWGN channel (BI-AWGNC), the results in [9][10][11][12]
`demonstrate that a LDPC code that is good on the BI-AWGNC
`tends to be universally good and can be expected to be good
`on most wireless, optical, and storage channels.
`We favor code designs which are most appropriate for appli-
`cations, by which we mean codes which have low-complexity
`encoding, good waterfall regions, and low error floors. Thus,
`we discuss quasi-cyclic (QC) codes because their encoders
`may be implemented by shift-register circuits [13]. We also
`discuss accumulator-based codes because low-complexity en-
`coding is possible from their parity-check matrices, whether
`they are quasi-cyclic or not. The code classes discussed tend
`to be the ones (or related to the ones) used in applications
`or adopted for standards. Due to time and space limitations,
`we cannot provide a complete survey. The present survey is
`biased toward the expertise and interests of the authors.
`Before a code can be designed, the code designer needs
`to know the design target. For this reason, Section II first
`briefly reviews the belief propagation decoder for LDPC
`codes and then presents the so-called extrinsic information
`transfer (EXIT) chart technique for this decoder. The EXIT
`chart technique allows one to obtain near-optimal parameters
`for LDPC code ensembles which guide the code designer.
`The EXIT technique is extended in Section III to the case
`of codes based on protographs. Section IV considers LDPC
`codes based on accumulators. The code types treated in that
`section are: repeat-accumulate,
`irregular repeat-accumulate,
`irregular repeat-accumulate-accumulate, generalized irregular
`repeat-accumulate, and accumulate-repeat-accumulate. That
`section also gives examples of quasi-cyclic code design using
`protograph (or base matrix) representations. Section V surveys
`the literature on cyclic and quasi-cyclic LDPC code design
`based on finite geometries. Section VI presents several LDPC
`code design techniques based on Reed-Solomon codes. Section
`VII presents the masking technique for converting regular QC
`codes to irregular QC codes to conform to prescribed code
`parameters. Section VIII contains some concluding remarks
`and some open problems.
`
`Manuscript received July 04, 2006; revised August 25, 2006. This work
`was supported by the University of Bologna, NASA-Goddard, and NSF.
`This paper has been approved by F. Chiaraluce.
`Gianluigi
`Liva
`is with
`the University
`gliva@deis.unibo.it).
`Shumei Song, Lan Lan, and Shu Lin are with the University of Cal-
`ifornia at Davis (e-mail: ssmsong@ece.ucdavis.edu, squashlan@gmail.com,
`shulin@ece.ucdavis.edu).
`Yifei Zhang and William E. Ryan are with the University of Arizona, U.S.A.
`(e-mail: {yifeiz, ryan}@ece.arizona.edu).
`
`of Bologna
`
`(email:
`
`II. DESIGN VIA EXIT CHARTS
`We start with an m × n low-density parity-check matrix
`H, which corresponds to a code with design rate (n − m)/n,
`1845-6421/06/6101 c(cid:176) 2006 CCIS
`
`CALTECH - EXHIBIT 2008
`Apple Inc. v. California Institute of Technology
`IPR2017-00219
`
`

`

`192
`
`JOURNAL OF COMMUNICATIONS SOFTWARE AND SYSTEMS, VOL. 2, NO. 3, SEPTEMBER 2006
`
`Fig. 1. Tanner graph representation of LDPC codes.
`
`We now discuss the EXIT chart technique [14][15][11] for
`this decoder and channel model. The idea is that the VNDs
`and the CNDs work cooperatively and iteratively to make
`bit decisions, with the metric of interest generally improving
`with each half-iteration. A transfer curve which plots the
`input metric versus the output metric can be obtained for
`both the VNDs and the CNDs, where the transfer curve for
`the VNDs depends on the channel SNR. Further, since the
`output metric for one processor is the input metric for its
`companion processor, one can plot both transfer curves on
`the same axes, but with the abscissa and ordinate reversed
`for one processor. Such a chart aids in the prediction of the
`decoding threshold of the ensemble of codes characterized by
`given VN and CN degree distributions: the decoding threshold
`is the SNR at which the two transfer curves just
`touch,
`precluding convergence of the two processors. EXIT chart
`computations are thus integral to the optimization of Tanner
`graph node degree distributions for LDPC codes and are the
`main computation in the optimization process. We emphasize
`that decoding threshold prediction techniques such as EXIT
`charts or density evolution [16] assume a graph with no
`cycles, an infinite codeword length, and an infinite number
`of decoding iterations.
`An EXIT chart example is depicted in Fig. 2 for the
`ensemble of regular LDPC codes on the BI-AWGNC with
`dv(i) = dv = 3 for i = 1, ..., n, and dc(j) = dc = 6 for
`j = 1, ..., m. In the figure, the metric used for the transfer
`curves is extrinsic mutual information, giving rise to the name
`extrinsic information transfer (EXIT) chart. (The notation
`used in the figure is explained below.) Also shown in the
`figure is the decoding trajectory corresponding to these EXIT
`curves. As the SNR increases, the top curve shifts upwards,
`increasing the ”tunnel” between the two curves and thus the
`decoder convergence rate. The SNR for this figure is just
`above the decoding threshold for codes with (dv, dc) = (3, 6),
`(Eb/N0)thres = 1.1 dB. Other metrics, such as SNR and mean
`[17][18] and error probability [19] are possible, but mutual
`information generally gives the most accurate prediction of the
`decoding threshold [14][20] and is a universally good metric
`across many channels [9][10][11][12].
`To facilitate EXIT chart computations, the following Gaus-
`sian assumption is made. First, we note that the LLR Lch
`in (1) corresponding to the BI-AWGNC is Gaussian with
`mean µch = 2x/σ2
`ch = 4/σ2
`w and variance σ2
`w. From this
`and the usual assumption that the all-zeros codeword was
`
`transmitted (thus, xi = +1 for i = 1, ..., n), σ2ch = 2µch.
`This is equivalent to the symmetric condition of [16] which
`states that the conditional pdf of an LLR value L must satisfy
`pL (l | x) = pL (−l | x) exl. Now, it has been observed that
`under normal operating conditions and after a few iterations,
`the LLRs Li→j and Lj→i are approximately Gaussian and,
`further, if they are assumed to be symmetric-Gaussian, as
`is the case for Lch, the decoding threshold predictions are
`very accurate (e.g., when compared to the more accurate,
`but more computationally intensive density evolution results
`[16]). Moreover, the symmetric-Gaussian assumption vastly
`simplifies EXIT chart analyses.
`We now consider the computation of EXIT transfer curves
`
`which could be less than the actual rate, R = k/n, where k
`is the number of information bits per codeword. H gives rise
`to a Tanner graph which has m check nodes, one for each
`row of H, and n variable nodes, one for each column of H.
`Considering the general case in which H has non-uniform row
`and column weight, the Tanner graph can be characterized
`by degree assignments {dv(i)}ni=1 and {dc(j)}mj=1, where
`
`
`dv(i) is the degree of the i-th variable node and dc(j) is the
`degree of the j-th check node. Such a graph, depicted in Fig.
`1, is representative of the iterative decoder, with each node
`representing a soft-in/soft-out processor (or node decoder).
`We shall assume the BI-AWGNC in our description of the
`LDPC iterative decoder. In this model, a received channel
`sample y is given by y = x + w, where x = (−1)c ∈ {±1}
`is the bipolar representation of the transmitted code bit c ∈
`{0, 1} and w is a white Gaussian noise sample distributed
`0, σ2
`w = N0/2, following convention. The
`as η
`, where σ2
`w
`channel bit log-likelihood ratios (LLRs) are computed as
`p (x = +1 | y)
`2y
`p (x = −1 | y)
`σ2
`w
`In one iteration of the conventional, flooding-schedule iter-
`ative decoder, the variable node decoders (VNDs) first process
`their input LLRs and send the computed outputs (messages) to
`each of their neighboring check node decoders (CNDs); then
`the CNDs process their input LLRs and send the computed
`outputs (messages) to each of their neighboring VNDs. More
`specifically, the message from the i-th VND to the j-th CND
`is
`
`(cid:161)
`
`(cid:162)
`
`(cid:181)
`
`(cid:182)
`
`Lch = log
`
`=
`
`.
`
`(1)
`
`(cid:88) j
`
`Li→j = Lch,i +
`
`Lj(cid:48)→i
`
`(2)
`
`(cid:33)
`
`(cid:48)(cid:54)=j
`where Lj(cid:48)→i is the incoming message from CND j(cid:48) to VND
`i and where the summation is over the dv(i) − 1 check node
`neighbors of variable node i, excluding check node j. The
`message from CND j to VND i is given by
`
`(cid:195)(cid:81)
`
`Lj→i = 2 tanh−1
`
`tanh (Li(cid:48)→j)
`
`(3)
`
`i(cid:48)(cid:54)=i
`where Li(cid:48)→j is the incoming message from VND i(cid:48) to CND
`j and where the product is over the dc(j) − 1 variable node
`neighbors of check node j, excluding variable node i . This
`decoding algorithm is called the sum-product algorithm (SPA).
`
`C1
`
`C2
`
`Cm
`
`. . .
`
`
`
`
`
`
`
`
`
`
`
`
`l l l
`
`. . .
`
`l l
`
`V1
`
`V2
`
`V3
`
`Vn−1
`
`Vn
`
`

`

`(cid:181)(cid:113)
`
`IE,V = J (σ) = J
`
`For convenience we write this as
`(dv − 1) σ2
`A + σ2
`
`(cid:182)
`
`193
`
`,
`
`(5)
`
`ch
`
`following [15]. To plot IE,V versus IA,V , where IA,V is the
`mutual information between the VND inputs Lj→i and the
`channel bits xi, we apply the symmetric-Gaussian assumption
`to these inputs so that
`
`and
`
`IA,V = J (σA)
`
`(cid:181)(cid:113)
`
`(6)
`
`(cid:182)
`
`ch
`
`(dv − 1) [J−1 (IA,V )]2 + σ2
`IE,V = J (σ) = J
`. (7)
`The inverse function J−1 (·) exists since J (σA) is monotonic
`in σA. Lastly, IE,V can be parameterized by Eb/N0 for
`ch = 4/σ2w = 8R (Eb/N0) .
`
`a given code rate R since σ2
`Approximations of the functions J (·) and J−1 (·) are given
`in [15].
`To obtain the CND EXIT curve, IE,C versus IA,C, we can
`proceed as we did in the VND case, e.g., begin with the
`symmetric-Gaussian assumption. However, this assumption is
`not sufficient because determining the mean and variance for
`a CND output Lj→i is not straightforward, as is evident from
`the computation for CNDs in (3). Closed-form expressions
`have been derived for the check node EXIT curves [21][22].
`Computer-based numerical techniques can also be used to
`obtain these curves. However, the simplest technique exploits
`the following duality relationship (proven to be exact for the
`binary erasure channel [11]): the EXIT curve for a degree-dc
`check node (i.e., rate-(dc − 1)/dc single-parity check (SPC)
`code) and that of a degree-dc variable node (i.e., rate-1/dc
`repetition code) are related as
`IE,SP C (dc, IA) = 1 − IE,REP (dc, 1 − IA) .
`This relationship was shown to be very accurate for the BI-
`AWGNC in [21][22]. Thus,
`IE,C = 1 − IE,V (σch = 0, dv ← dc, IA,V ← 1 − IA,C)
`= 1 − J
`(dc − 1) [J−1 (1 − IA,C)]2
`(8)
`
`(cid:181)(cid:113)
`
`(cid:182)
`
`.
`
`(cid:80)dv
`
`(cid:80)dc
`
`For irregular LDPC codes, IE,V and IE,C are computed as
`weighted averages. The weighting is given by the coefficients
`of the ”edge perspective” degree distribution polynomials
`d=1 λdzd−1 and ρ(z) =
`d=1 ρdzd−1, where λd is
`λ(z) =
`the fraction of edges in the Tanner graph connected to degree-d
`variable nodes, ρd is the fraction of edges connected to degree-
`d check nodes, and λ(1) = ρ(1) = 1. Then, for irregular
`LDPC codes,
`
`IE,V =
`
`λdIE,V (d, IA,V )
`
`(9)
`
`d=1
`where IE,V (d) is given by (7) with dv replaced by d, and
`
`dv(cid:88)
`dc(cid:88)
`
`LIVA et al.: DESIGN OF LDPC CODES: A SURVEY AND NEW RESULTS
`
`Fig. 2. EXIT chart example for (dv, dc) = (3, 6) regular LDPC code.
`
`for both VNDs and the CNDs, first for regular LDPC codes
`and then for irregular codes. Following [14][15], excluding the
`inputs from the channel, we consider VND and CND inputs to
`be a priori information, designated by ‘A’, and their outputs to
`be extrinsic information, designated by ‘E’. Thus, an extrinsic
`information transfer curve for the VNDs plots the extrinsic
`information IE as a function of its input a priori information,
`IA, and similarly for the CNDs.
`the
`The VND EXIT curve, IE,V versus IA,V , under
`symmetric-Gaussian assumption for VND inputs, Lch,i and
`{Lj(cid:48)→i}, and outputs, Li→j, can be obtained as follows.
`From (2) and an independent-message assumption, Li→j is
`ch + (dv − 1) σ2
`Gaussian with variance σ2 = σ2
`A (hence, mean
`σ2/2). The mutual information between the random variable
`X (corresponding to the realization xi) and the extrinsic LLR
`Li→j is therefore (for simplicity, we write L for Li→j, x for
`xi, and pL (l | ±) for pL (l | x = ±1))
`IE,V = H(X) − H(X | L)
`= 1 − E
`1/pX | L (x | l)
`log2
`(cid:182)
`= 1 −
`pL (l | x)
`−∞
`x=±1
`(cid:181)
`pL (l | +) + pL (l | −)
`· log2
`pL (l | x)
`1 + pL (l | −)
`1 + e−l(cid:162)
`(cid:161)
`= 1 −
`pL (l | +) log
`pL (l | +)
`pL (l | +) log
`
`(cid:162)(cid:164)
`
`(cid:182)
`
`dl
`
`dl
`
`dl
`
`(cid:161)
`(cid:90) ∞
`
`1 2
`
`(cid:163)
`(cid:88)
`(cid:181)
`(cid:90) ∞
`(cid:90) ∞
`
`−∞
`
`−∞
`
`= 1 −
`
`(cid:161)
`
`σ2/2, σ2
`
`(cid:162)
`
`1√
`2πσ
`
`e−(l−σ2/2)2
`
`/2σ2 log
`
`(cid:90) ∞
`
`−∞
`
`IE,V = 1 −
`
`where the last line follows from the symmetry condition and
`because pL (l | x = −1) = pL (−l | x = +1) for Gaussian
`densities.
`Since Li→j ∼ η
`+1), we have
`
`(when conditioned on xi =
`
`(cid:161)
`
`1 + e−l(cid:162)
`
`dl .
`(4)
`
`IE,C =
`
`ρdIE,C(d, IA,C)
`
`(10)
`
`d=1
`where IE,C(d) is given by (8) with dc replaced by d.
`
` I
`(E
`EV
`
`/N
`, I
`)
`b
`0
`AV
`
`decoding
`trajectory
`
`I
`(I
`)
`AC
`EC
`
`1
`
`0.9
`
`0.8
`
`0.7
`
`0.6
`
`0.5
`
`0.4
`
`0.3
`
`0.2
`
`0.1
`
` = 6
`d
` = 3, d
`v
`c
`
`E
`/N
` = 1.1 dB
`b
`0
`
`0
`
`0
`
`0.1
`
`0.2
`
`0.3
`
`0.4
`
`0.5
`I
` or I
`AV
`EC
`
`0.6
`
`0.7
`
`0.8
`
`0.9
`
`1
`
`)
`
`EC
`
`(I
`
`AC
`
`) or I
`
`AV
`
`, I
`
`0
`
`/N
`
`b
`
`(E
`
`EV
`
`I
`
`

`

`194
`
`JOURNAL OF COMMUNICATIONS SOFTWARE AND SYSTEMS, VOL. 2, NO. 3, SEPTEMBER 2006
`
`Fig. 3. EXIT chart for rate-1/2 irregular LDPC code. (Ack: S. AbuSurra)
`
`Fig. 4.
`copies.
`
`Illustration of the protograph copy and permute procedure with q = 4
`
`(cid:82) 1
`
`R = 1 −(cid:82) 1
`
`to optimize the decoding
`It has been shown [11] that
`threshold on the binary erasure channel, the shapes of the VND
`and CND transfer curves must be well matched in the sense
`that the CND curve fits inside the VND curve (an example
`will follow). This situation has also been observed on the BI-
`AWGNC [15]. Further, to achieve a good match, the number
`of different VN degrees need only be about 3 or 4 and the
`number of different CN degrees need only be 1 or 2.
`Example 1: We consider the design of a rate-1/2 irreg-
`ular LDPC code with four possible VN degrees and two
`possible CN degrees. Given than λ(1) = ρ(1) = 1 and
`0 ρ(z)dz/
`0 λ(z)dz [16],[4], only two of the
`four coefficients for λ(z) need be specified and only one of
`the two for ρ(z) need be specified. A non-exhaustive search
`yielded λ(z) = 0.267z + 0.176z2 + 0.127z3 + 0.430z9 and
`ρ(z) = 0.113z4 + 0.887z7 with a decoding threshold of
`(Eb/N0)thres = 0.414 dB. The EXIT chart for Eb/N0 = 0.55
`dB is presented in Fig. 3. The figure also gives the ”node
`perspective” degree distribution information. (cid:164)
`The references contain additional
`information on EXIT
`charts, including the so-called area property, EXIT charts for
`the Rayleigh channel, for higher-order modulation, and for
`multi-input/multi-output channels [14][15][11][23].
`
`III. DESIGN OF PROTOGRAPH-BASED CODES
`A. Definition and Problem Statement
`A protograph [24][25][26][27] is a relatively small bipartite
`graph from which a larger graph can be obtained by a copy-
`and-permute procedure: the protograph is copied Q times,
`and then the edges of the individual replicas are permuted
`among the replicas (under restrictions described below) to
`obtain a single, large graph. An example is presented in Fig.
`4. The permuted edge connections are specified by the parity-
`check matrix H. Note that the edge permutations cannot be
`arbitrary. In particular, the nodes of the protograph are labeled
`so that if variable node V is connected to check node C in
`the protograph, then variable node V in a replica can only
`connect to one of the Q replicated C check nodes. Doing so
`
`preserves the decoding threshold properties of the protograph.
`A protograph can possess parallel edges, i.e., two nodes can
`be connected by more than one edge. For LDPC codes,
`the copy-and-permute procedure must eliminate such parallel
`connections in order to obtain a derived graph appropriate for
`a parity-check matrix.
`It is convenient to choose the parity-check matrix H as an
`M × N array of Q × Q (weight-one) circulant permutation
`matrices (some of which may be the Q × Q zero matrix).
`When H is an array of circulants, the LDPC code will be
`quasi-cyclic. Such a structure has a favorable impact on both
`the encoder and the decoder. The encoder for QC codes can
`be implemented with shift-register circuits with complexity
`linearly proportional to m for serial encoding and to n for
`parallel encoding [13]. By contrast, encoders for unstructured
`LDPC codes require much more work. The decoder for QC
`LDPC codes can be implemented in a modular fashion by
`exploiting the circulant-array structure of H [28][29].
`Below we present an extension of the EXIT approach
`to codes defined by protographs. This extension is a multi-
`dimensional numerical technique and as such does not have
`a two-dimensional EXIT chart representation of the itera-
`tive decoding procedure. Still, the technique yields decoding
`thresholds for LDPC code ensembles specified by protographs.
`This multi-dimensional technique is facilitated by the rela-
`tively small size of protographs and permits the analysis of
`protograph code ensembles characterized by the presence of
`critical node types, i.e., node types which can lead to failed
`EXIT-based convergence of code ensembles. Examples of
`critical node types are degree-1 variable nodes and punctured
`variable nodes.
`A code ensemble specified by a protograph is a refinement
`(sub-ensemble) of a code ensemble specified simply by the
`protograph’s (hence, LDPC code’s) degree distributions. To
`demonstrate this, we introduce the adjacency matrix B = [bji]
`for a protograph, also called a base matrix [25], where bji is
`the number of edges between CN j and VN i. As an example,
`for the protograph at the top of Fig. 4,
`2 1 1
`1 1 1
`
`(cid:182)
`
`.
`
`(cid:181)
`
`B =
`
`1
`
`0.9
`
`0.8
`
`0.7
`
`0.6
`
`0.5
`
`0.4
`
`0.3
`
`0.2
`
`0.1
`
`0
`0
`
`I
`(I
`, E
`/N
`)
`EV
`AV
`b
`0
`
`I
`(I
`)
`AC
`EC
`
`E
`/N
` = 0.55 dB
`b
`0
`(Threshold = 0.414 dB)
`
`Node perspective degree distributions:
`VNs: 0.5z + 0.22z2 + 0.12z3 + 0.16z9
`CNs: 0.17z4 + 0.83z7
`
`
`
`0.2
`
`0.4
`
`I
` or I
`AV
`EC
`
`0.6
`
`0.8
`
`1
`
`)
`
`EC
`
`(I
`
`AC
`
`) or I
`
`0
`
`/N
`
`b
`
`, E
`
`AV
`
`(I
`
`EV
`
`I
`
`

`

`LIVA et al.: DESIGN OF LDPC CODES: A SURVEY AND NEW RESULTS
`
`195
`
`Consider also an alternative protograph and base matrix spec-
`ified by
`
`(cid:181)
`
`B(cid:48) =
`
`(cid:182)
`
`.
`
`2
`2 0
`0
`1 2
`The degree distributions of both of these protographs are
`identical and are easily seen to be
`
`3 7
`
`z +
`
`z2
`
`z2 +
`
`z3.
`
`4 7
`
`4 7
`
`3 7
`
`λ(z) =
`
`ρ(z) =
`
`code bits associated with “type i” VNs and the LLRs Lj→i
`sent from “type j” CNs to these VNs. Then, because I j→i
`E,C
`acts as a priori mutual information in the calculation of I i→j
`E,V ,
`following (7) we have (given an edge exists between CN j
`and VN i, i.e., given bji (cid:54)= 0)
`
`(cid:179)
`
`(bci − δcj)
`
`J−1(I c→i
`E,C )
`
`(cid:180)2
`
`+ σ2
`ch,i
`
` ,
`
`(cid:118)(cid:117)(cid:117)(cid:116) M(cid:88)
`
`
`I i→j
`E,V = J
`
`(11)
`where δcj = 1 when c = j and δcj = 0 when c (cid:54)= j. σ2
`ch,i is
`set to zero if code bit i is punctured. Similarly, because I i→j
`E,V
`acts as a priori mutual information in the calculation of I j→i
`E,C ,
`following (8) we have (when bji (cid:54)= 0)
`
`c=1
`
`(cid:118)(cid:117)(cid:117)(cid:116) N(cid:88)
`
`
`I j→i
`E,C = 1 − J
`
`(cid:179)
`
`(bjv − δci)
`
`J−1(1 − I v→j
`E,V )
`
`(cid:180)2
`
` .
`
`v=1
`
`(12)
`The multidimensional EXIT algorithm can now be presented
`as follows.
`1) Initialization. Select Eb/N0. Initialize a vector σch =
`(σch,0, . . . , σch,N−1) such that
`
`(cid:181)
`
`(cid:182)
`
`Eb
`N0
`where (Eb/N0)i equals zero when xi is punctured and
`equals the selected Eb/N0 otherwise.
`2) VN to CN. For i = 0, . . . , N − 1 and j = 0, . . . , M − 1,
`compute (11).
`3) CN to VN. For i = 0, . . . , N − 1 and j = 0, . . . , M − 1,
`compute (12).
`4) Cumulative mutual information. For i = 0, . . . , N − 1,
`compute
`
`σch,i = 8R
`
`i
`
`(cid:118)(cid:117)(cid:117)(cid:116) M(cid:88)
`
`
`(cid:179)
`
`CM I = J
`I i
`
`(cid:180)2
`
`J−1(I c→i
`E,C )
`
`+ σ2
`ch,i
`
` .
`
`c=1
`
`CM I = 1 (up to desired precision) for all i, then
`5) If I i
`stop; otherwise, go to step 2.
`This algorithm converges only when the selected Eb/N0
`is above the threshold. Thus,
`the threshold is the lowest
`
`value of Eb/N0 for which all I iCM I converge to 1. As
`shown in [30][31], the thresholds computed by this algorithm
`are typically within 0.05 dB of those computed by density
`evolution. Recalling that many classes of multi-edge type
`(MET) [26] LDPC codes rely on simple protographs,
`the
`above algorithm provides an accurate threshold estimation for
`MET ensembles, with a remarkable reduction in computational
`complexity relative to the density evolution analysis proposed
`in [26].
`
`IV. ACCUMULATOR-BASED CODE DESIGNS
`A. Repeat-Accumulate Codes
`This section provides an overview of the design of LDPC
`codes that can be considered to be a concatenation of a set
`of repetition codes with one or more accumulators, through
`
`
` ,
`
`1 2
`1 3
`
`However, the ensemble corresponding to B has a threshold
`of Eb/N0 = 0.78 dB and that corresponding to B(cid:48) has a
`threshold at 0.83 dB. (For reference, density evolution [16]
`applied to the above degree distributions gives 0.817 dB.)
`As another example, let
`
`B =
`
`2 1
`1 2
`
`1 1 0
`1 1 0
`0 0 1
`
`and
`
`B(cid:48) =
`
`1 0 0
`1 1 0
`2 1
`0 1 1
`1 1
`noting that they have identical degree distributions. We also
`puncture the bits corresponding to the second column in
`each base matrix. Using the multidimensional EXIT algorithm
`described below, the thresholds for B and B(cid:48) in this case were
`computed to be 0.48 dB and +∞, respectively.
`Thus, standard EXIT analysis based on degree distributions
`is inadequate for protograph-based LDPC code design. In fact,
`the presence of degree-1 variable nodes as in our second
`example implies that there is a term in the summation in (9)
`of the form
`
`(cid:80)dv
`
`λ1IE,V (1, IA,V ) = J (σch) .
`Since J (σch) is always less than one for 0 < σch < ∞
`d=1 λd = 1, the summation in (9), that is, IE,V ,
`and since
`will be strictly less than one. Again, standard EXIT analysis
`implies failed convergence for codes with the same degree
`distributions as B and B(cid:48). This is in contrast with the fact
`that codes in the B ensemble do converge when the SNR
`exceeds the threshold of 0.48 dB.
`In the following, a multidimensional EXIT technique
`[30][31] will be presented which overcomes this issue and
`allows the determination of the decoding threshold for codes
`based on protographs (possibly with punctured nodes).
`
`B. Multidimensional EXIT Analysis
`The algorithm presented in [30][31] eliminates the average
`in (9) and considers the propagation of the messages on a
`decoding tree which is specified by the protograph of the
`ensemble. Let B = [bji] be the M × N base matrix for the
`protograph under analysis. Let I i→j
`E,V be the extrinsic mutual
`information between code bits associated with “type i” VNs
`and the LLRs Li→j sent from these VNs to “type j” CNs.
`Similarly, let I j→i
`E,C be the extrinsic mutual information between
`
`

`

`196
`
`JOURNAL OF COMMUNICATIONS SOFTWARE AND SYSTEMS, VOL. 2, NO. 3, SEPTEMBER 2006
`
`Fig. 5.
`codes.
`
`Tanner graph (a) and encoder (b) for irregular repeat-accumulate
`
`and ¯a as the average of the degrees {dc,j},
`
`m(cid:88)
`
`dc,j .
`
`1 m
`
`¯a =
`
`R =
`
`.
`
`j=1
`Then the code rate for systematic IRA codes is
`1
`1 + q/¯a
`For non-systematic IRA codes, R = ¯a/q.
`The parity-check matrix for systematic RA and IRA codes
`has the form
`
`H = [Hu Hp],
`where Hp is an m × m ”dual-diagonal” square matrix,
`1
`(1)
`1
`
`an interleaver. The first example of accumulator-based codes
`were the so-called repeat-accumulate (RA) codes [32]. Despite
`their simple structure,
`they were shown to provide good
`performance and, more importantly, they paved a path toward
`the design of efficiently encodable LDPC codes. RA codes
`and other accumulator-based codes are LDPC codes that can
`be decoded as serial turbo codes or as LDPC codes.
`An RA code consists of a serial concatenation of a single
`rate-1/q repetition code through an interleaver with an accu-
`mulator having transfer function 1/(1 ⊕ D). RA codes can
`be either non-systematic or systematic. In the first case, the
`accumulator output, p, is the codeword and the code rate is
`1/q. For systematic RA codes, the information word, u, is
`combined with p to yield the codeword c = [u p] and so
`that the code rate is 1/(1 + q). RA codes perform reasonably
`well on the AWGN channel, and they tend to approach the
`channel capacity as their rate R → 0 and their block length
`n → ∞. Their main limitations are the code rate, which cannot
`be higher than 1/2, and the performance of short and medium-
`length RA codes. The following subsections will present a
`brief overview of the major enhancements to RA codes which
`permit operation closer to capacity for both high and low rates.
`
`B. Irregular Repeat-Accumulate codes
`
`The systematic irregular repeat-accumulate (IRA) codes
`generalize the systematic RA codes in that
`the repetition
`rate may differ across the k information bits and that a
`variable number of bits in the repeated word are combined
`(modulo 2) prior to sending them through the accumulator.
`Irregular repeat-accumulate [33] codes provide several ad-
`vantages over RA codes. They allowing both flexibility in
`the choice of the repetition rate for each information bit so
`that high rate codes may be designed and capacity is more
`easily approached. 57.8317in;original-height 7.0188in;cropleft
`”0”;croptop ”1”;cropright
`The Tanner graph for IRA codes is presented in Fig. 5(a)
`and the encoder structure (to be discussed further later) is
`depicted in Fig. 5(b). The variable repetition rate is accounted
`for in the graph by letting db,i vary with i. The accumulator
`is represented by the right-most part of the graph, where the
`dashed edge is added to include the possibility of a tail-biting
`trellis. Also, we see that dc,j interleaver output bits are added
`(modulo 2) to produce the j-th accumulator input. Fig. 5 also
`includes the representation for RA codes. As indicated in the
`table in the figure, for an RA code, each information bit node
`connects to exactly q check nodes (db,i = q) and each check
`node connects to exactly one information bit node (dc,j = 1).
`We remark that {db,i} and {dc,j} can be related to our earlier
`notation, {dv(i)} and {dc(j)}, as follows: dv(i) = db,i for
`i = 1, ..., k, dv(i) = 2 for i = k + 1, ..., n, and dc(j) =
`dc,j + 2 for j = 1, ..., m.
`To determine the code rate for an IRA code, define q to be
`the average repetition rate of the information bits
`
`k(cid:88)
`
`i=1
`
`db,i,
`
`1 k
`
`q =
`
`(13)
`
`(14)
`
` ,
`
`(cid:164)
`
`11
`
`(cid:163)
`
`...
`1
`
`1.
`
`..
`
`
`
`Hp =
`
`1
`where the upper-right 1 is included for tailing-biting ac-
`cumulators. For RA codes, Hu is a regular matrix having
`column weight q and row weight 1. For IRA codes, Hu has
`column weights {db,i} and row weights {dc,j}. The encoder
`of Fig. 5(b) is obtained by noting that the generator matrix
`u H−T
`corresponding to H in (13) is G =
`and writing
`I HT
`p
`Hu as ΠT AT , where Π is a permutation matrix. Note also
`performs the same computation as 1/(1 ⊕ D) (and
`that H−T
`p
`H−T
`exists only when the ”tail-biting 1” is absent). Two
`p
`encoding alternatives exist: (1) When the accumulator is not
`tail-biting, one may use H to encode since one may solve
`for the parity bits sequentially from the equation cHT = 0
`starting with the top row of H and moving on downward.
`(2) As discussed in the next section, quasi-cyclic IRA code
`
`

`

`LIVA et al.: DESIGN OF LDPC CODES: A SURVEY AND NEW RESULTS
`
`197
`
`designs are possible, in which case the techniques of [13] may
`be used.
`We remark that the choice of the degree distributions of
`the variable nodes for an IRA code are constrained by the
`presence of (at least) n − k − 1 degree-2 variable nodes.
`Although such a constraint ostensibly limits the code designer,
`for rates R ≥ 1/2, EXIT analysis leads to optimized degree
`distributions having approximately n− k−1 degree-2 variable
`nodes. Moreover, when the number of degree-2 variable nodes
`is exactly n−k−1, the edge connections involving the degree-
`2 variable nodes induced by the IRA structure are optimal in
`the sense of avoiding low weight codewords [34][35].
`IRA codes and a generalization will be discussed in the
`next two sections. Additional information may be found in
`the following references: [33][35][36][24][40][41] [42][43].
`
`Performance of a (2044,1024) S-IRA code on the BI-AWGNC.
`Fig. 6.
`HW=hardware simulator. SW=software simulator.
`
`where we have used the fact that Π−T = Π. Finally, we
`permute only the columns corresponding to the parity part of
`Hb, which gives
`
`HS-IRA = [P ΠHpΠT ].
`It is easily shown that the parity part of HS-IRA, that is,
`ΠHpΠT , is exactly in QC form,
`
`
`
`I1
`
`I0
`I0
`
`I0
`...
`
`...
`I0
`
`C. Structured IRA and IRAA Codes
`Given the code rate, length, and degree distributions, an
`IRA code is defined entirely by the matrix Hu (equivalently,
`by A and Π). While a random-like Hu would generally
`give good performance, it is problematic for both encoder
`and decoder implementations. For, in this case, a substantial
`amount of memory would be required to store the connection
`information implicit in Hu. In addition, although standard
`message-passing decoding algorithms for LDPC codes are
`inherently parallel, the physical interconnections required to
`realize a code’s bipartite graph becomes an implementation
`bottleneck and prohibits a fully parallel decoder [29]. Using a
`structured Hu matrix mitigates these problems.
`Tanner [24] was the first to consider structured RA codes,
`more specifically, quasi-cyclic RA codes, which require tailbit-
`ing in the accumulator. Simula