Life Above Threshold: From List Decoding to Area Theorem and MSE

Simple item page
dc.creatorMeasson, Cyril
dc.creatorMontanari, Andrea
dc.creatorRichardson, Tom
dc.creatorUrbanke, Rudiger
dc.date2004-10-13
dc.date2004-11-14
dc.date.accessioned2026-07-07T08:15:15Z
dc.date.available2026-07-07T08:15:15Z
dc.descriptionWe consider communication over memoryless channels using low-density parity-check code ensembles above the iterative (belief propagation) threshold. What is the computational complexity of decoding (i.e., of reconstructing all the typical input codewords for a given channel output) in this regime? We define an algorithm accomplishing this task and analyze its typical performance. The behavior of the new algorithm can be expressed in purely information-theoretical terms. Its analysis provides an alternative proof of the area theorem for the binary erasure channel. Finally, we explain how the area theorem is generalized to arbitrary memoryless channels. We note that the recently discovered relation between mutual information and minimal square error is an instance of the area theorem in the setting of Gaussian channels.
dc.description2004 IEEE Information Theory Workshop, San Antonio, October 24-29 (invited paper)
dc.identifierhttps://arxiv.org/abs/cs/0410028
dc.identifierhttp://arxiv.org/abs/cs/0410028
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/133391
dc.subjectInformation Theory
dc.subjectDisordered Systems and Neural Networks
dc.titleLife Above Threshold: From List Decoding to Area Theorem and MSE
dc.typetext

Files

Collections

arXiv