MAXIMUM-LIKELIHOOD SEQUENCE ESTIMATION FROM THE LATTICE VIEWPOINT

We consider the problem of data detection in multilevel lattice-type modulation systems in the presence of intersymbol interference and additive white Gaussian noise. The conventional maximum likelihood sequence estimator using the Viterbi algorithm has a time complexity of O(m(v+1)) operations per symbol and a space complexity of O(delta m(v)) storage elements, where m is the size of input alphabet, v is the length of channel memory, and delta is the truncation depth. By revising the truncation scheme and viewing the channel as a linear transform, we identify the problem of maximum likelihood sequence estimation with that of finding the nearest lattice point. From this lattice viewpoint, the lattice sequence estimator for PAM systems is developed, which has the following desired properties: 1) its expected-time complexity grows as delta(2), as SNR --> infinity; 2) its space complexity grow as delta; and 3) its error performance is effectively optimal for sufficiently large m. A tight upper bound on the symbol error probability of the new estimator is derived, and is confirmed by the simulation results of an example channel. It turns out that the estimator is effectively optimal for m greater than or equal to 4 and the loss in signal-to-noise ratio is less than 0.5 dB even for m = 2. Finally, limitations of the proposed estimator are also discussed.