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

Thumbnail Image

Date

Authors

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

Description

We 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.
2004 IEEE Information Theory Workshop, San Antonio, October 24-29 (invited paper)

Keywords

Information Theory, Disordered Systems and Neural Networks

Citation

URI

http://salesiana.dossiersoluciones.com/handle/123456789/133391

Consulte el texto completo en el siguiente enlace:

https://arxiv.org/abs/cs/0410028
 http://arxiv.org/abs/cs/0410028

Collections

arXiv