Tight bounds for LDPC and LDGM codes under MAP decoding

Abstract

A new method for analyzing low density parity check (LDPC) codes and low density generator matrix (LDGM) codes under bit maximum a posteriori probability (MAP) decoding is introduced. The method is based on a rigorous approach to spin glasses developed by Francesco Guerra. It allows to construct lower bounds on the entropy of the transmitted message conditional to the received one. Based on heuristic statistical mechanics calculations, we conjecture such bounds to be tight. The result holds for standard irregular ensembles when used over binary input output symmetric channels. The method is first developed for Tanner graph ensembles with Poisson left degree distribution. It is then generalized to `multi-Poisson' graphs, and, by a completion procedure, to arbitrary degree distribution.

28 pages, 9 eps figures; Second version contains a generalization of the previous result

References in corpus (2)

• Broken Replica Symmetry Bounds in the Mean Field Spin Glass Model
• Replica bounds for diluted non-Poissonian spin systems

Cited by in corpus (17)

• Threshold Saturation for Spatially-Coupled LDPC and LDGM Codes on BMS Channels
• Information-theoretic thresholds from the cavity method
• Combinatorial approach to the interpolation method and scaling limits in sparse random graphs
• A Simple Proof of Maxwell Saturation for Coupled Scalar Recursions
• Analysis of Regularized LS Reconstruction and Random Matrix Ensembles in Compressed Sensing
• Mutual Information and Optimality of Approximate Message-Passing in Random Linear Estimation
• A note on classical ground state energies
• The adaptive interpolation method for proving replica formulas. Applications to the Curie-Weiss and Wigner spike models
• Typology of phase transitions in Bayesian inference problems
• On Universal Properties of Capacity-Approaching LDPC Ensembles
• Sharp Bounds for Optimal Decoding of Low Density Parity Check Codes
• Replica Bounds by Combinatorial Interpolation for Diluted Spin Systems
• The Generalized Random Energy Model and its Application to the Statistical Physics of Ensembles of Hierarchical Codes
• The random energy model in a magnetic field and joint source-channel coding
• Concentration of multi-overlaps for random ferromagnetic spin models
• Statistical mechanics of LDPC codes on channels with memory
• Applications of correlation inequalities to low density graphical codes