Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

IEEE Transactions on Information Theory

Using Linear Programming to Decode Binary Linear Codes

J. Feldman, Martin J. Wainwright, David Ron Karger

Published Feb 28, 2005• 547 citations
Publisher

Abstract

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.

DOI
10.1109/tit.2004.842696

Related papers

Using Linear Programming to Decode Linear Codes

Jon Feldman, Martin J. Wainwright, David Ron Karger

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.

•Jan 1, 2003•33 citations

On Iterative Joint Decoding and Demodulation

Hui Jin, Tom Richardson

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.

•Oct 1, 2003•0 citations

Applications of linear programming to coding theory

Nathan Axvig

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.

•Jan 1, 2010•3 citations

Iterative Approximate Linear Programming Decoding of LDPC Codes With Linear Complexity

David Burshtein

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.

IEEE Transactions on Information Theory•Oct 27, 2009•62 citations

An Efficient Pseudocodeword Search Algorithm for Linear Programming Decoding of LDPC Codes

Michael Chertkov, Mikhail Stepanov

In linear programming (LP) decoding of a low-density parity-check (LDPC) code one minimizes a linear functional, with coefficients related to log-likelihood ratios, over a relaxation of the polytope spanned by the codewords. In order to quantify LP decoding it is important to study vertexes of the relaxed polytope, so-called pseudocodewords. We propose a technique to heuristcally create a list of pseudocodewords close to the zero codeword and their distances. Our pseudocodeword-search algorithm starts by randomly choosing configuration of the noise. The configuration is modified through a discrete number of steps. Each step consists of two substeps: one applies an LP decoder to the noise-configuration deriving a pseudocodeword, and then finds configuration of the noise equidistant from the pseudocodeword and the zero codeword. The resulting noise configuration is used as an entry for the next step. The iterations converge rapidly to a pseudocodeword neighboring the zero codeword. Repeated many times, this procedure is characterized by the distribution function of the pseudocodeword effective distance. The efficiency of the procedure is demonstrated on examples of the Tanner code and Margulis codes operating over an additive white Gaussian noise (AWGN) channel.

arXiv:cs/0601113•IEEE Transactions on Information Theory•Mar 27, 2008•56 citations

Message-Passing Algorithms and Improved LP Decoding

Sanjeev Arora, Constantinos Daskalakis, David Steurer

Linear programming (LP) decoding for low-density parity-check codes (and related domains such as compressed sensing) has received increased attention over recent years because of its practical performance-coming close to that of iterative decoding algorithms-and its amenability to finite-blocklength analysis. Several works starting with the work of Feldman showed how to analyze LP decoding using properties of expander graphs. This line of analysis works for only low error rates, about a couple of orders of magnitude lower than the empirically observed performance. It is possible to do better for the case of random noise, as shown by Daskalakis and Koetter and Vontobel. Building on work of Koetter and Vontobel, we obtain a novel understanding of LP decoding, which allows us to establish a 0.05 fraction of correctable errors for rate-½ codes; this comes very close to the performance of iterative decoders and is significantly higher than the best previously noted correctable bit error rate for LP decoding. Our analysis exploits an explicit connection between LP decoding and message-passing algorithms and, unlike other techniques, directly works with the primal linear program. An interesting byproduct of our method is a notion of a “locally optimal” solution that we show to always be globally optimal (i.e., it is the nearest codeword). Such a solution can in fact be found in near-linear time by a “reweighted” version of the min-sum algorithm, obviating the need for LP. Our analysis implies, in particular, that this reweighted version of the min-sum decoder corrects up to a 0.05 fraction of errors.

IEEE Transactions on Information Theory•Jul 13, 2012•23 citations
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.
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.
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.
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 linear programming (LP) decoding of a low-density parity-check (LDPC) code one minimizes a linear functional, with coefficients related to log-likelihood ratios, over a relaxation of the polytope spanned by the codewords. In order to quantify LP decoding it is important to study vertexes of the relaxed polytope, so-called pseudocodewords. We propose a technique to heuristcally create a list of pseudocodewords close to the zero codeword and their distances. Our pseudocodeword-search algorithm starts by randomly choosing configuration of the noise. The configuration is modified through a discrete number of steps. Each step consists of two substeps: one applies an LP decoder to the noise-configuration deriving a pseudocodeword, and then finds configuration of the noise equidistant from the pseudocodeword and the zero codeword. The resulting noise configuration is used as an entry for the next step. The iterations converge rapidly to a pseudocodeword neighboring the zero codeword. Repeated many times, this procedure is characterized by the distribution function of the pseudocodeword effective distance. The efficiency of the procedure is demonstrated on examples of the Tanner code and Margulis codes operating over an additive white Gaussian noise (AWGN) channel.
Linear programming (LP) decoding for low-density parity-check codes (and related domains such as compressed sensing) has received increased attention over recent years because of its practical performance-coming close to that of iterative decoding algorithms-and its amenability to finite-blocklength analysis. Several works starting with the work of Feldman showed how to analyze LP decoding using properties of expander graphs. This line of analysis works for only low error rates, about a couple of orders of magnitude lower than the empirically observed performance. It is possible to do better for the case of random noise, as shown by Daskalakis and Koetter and Vontobel. Building on work of Koetter and Vontobel, we obtain a novel understanding of LP decoding, which allows us to establish a 0.05 fraction of correctable errors for rate-½ codes; this comes very close to the performance of iterative decoders and is significantly higher than the best previously noted correctable bit error rate for LP decoding. Our analysis exploits an explicit connection between LP decoding and message-passing algorithms and, unlike other techniques, directly works with the primal linear program. An interesting byproduct of our method is a notion of a “locally optimal” solution that we show to always be globally optimal (i.e., it is the nearest codeword). Such a solution can in fact be found in near-linear time by a “reweighted” version of the min-sum algorithm, obviating the need for LP. Our analysis implies, in particular, that this reweighted version of the min-sum decoder corrects up to a 0.05 fraction of errors.