Linear programming (LP) relaxation is a common technique used to find good solutions to complex optimization problems.We present the method of "LP decoding": applying LP relaxation to the problem of maximum-likelihood (ML) decoding.An arbitrary binary-input memoryless channel is considered.This treatment of the LP decoding method places our previous work on turbo codes [6] and low-density parity-check (LDPC) codes [8] into a generic framework.We define the notion of a proper relaxation, and show that any LP decoder that uses a proper relaxation exhibits many useful properties.We describe the notion of pseudocodewords under LP decoding, unifying many known characterizations for specific codes and channels.The fractional distance of an LP decoder is defined, and it is shown that LP decoders correct a number of errors equal to half the fractional distance.We also discuss the application of LP decoding to binary linear codes.We define the notion of a relaxation being symmetric for a binary linear code.We show that if a relaxation is symmetric, one may assume that the all-zeros codeword is transmitted.
Linear programming (LP) relaxation is a common technique used to find good solutions to complex optimization problems.We present the method of "LP decoding": applying LP relaxation to the problem of maximum-likelihood (ML) decoding.An arbitrary binary-input memoryless channel is considered.This treatment of the LP decoding method places our previous work on turbo codes [6] and low-density parity-check (LDPC) codes [8] into a generic framework.We define the notion of a proper relaxation, and show that any LP decoder that uses a proper relaxation exhibits many useful properties.We describe the notion of pseudocodewords under LP decoding, unifying many known characterizations for specific codes and channels.The fractional distance of an LP decoder is defined, and it is shown that LP decoders correct a number of errors equal to half the fractional distance.We also discuss the application of LP decoding to binary linear codes.We define the notion of a relaxation being symmetric for a binary linear code.We show that if a relaxation is symmetric, one may assume that the all-zeros codeword is transmitted.
A new method is given for performing approximate maximum-likelihood (ML) decoding of an arbitrary binary linear code based on observations received from any discrete memoryless symmetric channel. The decoding algorithm is based on a linear programming (LP) relaxation that is defined by a factor graph or parity-check representation of the code. The resulting "LP decoder" generalizes our previous work on turbo-like codes. A precise combinatorial characterization of when the LP decoder succeeds is provided, based on pseudocodewords associated with the factor graph. Our definition of a pseudocodeword unifies other such notions known for iterative algorithms, including "stopping sets," "irreducible closed walks," "trellis cycles," "deviation sets," and "graph covers." The fractional distance d/sub frac/ of a code is introduced, which is a lower bound on the classical distance. It is shown that the efficient LP decoder will correct up to /spl lceil/d/sub frac//2/spl rceil/-1 errors and that there are codes with d/sub frac/=/spl Omega/(n/sup 1-/spl epsi//). An efficient algorithm to compute the fractional distance is presented. Experimental evidence shows a similar performance on low-density parity-check (LDPC) codes between LP decoding and the min-sum and sum-product algorithms. Methods for tightening the LP relaxation to improve performance are also provided.
Abstract — Given a linear code and observations from a noisy channel, the decoding problem is to determine the most likely (ML) codeword. We describe a method for approximate ML decoding of an arbitrary binary linear code, based on a linear programming (LP) relaxation that is defined by a factor graph or parity check representation of the code. The resulting LP decoder, which generalizes our previous work on turbo-like codes [FK02, FWK02], has the ML certificate property: it either outputs the ML codeword with a guarantee of correctness, or acknowledges an error. We provide a precise characterization of when the LP decoder succeeds, based on the cost of pseudocodewords associated with the factor graph. We introduce the notion of the fractional distance δ of a code, defined with respect to a particular LP relaxation, and prove that the LP decoder will correct up to [δ/2] − 1 errors. For the BEC, we prove that the performance of LP decoding is equivalent to standard iterative decoding. I.
Maximum-likelihood decoding is often the optimal decoding rule one can use, but it is very costly to implement in a general setting. Much effort has therefore been dedicated to find efficient decoding algorithms that either achieve or approximate the error-correcting performance of the maximum-likelihood decoder. This dissertation examines two approaches to this problem. In 2003 Feldman and his collaborators defined the linear programming decoder, which operates by solving a linear programming relaxation of the maximum-likelihood decoding problem. As with many modern decoding algorithms, is possible for the linear programming decoder to output vectors that do not correspond to codewords; such vectors are known as pseudocodewords. In this work, we completely classify the set of linear programming pseudocodewords for the family of cycle codes. For the case of the binary symmetric channel, another approximation of maximum-likelihood decoding was introduced by Omura in 1972. This decoder employs an iterative algorithm whose behavior closely mimics that of the simplex algorithm. We generalize Omura's decoder to operate on any binary-input memoryless channel, thus obtaining a soft-decision decoding algorithm. Further, we prove that the probability of the generalized algorithm returning the maximum-likelihood codeword approaches 1 as the number of iterations goes to infinity.
This paper considers the joint-decoding problem for finite-state channels (FSCs) and low-density parity-check (LDPC) codes. In the first part, the linear-programming (LP) decoder for binary linear codes is extended to perform joint-decoding of binary-input FSCs. In particular, we provide a rigorous definition of LP joint-decoding pseudo-codewords (JD-PCWs) that enables evaluation of the pairwise error probability between codewords and JD-PCWs in AWGN. This leads naturally to a provable upper bound on decoder failure probability. If the channel is a finite-state intersymbol interference channel, then the joint LP decoder also has the maximum-likelihood (ML) certificate property and all integer-valued solutions are codewords. In this case, the performance loss relative to ML decoding can be explained completely by fractional-valued JD-PCWs. After deriving these results, we discovered some elements were equivalent to earlier work by Flanagan on linear-programming receivers. In the second part, we develop an efficient iterative solver for the joint LP decoder discussed in the first part. In particular, we extend the approach of iterative approximate LP decoding, proposed by Vontobel and Koetter and analyzed by Burshtein, to this problem. By taking advantage of the dual-domain structure of the joint-decoding LP, we obtain a convergent iterative algorithm for joint LP decoding whose structure is similar to BCJR-based turbo equalization (TE). The result is a joint iterative decoder whose per-iteration complexity is similar to that of TE but whose performance is similar to that of joint LP decoding. The main advantage of this decoder is that it appears to provide the predictability and superior performance of joint LP decoding with the computational complexity of TE. One expected application is coding for magnetic storage where the required block-error rate is extremely low and system performance is difficult to verify by simulation.
The problem of low complexity linear programming (LP) decoding of low-density parity-check (LDPC) codes is considered. An iterative algorithm, similar to min-sum and belief propagation, for efficient approximate solution of this problem was proposed by Vontobel and Koetter. In this paper, the convergence rate and computational complexity of this algorithm are studied using a scheduling scheme that we propose. In particular, we are interested in obtaining a feasible vector in the LP decoding problem that is close to optimal in the following sense. The distance, normalized by the block length, between the minimum and the objective function value of this approximate solution can be made arbitrarily small. It is shown that such a feasible vector can be obtained with a computational complexity which scales linearly with the block length. Combined with previous results that have shown that the LP decoder can correct some fixed fraction of errors we conclude that this error correction can be achieved with linear computational complexity. This is achieved by first applying the iterative LP decoder that decodes the correct transmitted codeword up to an arbitrarily small fraction of erroneous bits, and then correcting the remaining errors using some standard method. These conclusions are also extended to generalized LDPC codes.
In this paper, the linear programming (LP) decoder for binary linear codes, introduced by Feldman, et al. is extended to joint-decoding of binary-input finite-state channels. In particular, we provide a rigorous definition of LP joint-decoding pseudo-codewords (JD-PCWs) that enables evaluation of the pairwise error probability between codewords and JD-PCWs. This leads naturally to a provable upper bound on decoder failure probability. If the channel is a finite-state intersymbol interference channel, then the LP joint decoder also has the maximum-likelihood (ML) certificate property and all integer valued solutions are codewords. In this case, the performance loss relative to ML decoding can be explained completely by fractional valued JD-PCWs.