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.
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.
Recently, a new decoding rule called jar decoding was proposed, under which the decoder first forms a set of suitable size, called a jar, consisting of sequences from the channel input alphabet considered to be closely related to yn, and then takes any codeword from the jar as the estimate of the transmitted codeword. In this paper, we show that under jar decoding, the analysis of low density parity check (LDPC) codes is much easier compared to maximum a posteriori (MAP) or maximum likelihood (ML) and Belief Propagation (BP) decoding, and new general LDPC coding theorems can be established. Specifically, it is proved that LDPC codes can approach the mutual information, with diminishing bit error probability, of any binary input memoryless channel with uniform input distribution when the average variable node degree is large. Moreover, simulation shows an interesting connection between jar decoding and BP decoding, i.e., BP decoding can be regarded as one of many ways to pick up a codeword from the jar for LDPC codes when it succeeds in outputting a codeword.
This paper is focused on the derivation of some universal properties of capacity-approaching low-density parity-check (LDPC) code ensembles whose transmission takes place over memoryless binary-input output-symmetric (MBIOS) channels. Properties of the degree distributions, graphical complexity, and the number of fundamental cycles in the bipartite graphs are considered via the derivation of information-theoretic bounds. These bounds are expressed in terms of the target block/bit error probability and the gap (in rate) to capacity. Most of the bounds are general for any decoding algorithm, and some others are proved under belief propagation (BP) decoding. Proving these bounds under a certain decoding algorithm, validates them automatically also under any suboptimal decoding algorithm. A proper modification of these bounds makes them universal for the set of all MBIOS channels which exhibit a given capacity. Bounds on the degree distributions and graphical complexity apply to finite-length LDPC codes and to the asymptotic case of an infinite block length. The bounds are compared with capacity-approaching LDPC code ensembles under BP decoding, and they are shown to be informative and are easy to calculate. Finally, some interesting open problems are considered.
A universal design of low-density parity-check (LDPC) code ensembles which enables to operate reliably over various channels is of great interest. This paper considers the universality of LDPC code ensembles over sets of memoryless binary-input output-symmetric (MBIOS) channels, addressing their universality under belief-propagation (BP) and maximum-likelihood (ML) decoding. Based on the density evolution approach, closed-form, easy-to-calculate, analytical results related to the universality of LDPC code ensembles under BP decoding are derived. LP Bounds on the achievable rate of LDPC code ensembles over a set of equi-capacity channels are also derived. This paper considers the universality under ML decoding of properly selected regular LDPC code ensembles for the set of equi-capacity MBIOS channels. The full paper version related to this work [13] provides further results, full proofs, and additional discussions on the theorems.
There is a fundamental relationship between belief propagation (BP) and maximuma posterioridecoding. The case of transmission over the binary erasure channel was investigated in detail in a companion paper (C. MEacuteasson, A. Montanari, and R. Urbanke, "Maxwell's construction: The hidden bridge between iterative and maximum a posteriori decoding,"IEEE Transactions on Information Theory, submitted for publication). This paper investigates the extension to general memoryless channels (paying special attention to the binary case). An area theorem for transmission over general memoryless channels is introduced and some of its many consequences are discussed. We show that this area theorem gives rise to an upper bound on the maximuma posteriorithreshold for sparse graph codes. In situations where this bound is tight, the extrinsic soft bit estimates delivered by the BP decoder coincide with the correcta posterioriprobabilities above the maximuma posteriorithreshold. More generally, it is conjectured that the fundamental relationship between the maximuma posterioriprobability (MAP) and the BP decoder which was observed for transmission over the binary erasure channel carries over to the general case. We finally demonstrate that in order for the design rate of an ensemble to approach the capacity under BP decoding the component codes have to be perfectly matched, a statement which is well known for the special case of transmission over the binary erasure channel.
A universal design of low-density parity-check (LDPC) code ensembles which enables to operate reliably over various channels is of great theoretical and practical interest. This paper considers the universality of LDPC code ensembles over multitude memoryless binary-input output-symmetric (MBIOS) channels, addressing their universality under belief-propagation (BP) decoding. Based on the density evolution approach, analytical results related to the universality of LDPC code ensembles under BP decoding are derived; these results are expressed in closed form, and are easy to calculate. The full paper version related to this work provides further results, full proofs, additional discussions on the theorems, and it also considers the universality issue under ML decoding.
This paper investigates about the usefulness of some recently published low complexity upper bounds on belief-propagation decoding thresholds for irregular low-density parity-check (LDPC) codes to analyze their performance on memoryless binary input - additive white Gaussian noise (BI-AWGN) channels, with sum-product decoding. Irregular LDPC codes are known to perform better than regular ones, and to exhibit, like them, the so called “threshold phenomenon”, being the threshold defined as the maximum noise level such that an arbitrarily small bit-error probability can be achieved as the block length tends to infinity. We use a simplified analysis of the belief-propagation decoding algorithm, i.e., consider a Gaussian approximation for message densities under density evolution, and a simple algorithmic method, defined recently, to estimate the decoding thresholds for regular and irregular LDPC codes on BI-AWGN channels.