Using Linear Programming to Decode Linear Codes

Given a linear code and observations from a noisy channel, the decoding problem is to de- termine the most likely (ML) codeword. We describe a method for approximate ML decoding of an arbi- trary binary linear code, based on a linear program- ming (LP) relaxation that is dened by a factor graph or parity check representation of the code. The result- ing LP decoder, which generalizes our previous work on turbo-like codes (FK02, FWK02), has the ML cer- tic ate 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 pseu- docodewords associated with the factor graph. We in- troduce the notion of the fractional distance of a code, dened with respect to a particular LP relax- ation, 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.  In this paper, we generalize our meth- ods to an arbitrary binary linear code. We dene the linear code linear program (LCLP), which is an approximation to the maximum-likelihood (ML) decoding problem based on the method of linear programming (LP) relaxation. An LP decoder is a decoder based on the LCLP relaxation. Experiments show that the performance of LP decoding is on par with the iter- ative min-sum algorithm. In addition, as in turbo-like codes, the LP decoder has the ML certic ate property; whenever it outputs a codeword, it is guaranteed to be the ML codeword. None of the standard iterative methods are known to have this desirable property. We give an exact combinatorial characterization of the con- ditions for LP decoding success. We use the channel model to dene a cost function on the bits such that the lowest cost codeword is the ML codeword. We dene the set of pseu- docodewords, which is a superset of the set of codewords, and we prove that the LP decoder always nds the lowest cost pseudocodeword. Thus, the LP decoder succeeds if and only if the lowest cost pseudocodeword is actually the transmitted codeword. Our notion of a pseudocodeword unies other known results for particular cases of codes and channels. For tail-biting trel- lises, the pseudocodewords analyzed in this paper are equiva- lent to those introduced by Forney et al. (FKKR01). For the case of the binary erasure channel (BEC), pseudocodewords are exactly stopping sets, as dened by Di et al. (DPR + 02). Thus, the performance of the LP decoder is equivalent to it- erative methods in both these cases. Also, when applied to the analysis of computation trees for min-sum decoding, pseu- docodewords have a connection to the deviation sets dened by Wiberg (Wib96). We dene the notion of the fractional distance of a linear code, which is a generalization of the classical distance. In analogy to the performance guarantees of exact ML decod- ing with respect to classical distance, we prove that the LP decoder can correct up to =2 1 errors in the binary sym- metric channel (BSC). We prove that the fractional distance of a linear code with check degree at least three is at least ex- ponential in the girth of the graph associated with that code. Thus, given a graph with logarithmic girth, the fractional dis- tance can be lower bounded by ( n 1 ), for some constant ,