Math @ Duke

Publications [#319369] of Henry Pfister
Papers Published
 Jian, YY; Pfister, HD, Convergence of weighted minsum decoding via dynamic programming on coupled trees,
6th International Symposium on Turbo Codes and Iterative Information Processing, ISTC 2010
(November, 2010),
pp. 487491, ISBN 9781424467457 [doi]
(last updated on 2018/07/22)
Abstract: Applying the maxproduct (and beliefpropagation) 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 minsum (a.k.a. attenuated maxproduct) 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 linearprogramming (LP) and maximumlikelihood (ML) solution. For (d v , d c )regular LDPC codes, the weight must satisfy 1/β > d v  1 whereas the result of Koetter and Frey requires instead that 1/β > (d v  l)(d c  1). A counterexample is also given that shows a fixed point might not be the ML solution if 1/β < d v  1. Finally, connections are explored with recent work by Arora et al. on the threshold of LP decoding.


dept@math.duke.edu
ph: 919.660.2800
fax: 919.660.2821
 
Mathematics Department
Duke University, Box 90320
Durham, NC 277080320

