We derive the asymptotic spectra of low-density parity-check (LDPC) ensembles over Z/sub q/. We consider two ensembles of LDPC matrices, one is binary and the other q-ary. We also show that for modulo-additive noise channels, both ensembles achieve the random coding error exponent, for graphs with sufficiently large connectivity.

We show how asymptotic estimates of powers of polynomials with nonnegative coefficients can be used in the analysis of low-density parity-check (LDPC) codes. In particular, we show how these estimates can be used to derive the asymptotic distance spectrum of both regular and irregular LDPC code ensembles. We then consider the binary erasure channel (BEC). Using these estimates we derive lower bounds on the error exponent, under iterative decoding, of LDPC codes used over the BEC. Both regular and irregular code structures are considered. These bounds are compared to the corresponding bounds when optimal (maximum-likelihood (ML)) decoding is applied.

We propose an efficient maximum-likelihood (ML) decoding algorithm for decoding low-density parity-check (LDPC) codes over the binary-erasure channel (BEC). We also analyze the computational complexity of the proposed algorithm.

We derive upper bounds on the rate of low-density parity-check (LDPC) codes for which reliable communication is achievable. We first generalize Gallager's (1963) bound to a general binary-input symmetric-output channel. We then proceed to derive tighter bounds. We also derive upper bounds on the rate as a function of the minimum distance of the code. We consider both individual codes and ensembles of codes.

We consider Gallager's (1963) soft-decoding (belief propagation) algorithm for decoding low-density parity-check (LDPC) codes, when applied to an arbitrary binary-input symmetric-output channel. By considering the expected values of the messages, we derive both lower and upper bounds on the performance of the algorithm. We also derive various properties of the decoding algorithm, such as a certain robustness to the details of the channel noise. Our results apply both to regular and irregular LDPC codes.

We show how expander-based arguments may be used to prove that message-passing algorithms can correct a linear number of erroneous messages. The implication of this result is that when the block length is sufficiently large, once a message-passing algorithm has corrected a sufficiently large fraction of the errors, it will eventually correct all errors. This result is then combined with known results on the ability of message-passing algorithms to reduce the number of errors to an arbitrarily small fraction for relatively high transmission rates. The results hold for various message-passing algorithms, including Gallager's hard-decision and soft-decision (with clipping) decoding algorithms. Our results assume low-density parity-check (LDPC) codes based on an irregular bipartite graph.

We derive both upper and lower bounds on the decoding error probability of maximum-likelihood (ML) decoded low-density parity-check (LDPC) codes. The results hold for any binary-input symmetric-output channel. Our results indicate that for various appropriately chosen ensembles of LDPC codes, reliable communication is possible up to channel capacity. However, the ensemble averaged decoding error probability decreases polynomially, and not exponentially. The lower and upper bounds coincide asymptotically, thus showing the tightness of the bounds. However, for ensembles with suitably chosen parameters, the error probability of almost all codes is exponentially decreasing, with an error exponent that can be set arbitrarily close to the standard random coding exponent.