SUBMITTED TO IEEE TRANSACTIONS ON INFORMATION THEORY 100 Binary Intersymbol Interference Channels: Gallager Codes, Density Evolution and Code Performance Bounds

We study the limits of performance of Gallager codes (low-density parity-check codes) over binary linear intersymbol interference (ISI) channels with additive Gaussian noise. Using the graph representa-tions 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 dierent types of message ow 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 sum-product algorithm for nite (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 C i:i:d: denotes the maximal achievable mutual information rate when the channel inputs are independent identically distributed (i.i.d.) binary random variables (C i: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 C i: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 o the computational requirements and the performance of the decoder