Easily Computed Lower Bounds on the Information Rate of Intersymbol Interference Channels

Seongwook Jeong, Jaekyun Moon

This paper, published in 2011, addresses a fundamental challenge in digital communications: how to efficiently and accurately estimate the information rate of channels plagued by Intersymbol Interference (ISI).

TL;DR

The authors develop a new, provable lower bound for the information rate of ISI channels that is computationally "cheap" to evaluate. By using a "mismatched" mutual information function and identifying dominant interference clusters, they provide a mathematical tool that is as tight as popular unproven conjectures (like the Shamai-Laroia bound) but significantly faster than traditional simulation-based methods.

What Problem Does This Paper Address?

In digital communication, "capacity" tells us the maximum rate at which we can send data reliably. For a simple channel with white noise, this is easy to calculate. However, real-world channels often have "memory"—previous symbols bleed into the current one, a phenomenon called Intersymbol Interference (ISI).

Calculating the Symmetric Information Rate (SIR)—the capacity when inputs are chosen uniformly—for ISI channels is notoriously difficult. Historically, researchers had three choices:

  1. Monte-Carlo Simulations (BCJR algorithm): Accurate but computationally expensive, especially for channels with long memory.
  2. The Hirt Bound: Requires high-dimensional integration, making it impractical for long blocks.
  3. The Shamai-Laroia Conjecture (SLC): A very popular, fast "rule of thumb" that works well in practice but lacks a formal mathematical proof.

The authors sought a "middle way": a bound that is mathematically proven (unlike SLC) but doesn't require the heavy lifting of massive simulations.

Methods

The authors' approach relies on two clever mathematical steps:

  1. Mismatched Mutual Information (MMI): They define a new information function, $I'(X; Y)$. The "mismatch" comes from calculating entropy using a Gaussian distribution that matches the variance of the actual interference, rather than using the true (and complex) probability density function of the ISI. They prove that this mismatched version is always a lower bound to the true information rate.
  2. Cluster Identification: The interference in an ISI channel is essentially a "Gaussian mixture"—a sum of many discrete points blurred by noise. To make their bound tighter, the authors identify a few "dominant" interference taps (clusters). They calculate the exact distribution for these big taps and treat the remaining "tail" of smaller taps as a simple variance term.
  3. Numerical Integration: By reducing the problem to a few single-dimensional integrals, the bound can be computed in a fraction of the time it takes to run a trellis-based simulation like BCJR.

Datasets

The paper evaluates the new bounds using several standard synthetic ISI channel models frequently used in communication theory benchmarks:

  • Simple 2-tap channel: $h(D) = 2^{-1/2}(1+D)$.
  • 4-tap channel: A standard model for channels with moderate memory.
  • 7-tap Magnetic Recording Channel: Simulates the high-density interference found in hard disk drives.
  • Long ISI Channel: A 10-tap model previously used to test complex iterative algorithms.
  • Complex-valued Channel: A QPSK-based partial response channel to demonstrate the method's versatility.

Key Insights and Ideas

  • The "Worst-Case" Gaussian: A recurring theme in information theory is that Gaussian noise is often the "worst" kind of noise for a given variance. By forcing the math to "think" the interference is Gaussian (the mismatch), the authors create a safe, provable floor for the information rate.
  • Separating the "Big" from the "Small": The "aha moment" is realizing that you don't need to model every single interference tap perfectly. Modeling the top 2 or 3 taps exactly and approximating the rest provides a massive boost in accuracy with minimal extra math.
  • Proving the Conjecture: For many years, engineers used the Shamai-Laroia Conjecture (SLC) because it "just worked." This paper provides a provable bound that often overlaps with or exceeds the SLC, giving researchers more confidence in using these types of approximations.

Key Results

  • Tightness: The new bound is remarkably close to the true SIR. In many cases, it is indistinguishable from the SLC at low-to-mid Signal-to-Noise Ratios (SNR).
  • High SNR Superiority: At high SNRs, the new bound actually becomes tighter than the Shamai-Laroia Conjecture.
  • Efficiency: Compared to state-of-the-art simulation methods (like the iterative EM-type algorithms of the era), this analytical bound achieves similar accuracy with a much lower computational load. For example, it can reach within 0.84 dB of the true SIR using only two clusters, whereas complex trellis-based simulations might require 64 states and multiple iterations to achieve similar results.

Limitations and Future Work

  • The "Scattered" Channel Problem: The method relies on identifying "dominant" taps. If a channel has hundreds of tiny, equal-sized taps (like a highly scattered indoor wireless environment), the "cluster" approach loses its edge, and the bound may not be as tight.
  • Exponential Scaling: While "easy" compared to simulations, the complexity of the bound still grows exponentially with the number of dominant clusters ($M$) chosen ($2^M$ integrals).
  • Alphabet Constraints: The derivation focuses on BPSK and QPSK. While the authors suggest extensions to higher-order alphabets (like 16-QAM) are straightforward, the computational cost would increase.

Reference: Jeong, S., & Moon, J. (2011). Easily Computed Lower Bounds on the Information Rate of Intersymbol Interference Channels. arXiv:1110.0560v1 [cs.IT].

Summary updated

Abstract

Provable lower bounds are presented for the information rate I(X; X+S+N) where X is the symbol drawn independently and uniformly from a finite-size alphabet, S is a discrete-valued random variable (RV) and N is a Gaussian RV. It is well known that with S representing the precursor intersymbol interference (ISI) at the decision feedback equalizer (DFE) output, I(X; X+S+N) serves as a tight lower bound for the symmetric information rate (SIR) as well as capacity of the ISI channel corrupted by Gaussian noise. When evaluated on a number of well-known finite-ISI channels, these new bounds provide a very similar level of tightness against the SIR to the conjectured lower bound by Shamai and Laroia at all signal-to-noise ratio (SNR) ranges, while being actually tighter when viewed closed up at high SNRs. The new lower bounds are obtained in two steps: First, a “mismatched” mutual information function is introduced which can be proved as a lower bound to I(X; X+S+N). Secondly, this function is further bounded from below by an expression that can be computed easily via a few single-dimensional integrations with a small computational load.
BibTeX
@article{jeong2012easily,
  author = {Seongwook Jeong and Jaekyun Moon},
  title = {{Easily Computed Lower Bounds on the Information Rate of Intersymbol Interference Channels}},
  journal = {IEEE Trans. Information Theory},
  year = {2012},
  url = {https://openreview.net/forum?id=LDjsvWJ-oN},
}

Loading related content...

Figure