IEEE JOURNAL OF SELECTED TOPICS IN SIGNAL PROCESSING, VOL. 5, NO. 8, DECEMBER 2011 1563
Joint Decoding of LDPC Codes and Finite-StateChannels Via Linear-Programming
Byung-Hak Kim, Student Member, IEEE, and Henry D. Pfister, Senior Member, IEEE
Abstract—This paper considers the joint-decoding problem forfinite-state channels (FSCs) and low-density parity-check (LDPC)codes. In the first part, the linear-programming (LP) decoder forbinary linear codes is extended to perform joint-decoding of bi-nary-input FSCs. In particular, we provide a rigorous definitionof LP joint-decoding pseudo-codewords (JD-PCWs) that enablesevaluation of the pairwise error probability between codewordsand JD-PCWs in AWGN. This leads naturally to a provable upperbound on decoder failure probability. If the channel is a finite-stateintersymbol interference channel, then the joint LP decoder alsohas the maximum-likelihood (ML) certificate property and all in-teger-valued solutions are codewords. In this case, the performanceloss relative to ML decoding can be explained completely by frac-tional-valued JD-PCWs. After deriving these results, we discov-ered some elements were equivalent to earlier work by Flanaganon linear-programming receivers. In the second part, we developan efficient iterative solver for the joint LP decoder discussed inthe first part. In particular, we extend the approach of iterativeapproximate LP decoding, proposed by Vontobel and Koetter andanalyzed by Burshtein, to this problem. By taking advantage ofthe dual-domain structure of the joint-decoding LP, we obtain aconvergent iterative algorithm for joint LP decoding whose struc-ture is similar to BCJR-based turbo equalization (TE). The resultis a joint iterative decoder whose per-iteration complexity is sim-ilar to that of TE but whose performance is similar to that of jointLP decoding. The main advantage of this decoder is that it ap-pears to provide the predictability and superior performance ofjoint LP decoding with the computational complexity of TE. Oneexpected application is coding for magnetic storage where the re-quired block-error rate is extremely low and system performanceis difficult to verify by simulation.
Index Terms—BCJR algorithm, finite-state channels, joint-de-coding, low-density parity-check (LDPC) codes, linear-program-ming (LP) decoding, turbo equalization.
I. INTRODUCTION
A. Motivation and Problem Statement
I TERATIVE decoding of error-correcting codes, while in-troduced by Gallager in his 1960 Ph.D. thesis, was largely
forgotten until the 1993 discovery of turbo codes by Berrou et al.
Manuscript received January 26, 2011; revised May 15, 2011, July 20, 2011;accepted July 29, 2011. Date of publication August 22, 2011; date of currentversion November 18, 2011. This work was supported by the National ScienceFoundation under Grant 0747470. The material in this paper was presentedin part at the IEEE International Symposium on Information Theory (ISIT),Austin, TX, June 2010 and the IEEE International Conference on Communi-cations (ICC), Kyoto, Japan, June 2011. The associate editor coordinating thereview of this manuscript and approving it for publication was Prof. RiccardoRaheli.
The authors are with the Department of Electrical and Computer Engineering,Texas A&M University, College Station, TX 77843 USA (e-mail: [emailprotected]; [emailprotected]).
Color versions of one or more of the figures in this paper are available onlineat http://ieeexplore.ieee.org.
Digital Object Identifier 10.1109/JSTSP.2011.2165525
Since then, message-passing iterative decoding has been a verypopular decoding algorithm in research and practice. In 1995,the turbo decoding of a finite-state channel (FSC) and a convolu-tional code (instead of two convolutional codes) was introducedby Douillard et al. as turbo equalization (TE) and this enabledthe joint-decoding of the channel and the code by iterating be-tween these two decoders [1]. Before this, one typically sepa-rated channel decoding (i.e., estimating the channel inputs fromthe channel outputs) from the decoding of the error-correctingcode (i.e., estimating the transmitted codeword from estimatesof the channel inputs) [2], [3]. This breakthrough received im-mediate interest from the magnetic recording community, andTE was applied to magnetic recording channels by a variety ofauthors (e.g., [4]–[7]). TE was later combined with turbo codesand also extended to low-density parity-check (LDPC) codes(and called joint iterative decoding) by constructing one largegraph representing the constraints of both the channel and thecode (e.g., [8] and [9]).
In the magnetic storage industry, error correction basedon Reed–Solomon codes with hard-decision decoding hasprevailed for the last 25 years. Recently, LDPC codes haveattracted a lot of attention and some hard-disk drives (HDDs)have started using iterative decoding (e.g., [10]–[12]). Despiteprogress in the area of reduced-complexity detection anddecoding algorithms, there has been some resistance to thedeployment of TE structures (with iterative detectors/decoders)in magnetic recording systems because of error floors and thedifficulty of accurately predicting performance at very low errorrates. Furthermore, some of the spectacular gains of iterativecoding schemes have been observed only in simulations withblock-error rates above . The challenge of predicting theonset of error floors and the performance at very low error rates,such as those that constitute the operating point of HDDs (thecurrent requirement of an overall block error rate of ,remains an open problem. The presence of error floors and thelack of analytical tools to predict performance at very low errorrates are current impediments to the application of iterativecoding schemes in magnetic recording systems.
In the last five years, linear programming (LP) decoding hasbeen a popular topic in coding theory and has given new in-sight into the analysis of iterative decoding algorithms and theirmodes of failure [13]–[15]. In particular, it has been observedthat LP decoding sometimes performs better than iterative (e.g.,sum-product) decoding in the error-floor region. We believe thisstems from the fact that the LP decoder always converges toa well-defined LP optimum point and either detects decodingfailure or outputs an ML codeword. For both decoders, frac-tional vectors, known as pseudo-codewords (PCWs), play animportant role in the performance characterization of these de-coders [14], [16]. This is in contrast to classical coding theory
1932-4553/$26.00 © 2011 IEEE
1564 IEEE JOURNAL OF SELECTED TOPICS IN SIGNAL PROCESSING, VOL. 5, NO. 8, DECEMBER 2011
where the performance of most decoding algorithms (e.g., max-imum-likelihood (ML) decoding) is completely characterizedby the set of codewords.
While TE-based joint iterative decoding provides goodperformance close to capacity, it typically has some troublereaching the low error rates required by magnetic recording andoptical communication. To combat this, we extend LP decodingto perform joint-decoding of a binary-input FSC and an outerLDPC code. During the review process of our conference paperon this topic [17], we discovered that this LP formulation ismathematically equivalent to Flanagan’s general formulation oflinear-programming receivers [18], [19]. Since our main focuswas different than Flanagan’s, our main results and extensionsdiffer somewhat from his.
Our main motivation is that critical storage applications (e.g.,HDDs) require block error rates that are too low to be easilyverifiable by simulation. For these applications, an efficientiterative solver for the joint-decoding LP would have favor-able properties: error floors predictable by pseudo-codewordanalysis and convergence based on a well-defined optimizationproblem. Therefore, we introduce a novel iterative solver forthe joint LP decoding problem whose per-iteration complexity(e.g., memory and time) is similar to that of TE but whoseperformance appears to be superior at high SNR [17], [20].
B. Notation
Throughout the paper we borrow notation from [14]. Letand be sets of indices for the
variable and parity-check nodes of a binary linear code. A vari-able node is connected to the set of neighboringparity-check nodes. Abusing notation, we also let be theneighboring variable nodes of a parity-check node whenit is clear from the context. For the trellis associated with a FSC,we let index the set of trellis edges associatedwith one trellis section, be the set of possible states, and bethe set of noiseless output symbols. For each edge1, ,in the length- trellis, the functions
, andmap this edge to its respective time index, initial
state, final state, input bit, and noiseless output symbol. Finally,the set of edges in the trellis section associated with time isdefined to be .
C. Background: LP Decoding and Finite-State Channels
In [13], [14], Feldman et al. introduced a linear-program-ming (LP) decoder for binary linear codes, and applied it specif-ically to both LDPC and turbo codes. It is based on solving anLP relaxation of an integer program that is equivalent to max-imum-likelihood (ML) decoding. For long codes and/or lowSNR, the performance of LP decoding appears to be slightlyinferior to belief-propagation decoding. Unlike the iterative de-coder, however, the LP decoder either detects a failure or outputsa codeword which is guaranteed to be the ML codeword.
Let be the length- binary linear code definedby a parity-check matrix and be a codeword.
1In this paper, � is used to denote a trellis edge while � denotes the universalconstant that satisfies �� � � �.
Let be the set whose elements are the sets of indices involvedin each parity check, or
Then, we can define the set of codewords to be
The codeword polytope is the convex hull of . This polytopecan be quite complicated to describe though, so instead one con-structs a simpler polytope using local constraints. Each parity-check defines a local constraint equivalent to the extremepoints of a polytope in .
Definition 1: The local codeword polytope associ-ated with a parity check is the convex hull of the bit sequencesthat satisfy the check. It is given explicitly by
We use the notation to denote the simpler polytopecorresponding to the intersection of local check constraints; theformal definition follows.
Definition 2: The relaxed polytope is the intersectionof the LCPs over all checks and
The LP decoder and its ML certificate property is character-ized by the following theorem.
Theorem 3 ([13]): Consider consecutive uses of a sym-metric channel . If a uniform random code-word is transmitted and is received, then theLP decoder outputs given by
which is the ML solution if is integral (i.e., ).From simple LP-based arguments, one can see that LP de-
coder may also output nonintegral solutions.Definition 4: An LP decoding pseudo-codeword of a code
defined by the parity-check matrix is any nonintegral vertexof the relaxed (fundamental) polytope .
We also define the finite-state channel, which can be seenas a model for communication systems with memory whereeach output depends only on the current input and the previouschannel state instead of the entire past.
Definition 5: A finite-state channel (FSC) defines a proba-bilistic mapping from a sequence of inputs to a sequence of out-puts. Each output depends only on the current input
and the previous channel state instead of theentire history of inputs and channel states. Mathematically, wedefine
KIM AND PFISTER: JOINT DECODING OF LDPC CODES AND FINITE-STATE CHANNELS VIA LINEAR-PROGRAMMING 1565
Fig. 1. State diagrams for noiseless dicode channel without (left) and with pre-coding (right). The edges are labeled by the input/output pair.
for all , and use the shorthand notationand
where the notation denotes the subvector .An important subclass of FSCs is the set of finite-state in-
tersymbol interference channels which includes all determin-istic finite-state mappings of the inputs corrupted by memory-less noise.
Definition 6: A finite-state intersymbol interference channel(FSISIC) is a FSC whose next state is a deterministic function
of the current state and input . Mathematically, thisimplies that
ifotherwise.
Though our derivations are general, we use the followingFSISIC examples throughout the paper to illustrate concepts andperform simulations.
Definition 7: The dicode channel (DIC) is a binary-inputFSISIC with an impulse response of and addi-tive Gaussian noise [21]. If the input bits are differentially en-coded prior to transmission, then the resulting channel is calledthe precoded dicode channel (pDIC) [21]. The state diagramsof these two channels are shown in Fig. 1. For the trellis associ-ated with a DIC and pDIC, we letand . Also, the class-II Partial Response (PR2)channel is a binary-input FSISIC with an impulse response of
and additive Gaussian noise [21], [22].
D. Outline of the Paper
The remainder of this paper is organized as follows. InSection II, we introduce the joint LP decoder, define joint-de-coding pseudo-codewords (JD-PCWs), and describe theappropriate generalized Euclidean distance for this problem.Then, we discuss the decoder performance analysis using theunion bound (via pairwise error probability) over JD-PCWs.Section III is devoted to developing the iterative solver forthe joint LP decoder, i.e., iterative joint LP decoder and itsproof of convergence. Finally, Section IV presents the decodersimulation results and Section V gives some conclusions.
II. JOINT LP DECODER
Feldman et al. introduced the LP decoder for binary linearcodes in [13] and [14]. It is based on an LP relaxation of aninteger program that is equivalent to ML decoding. Later, thismethod was extended to codes over larger alphabets [23] and tothe simplified decoding of intersymbol interference (ISI) [24].In particular, this section describes an extension of the LP de-coder to the joint-decoding of binary-input FSCs and defines LPjoint-decoding pseudo-codewords (JD-PCWs) [17]. This exten-sion is natural because Feldman’s LP formulation of a trellisdecoder is general enough to allow optimal (Viterbi style) de-coding of FSCs, and the constraints associated with the outerLDPC code can be included in the same LP. This type of exten-sion has been considered as a challenging open problem in priorworks [13], [25] and was first given by Flanagan [18], [19], butwas discovered independently by us and reported in [17]. In par-ticular, Flanagan showed that any communication system whichadmits a sum-product (SP) receiver also admits a correspondinglinear-programming (LP) receiver. Since Flanagan’s approachis more general, it is also somewhat more complicated. Still, theresulting LPs are mathematically equivalent though. One ben-efit of restricting our attention to FSCs is that our descriptionof the LP is based on finding a path through a trellis, which issomewhat more natural for the joint-decoding problem.
These LP decoders provide a natural definition of PCWs forjoint-decoding, and they allow new insight into the joint-de-coding problem. Joint-decoding pseudo-codewords (JD-PCWs)are defined and the decoder error-rate is upper bounded by aunion bound sum over JD-PCWs. This leads naturally to a prov-able upper bound (e.g., a union bound) on the probability of LPdecoding failure as a sum over all codewords and JD-PCWs.Moreover, we can show that all integer solutions are indeedcodewords and that this joint LP decoder also has an ML certifi-cate property. Therefore, all decoder failures can be explainedby (fractional) JD-PCWs. It is worth noting that this property isnot guaranteed by other convex relaxations of the same problem(e.g., see Wadayama’s approach based on quadratic program-ming [25]).
Our primary motivation is the prediction of the error rate forjoint-decoding at high SNR. The basic idea is to run simula-tions at low SNR and keep track of all observed codeword andpseudo-codeword errors. An estimate of the error rate at highSNR is computed using a truncated union bound formed bysumming over all observed error patterns at low SNR. Com-puting this bound is complicated by the fact that the loss ofchannel symmetry implies that the dominant PCWs may de-pend on the transmitted sequence. Still, this technique providesa new tool to analyze the error rate of joint decoders for FSCsand low-density parity-check (LDPC) codes. Thus, novel pre-diction results are given in Section IV.
A. Joint LP Decoding Derivation
Now, we describe the joint LP decoder in terms of the trellisof the FSC and the checks in the binary linear code 2. Let bethe length of the code and be the receivedsequence. The trellis consists of vertices (i.e., onefor each state and time) and a set of at most edges (i.e.,
2It is straightforward to extend this joint LP decoder to non-binary linearcodes based on [23].
1566 IEEE JOURNAL OF SELECTED TOPICS IN SIGNAL PROCESSING, VOL. 5, NO. 8, DECEMBER 2011
one edge for each input-labeled state transition and time). TheLP formulation requires one indicator variable for each edge
, and we denote that variable by . So, is equal to1 if the candidate path goes through the edge in . Likewise,the LP decoder requires one cost variable for each edge and weassociate the branch metric with the edge given by
ifif
First, we define the trellis polytope formally as follows.Definition 8: The trellis polytope enforces the flow conser-
vation constraints for the channel decoder. The flow constraintfor state at time is given by
Using this, the trellis polytope is given by
for any
From simple flow-based arguments, it is known that the MLedge path on trellis can be found by solving a minimum-cost LPapplied to the trellis polytope .
Theorem 9 ([13, p. 94]): Finding the ML edge-path through aweighted trellis is equivalent to solving the minimum-cost flowLP
and the optimum must be integral (i.e., ) un-less there are ties.
The indicator variables are used to define the LP and thecode constraints are introduced by defining an auxiliary variable
for each code bit.Definition 10: Let the code-space projection be the map-
ping from to the input vectordefined by with
For the trellis polytope is the set of vectors whoseprojection lies inside the relaxed codeword polytope .
Definition 11: The trellis-wise relaxed polytope foris given by
The polytope has integral vertices which are in one-to-one correspondence with the set of trelliswise codewords.
Definition 12: The set of trellis-wise codewords for isdefined by
Finally, the joint LP decoder and its ML certificate propertyare characterized by the following theorem.
Theorem 13: The LP joint decoder computes
(1)
and outputs a joint ML edge-path if is integral.Proof: Let be the set of valid input/state sequence pairs.
For a given , the ML edge-path decoder finds the most likelypath, through the channel trellis, whose input sequence is acodeword. Mathematically, it computes
where ties are resolved in a systematic manner and has theextra term for the initial state probability. By re-laxing into , we obtain the desired result.
Corollary 14: For a FSISIC3, the LP joint decoder outputs ajoint ML codeword if is integral.
Proof: The joint ML decoder for codewords computes
where follows from Definition 6 and holds because eachinput sequence defines a unique edge-path. Therefore, the LPjoint-decoder outputs an ML codeword if is integral.
Remark 15: If the channel is not a FSISIC (e.g., if it is afinite-state fading channel), then integer valued solutions of theLP joint-decoder are ML edge-paths but not necessarily MLcodewords. This occurs because the joint LP decoder does notsum the probability of the multiple edge-paths associated withthe same codeword (e.g., when multiple distinct edge-pathsare associated with the same input labels). Instead, it simplygives the probability of the most-likely edge path associatedthat codeword.
B. Joint LP Decoding Pseudo-Codewords
Pseudo-codewords have been observed and given names by anumber of authors (e.g., [28]–[30]), but the simplest general def-inition was provided by Feldman et al. in the context of LP de-
3In fact, this holds more generally for the restricted class of FSCs used in [26],which are now called unifilar FSCs because they generalize the unifilar Markovsources defined in [27].
KIM AND PFISTER: JOINT DECODING OF LDPC CODES AND FINITE-STATE CHANNELS VIA LINEAR-PROGRAMMING 1567
Fig. 2. Illustration of joint LP decoder outputs for the single parity-check codeSPC(3,2) over DIC (starts in zero state). By ordering the trellis edges appropri-ately, joint LP decoder converges to either a TCW (0 1 0 0;0 0 0 1;.0 0 1 0) (topdashed blue path) or a JD-TPCW (0 1 0 0;0 0.5.5;.5 0.5 0) (bottom dashed redpaths). Using� to project them into ����, we obtain the corresponding SCW(1,1,0) and JD-SPCW (1,.5,0).
coding of parity-check codes [14]. One nice property of the LPdecoder is that it always returns either an integral codeword or afractional pseudo-codeword. Vontobel and Koetter have shownthat a very similar set of pseudo-codewords also affect mes-sage-passing decoders, and that they are essentially fractionalcodewords that cannot be distinguished from codewords usingonly local constraints [16]. The joint-decoding pseudo-code-word (JD-PCW), defined below, can be used to characterizecode performance at low error rates.
Definition 16: If for all , then the output of theLP joint decoder is a trellis-wise codeword (TCW). Otherwise,
for some and the solution is called a joint-de-coding trellis-wise pseudo-codeword (JD-TPCW); in this case,the decoder outputs “failure” (see Fig. 2 for an example of thisdefinition).
Definition 17: For any TCW , the projectionis called a symbol-wise codeword (SCW). Likewise, for anyJD-TPCW , the projection is called a joint-de-coding symbolwise pseudo-codeword (JD-SPCW) (see Fig. 2for a graphical depiction of this definition).
Remark 18: For FSISICs, the LP joint decoder has the MLcertificate property; if the decoder outputs a SCW, then it isguaranteed to be the ML codeword (see Corollary 14).
Definition 19: If is a JD-TPCW, thenwith
is called a joint-decoding symbol-wise signal-space pseudo-codeword (JD-SSPCW). Likewise, if is a TCW, then iscalled a symbol-wise signal-space codeword (SSCW).
C. Union Bound for Joint LP Decoding
Now that we have defined the relevant pseudo-codewords, weconsider how much a particular pseudo-codeword affects per-formance; the idea is to quantify pairwise error probabilities. Infact, we will use the insights gained in the previous section toobtain a union bound on the decoder’s word-error probability
and to analyze the performance of the proposed joint LP de-coder. Toward this end, let us consider the pairwise error eventbetween a SSCW and a JD-SSPCW first.
Theorem 20: A necessary and sufficient condition for thepairwise decoding error between a SSCW and a JD-SSPCW
is
(2)
where and are the LP variables for and, respectively.
Proof: By definition, the joint LP decoder (1) prefersover if and only if (2) holds.
For the moment, let be the SSCW of FSISIC to anAWGN channel whose output sequence is , where
is an independent and identically distributed(i.i.d.) Gaussian sequence with mean 0 and variance . Then,the joint LP decoder can be simplified as stated in the followingtheorem.
Theorem 21: Let be the output of a FSISIC with zero-meanAWGN whose variance is per output. Then, the joint LPdecoder is equivalent to
Proof: For each edge , the output is Gaussianwith mean and variance , so we have
. Therefore,the joint LP decoder computes
We will show that each pairwise probability has a simpleclosed-form expression that depends only on a generalizedsquared Euclidean distance and the noise variance
. One might notice that this result is very similar to thepairwise error probability derived in [31]. The main differenceis the trellis-based approach that allows one to obtain this resultfor FSCs. Therefore, the next definition and theorem can beseen as a generalization of [31].
Definition 22: Let be a SSCW and a JD-SSPCW. Thenthe generalized squared Euclidean distance between andcan be defined in terms of their trellis-wise descriptions by
where
Theorem 23: The pairwise error probability between a SSCWand a JD-SSPCW is
where .
1568 IEEE JOURNAL OF SELECTED TOPICS IN SIGNAL PROCESSING, VOL. 5, NO. 8, DECEMBER 2011
Proof: The pairwise error probability that theLP joint-decoder will choose the pseudo-codeword over canbe written as
where follows from the fact that has aGaussian distribution with mean and variance
, and follows from Definition 22.The performance degradation of LP decoding relative to ML
decodingcanbeexplainedbypseudo-codewordsand theircontri-bution to the error rate, which depends on . Indeed, bydefining as the number of codewords and JD-PCWs atdistance from and as the set of generalized Euclideandistances,wecanwrite theunionboundonword error rate (WER)as
(3)
Of course, we need the set of JD-TPCWs to computewith the Theorem 23. There are two complications with thisapproach. One is that, like the original problem [13], no gen-eral method is known yet for computing the generalized Eu-clidean distance spectrum efficiently. Another is, unlike originalproblem, the constraint polytope may not be symmetric undercodeword exchange. Therefore the decoder performance maynot be symmetric under codeword exchange. Hence, the decoderperformance may depend on the transmitted codeword. In thiscase, the pseudo-codewords will also depend on the transmittedsequence.
III. ITERATIVE SOLVER FOR THE JOINT LP DECODER
In the past, the primary value of linear programming (LP)decoding was as an analytical tool that allowed one to betterunderstand iterative decoding and its modes of failure. Thisis because LP decoding based on standard LP solvers is quiteimpractical and has a superlinear complexity in the block length.This motivated several authors to propose low-complexity algo-rithms for LP decoding of LDPC codes in the last five years (e.g.,[25], [32]–[37]). Many of these have their roots in the iterativeGauss–Seidel approach proposed by Vontobel and Koetter forapproximate LP decoding [32]. This approach was also analyzedfurther by Burshtein [36]. Smoothed Lagrangian relaxationmethods have also been proposed to solve intractable optimalinference and estimation for more general graphs (e.g., [38]).
In this section, we consider the natural extension of [32], [36]to the joint-decoding LP formulation developed in Section II.
TABLE IPRIMAL PROBLEM (PROBLEM-P)
We argue that, by taking advantage of the special dual-domainstructure of the joint LP problem and replacing minima inthe formulation with soft-minima, we can obtain an efficientmethod that solves the joint LP. While there are many waysto iteratively solve the joint LP, our main goal was to deriveone as the natural analogue of turbo equalization (TE). Thisshould lead to an efficient method for joint LP decoding whoseperformance is similar to that of joint LP and whose per-itera-tion complexity similar to that of TE. Indeed, the solution weprovide is a fast, iterative, and provably convergent form ofTE whose update rules are tightly connected to BCJR-basedTE. This demonstrates that an iterative joint LP solver with asimilar computational complexity as TE is feasible (see Re-mark 27). In practice, the complexity reduction of this iterativedecoder comes at the expense of some performance loss, whencompared to the joint LP decoder, due to convergence issues(discussed in Section III-B).
Previously, a number of authors have attempted to reverseengineer an objective function targeted by turbo decoding (andTE by association) in order to discuss its convergence andoptimality [39]–[41]. For example, [39] uses a duality link be-tween two optimality formulations of TE: one based on Bethefree energy optimization and the other based on constrainedML estimation. This results of this section establish a newconnection between iterative decoding and optimization forthe joint-decoding problem that can also be extended to turbodecoding.
A. Iterative Joint LP Decoding Derivation
In Section II, a joint LP decoder is presented as anLDPC-code constrained shortest-path problem on the channeltrellis. In this section, we develop the iterative solver for thejoint-decoding LP. There are few key steps in deriving itera-tive solution for the joint LP decoding problem. For the firststep, given by the primal problem (Problem-P) in Table I,we reformulate the original LP (1) in Theorem 13 using onlyequality constraints involving the indicator variables4 and
4The valid patterns � �� � � ��� � ��� is even� for each parity-check� � allow us to define the indicator variables � (for � � and � � � )which equal 1 if the codeword satisfies parity-check � using configuration� � � .
KIM AND PFISTER: JOINT DECODING OF LDPC CODES AND FINITE-STATE CHANNELS VIA LINEAR-PROGRAMMING 1569
Fig. 3. Illustration of primal variables � and� defined for Problem-P and dualvariables� and� defined for Problem-D1 on the same example given by Fig. 2:SPC(3,2) with DIC for � � �.
TABLE IIDUAL PROBLEM FIRST FORMULATION (PROBLEM-D1)
. The second step, given by the first formulation of the dualproblem (Problem-D1) in Table II, follows from standardconvex analysis (e.g., see ([42, p. 224]). Strong duality holdsbecause the primal problem is feasible and bounded. Therefore,the Lagrangian dual of Problem-P is equivalent to Problem-D1and the minimum of Problem-P is equal to the maximum ofProblem-D1. From now on, we consider Problem-D1, wherethe code and trellis constraints separate into two terms in theobjective function. See Fig. 3 for a diagram of the variablesinvolved.
The third step, given by the second formulation of the dualproblem (Problem-D2) in Table III, observes that forward/backward recursions can be used to perform the optimizationover and remove one of the dual variable vectors. Thissplitting is enabled by imposing the trellis flow normalizationconstraint in Problem-P only at one time instant . Thisdetail gives different ways to write the same LP and is animportant part of obtaining update equations similar to thoseof TE.
TABLE IIIDUAL PROBLEM SECOND FORMULATION (PROBLEM-D2)
Fig. 4. Illustration of Viterbi updates in Problem-D2 on the same examplegiven by Fig. 2: DIC for � � � with forward ��� and backward��� .
Lemma 24: Problem-D1 is equivalent to Problem-D2.Proof: By rewriting the inequality constraint in
Problem-D1 as
we obtain the recursive upper bound for as
...
This upper bound is achieved by theforward Viterbi update in Problem-D2 for .Again, by expressing the same constraint as
we get a recursive upper bound for . Similar reasoningshows this upper bound is achieved by the back-ward Viterbi update in Problem-D2 for .See Fig. 4 for a graphical depiction of this.
1570 IEEE JOURNAL OF SELECTED TOPICS IN SIGNAL PROCESSING, VOL. 5, NO. 8, DECEMBER 2011
Fig. 5. Illustration of Algorithm 1 steps for � � � on the same example given by Fig. 2: outer loop update (left) and inner loop update (right).
TABLE IVSOFTENED DUAL PROBLEM (PROBLEM-DS)
The fourth step, given by the softened dual problem(Problem-DS) in Table IV, is formulated by replacing theminimum operator in Problem-D2 with the soft-minimumoperation
This smooth approximation converges to the minimum func-tion as increases [32]. Since the soft-minimum functionis used in two different ways, we use different constants,and , for the code and trellis terms. The smoothness ofProblem-DS allows one to to take derivative of (4) (giving theKarush–Kuhn–Tucker (KKT) equations, derived in Lemma 25),and represent (5) and (6) using BCJR-like forward/backwardrecursions (given by Lemma 26).
Lemma 25: Consider the KKT equations associated withperforming the minimization in (4) only over the variables
. These equations have a unique solution givenby
for where
Proof: See Appendix A.Lemma 26: Equations (5) and (6) are equivalent to the BCJR-
based forward and backward recursion given by (7)–(9).
Proof: By letting,
and , we obtain the de-sired result by normalization.
Now, we have all the pieces to complete the algorithm. Asthe last step, we combine the results of Lemma 25 and 26 toobtain the iterative solver for the joint-decoding LP, which issummarized by the iterative joint LP decoding in Algorithm 1(see Fig. 5 for a graphical depiction).
Remark 27: While Algorithm 1 always has a bit-node up-date rule different from standard belief propagation (BP), wenote that setting in the inner loop gives the exact BPcheck-node update and setting in the outer loop givesthe exact BCJR channel update. In fact, one surprising result ofthis work is that such a small change to the BCJR-based TE up-date provides an iterative solver for the LP whose per-iterationcomplexity similar to TE. It is also possible to prove the con-vergence of a slightly modified iterative solver that is based ona less efficient update schedule.
KIM AND PFISTER: JOINT DECODING OF LDPC CODES AND FINITE-STATE CHANNELS VIA LINEAR-PROGRAMMING 1571
Algorithm 1 Iterative Joint Linear-Programming Decoding
• Step 1. Set and initialize for.
• Step 2. Update Outer Loop: For ,— (i) Compute bit-to-trellis message
where
— (ii) Compute forward/backward trellis messages
(7)
(8)
where for all .— (iii) Compute trellis-to-bit message
(9)
• Step 3. Update Inner Loop for rounds: For ,— (i) Compute bit-to-check msg for
— (ii) Compute check-to-bit msg for
(10)
where
(11)
• Step 4. Compute hard decisions and stopping rule— (i) For ,
ifotherwise
— (ii) If satisfies all parity checks or the maximumouter iteration number, , is reached, stop andoutput . Otherwise increment and go to Step 2.
B. Convergence Analysis
This section considers the convergence properties of Algo-rithm 1. Although simulations have not shown any convergenceproblems with Algorithm 1 in its current form, our proof re-quires a modified update schedule that is less computationallyefficient. Following Vontobel’s approach in [32], which isbased on general properties of Gauss–Seidel-type algorithmsfor convex minimization, we show that the modified versionAlgorithm 1 is guaranteed to converge. Moreover, a feasible
TABLE VSOFTENED PRIMAL PROBLEM (PROBLEM-PS)
solution to Problem-P can be obtained whose value is arbitrarilyclose to the optimal value of Problem-P.
The modified update rule for Algorithm 1 consists of cycli-cally, for each , computing the quantity (viastep 2 of Algorithm 1) and then updating for all(based on step 3 of Algorithm 1). The drawback of this approachis that one BCJR update is required for each bit update, ratherthan for bit updates. This modification allows us to interpretAlgorithm 1 as a Gauss–Seidel-type algorithm. We believe that,at the expense of a longer argument, the convergence proof canbe extended to a decoder which uses windowed BCJR updates(e.g., see [43]) to achieve convergence guarantees with muchlower complexity. Regardless, the next few lemmas and theo-rems can be seen as a natural generalization of [32], [36] to thejoint-decoding problem.
Lemma 28: Assume that all the rows of have Hammingweight at least 3. Then, the modified Algorithm 1 converges tothe maximum of the Problem-DS.
Proof: See Appendix B.Next, we introduce the softened primal problem (Problem-PS)
in Table V, using the definitions and. Using standard convex analysis (e.g., see
([42, p. 254, Ex. 5.5]), one can show that Problem-PS is theLagrangian dual of Problem-DS and that the minimum ofProblem-PS is equal to the maximum of Problem-DS. Inparticular, Problem-PS can be seen as a maximum-entropy reg-ularization of Problem-DS that was derived by smoothing dualproblem given by Problem-D2. Thus, Algorithm 1 is dually-re-lated to an interior-point method for solving the LP relaxationof joint ML decoding on trellis-wise polytope using the entropyfunction (for in the standard simplex)
(12)
as a barrier function (e.g., see ([38, p. 126]) for the polytope.Remark 29: By taking sufficiently large and , the
primal LP of joint LP decoder in Problem-P, emerges as the“zero temperature” limit of the approximate LP relaxationsgiven by Problem-PS [32], [38]. Also, Problem-PS can be seenas a convex free-energy minimization problem [38].
Next, we develop a relaxation bound, given by Lemma 30and Lemma 31 to quantify the performance loss of Algorithm 1(when it converges) in relation to the joint LP decoder.
Lemma 30: Let be the minimum value of Problem-P andbe the minimum value of Problem-PS. Then, one finds that
where
1572 IEEE JOURNAL OF SELECTED TOPICS IN SIGNAL PROCESSING, VOL. 5, NO. 8, DECEMBER 2011
and
Proof: See Appendix C.Lemma 31: For any , sufficiently many iterations
of the modified Algorithm 1 produces a feasible solution forProblem-DS that satisfies the KKT conditions within . If
, then one can construct a solution forProblem-PS that is feasible and whose value satisfies
where
Proof: Proof follows from careful modification of the ar-guments in ([36, pp. 4840–4841]) and the details can be foundin [44].
Lastly, we obtain the desired conclusion, which is stated asTheorem 32.
Theorem 32: For any , sufficiently many iterationsof the modified Algorithm 1 produces a feasible solution forProblem-DS that satisfies the KKT conditions within . If ,then one can construct a solution for Problem-P that isfeasible and whose value satisfies
where
Proof: Combining results of Lemma 28, Lemma 30, andLemma 31, we obtain the desired error bound.
Remark 33: The modified (i.e., cyclic schedule) Algorithm 1is guaranteed to converge to a solution whose value can be madearbitrarily close to . Therefore, the joint iterative LP decoderprovides an approximate solution to Problem-P whose valueis governed by the upper bound in Theorem 32. Algorithm 1can be further modified to be of Gauss–Southwell type so thatthe complexity analysis in [36] can be extended to this case.Still, the analysis in [36], although a valid upper bound, doesnot capture the true complexity of decoding because one mustchoose to guarantee that the iterative LP solverfinds the true minimum. Therefore, the exact convergencerate and complexity analysis of Algorithm 1 is left for futurestudy. In general, the convergence rate of coordinate-descentmethods (e.g., Gauss–Seidel and Gauss–Southwell type algo-rithms) for convex problems without strict convexity is an openproblem [45].
IV. ERROR RATE PREDICTION AND VALIDATION
In this section, we validate the proposed joint-decodingsolution and discuss some implementation issues. Then, wepresent simulation results and compare with other approaches.
In particular, we compare the performance of the joint LPdecoder and joint iterative LP decoder with the joint iterativemessage-passing decoder on two finite-state intersymbol in-terference channels (FSISCs) described in Definition 7. Forpreliminary studies, we use a (3, 5)-regular binary LDPCcode on the precoded dicode channel (pDIC) with length 155and 455. For a more practical scenario, we also consider a(3, 27)-regular binary LDPC code with length 4923 and rate8/9 on the class-II Partial Response (PR2) channel used as apartial-response target for perpendicular magnetic recording.All parity-check matrices were chosen randomly except thatdouble-edges and four-cycles were avoided. Since the perfor-mance depends on the transmitted codeword, the WER resultswere obtained for a few chosen codewords of fixed weight. Theweight was chosen to be roughly half the block length, givingweights 74, 226, and 2462 respectively.
The performance of the three algorithms was assessed basedon the following implementation details.
Joint LP Decoder: Joint LP decoding is performed inthe dual domain because this is much faster than the primaldomain when using MATLAB. Due to the slow speed of LPsolver, simulations were completed up to a WER of roughly
on the three different nonzero LDPC codes with blocklengths 155 and 455 each. To extrapolate the error rates tohigh SNR (well beyond the limits of our simulation), weuse a simulation-based semi-analytic method based on thetruncated union bound (3), as discussed in Section II. Theidea is to run a simulation at low SNR and keep track ofall observed codeword and pseudo-codeword (PCW) errorsand a truncated union bound is computed by summing overall observed errors. The truncated union bound is obtainedby computing the generalized Euclidean distances associatedwith all decoding errors that occurred at some low SNR points(e.g., WER of roughly than ) until we observe a stationarygeneralized Euclidean distance spectrum. It is quite easy, infact, to store these error events in a list which is finallypruned to avoid overcounting. Of course, low SNR allows thedecoder to discover PCWs more rapidly than high SNR andit is well-known that the truncated bound should give a goodestimate at high SNR if all dominant joint decoding PCWshave been found (e.g., [46], [47]). One nontrivial open questionis the feasibility and effectiveness of enumerating error eventsfor long codes. In particular, we do not address how manyinstances must be simulated to have high confidence that allthe important error events are found so there are no surprisesat high SNR.
Joint Iterative LP Decoder: Joint iterative decoding isperformed based on the Algorithm 1 on all three LDPC codesof different lengths. For block lengths 155 and 455, we chosethe codeword which shows the worst performance for thejoint LP decoder experiments. We used a simple schedulingupdate scheme: variables are updated according to Algorithm1 with cyclically with inner loop iterations for eachouter iteration. The maximum number of outer iterations is
, so the total iteration count, , is at most200. The choice of parameters are andon the LDPC codes with block lengths 155 and 455. For theLDPC code with length 4923, is reduced to 10. To prevent
KIM AND PFISTER: JOINT DECODING OF LDPC CODES AND FINITE-STATE CHANNELS VIA LINEAR-PROGRAMMING 1573
Fig. 6. Comparisons between the joint LP decoding, joint iterative LP decoding, and joint iterative message-passing (MP) decoding on the pDIC with AWGN forrandom (3,5) regular LDPC codes of length � � ��� (left) and � � ��� (right). The joint LP decoding experiments were repeated for three different nonzerocodewords and depicted in three different curves. The dashed curves are computed using the union bound in (3) based on JD-PCWs observed at 3.46 dB (left)2.6 dB (right). Note that SNR is defined as channel output power divided by � .
possible underflow or overflow, a few expressions must beimplemented carefully. When
a well-behaved approximation of (10) and (11) is given by
where is the usual sign function. Also, (9) should beimplemented using
where and .Joint Iterative Message-Passing Decoder: Joint iterative
message decoding is performed based on the state-based algo-rithm described in [43] on all three LDPC codes of different
lengths. To make a fair comparison with the Joint Iterative LPDecoder, the same maximum iteration count and the same code-words are used.
A. Results
Fig. 6 compares the results of all three decoders and the error-rate estimate given by the union bound method discussed inSection II. The solid lines represent the simulation curves whilethe dashed lines represent a truncated union bound for three dif-ferent nonzero codewords. Surprisingly, we find that joint LPdecoder outperforms joint iterative message passing decoder byabout 0.5 dB at WER of . We also observe that joint it-erative LP decoder loses about 0.1 dB at low SNR. This maybe caused by using finite values for and . At high SNR,however, this gap disappears and the curve converges towardsthe error rate predicted for joint LP decoding. This shows thatjoint LP decoding outperforms belief-propagation decoding forshort length code at moderate SNR with the predictability of LPdecoding. Of course, this can be achieved with a computationalcomplexity similar to turbo equalization.
One complication that must be discussed is the dependenceon the transmitted codeword. Computing the bound is compli-cated by the fact that the loss of channel symmetry implies thatthe dominant PCWs may depend on the transmitted sequence.It is known that long LDPC codes with joint iterative decodingexperience a concentration phenomenon [43] whereby the errorprobability of a randomly chosen codeword is very close, withhigh probability, to the average error probability over all code-words. This effect starts to appear even at the short block lengthsused in this example. More research is required to understandthis effect at moderate block lengths and to verify the same ef-fect for joint LP decoding.
Fig. 7 compares the joint iterative LP decoder and joint itera-tive message-passing decoder in a practical scenario. Again, wefind that the joint iterative LP decoder provides gains over thejoint iterative message-passing decoder at high SNR. The slopedifference between the curves also suggests that the
1574 IEEE JOURNAL OF SELECTED TOPICS IN SIGNAL PROCESSING, VOL. 5, NO. 8, DECEMBER 2011
Fig. 7. Comparisons between the joint iterative LP decoding, joint iterative MPdecoding and soft-output Viterbi algorithm (SOVA)-based TE decoding (takenfrom [22]) on the PR2 channel with AWGN for random (3,27) regular LDPCcodes of length � � ����. Note that SNR is defined as channel output powerdivided by � .
performance gains of joint iterative LP decoder will increasewith SNR. This shows that joint iterative LP decoding can pro-vide performance gains at high SNR with a computational com-plexity similar to that of turbo equalization.
V. CONCLUSION
In this paper, we consider the problem of linear-programming(LP) decoding of low-density parity-check (LDPC) codes andfinite-state channels (FSCs). First, we present an LP formulationof joint-decoding for LDPC codes on FSCs that offers decodingperformance improvements over joint iterative message-passingdecoding at moderate SNR. Then, joint-decoding pseudo-code-words (JD-PCWs) are defined and the decoder error rate is upperbounded by a union bound over JD-PCWs that is evaluated fordeterministic ISI channels with AWGN. Next, we propose asimulation-based semi-analytic method for estimating the errorrate of LDPC codes on finite-state intersymbol interferencechannel (FSISIC) at high SNR using only simulations at lowSNR. Finally, we present a novel iterative solver for the jointLP decoding problem. This greatly reduces the computationalcomplexity of the joint LP solver by exploiting the LP dualproblem structure. Its main advantage is that it combines thepredictability of LP decoding with a computational complexitysimilar to turbo equalization (TE) and provides performancegains over TE in the error-floor region.
APPENDIX
A. Proof of Lemma 25
Restricting the minimization in (4) to the variablesgives
(13)
The solution to (13) can be obtained by solving the KKT equa-tions. For , we take the first derivative with respect to
and set it to zero; this yields
(14)
By defining as
(15)
where we can rewrite (14) to obtain the de-sired result.
B. Proof of Lemma 28
To characterize the convergence of the iterative joint LP de-coder, we consider the modification of Algorithm 1 with cyclicupdates. The analysis follows [32] and uses the propositionabout convergence of block coordinate descent methods from([48, p. 247]).
Proposition 34: Consider the problem
where and each is aclosed convex subset of . The vector is partitionedso with . Suppose that iscontinuously differentiable and convex on and that, for every
and every , the problem
has a unique minimum. Now, consider the sequencedefined by
for . Then, every limit point of this sequence min-imizes over .
KIM AND PFISTER: JOINT DECODING OF LDPC CODES AND FINITE-STATE CHANNELS VIA LINEAR-PROGRAMMING 1575
By using Proposition 34, we will show that the modified Al-gorithm 1 converges. Define and
Let us consider cyclic coordinate decent algorithm which mini-mizes cyclically with respect to the coordinate variable. Thus,
is changed first, then and so forth through . Then(4)–(6) are equivalent to for each with proper as
Using the properties of log-sum-exp functions (e.g., see [42, p.72]), one can verify that is continuously differentiable andconvex. The minimum over for all is uniquely ob-tained because of the unique KKT solution in Lemma 25. There-fore, we can apply the Proposition 34 to achieve the desired con-vergence result under the modified update schedule. It is worthmentioning that the Hamming weight condition prevents degen-eracy of Problem-DS based on the fact that, otherwise, somepairs of bits must always be equal.
C. Proof of Lemma 30
Denote the optimum solution of Problem-P by and andthe optimum solution of Problem-PS by and . Since and
are the optimal with respect to the Problem-P, we have
(16)
On the other hand, and are the optimal with respect to theProblem-PS, we have
where is the entropy defined by (12). Rewrite this gives
(17)
The last inequality is due to nonnegativity of entropy. UsingJensen’s inequality, we obtain
(18)
and
(19)
By substituting (18) and (19) to (17), we have
(20)
Combining (16) and (20) gives the result.
REFERENCES
[1] C. Douillard, M. Jézéquel, C. Berrou, A. Picart, P. Didier, and A.Glavieux, “Iterative correction of intersymbol interference: Turboequalization,” Eur. Trans. Telecomm., vol. 6, no. 5, pp. 507–511,Sep.–Oct. 1995.
[2] R. G. Gallager, “Low-density parity-check codes,” Ph.D. dissertation,Mass. Inst. of Technol., Cambridge, MA, 1960.
[3] R. R. Müller and W. H. Gerstacker, “On the capacity loss due to sep-aration of detection and decoding,” IEEE Trans. Inf. Theory, vol. 50,no. 8, pp. 1769–1778, Aug. 2004.
[4] W. E. Ryan, “Performance of high rate turbo codes on a PR4-equal-ized magnetic recording channel,” in Proc. IEEE Int. Conf. Commun.,Atlanta, GA, Jun. 1998, pp. 947–951.
[5] L. L. McPheters, S. W. McLaughlin, and E. C. Hirsch, “Turbo codes forPR4 and EPR4 magnetic recording,” in Proc. Asilomar Conf. Signals,Syst. Comput., Pacific Grove, CA, Nov. 1998.
[6] M. Öberg and P. H. Siegel, “Performance analysis of turbo-equalizeddicode partial-response channel,” in Proc. 36th Annual Allerton Conf.Commun., Control, Comput.., Monticello, IL, Sep. 1998, pp. 230–239.
[7] M. Tüchler, R. Koetter, and A. Singer, “Turbo equalization: Principlesand new results,” IEEE Trans. Commun., vol. 50, no. 5, pp. 754–767,May 2002.
[8] B. M. Kurkoski, P. H. Siegel, and J. K. Wolf, “Joint message-passingdecoding of LDPC codes and partial-response channels,” IEEE Trans.Inf. Theory, vol. 48, no. 6, pp. 1410–1422, June 2002.
[9] G. Ferrari, G. Colavolpe, and R. Raheli, Detection Algorithms for Wire-less Communications, with Applications to Wired and Storage Sys-tems. New York: Wiley, 2004.
[10] A. Dholakia, E. Eleftheriou, T. Mittelholzer, and M. Fossorier,“Capacity-approaching codes: Can they be applied to the magneticrecording channel?,” IEEE Commun. Mag., vol. 42, no. 2, pp. 122–130,Feb. 2004.
[11] A. Anastasopoulos, K. Chugg, G. Colavolpe, G. Ferrari, and R. Raheli,“Iterative detection for channels with memory,” Proc. IEEE, vol. 95,no. 6, pp. 1272–1294, Jun. 2007.
[12] A. Kavcic and A. Patapoutian, “The read channel,” Proc. IEEE, vol.96, no. 11, pp. 1761–1774, Nov. 2008.
1576 IEEE JOURNAL OF SELECTED TOPICS IN SIGNAL PROCESSING, VOL. 5, NO. 8, DECEMBER 2011
[13] J. Feldman, “Decoding error-correcting codes via linear program-ming,” Ph.D. dissertation, Mass. Inst. of Technol., Cambridge, MA,2003.
[14] J. Feldman, M. J. Wainwright, and D. R. Karger, “Using linear pro-gramming to decode binary linear codes,” IEEE Trans. Inf. Theory, vol.51, no. 3, pp. 954–972, Mar. 2005.
[15] [Online]. Available: http://www.PseudoCodewords.info[16] P. Vontobel and R. Koetter, “Graph-cover decoding and finite-length
analysis of message-passing iterative decoding of LDPC codes,” Dec.2005 [Online]. Available: http://arxiv.org/abs/cs/0512078
[17] B.-H. Kim and H. D. Pfister, “On the joint decoding of LDPC codesand finite-state channels via linear programming,” in Proc. IEEE Int.Symp. Inf. Theory, Austin, TX, June 2010, pp. 754–758.
[18] M. F. Flanagan, “Linear-programming receivers,” in Proc. 47th AnnualAllerton Conf. Commun., Control, Comput., Monticello, IL, Sep. 2008,pp. 279–285.
[19] M. F. Flanagan, “A unified framework for linear-program-ming based communication receivers,” [Online]. Available:http://arxiv.org/abs/0902.0892, accepted for publication
[20] B.-H. Kim and H. D. Pfister, “An iterative joint linear-programmingdecoding of LDPC codes and finite-state channels,” in Proc. IEEE Int.Conf. Commun., Jun. 2011, pp. 1–6.
[21] K. A. S. Immink, P. H. Siegel, and J. K. Wolf, “Codes for digitalrecorders,” IEEE Trans. Inf. Theory, vol. 44, no. 6, pp. 2260–2299, Oct.1998.
[22] S. Jeon, X. Hu, L. Sun, and B. Kumar, “Performance evaluationof partial response targets for perpendicular recording using fieldprogrammable gate arrays,” IEEE Trans. Magn., vol. 43, no. 6, pp.2259–2261, Jun. 2007.
[23] M. F. Flanagan, V. Skachek, E. Byrne, and M. Greferath, “Linear-programming decoding of nonbinary linear codes,” IEEE Trans. Inf.Theory, vol. 55, no. 9, pp. 4134–4154, Sep. 2009.
[24] M. H. Taghavi and P. H. Siegel, “Graph-based decoding in the presenceof ISI,” IEEE Trans. Inf. Theory, vol. 57, no. 4, pp. 2188–2202, Apr.2011.
[25] T. Wadayama, “Interior point decoding for linear vector channels basedon convex optimization,” IEEE Trans. Inf. Theory, vol. 56, no. 10, pp.4905–4921, Oct. 2010.
[26] J. Ziv, “Universal decoding for finite-state channels,” IEEE Trans. Inf.Theory, vol. 31, no. 4, pp. 453–460, Jul. 1985.
[27] R. Ash, Information Theory. New York: Dover, 1990.[28] N. Wiberg, “Codes and decoding on general graphs,” Ph.D. disserta-
tion, Linköping Univ., Linköping, Sweden, 1996, S-581 83.[29] C. Di, D. Proietti, E. Telatar, T. J. Richardson, and R. Urbanke, “Finite-
length analysis of low-density parity-check codes on the binary erasurechannel,” IEEE Trans. Inf. Theory, vol. 48, no. 6, pp. 1570–1579, Jun.2002.
[30] T. Richardson, “Error floors of LDPC codes,” in Proc. 42nd Annu.Allerton Conf. Commun., Control, and Comput., Oct. 2003.
[31] G. D. Forney, Jr., R. Koetter, F. R. Kschischang, and A. Reznik, “On theeffective weights of pseudocodewords for codes defined on graphs withcycles,” in Codes, Systems and Graphical Models, ser. IMA VolumesSeries, B. Marcus and J. Rosenthal, Eds. New York: Springer, 2001,vol. 123, pp. 101–112.
[32] P. Vontobel and R. Koetter, “Towards low-complexity linear-program-ming decoding,” in Proc. Int. Symp. Turbo Codes Rel. Topics, Munich,Germany, Apr. 2006.
[33] P. Vontobel, “Interior-point algorithms for linear-programming de-coding,” in Proc. 3rd Annu. Workshop Inf. Theory and its Appl., SanDiego, CA, Feb. 2008.
[34] M. Taghavi and P. Siegel, “Adaptive methods for linear programmingdecoding,” IEEE Trans. Inf. Theory, vol. 54, no. 12, pp. 5396–5410,Dec. 2008.
[35] T. Wadayama, “An LP decoding algorithm based on primal path-fol-lowing interior point method,” in Proc. IEEE Int. Symp. Inf. Theory,Seoul, Korea, Jun. 2009, pp. 389–393.
[36] D. Burshtein, “Iterative approximate linear programming decoding ofLDPC codes with linear complexity,” IEEE Trans. Inf. Theory, vol. 55,no. 11, pp. 4835–4859, Nov. 2009.
[37] M. Punekar and M. F. Flanagan, “Low complexity linear programmingdecoding of nonbinary linear codes,” in Proc. 48th Annu. Allerton Conf.Commun., Control, Comput.., Monticello, IL, Sep.. 2010.
[38] J. K. Johnson, “Convex relaxation methods for graphical models: La-grangian and maximum entropy approaches,” Ph.D. dissertation, Mass.Inst. of Technol., Cambridge, MA, 2008.
[39] P. Regalia and J. Walsh, “Optimality and duality of the turbo decoder,”Proc. IEEE, vol. 95, no. 6, pp. 1362–1377, Jun. 2007.
[40] F. Alberge, “Iterative decoding as Dykstra’s algorithm with alternatei-projection and reverse i-projection,” in Proc. Eur. Signal Process.Conf., Lausanne, Switzerland, 2008.
[41] J. Walsh and P. Regalia, “Belief propagation, Dykstra’s algorithm, anditerated information projections,” IEEE Trans. Inf. Theory, vol. 56, no.8, pp. 4114–4128, Aug. 2010.
[42] S. Boyd and L. Vandenberghe, Convex Optimization. Cambridge,U.K.: Cambridge Univ. Press, 2004.
[43] A. Kavcic, X. Ma, and M. Mitzenmacher, “Binary intersymbol interfer-ence channels: Gallager codes, density evolution and code performancebounds,” IEEE Trans. Inf. Theory, vol. 49, no. 7, pp. 1636–1652, Jul.2003.
[44] B.-H. Kim, “Joint equalization and decoding via convex optimization,”Ph.D. dissertation, Texas A&M Univ., College Station, TX.
[45] Z. Q. Luo and P. Tseng, “On the convergence of the coordinate descentmethod for convex differentiable minimization,” J. Optim. Theory Ap-plicat., vol. 72, no. 1, pp. 7–35, Jan. 1992.
[46] X. Hu, Z. Li, V. Kumar, and R. Barndt, “Error floor estimation of longLDPC codes on magnetic recording channels,” IEEE Trans. Magn., vol.46, no. 6, pp. 1836–1839, Jun. 2010.
[47] P. Lee, L. Dolecek, Z. Zhang, V. Anantharam, B. Nikolic, and M. Wain-wright, “Error floors in LDPC codes: Fast simulation, bounds and hard-ware emulation,” in Proc. IEEE Int. Symp. Inf. Theory, Toronto, ON,Canada, Jul. 2008, pp. 444–448.
[48] D. Bertsekas, Nonlinear Programming. Belmont, MA: Athena Sci-entific, 1995.
Byung-Hak Kim (S’09) received the B.S. and M.S.degrees in electrical engineering from Korea Univer-sity, Seoul, Korea, in 2000 and 2002, respectively. Heis currently working toward the Ph.D. degree in elec-trical engineering at Texas A&M University, CollegeStation.
During the summer of 2007, he interned at Qual-comm, Inc, San Diego, CA. His current researchinterests include information theory and channelcoding with applications in wireless communica-tions, data storage, and statistical inference.
Henry D. Pfister (S’99–M’03–SM’09) received thePh.D. degree in electrical engineering from the Uni-versity of California, San Diego, in 2003.
He joined the faculty of the School of Engineeringat Texas A&M University, College Station, in 2006.Prior to that, he spent two years in R&D at Qual-comm, Inc, San Diego. and one year as a post-docat EPFL.
Dr. Pfister received the NSF Career Award in 2008and was a coauthor of the 2007 IEEE COMSOCbest paper in Signal Processing and Coding for Data
Storage. His current research interests include information theory, channelcoding, and iterative decoding with applications in wireless communicationsand data storage.
