Fast Maximum Likelihood Sequence Detection Over Vector Intersymbol Interference Channels

We consider the communication system that transmits a sequence of binary vector symbols over a vector intersymbol interference (ISI) channels subject to additive white Gaussian noise. Conventionally, maximum likelihood (ML) sequence is computed using the Viterbi algorithm (VA), whose complexity scales exponentially in both the symbol vector length and the number of ISI channel taps. We show that, as the signal to noise ratio (SNR) goes to infinity, the ML sequence can be obtained with an asymptotic complexity scaling linearly in the number of channel taps and quadratically in the symbol vector length.