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

TLDR

Let's aggregate. Background sentences: two lines: "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." and "in the case of a binary-symmetric channel and a binary message-passing algorithm, is a general phenomenon." Combine: The background: concentration phenomenon of decoder performance around average, general for binary-symmetric channel and binary message-passing algorithm. Purpose sentences: multiple: first line [Purpose, Mechanism] "We present a general method for determining the capacity of low-density parity-check (LDPC) codes under message-passing decoding when used over any binary-input memoryless channel with discrete or continuous output alphabets." Also [Purpose, Mechanism] "For the particularly important case of belief-propagation decoders, we provide an effective algorithm to determine the corresponding capacity to any desired degree of accuracy." Also [Purpose] "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." So purpose: present general method to determine capacity of LDPC codes under message-passing decoding over any binary-input memoryless channel, with effective algorithm for belief-propagation decoders, and outline extensions to larger alphabets, turbo codes, etc. The purpose is the goal; mechanism is how they do it.

Abstract

We present a general method for determining the capacity of low-density parity-check (LDPC) codes under message-passing decoding when used over any binary-input memoryless channel with discrete or continuous output alphabets. Transmitting at rates below this capacity, a randomly chosen element of the given ensemble will achieve an arbitrarily small target probability of error with a probability that approaches one exponentially fast in the length of the code. (By concatenating with an appropriate outer code one can achieve a probability of error that approaches zero exponentially fast in the length of the code with arbitrarily small loss in rate.) Conversely, transmitting at rates above this capacity the probability of error is bounded away from zero by a strictly positive constant which is independent of the length of the code and of the number of iterations performed. 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 corresponding 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.