Convergence of weighted min-sum decoding via dynamic programming on coupled trees

Applying the max-product (and belief-propagation) algorithms to loopy graphs is now quite popular for constraint satisfaction problems. This is largely due to their low computational complexity and impressive performance in practice. Still, there is no general understanding of the conditions required for convergence and/or the optimality of converged solutions. This paper presents an analysis of weighted min-sum (a.k.a. attenuated max-product) decoding for LDPC codes that guarantees convergence to a fixed point when the weight β is sufficiently small. It also shows that, if the fixed point satisfies all the constraints, then it must be both the linear-programming (LP) and maximumlikelihood (ML) solution. For (dv, dc)-regular LDPC codes, the weight must satisfy 1/β > dv - 1 whereas the result of Koetter and Frey requires instead that 1/β > (dv - l)(dc - 1). A counterexample is also given that shows a fixed point might not be the ML solution if 1/β < dv - 1. Finally, connections are explored with recent work by Arora et al. on the threshold of LP decoding.

Duke Scholars

Author Henry Pfister Electrical and Computer Engineering