Sharp Bounds for Optimal Decoding of Low Density Parity Check Codes
arXiv:0807.3065 · doi:10.1109/TIT.2009.2027523
Abstract
Consider communication over a binary-input memoryless output-symmetric channel with low density parity check (LDPC) codes and maximum a posteriori (MAP) decoding. The replica method of spin glass theory allows to conjecture an analytic formula for the average input-output conditional entropy per bit in the infinite block length limit. Montanari proved a lower bound for this entropy, in the case of LDPC ensembles with convex check degree polynomial, which matches the replica formula. Here we extend this lower bound to any irregular LDPC ensemble. The new feature of our work is an analysis of the second derivative of the conditional input-output entropy with respect to noise. A close relation arises between this second derivative and correlation or mutual information of codebits. This allows us to extend the realm of the interpolation method, in particular we show how channel symmetry allows to control the fluctuations of the overlap parameters.
40 Pages, Submitted to IEEE Transactions on Information Theory
References in corpus (2)
Cited by in corpus (10)
- Threshold Saturation for Spatially-Coupled LDPC and LDGM Codes on BMS Channels
- A Simple Proof of Maxwell Saturation for Coupled Scalar Recursions
- Mutual Information and Optimality of Approximate Message-Passing in Random Linear Estimation
- Analysis of Regularized LS Reconstruction and Random Matrix Ensembles in Compressed Sensing
- A note on classical ground state energies
- The adaptive interpolation method for proving replica formulas. Applications to the Curie-Weiss and Wigner spike models
- Applications of Large Random Matrices in Communications Engineering
- Spatial Coupling as a Proof Technique
- On the concentration of the number of solutions of random satisfiability formulas
- Concentration of multi-overlaps for random ferromagnetic spin models