IEEE International Symposium on Information Theory (ISIT)

Tight bounds for LDPC codes under MAP decoding

Andrea Montanari A

Published Dec 23, 2004• 2 citations

Abstract

We present a new approach to the analysis of codes on graphs under symbol-maximum a posteriori probability (MAP) decoding. The approach is based on Guerra's interpolation technique for spin glasses. The basic idea is to consider a smooth interpolation between the original decoding problem, and a much simpler system in which each bit is retransmitted without coding through a (different) "effective" channel. Quite interestingly, the resulting expressions are strictly related to the density-evolution analysis of belief propagation decoding. The fundamental quantities involved in the interpolation procedure are, for instance, the same as in density evolution, i.e. densities of messages. Motivated by heuristic statistical mechanics results, we conjecture our bounds to be tight.

DOI: 10.1109/isit.2004.1365511

Related papers

Tight Bounds for LDPC and LDGM Codes Under MAP Decoding

Andrea Montanari A

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 one 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 (BIOS) 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

arXiv:cs/0407060IEEE Transactions on Information TheoryAug 24, 2005105 citations

Tight bounds for LDPC and LDGM codes under MAP decoding

Andrea Montanari A

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 method is illustrated on codes with Poisson left degree distributions when used over binary input output symmetric channels. However, it is arguably much more general. UMR 8549, Unité Mixte de Recherche du Centre National de la Recherche Scientifique et de l ’ Ecole Normale

Jan 1, 2005101 citations

Sharp Bounds on Generalized EXIT Functions

Nicolas Macris

We consider communication over binary-input memoryless symmetric channels with low-density parity-check (LDPC) codes. The relationship between maximum a posteriori and belief propagation decoding is investigated using a set of correlation inequalities that first appeared in statistical mechanics of Gaussian spin glasses. We prove bounds on generalized extrinsic information transfer (EXIT) functions, that are believed to be tight, and discuss their relationship with the ones obtained by the interpolation method.

IEEE Transactions on Information TheoryJun 28, 200746 citations

Decoding with belief propagation

Marc Mézard, Andrea Montanari A

Abstract This chapter revisits the problem of decoding low density parity check (LDPC) codes. The maximum a posteriori probability (MAP) decoding of a bit is described as a statistical inference problem, and belief propagation is applied to its solution. The corresponding message passing procedure is analyzed in details, and the threshold noise level below which this ‘iterative decoding’ achieves perfect decoding is derived. The chapter ends with a general discussion of the relation between message passing and optimal (exact symbol MAP) decoding.

Jan 22, 20090 citations

Statistical physics methods for sparse graph codes

Shrinivas Kudekar

This thesis deals with the asymptotic analysis of coding systems based on sparse graph codes. The goal of this work is to analyze the decoder performance when transmitting over a general binary-input memoryless symmetric-output (BMS) channel. We consider the two most fundamental decoders, the optimal maximum a posteriori (MAP) decoder and the sub-optimal belief propagation (BP) decoder. The BP decoder has low-complexity and its performance analysis is, hence, of great interest. The MAP decoder, on the other hand, is computationally expensive. However, the MAP decoder analysis provides fundamental limits on the code performance. As a result, the MAP-decoding analysis is important in designing codes which achieve the ultimate Shannon limit. It would be fair to say that, over the binary erasure channel (BEC), the performance of the MAP and BP decoder has been thoroughly understood. However, much less is known in the case of transmission over general BMS channels. The combinatorial methods used for analyzing the case of BEC do not extend easily to the general case. The main goal of this thesis is to advance the analysis in the case of transmission over general BMS channels. To do this, we use the recent convergence of statistical physics and coding theory. Sparse graph codes can be mapped into appropriate statistical physics spin-glass models. This allows us to use sophisticated methods from rigorous statistical mechanics like the correlation inequalities, interpolation method and cluster expansions for the purpose of our analysis. One of the main results of this thesis is that in some regimes of noise, the BP decoder is optimal for a typical code in an ensemble of codes. This result is a pleasing extension of the same result for the case of BEC. An important consequence of our results is that the heuristic predictions of the replica and cavity methods of spin-glass theory are correct in the realm of sparse graph codes.

Jan 1, 20093 citations

Correlation inequalities: a useful tool in the theory of LDPC codes

Nicolas Macris

It is shown that a correlation inequality of statistical mechanics can be applied to low-density parity-check codes. Thanks to this tool we prove that the growth rate of regular LDPC codes, can be exactly calculated by iterative methods, at least on the interval where it is a concave function of the relative weight of code words. We also consider communication over a binary input additive white Gaussian noise channel with a Poisson LDPC code and prove that (at least part of) the GEXIT curve (associated to MAP decoding) can also be computed exactly by the belief propagation decoder. In both problems, the correlation inequality yields sharp lower bounds. We also use a non trivial extension of the interpolation techniques that have recently led to rigorous results in spin glass theory and in the SAT problem

IEEE International Symposium on Information Theory (ISIT)Jan 1, 20058 citations