Sergio Verdú

COMMUNICATION THEORY

2.1 MULTIUSER DETECTION

Currently, there is an explosion of research activity in the field of signal processing for wireless communication, and in particular in the field of multiuser detection. Multiuser detection studies the demodulation of one or more digital signals in the presence of multiuser interference. This technique is applicable to multiaccess techniques such as asynchronous CDMA (where interuser interference occurs by design) and TDMA (where interuser interference occurs due to nonideal effects such as channel distortion and out-of-cell interference). At the time of my Ph.D. thesis

the conventional wisdom was that it was best to simply neglect the presence of multiaccess interference since its statistical properties would be similar to additive white Gaussian noise, and therefore a single-user matched filter should be near-optimal to combat such interference. This conventional wisdom was proven wrong by the derivation and analysis of the optimal multiuser detector, whose earliest reference is: A full analysis and derivation can be found in This paper showed that there is, in general, a huge gap in performance between the performance of the conventional single-user matched filter and the optimal attainable performance. Furthermore, the infamous near-far problem was shown to be not an inherent flaw of CDMA but a consequence of the inability of the single-user matched filter to exploit the structure of the multiuser interference. The Jan. 1996 paper introduced a new analysis technique for the bit error rate of systems subject to interference: the approach of indecomposable sequences. It was later used succesfully in the analysis of single-user intersymbol interference problems (see 2.2.1). The performance measure of asymptotic multiuser efficiency, now widely used in the analysis of multiuser detectors was also introduced in the Jan. 1996 paper, and further studied in The optimum K-user detector in the Jan. 1996 paper consists of a bank of matched filters followed by a dynamic programming algorithm of the forward (Viterbi) type (for maximum-likelihood detection) or of the backward-forward type (for minimum bit-error-rate detection) (see 4.1). The time-complexity of this algorithm is exponential in K. This means that with the computational power of a Pentium chip one can demodulate 9 simultaneous users transmitting at 8 kbps, but if the number of users is, say, twice that many, optimum multiuser detection is computationally intractable. The reason for this intractability, as proved in my thesis and published in is that the optimum multiuser detection problem (whether in the synchronous or asynchronous versions) is NP-complete, and thus it admits a polynomial solution if and only if a polynomial solution can be found for famous combinatorial optimization problems such as the traveling salesman problem which are widely believed not to be solvable in polynomial time. My doctoral thesis also considered the analogous optimal demodulation problem for optical communication channels, a work that was published in (see 2.3.2) NonGaussian detection problems leading to nonlinear single-user detectors arise when the multiaccess interference is modeled with random phases and possibly random signature sequences. Solutions are given for various asymptotic situations (such as weak interferers, high spreading gain and high SNR) in The large gaps in performance and complexity between optimum multiuser detection and conventional single-user detection have spurred much work on suboptimal solutions. The first such detector I considered was the decorrelating detector: showed that this detector achieves the same near-far resistance as the optimum detector for synchronous channels. This result plus the justification of the decorrelating detector as the maximum likelihood solution when the received amplitudes are unknown were published in That paper also considered linear multiuser detectors that exploit knowledge of the received amplitudes to maximize asymptotic efficiency. The fact that linear detectors such as the decorrelator and the MMSE detector achieve optimum near-far resistance is a central result in multiuser detection, which does not find a counterpart in single-user digital communication. A saddle-point justification for the decorrelating detector was obtained in which gives the asynchronous version of the decorrelator as a doubly infinite impulse response filter. The one-shot decorrelating detector is due to An approximate decorrelator detector, which requires no algebraic operations with the crosscorrelations and is particularly simple to implement (even in systems where the signature sequence spans an arbitrary number of symbol periods) is proposed in the tutorial Such an approximation is justified by the analysis in A review of adaptive linear methods for multiuser detection is given in An important conceptual development in adaptive multiuser detection has been the proof that the MMSE detector is equivalent to an orthogonally anchored detector (linear transformation equal to the nonadaptive signature waveform of the desired user plus an orthogonal adaptive component) chosen to minimize the output energy: This paper shows how to perform optimally near-far resistant multiuser demodulation without knowledge of the signature waveforms, data sequences, timing and amplitudes of the interferers. The principle in the July 1995 paper is extended to the case where the desired signature waveform is not completely known (because of multipath) in A retrospective of the state-of-the-art in multiuser detection with a critical examination of some of the misconceptions that have arisen in its development is given in:
This page maintained by Michelle Young - Last modified 12/17/96