期刊
IEEE TRANSACTIONS ON INFORMATION THEORY
卷 51, 期 3, 页码 954-972出版社
IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC
DOI: 10.1109/TIT.2004.842696
关键词
belief propagation (BP); iterative decoding; low-density parity-check (LDPC) codes; linear codes; linear programming (LP); LP decoding; minimum distance; pseudocodewords
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.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据