Journal
IEEE TRANSACTIONS ON INFORMATION THEORY
Volume 51, Issue 3, Pages 954-972Publisher
IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC
DOI: 10.1109/TIT.2004.842696
Keywords
belief propagation (BP); iterative decoding; low-density parity-check (LDPC) codes; linear codes; linear programming (LP); LP decoding; minimum distance; pseudocodewords
Ask authors/readers for more resources
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(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 [d(frac)/2] - 1 errors and that there are codes with d(frac) = Omega(n(1-epsilon)). 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.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available