Tight Bounds for LDPC and LDGM Codes Under MAP Decoding
From MaRDI portal
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.
Cited in
(10)- Replica bounds by combinatorial interpolation for diluted spin systems
- Concentration of multi-overlaps for random dilute ferromagnetic spin models
- The adaptive interpolation method: a simple scheme to prove replica formulas in Bayesian inference
- On the concentration of the number of solutions of random satisfiability formulas
- Conditional random fields, planted constraint satisfaction, and entropy concentration
- Right-convergence of sparse random graphs
- The adaptive interpolation method for proving replica formulas. Applications to the Curie–Weiss and Wigner spike models
- Information theoretic limits of learning a sparse rule
- Inference and mutual information on random factor graphs
- Exact solution of the gauge symmetric \(p\)-spin glass model on a complete graph
This page was built for publication: Tight Bounds for LDPC and LDGM Codes Under MAP Decoding
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3547394)
