The capacity of low-density parity-check codes under message-passing decoding

In this paper, we present a general method for determining the capacity of low-density parity-check (LDPC) codes under message-passing decoding when u sed over any binary-input memoryless channel with discrete or continuous ou tput alphabets, Transmitting at rates below this capacity, a randomly chose n element of the given ensemble will achieve an arbitrarily small target pr obability of error with a probability that approaches one exponentially fas t in the length of the code. (By concatenating with an appropriate outer co de one can achieve a probability of error that approaches zero exponentiall y fast in the length of the code with arbitrarily small loss in rate.) Conv ersely, transmitting at rates above this capacity the probability of error is bounded away from zero by a strictly positive constant which is independ ent of the length of the code and of the number of iterations performed. Ou r results are based on the observation that the concentration of the perfor mance of the decoder around its average performance, as observed by Luby et al. [1] in the case of a binary-symmetric channel and a binary message-pas sing algorithm, is a general phenomenon, For the particularly important cas e of belief-propagation decoders, we provide an effective algorithm to dete r-mine the corresponding capacity to any desired degree of accuracy, The id eas presented in this paper are broadly applicable and extensions of the ge neral method to low-density parity-check codes over larger alphabets, turbo codes, and other concatenated coding schemes are outlined.