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 message-passing decoders applied to low density parity check codes used over any binary-input memoryless channel with discrete or continuous output alphabets. We show that for almost all codes in a suitably defined ensemble, transmission at rates below this capacity results in error probabilities that approach zero exponentially fast in the length of the code, whereas for transmission at rates above the capacity the error probability stays bounded away from zero. Our results are based on the observation that the concentration of the performance of the decoder around its average performance, as observed by Luby et al in the case of a binary symmetric channel and a binary message passing algorithm, is a general phenomenon. For the particularly important case of belief propagation decoders we provide an effective algorithm to determine the corresonding capacity to any desired degree of accuracy. The ideas presented in this paper are broadly applicable and extensions of the general method to low density parity check codes over larger alphabets, turbo codes, and other concatenated coding schemes are outlined.