Computer Science – Information Theory
Scientific paper
2011-07-15
Computer Science
Information Theory
43 pages, 3 figures
Scientific paper
Applying the max-product (and belief-propagation) algorithms to loopy graphs is now quite popular for best assignment 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 both attenuated max-product (AMP) decoding and weighted min-sum (WMS) decoding for LDPC codes which guarantees convergence to a fixed point when a weight parameter, {\beta}, is sufficiently small. It also shows that, if the fixed point satisfies some consistency conditions, then it must be both the linear-programming (LP) and maximum-likelihood (ML) solution. For (dv,dc)-regular LDPC codes, the weight must satisfy {\beta}(dv-1) \leq 1 whereas the results proposed by Frey and Koetter require instead that {\beta}(dv-1)(dc-1) < 1. A counterexample which shows a fixed point might not be the ML solution if {\beta}(dv-1) > 1 is also given. Finally, connections are explored with recent work by Arora et al. on the threshold of LP decoding.
Jian Yung-Yih
Pfister Henry D.
No associations
LandOfFree
Convergence of Weighted Min-Sum Decoding Via Dynamic Programming on Trees does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Convergence of Weighted Min-Sum Decoding Via Dynamic Programming on Trees, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Convergence of Weighted Min-Sum Decoding Via Dynamic Programming on Trees will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-549502