####
Capacity Approaching Signal Consteallations for Channels with Memory

We study the limits of performance of Gallager codes (low-density
parity-check (LDPC) codes) over binary linear intersymbol interference
(ISI) channels with additive white Gaussian noise (AWGN). Using the
graph representations of the channel, the code, and the sum-product
message-passing detector/decoder, we prove two error concentration
theorems. Our proofs expand on previous work by handling complications
introduced by the channel memory. We circumvent these problems by
considering not just linear Gallager codes but also their cosets and
by distinguishing between different types of message flow
neighborhoods depending on the actual transmitted symbols. We compute
the noise tolerance threshold using a suitably developed density
evolution algorithm and verify, by simulation, that the thresholds
represent accurate predictions of the performance of the iterative
sum-product algorithm for finite (but large) block lengths. We also
demonstrate that for high rates, the thresholds are very close to the
theoretical limit of performance for Gallager codes over ISI
channels. If C denotes the capacity of a binary ISI channel and if
Ci.i.d. denotes the maximal achievable mutual information rate when
the channel inputs are independent and identically distributed
(i.i.d.) binary random variables (Ci.i.d. <= C), we prove that the
maximum information rate achievable by the sum-product decoder of a
Gallager (coset) code is upper-bounded by Ci.i.d. The last topic
investigated is the performance limit of the decoder if the trellis
portion of the sum-product algorithm is executed only once; this
demonstrates the potential for trading off the computational
requirements and the performance of the decoder.