Skip to main content

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

Publication ,  Conference
Jian, YY; Pfister, HD
Published in: 6th International Symposium on Turbo Codes and Iterative Information Processing, ISTC 2010
November 29, 2010

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

Published In

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

DOI

ISBN

9781424467457

Publication Date

November 29, 2010

Start / End Page

487 / 491
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Jian, Y. Y., & Pfister, H. D. (2010). Convergence of weighted min-sum decoding via dynamic programming on coupled trees. In 6th International Symposium on Turbo Codes and Iterative Information Processing, ISTC 2010 (pp. 487–491). https://doi.org/10.1109/ISTC.2010.5613901
Jian, Y. Y., and H. D. Pfister. “Convergence of weighted min-sum decoding via dynamic programming on coupled trees.” In 6th International Symposium on Turbo Codes and Iterative Information Processing, ISTC 2010, 487–91, 2010. https://doi.org/10.1109/ISTC.2010.5613901.
Jian YY, Pfister HD. Convergence of weighted min-sum decoding via dynamic programming on coupled trees. In: 6th International Symposium on Turbo Codes and Iterative Information Processing, ISTC 2010. 2010. p. 487–91.
Jian, Y. Y., and H. D. Pfister. “Convergence of weighted min-sum decoding via dynamic programming on coupled trees.” 6th International Symposium on Turbo Codes and Iterative Information Processing, ISTC 2010, 2010, pp. 487–91. Scopus, doi:10.1109/ISTC.2010.5613901.
Jian YY, Pfister HD. Convergence of weighted min-sum decoding via dynamic programming on coupled trees. 6th International Symposium on Turbo Codes and Iterative Information Processing, ISTC 2010. 2010. p. 487–491.

Published In

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

DOI

ISBN

9781424467457

Publication Date

November 29, 2010

Start / End Page

487 / 491