Department of Mathematics
 Search | Help | Login | pdf version | printable version

Math @ Duke



Publications [#319369] of Henry Pfister

Papers Published

  1. 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 (November, 2010), pp. 487-491, IEEE, ISBN 9781424467457 [doi]
    (last updated on 2019/07/21)

    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.
ph: 919.660.2800
fax: 919.660.2821

Mathematics Department
Duke University, Box 90320
Durham, NC 27708-0320