The Mutual information of LDGM codes

MaRDI QIDQ6288992zbMATH OpenFDO

Authors Jan van Den Brand, Nor Jaafari

Publication date 14 July 2017

Mathematics Subject Classification ID

Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Measures of information, entropy (94A17)

Abstract: We provide matching upper and lower bounds on the mutual information in noisy reconstruction of parity check codes and thereby prove a long-standing conjecture by Montanari [IEEE Transactions on Information Theory 2005]. Besides extending a prior concentration result of Abbe and Montanari [Theory of Computing 2015] to the case of odd check degrees, we precisely determine the conjectured formula for code ensembles of arbitrary degree distribution, thus capturing a broad class of capacity approaching codes.

This page was built for publication: The Mutual information of LDGM codes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6288992)