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


Conference Paper

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.

Full Text

Duke Authors

Cited Authors

  • Jian, YY; Pfister, HD

Published Date

  • November 29, 2010

Published In

  • 6th International Symposium on Turbo Codes and Iterative Information Processing, Istc 2010

Start / End Page

  • 487 - 491

International Standard Book Number 13 (ISBN-13)

  • 9781424467457

Digital Object Identifier (DOI)

  • 10.1109/ISTC.2010.5613901

Citation Source

  • Scopus