Sufficient Conditions for Convergence of the Sum-Product Decoding

Fernando Hernando, Kristine Lally, Diego Ruano

Yung-Yih Jian, Henry D. Pfister

Applying the max-product (and sum-product) 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 or optimality of converged solutions or both. This paper presents an analysis of both attenuated max-product decoding and weighted min-sum decoding for low-density parity-check (LDPC) codes, which guarantees convergence to a fixed point when a weight factor, β, is sufficiently small. It also shows that, if the fixed point satisfies some consistency conditions, then it must be both a linear-programming (LP) and maximum-likelihood (ML) decoding solution. For (dv, dc)-regular LDPC codes, the weight factor must satisfy β(dv-1)v-1)(dc-1) ≤ 1. In addition, the range of the weight factor for a provable ML decoding solution is extended to 0v-1) 1. In addition, counterexamples that show a fixed point might not be the ML decoding solution if β(dv-1) > 1 are given. Finally, connections are explored with recent work on the threshold of LP decoding.

Yung-Yih Jian, Henry D. Pfister

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/β > dν- 1 whereas the result of Koetter and Frey requires instead that 1/β > (dv- 1)(dc- 1). A counterexample is also given that shows a fixed point might not be the ML solution if 1/βν- 1. Finally, connections are explored with recent work by Arora et al. on the threshold of LP decoding.

Kazuhiko Yamaguchi

Yung-Yih Jian

This dissertation studies methods to achieve reliable communication over unreliable channels. Iterative decoding algorithms for low-density parity-check (LDPC) codes and generalized LDPC (GLDPC) codes are analyzed.\n\nA new class of error-correcting codes to enhance the reliability of the communication for high-speed systems, such as optical communication systems, is proposed. The class of spatially-coupled GLDPC codes is studied, and a new iterative hard- decision decoding (HDD) algorithm for GLDPC codes is introduced. The main result is that the minimal redundancy allowed by Shannon’s Channel Coding Theorem can be achieved by using the new iterative HDD algorithm with spatially-coupled GLDPC codes. A variety of low-density parity-check (LDPC) ensembles have now been observed to approach capacity with iterative decoding. However, all of them use soft (i.e., non-binary) messages and a posteriori probability (APP) decoding of their component codes. To the best of our knowledge, this is the first system that can approach the channel capacity using iterative HDD.\n\nThe optimality of a codeword returned by the weighted min-sum (WMS) algorithm, an iterative decoding algorithm which is widely used in practice, is studied as well. The attenuated max-product (AttMP) decoding and weighted min-sum (WMS) decoding for LDPC codes are analyzed. Applying the max-product (and belief- propagation) algorithms to loopy graphs are 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 work presents an analysis of both AttMP decoding and WMS decoding for LDPC codes which guarantees convergence to a fixed point when a weight factor, β, is sufficiently small. It also shows that, if the fixed point satisfies some consistency conditions, then it must be both a linear-programming (LP) and maximum-likelihood (ML) decoding solution.

Ilya I. Dumer