Reduced Precision Requirements for Power Control - Since the impact of MAI and the near-far effect is much reduced, the need for all users to arrive at the receiver at exactly the same power is reduced; thus, less precision is needed in controlling the transmitted power of the mobiles. Therefore, the additional complexity at the base station required for multi- user detection may allow reduced complexity at the mobiles [15].

More Efficient Power Utilization - The reduction of interference on the uplink may translate to some reduction in the required transmit power of the mobiles [15]. Alternatively, the same transmit power may be used to extend the size of the coverage region.

Matrix-Vector Notation
In discussing multi-user detection, it is convenient to introduce a matrix-vector system model to describe the output of the conventional detector. We begin with a simple example to help illustrate our discussion: a three user synchronous system. From Eq. (3), the output for each of the users for one bit is

y1 = A1d1 + r2,1 A2d2 + r3,1 A3d3 +z1
y2 =r1,2 A1d1 + A2d2 + r3,2 A3d3 +z2            (4)
y3 = r1,3 A1d1 + r2,3 A2d2 + A3d3 +z3

(5)

or

y = RAd + z (6)

For a K user system, the vectors d, z, and y, are K-vectors that hold the data, noise, and matched filter outputs of all K users, respectively; the matrix A is a diagonal matrix containing the corresponding received amplitudes; the matrix R is a K x K correlation matrix, whose entries contain the values of the correlations between every pair of codes. Note that since ri,k = rk,i, the matrix R is clearly symmetric.
It is instructive to break up R into two matrices: one representing the autocorrelations, the other the crosscorrelations. Therefore, parallel to Eq. (3), the conventional matched filter detector output can be expressed as three terms:

y = Ad + QAd + z (7)

where Q contains the off-diagonal elements (crosscorrelations) of R, that is, R = I + Q (I is the identity matrix). The first term, Ad, is simply the decoupled data weighted by the received amplitudes. The second term, QAd, represents the MAI interference.

Asynchronous Channel
The detection problem in an asynchronous channel is more complicated than in a synchronous channel. In a synchronous channel, by definition, the bits of each user are aligned in time. Thus, detection can focus on one bit interval independent of the others (e.g., Eq. (3)); the detection of N bits of K users is equivalent to N separate "one-shot" detection problems. In most realistic applications, however, the channel is asynchronous and thus, there is overlap between bits of different intervals. Here, any decision made on a particular bit ideally needs to take into account the decisions on the 2 overlapping bits of each user; the decisions on these overlapping bits must then further take into account decisions on bits that overlap them and so on. Therefore, the detection problem must optimally be framed over the whole message [40].
The continuous-time model expressed in Eq. (1) can easily be modified for asynchronous channels by including the relative time delays (offsets) between signals. The received signal is now written as

(8)

where tk is the delay for user k.
The discrete-time matrix-vector model describing the asynchronous channel takes the same form as Eq. (6). However, now the equation must encompass the entire message; thus, assuming there are N bits per user, the size of the vectors and the order of the matrices are NK. The vectors d, z, and y hold the data, noise, and matched filter outputs of all K users for all N bit intervals, and the matrix A contains the corresponding received amplitudes. The matrix R now contains the partial correlations that exist between every pair of the NK code words and is of size NK x NK. We use the term partial correlations because in an asynchronous channel, the codes for each bit only partially overlap each other.
An example helps to illustrate our discussion. Consider the timing diagram of Fig. 2, where there are a total of two users and 3 bits per user. The output of the conventional detector can be described using Eq. (6), where we treat the problem as if there were six users (each transmitting 1 bit over the interval 3Tb + t2 - t1). The vectors d, z, and y hold the data, noise, and matched filter outputs associated with each of these 6 bits. The correlation matrix, R, is of dimension 6 x 6 and can be written as

(9)

where ri,K is now the partial cross-correlation between the code associated with bit i and that associated with bit k; in other words, it denotes the cross-correlation between the overlapping part of code i and code k. Note that the 0 entrees correspond to the correlations between bits that do not overlap. For a typical message length N is much greater than K; hence, the correlation matrix is sparse because most of the NK bits do not overlap.
For the remainder of this article, an asynchronous channel is assumed unless otherwise stated. A more in-depth presentation of the mathematical details of the asynchronous channel can be found in [16, 18].

Maximum-Likelihood Sequence Detection
The detector which yields the most likely transmitted sequence, d, chooses d to maximize the probability that d was transmitted given that r(t) was received, where r(t) extends over the whole message. This probability is referred to as the joint a posteriori probability, P(d|(r(t), for all t)) [8]. Under the assumption that all possible transmitted sequences are equally probable, this detector is known as the maximum-likelihood sequence (MLS) detector [8].11-13
The problem with the MLS approach is that here there are 2NK possible d vectors; an exhaustive search is clearly impractical for typical message sizes and numbers of users. However, it turns out that MLS detection can be implemented for DS-CDMA by following the matched filter bank with a Viterbi algorithm [31].14 This method parallels the use of the Viterbi algorithm to implement MLS detection in channels corrupted by intersymbol interference [8, 31]. Unfortunately, the required Viterbi algorithm has a complexity that is still exponential in the number of users, that is, on the order of 2K.15
Another disadvantage of the MLS detector is that it requires knowledge of the received amplitudes and phases. These values, however, are not known a priori, and must be estimated (e.g. [34-37]).
Despite the huge performance and capacity gains over conventional detection, the MLS detector is not practical. A realistic direct-sequence system has a relatively large number of active users; thus, the exponential complexity in the number of users makes the cost of this detector too high. In the remainder of this article we look at various suboptimal multi-user detectors that are simpler to implement.

Linear Detectors
An important group of multi-user detectors are linear multi-user detectors. These detectors apply a linear mapping, L, to the soft output of the conventional detector to reduce the MAI seen by each user. In this section we briefly review the two most popular of these, the decorrelating and minimum mean-squared error detectors. We then examine the polynomial expansion detector, a linear detector recently proposed by the author that can efficiently implement both of the aforementioned detectors.

Decorrelating Detector
The decorrelating detector applies the inverse of the correlation matrix

Ldec = R-1 (10)

to the conventional detector output in order to decouple the data. (Note that R can be assumed to be invertible for asynchronous systems [40].) From Eq. (6), the soft estimate of this detector is

dec = R-1y = Ad + R-1z
= Ad + zdec (11)
which is just the decoupled data plus a noise term. Thus, we see that the decorrelating detector completely eliminates the MAI. This detector is very similar to the zero-forcing equalizer [8] which is used to completely eliminate ISI.
The decorrelating detector was initially proposed in [38, 39]. It is extensively analyzed by Lupas and Verdu in [40, 41], and is shown to have many attractive properties. Foremost among these properties are [16, 40, 41]:

• Provides substantial performance/capacity gains over the conventional detector under most conditions.16
• Does not need to estimate the received amplitudes. In contrast, detectors that require amplitude estimation are often quite sensitive to estimation error. (Note that as in the case of most multi-user detectors, the need to estimate the received phases can also be avoided through the use of noncoherent detection .9)
• Has computational complexity significantly lower than that of the maximum likelihood sequence detector. The per-bit complexity is linear in the number of users, excluding the costs of recomputation of the inverse mapping. Other desirable features of the decorrelating detector are [16, 40, 41]:
• Corresponds to the maximum likelihood sequence detector when the energies of all users are not known at the receiver. In other words, it yields the joint maximum likelihood sequence estimation of the transmitted bits and their received amplitudes.
• Has a probability of error independent of the signal energies. This simplifies the probability of error analysis, and makes the decorrelating detector resistant to the near-far problem.
• Yields the optimal value of the near-far resistance performance metric.17
• Can decorrelate one bit at a time. For bit k, we only need apply the kth row of R-1 to the matched filter bank outputs.

Minimum Mean-Squared Error (MMSE) Detector
The minimum mean-squared error (MMSE) detector [45] is a linear detector which takes into account the background noise and utilizes knowledge of the received signal powers. This detector implements the linear mapping which minimizes E[|d - Ly|2], the mean- squared error between the actual data and the soft output of the conventional detector. This results in [45, 84]

LMMSE = [R + (N0/2)A-2]-1 (12)

Thus, the soft estimate of the MMSE detector is simply

MMSE = LMMSE y (13)

As can be seen, the MMSE detector implements a partial or modified inverse of the correlation matrix. The amount of modification is directly proportional to the background noise; the higher the noise level, the less complete an inversion of R can be done without noise enhancement causing performance degradation. Thus, the MMSE detector balances the desire to decouple the users (and completely eliminate MAI) with the desire to not enhance the background noise. (Additional explanation can be found in [54].) This multi- user detector is exactly analogous to the MMSE linear equalizer used to combat ISI [8].
Because it takes the background noise into account, the MMSE detector generally provides better probability of error performance than the decorrelating detector. As the background noise goes to zero, the MMSE detector converges in performance to the decorrelating detector.23
An important disadvantage of this detector is that, unlike the decorrelating detector, it requires estimation of the received amplitudes. Another disadvantage is that its performance depends on the powers of the interfering users [45]. Therefore, there is some loss of resistance to the near-far problem as compared to the decorrelating detector. Like the decorrelating detector, the MMSE detector faces the task of implementing matrix inversion. Thus, most of the suboptimal techniques for implementing the decorrelating detector are applicable to this detector as well.24

Polynomial Expansion (PE) Detector
The polynomial expansion (PE) detector [54, 55], applies a polynomial expansion in R to the matched filter bank output, y. Thus, the linear mapping for the PE detector is

(14)

and the soft estimates of d are given by

PE = LPE y (15)

For a given R and Ns, the weights (polynomial coefficients) wi, i = 0, 1, \012, Ns can be chosen to optimize some performance measure.

The structure which implements the matrix R is shown in Fig. 3, and the full detector (with two stages) is shown in Fig. 4. Each stage implements R by recreating the overall modulation (spreading), noiseless channel (summing), and demodulation (matched filtering) process. The fact that this implements R is clear from the expression for the noiseless conventional detector output, y = RAd (Eq. (6)). Cascading these stages produces higher-order terms of the polynomial. A two-stage PE detector is shown in Fig. 4 ; the detector corresponding to Eq. (14) requires Ns stages.

It can be shown (by the Cayley-Hamilton Theorem) that the PE detector structure can exactly implement the decorrelating detector for finite message length, N [54]. However, for typical N this would require a prohibitive number of stages. As N ---< infinite stages would be needed, with one bit delay required per stage.25 Fortunately, good approximations can be obtained with a relatively small number of stages. Therefore, we can choose w = [w0 w1 \012 wNs] so that

(16)

The resulting weights are used in the structure of Fig. 4 to yield a K-input K-output finite memory-length detector, which approximates the decorrelating detector.
The PE detector structure can also be used to approximate the MMSE detector, as described in [54].
The polynomial expansion detector has a number of attractive features [54, 55]:

• Can approximate the decorrelating and MMSE detectors. As such, it can enjoy the desirable features of these two detectors, which were discussed earlier.
• Has low computational complexity. In approximating the decorrelating (or MMSE) detector, neither the matrix R nor its inverse must be explicitly calculated. Everything can be implemented on-line, using anything from analog hardware to DSP chips.
• Does not need to estimate the received amplitudes (or phases). This important feature, which is true for the decorrelating detector, is also true for the PE detector in approximating the decorrelating detector. (If the PE detector is approximating the MMSE detector, however, amplitude estimation will be necessary).
• Can be implemented just as easily using long codes as short codes. (See [51] which points out a problem with using short codes.)
• Can use weights that work well over a large variation of system parameters. As shown in [54], the use of additional stages in the PE detector (a higher order polynomial) allows more flexibility to use pre-computed weights that work well over a broad operating range. This minimizes or eliminates the need to adapt the weights to changes in the operating environment.
• Has a relatively simple structure. The types of system components used are the same as those of the conventional detector. The amount of system components increases linearly with the product of the number of users and the number of stages. As we will see in the next section, the structure is very similar to that of the parallel interference cancellation detector structure. In that structure, each stage contains a modulator (spreader) a partial summer, and a demodulator (matched-filter bank), which implements the matrix Q (R with its main diagonal removed).

Successive Interference Cancellation (SIC)
The successive interference cancellation (SIC) detector [60, 68] takes a serial approach to canceling interference. Each stage of this detector decisions, regenerates, and cancels out one additional direct-sequence user from the received signal, so that the remaining users see less MAI in the next stage. (Note that the basic concept behind this approach can be found earlier in information theory [61-63].)
A simplified diagram of the first stage of this detector is shown in Fig. 5, where a hard- decision approach is assumed. The first stage is preceded by an operation which ranks the signals in descending order of received powers (not shown). The first stage implements the following steps:
1. Detect with the conventional detector the strongest signal, s1.
2. Make a hard data decision on s1.
3. Regenerate an estimate of the received signal for user one, \026s1(t) , using:

• Data decision from step 2
• Knowledge of its PN sequence
• Estimates of its timing and amplitude (and phase)9

Assuming that the estimation of ^s1(t) in step 3 above was accurate, the outputs of the first stage are:
1. A data decision on the strongest user
2. A modified received signal without the MAI caused by the strongest user
This process can be repeated in a multistage structure: the kth stage takes as its input the "partially cleaned" received signal output by the previous stage, r(k - 1) (t), and outputs one additional data decision (for signal sk) and a "cleaner" received signal, r(k)(t).27, 28
The reasons for canceling the signals in descending order of signal strength are straightforward [17, 68]. First, it is easiest to achieve acquisition and demodulation on the strongest users (best chance for a correct data decision). Second, the removal of the strongest users gives the most benefit for the remaining users. The result of this algorithm is that the strongest user will not benefit from any MAI reduction; the weakest users, however, will potentially see a huge reduction in their MAI.29
The SIC detector requires only a minimal amount of additional hardware and has the potential to provide significant improvement over the conventional detector. It does, however, pose a couple of implementation difficulties. First, one additional bit delay is required per stage of cancellation. Thus, a trade-off must be made between the number of users that are canceled and the amount of delay that can be tolerated [64]. Second, there is a need to reorder the signals whenever the power profile changes [64]. Here, too, a trade-off must be made between the precision of the power ordering and the acceptable processing complexity.
A potential problem with the SIC detector occurs if the initial data estimates are not reliable. In this case, even if the timing, amplitude, and phase estimates are perfect, if the bit estimate is wrong, the interfering effect of that bit on the signal-to-noise ratio is quadrupled in power (the amplitude doubles, so the power quadruples). Thus, a certain minimum performance level of the conventional detector is required for the SIC detector to yield improvements; it is crucial that the data estimates of at least the strong users that are canceled first be reliable.

Parallel Interference Cancellation
In contrast to the SIC detector, the parallel interference cancellation (PIC) detector estimates and subtracts out all of the MAI for each user in parallel. The multistage PIC structure which we assume here was introduced in [67]. A basic one stage PIC structure is assumed in [68, 69] and several earlier references (see [18]).
The first stage of this detector is pictured in Fig. 6, where a hard-decision approach is assumed. The initial bit estimates, \026di(0), are derived from the matched filter detector (not shown), which we refer to as stage 0 of this detector. These bits are then scaled by the amplitude estimates and respread by the codes, which produces a delayed estimate of the received signal for each user, \026sk(t - Tb). The partial summer sums up all but one input signal at each of the outputs, which creates the complete MAI estimate for each user.
Assuming perfect amplitude and delay estimation, the result after subtracting the MAI estimate for user k is

(17)

As shown in Fig. 6, the result of Eq. (17) (for k = 1\012K) is passed on to a second bank of matched filters to produce a new, hopefully better, set of data estimates.

This process can be repeated for multiple stages. Each stage takes as its input the data estimates of the previous stage and produces a new set of estimates at its output. We can use a matrix-vector formulation to compactly express the soft output of stage m + 1 of the PIC detector for all N bits of all K users as [70]

(m + 1) = y - QA\026d(m)
= Ad + QA(d - \026d(m)) + z (18)

The term QA\026d(m) represents an estimate of the MAI (7). (As usual, for BPSK, the hard data decisions, \026d(m), are made according to the signs of the soft outputs, (m).) Perfect data estimates, coupled with our assumption of perfect amplitude and delay estimation, result in the complete elimination of MAI.30
A number of studies have investigated PIC detection which utilizes soft decisions, such as [55, 72, 76, 86]. In [72] soft-decision PIC and SIC detectors are compared; since soft- decision SIC exploits power variation by canceling in order of signal strength, it is found to be superior in a non-power-controlled fading channel. On the other hand, soft-decision PIC is found to be superior in a well-power-controlled channel.
A number of variations on the PIC detector have been proposed for improved performance. These include the following.

Using the Decorrelating Detector as the First Stage [70] - The performance of the PIC detector depends heavily on the initial data estimates [67]. As we pointed out for the SIC detector, the subtraction of an interfering bit based on an incorrect bit estimate causes a quadrupling in the interfering power for that bit. Thus, too many incorrect initial data estimates may cause performance to degrade relative to the conventional detector (no cancelation may be better than poor cancelation). Therefore, using the decorrelating detector as the first stage significantly improves the performance of the PIC detector. (An additional benefit from this approach is that the perormance analysis is found to be much simplified.)31, 32

Using the Already Detected Bits at the Output of the Current Stage to Improve Detection of the Remaining Bits in the Same Stage [74] - Thus, the most up-to-date bit decisions available are always used. This contrasts with the standard PIC detector, which only uses the previous stage's decisions. This detector is referred to as a multistage decision feedback detector [74]. Proposals for the initial stage of this detector include a decision-feedback detector [74], the conventional detector [45], and the decorrelating detector [78].33

Linearly Combining the Soft-Decision Outputs of Different Stages of the PIC Detector [55] - This simple modification yields very large gains in performance over the standard soft- decision PIC detector. The reason for this has to do with the extensive noise correlations that exist between outputs of different stages. The linear combination is made in such a way as to capitalize on the noise correlations and cause cancellation among noise terms.

Doing a Partial MAI Cancellation at Each Stage, with the Amount of Cancellation Increasing for Each Successive Stage [76] - Thus, the MAI estimate is first scaled by a fraction before cancellation; the value of the fraction increases for successive stages. This takes into account the fact that the tentative decisions of the earlier stages are less reliable than those of the later stages. Huge gains in performance and capacity are reported over the standard ("brute force") PIC detector. This recently proposed detector may be the most powerful of the subtractive interference cancellation detectors, and needs to be studied further.

Zero-Forcing Decision-Feedback (ZF-DF) Detector
The zero-forcing decision-feedback (ZF-DF) detector (also referred to as the decorrelating DF detector)[77-79, 81] performs two operations: linear preprocessing followed by a form of SIC detection. The linear operation partially decorrelates the users (without enhancing the noise), and the SIC operation decisions and subtracts out the interference from one additional user at a time, in descending order of signal strength. As we describe below, the initial partial decorrelation enables the SIC operation to be much more powerful. The ZF-DF detector is based on a white noise channel model. A noise-whitening filter is obtained by factoring R by the Cholesky decomposition [83], R = FTF, where F is a lower triangular matrix. Applying (FT)-1 to the matched filter bank outputs of Eq. (6) yields the white noise model [77]

yw = FAd + zw (19)

where the covariance matrix of the noise term, zw, is (N0/2)I (white noise). (This is similar to the white noise model that is derived for ISI chanels [8].)

In the white noise model of Eq. (19), the data bits are partially decorrelated. This can be shown to arise from the fact that the matrix F is lower triangular [77]. Thus, the output for bit one of the first user contains no MAI; the output for bit one of the second user contains MAI only from bit one of the first user, and is completely decorrelated from all other users; similarly, the output for user k at bit interval i is completely decorrelated from users k + 1, k + 2, \012, K, at time i, and from all bits at future time intervals.
The ZF-DF detector uses SIC detection to exploit the partial decorrelation of the bits in the white noise model. The soft output of bit one of the first user, which is completely free of MAI, is used to regenerate and cancel out the MAI it causes, thereby leaving the soft output of bit one of the second user also free of MAI (decorrelated). This process continues: for each iteration, the MAI contributed by one additional bit (the previously decorrelated bit) is regenerated and canceled, thereby yielding one additional decorrelated bit.
Prior to forming and applying (FT)-1 to create the white noise model, the users are ordered according to their signal strength, thus insuring that interference cancellation takes place in descending order of signal strength. This maximizes the gains to be had from SIC detection, as discussed earlier.
A diagram of the ZF-DF detector is shown in Fig. 7, where we assume a synchronous channel for clarity.34 In a synchronous channel we can deal with one bit interval at a time; hence, the size of the vectors and the order of F in Eq. (19) are reduced to K. Assuming perfect estimates of F and the received amplitudes, the soft output for the kth user is [77]

(20)

where \026di = sign [i] are the previously detected bits (of the stronger users), Ai is the received amplitude of this bit, and Fk,i is the (k, i)th element of F.
Under the assumption that all past decisions are correct, the ZF-DF detector eliminates all MAI and maximizes the signal-to-noise ratio [78].35 It is analogous to the ZF-DF equalizer used to combat ISI.36, 37
An important difficulty with the ZF-DF detector is the need to compute the Cholesky decomposition38 and the whitening filter (FT)-1 (matrix inversion). Attempts to simplify its implementation are similar to those of the decorrelating detector.
The ZF-DF detector, like the other nonlinear detectors, has the disadvantage of needing to estimate the received signal amplitudes. If the soft outputs of the decorrelating detector are used to estimate the amplitudes, the ZF-DF detector is equivalent to the decorrelating detector [78]. If the amplitude estimates are more reliable than those produced by the decorrelating detector, the ZF-DF detector performs better than the decorrelating detector; if less reliable, however, the ZF-DF detector performs worse than the decorrelating detector.

Summary and Conclusion
Multiple access interference significantly limits the performance and capacity of conventional DS-CDMA systems. Much research has been directed at mitigating this problem through the design of multi-user detectors.
In multi-user detection, code and timing information of multiple users is jointly used to better detect each individual user. The optimum multi-user sequence detector is known, and provides huge gains in performance and capacity over the conventional detector; it also minimizes the need for power control. Unfortunately, it is too complex to implement for practical DS-CDMA systems.
Many simpler suboptimal multi-user detectors have been proposed in the last few years, all of which have the potential to provide substantial performance and capacity gains over the conventional detector. Most of the detectors fall into two categories: linear and subtractive interference cancellation.

Linear Detectors
Linear multi-user detectors, which include the decorrelating, minimum mean-squared error (MMSE), and polynomial expansion (PE) detectors, apply a linear transformation to the outputs of the matched filter bank to reduce the MAI seen by each user.
The decorrelating detector applies the inverse of the correlation matrix to the matched filter bank outputs, thereby decoupling the signals. It has many desirable features, including its ability to be implemented without knowledge of the received amplitudes.
The MMSE detector applies a modified inverse of the correlation matrix to the matched filter bank outputs. It yields a better error rate performance than the decorrelating detector, but it requires estimation of the received powers.
Both the decorrelating and MMSE detectors require nontrivial computations that are a function of the cross-correlations. This is particularly difficult for the case of long (time- varying) codes, where the cross-correlations change each bit. Many proposals for simplifying the necessary computations have been made, but difficulties remain.
The polynomial expansion detector applies a polynomial expansion in the correlation matrix to the outputs of the matched filter bank. This detector has the important advantage that it can efficiently approximate either the decorrelating or MMSE detectors; in doing so, neither the correlation matrix nor its inverse needs to be explicitly calculated. Like the decorrelating detector, it does not need to estimate the received amplitudes. Unlike the decorrelating detector, it can easily be implemented with long codes. Also, it appears that weights (polynomial coefficients) can be chosen that are fairly robust over a wide range of system parameters, thereby minimizing or eliminating the need for adaptation.

Subtractive Interference Cancellation Detectors
Subtractive interference cancellation detectors attempt to estimate and subtract off the MAI. These detectors include the successive interference cancellation (SIC), parallel interference cancellation (PIC), and zero-forcing decision-feedback (ZF- DF) detectors.
The bit decisions used to estimate the MAI may be either hard decisions or soft decisions. Soft decisions provide a joint estimate of data and amplitude and are easier to implement. If reliable channel estimates are available, however, hard- decision (nonlinear) schemes perform better than their soft-decision counterparts.
The SIC detector takes a serial approach to subtracting out the MAI: it decisions, regenerates, and cancels out one additional direct-sequence user at a time. In contrast, the PIC detector estimates and subtracts out all of the MAI for each user in parallel. Both of these detectors may be implemented with a variable number of stages.
From the work in [72], it appears that the SIC detector performs better than the PIC detector in a fading environment, while the reverse is true in a well-power-controlled environment, (although this work has been done specifically for the case of soft decisions). The PIC detector requires more hardware, but the SIC detector faces the problems of power reordering and large delays.
Various methods for improving PIC detection have been proposed. The recently proposed improved PIC detector of [76] may be the most powerful of the subtractive interference cancellation detectors, and needs to be studied further.
Several detectors combine linear preprocessing with subtractive interference cancellation. Examples are the ZF-DF detector and a PIC detector with a decorrelating detector as the first stage. A significant disadvantage of the ZF-DF detector is that it requires Cholesky factorization and matrix inversion.
A major disadvantage of nonlinear detectors is their dependence on reliable estimates of the received amplitudes. Studies such as [56, 57] indicate that imperfect amplitude estimation may significantly reduce or even reverse the gains to be had from using these detectors.

Conclusion
Multi-user detection holds much promise for improving DS-CDMA performance and capacity. Although multi-user detection is currently in the research stage, efforts to commercialize multi-user detectors are expected in the coming years as DS-CDMA systems are more widely deployed. The success of these efforts will depend on the outcome of careful performance and cost analyses for the realistic environment.

Acknowledgment
The author sincerely thanks Dr. Mahesh Varanasi, Dr. Ken Smolik, Dr. Zoran Siveski, Dr. Howard Sherry, Dr. Joseph Wilkes, and Dr. Larry Ozarow for their helpful comments. The author also expresses his warm appreciation to his wife, Adina, for her help in editing this article.

References
[1] A. J. Viterbi, "The orthogonal-random waveform dichotomy for digital mobile personal communications," IEEE Pers. Commun, 1st qtr., 1994., pp. 18-24.
[2] W. C. Y. Lee, "Overview of Cellular CDMA," IEEE Trans. Vehic. Tech., vol. 40, no. 2, May 1991, pp. 291-302.
[3] K. S. Gilhousen et al., "On the capacity of a cellular CDMA system," IEEE Trans. Vehic. Tech., vol. 40, no. 2, May 1991, pp. 303-12.
[4] R. L. Pickholtz, L. B. Milstein, and D. L. Schilling, "Spread spectrum for mobile communications," IEEE Trans. Vehic. Tech., vol. 40, no. 2, May 1991, pp. 313-22.
[5] V. K. Garg, K. Smolik, and J. E. Wilkes, Applications of code-division multiple access (CDMA) in wireless/personal communications, Upper Saddle River, NJ: Prentice Hall, 1996.
[6] H. V. Poor and L. A. Rusch, "Narrowband interference suppression in spread spectrum CDMA," IEEE Pers. Commun., 3rd qtr., 1994,pp. 14-27.
[7] L. A. Rusch and H. V. Poor, "Multi-user detection techniques for narrowband interference suppression in spread spectrum communications," IEEE Trans. Commun., vol. 43, no. 2/3/4, Feb./Mar./Apr. 1995, pp. 1725-37.
[8] J. G. Proakis, Digital Communications, 2nd ed., New York: McGraw-Hill, 1989.
[9] M. B. Pursley, "Performance evaluation for phase-coded spread-spectrum multiple- access communication - Part I: system analysis," IEEE Trans. Commun., vol. COM-25, no. 8, Aug. 1977, pp. 795-99.
[10] K. Yao, "Error probability of asynchronous spread spectrum multiple access communication systems," IEEE Trans. Commun., vol. COM-25, no. 8, Aug. 1977, pp. 803-9.
[11] D. V. Sarwate and M. B. Pursley, "Crosscorrelation properties of pseudorandom and related sequences," Proc. IEEE, vol. 68, no. 5, May 1980, pp. 593-619.
[12] R. Kohno, "Pseudo-noise sequences and interference Cancellation Techniques for Spread Spectrum Systems," IEICE Trans. Commun., vol. J74-B-I, no. 5, May 1991, pp. 1083-92. Reprinted in Multiple Access Communications: Foundations for Emerging Technologies, N. Abramson, ed., IEEE Press, 1993.
[13] J. M. Holtzman, "CDMA Power Control for Wireless Networks," Third Generation Wireless Information Networks, D. G. Goodman and S. Nanda, eds., Norwell, MA: Kluwer, 1992, pp. 299-311.
[14] J. C. Liberti, "Spatial Processing for High Tier Wireless Systems," Bellcore Pub. IM- 558, Sept. 1996.
[15] S. Verdu, "Adaptive Multi-User Detection," Code Division Multiple Access Communications, S. G. Glisic and P. A. Leppanen, Eds., pp. 97-116, The Netherlands: Kluwer, 1995.
[16] S. Verdu, "Multi-User Detection," Advances in Statistical Signal Processing, vol. 2, JAI Press 1993, pp. 369-409.
[17] A. Duel-Hallen, J. Holtzman, and Z. Zvonar, "Multi-User Detection for CDMA Systems," IEEE Pers. Commun., vol. 2, no. 2, Apr. 1995, pp. 46-58.
[18] S. Moshavi, "Survey of Multi-User Detection for DS-CDMA Systems," Bellcore pub., IM-555, Aug. 1996.
[19] Z. Zvonar and D. Brady, "Linear Multipath-Decorrelating Receivers for CDMA Frequency-Selective Fading Channels," IEEE Trans. Commun., vol. 44, no. 6, June 1996, pp. 650-53.
[20] Z. Zvonar and D. Brady, "Suboptimal Multi-User Detector for Frequency-Selective Rayleigh Fading Synchronous CDMA Channels," IEEE Trans. Commun., vol. 43, no. 2/3/4, Feb./Mar./Apr. 1995, pp. 154-57.
[21] Z. Zvonar, "Multi-User Detection and Diversity Combining for Wireless CDMA Systems," Wireless and Mobile Communications, J. Holtzman and D. Goodman, eds., Boston: Kluwer, 1994, pp. 51-65.
[22] Z. Zvonar, "Combined Multi-User Detection and Diversity Reception for Wireless CDMA Systems," IEEE Trans. Vehic. Tech., vol. 45, no. 1, Feb. 1996, pp. 205-11.
[23] H. C. Huang and S. C. Schwartz, "A Comparative Analysis of Linear Multi-User Detectors for Fading Multipath Channels," Proc. IEEE Globecom '94, San Francisco, CA, Nov. 1994, pp. 11-15.
[24] Y. C. Yoon, R. Kohno, and H. Imai, "A Spread-Spectrum Multi-Access System with Cochannel Interference Cancellation for Multipath Fading Channels," IEEE JSAC, vol. 11, no. 7, Sept. 1993, pp. 1067-75.
[25] P. M. Grant, S. Mowbray, and R. D. Pringle, "Multipath and Cochannel CDMA Interference Cancellation," Proc. IEEE 2nd Int'l. Symp. on Spread Spectrum Techniques and Apps. (ISSSTA '92), Yokohama, Japan, Dec. 1992, pp. 83-86.
[26] M. K. Varanasi and S. Vasudevan, "Multi-User Detectors for Synchronous CDMA Communications over Non-Selective Rician Fading Channels," IEEE Trans. Commun., vol. 42, no. 2/3/4, Feb/Mar/Apr 1994, pp. 711-22.
[27] S. Vasudevan, and M. K. Varanasi, "Optimum Diversity Combiner Based Multi-User Detection for Time-Dispersive Rician Fading CDMA Channels," IEEE JSAC, vol. 12, no. 4, May 1994, pp. 580-92.
[28] M. K. Varanasi and B. Aazhang, "Optimally Near-Far Resistant Multi-User Detection in Differentially Coherent Synchronous Channels," IEEE Trans. Info. Theory, vol. 37, no. 4, July 1991, pp. 1006-18.
[29] M. K. Varanasi, "Noncoherent Detection in Asynchronous Multi-User Channels," IEEE Trans. Info. Theory, vol. 39, no. 1, Jan. 1993, pp. 157-76.
[30] Z. Zvonar and D. Brady, "Multi-User Detection in Single-Path Fading Channels," IEEE Trans. Commun., vol. 42, no. 2/3/4, Feb./Mar./Apr. 1994, pp. 1729-39.
[31] S. Verdu, "Minimum Probability of Error for Asynchronous Gaussian Multiple- Access Channels," IEEE Trans. Info. Theory, vol. IT-32, no. 1, Jan. 1986, pp. 85-96.
[32] S. Verdu, "Minimum Probability of Error for Asynchronous Multiple Access Communication Systems," Proc. IEEE MILCOM \01483, vol. 1, Nov. 1983, pp. 213-19.
[33] Z. Xie, C. K. Rushforth, and R. T. Short, "Multi-User Signal Detection Using Sequential Decoding," IEEE Trans. Commun., vol. 38, no. 5, May 1990, pp. 578-83.
[34] H. V. Poor, "On Parameter Estimation in DS/SSMA Formats," Lecture Notes in Control and Information Sciences - Advances in Communications and Signal Processing, Springer Verlag, 1989, pp. 59-70.
[35] Z. Xie et al., "Joint Signal Detection and Parameter Estimation in Multi-User Communications," IEEE Trans. Commun., vol. 41, no. 7, Aug. 1993, pp. 1208-16.
[36] Y. Steinberg and H. V. Poor, "Sequential Amplitude Estimation in Multi-User Communications," IEEE Trans. Info. Theory., vol. 40, no. 1, Jan. 1994, pp. 11-20.
[37] T. K. Moon et al., "Parameter Estimation in a Multi-User Communication System," IEEE Trans. Commun., vol. 42, no. 8, Aug. 1994, pp. 2553-60.
[38] K. S. Schneider, "Optimum Detection of Code Division Multiplexed Signals," IEEE Trans. Aerospace Elect. Sys., vol. AES-15, no., Jan. 1979, pp. 181-85.
[39] R. Kohno, M. Hatori, and H. Imai, "Cancellation Techniques of Co-Channel Interference in Asynchronous Spread Spectrum Multiple Access Systems," Elect. and Commun. in Japan, vol. 66-A, no. 5, 1983, pp. 20-29.
[40] R. Lupas and S. Verdu, "Near-Far Resistance of Multi-User Detectors in Asynchronous Channels," IEEE Trans. Commun., vol. 38, no. 4, Apr. 1990, pp. 496- 508.
[41] R. Lupas and S. Verdu, "Linear Multi-User Detectors for Synchronous Code-Division Multiple-Access Channels," IEEE Trans. Info. Theory, vol. 35, no. 1, Jan. 1989, pp. 123-36.
[42] M. K. Varanasi, "Group Detection for Synchronous Gaussian Code-Division Multiple-Access Channels," IEEE Trans. Info. Theory, vol. 41, no. 4, July 1995, pp. 1083-96.
[43] M. K. Varanasi, "Parallel Group Detection for Synchronous CDMA Communication over Frequency Selective Rayleigh Fading Channels," IEEE Trans. Info. Theory, vol. 42, no. 1, Jan. 1996, pp. 116-28.
[44] R. Lupas-Golaszewski and S. Verdu, "Asymptotic Efficiency of Linear Multi-User Detectors," Proc. 25th Conf. on Decision and Control, Athens, Greece, Dec. 1986, pp. 2094-2100.
[45] Z. Xie, R. T. Short, and C. K. Rushforth, "A Family of Suboptimum Detectors for Coherent Multi-User Communications," IEEE JSAC, vol. 8, no. 4, May 1990, pp. 683- 90.
[46] S. S. H. Wijayasuriya, G. H. Norton, and J. P. McGeehan, "A Near-Far Resistant Sliding Window Decorrelating Algorithm for Multi-User Detectors in DS-CDMA Systems," Proc. IEEE Globecom '92, Dec. 1992, pp. 1331-38.
[47] A. Kajiwara and M. Nakagawa, "Microcellular CDMA System with a Linear Multi- User Interference Canceller," IEEE JSAC, vol. 12, no. 4, May 1994, pp. 605-11.
[48] F. Zheng and S. K. Barton, "Near Far Resistant Detection of CDMA Signals via Isolation Bit Insertion," IEEE Trans. Commun., vol. 43, no. 2/3/4, Feb./Mar./Apr. 1995, pp. 1313-17.
[49] A. Kajiwara and M. Nakagawa, "Crosscorrelation Cancellation in SS/DS Block Demodulator," IEICE Trans., vol. E 74, no. 9, Sept. 1991, pp. 2596-2601.
[50] D. S. Chen and S. Roy, "An Adaptive Multi-User Receiver for CDMA Systems," IEEE JSAC, vol. 12, no. 5, June 1994, pp. 808-16.
[51] S. Vembu, and A. J. Viterbi, "Two Different Philosophies in CDMA - A Comparison," Proc. IEEE Vehic. Tech. Conf. 1996 (VTC '96), Atlanta, GA, Apr. 28- May 1, 1996, pp. 869-73.
[52] S. S. H. Wijayasuriya, G. H. Norton and J. P. McGeehan, "A Novel Algorithm for Dynamic Updating of Decorrelator Coefficients in Mobile DS-CDMA," Proc. 4th Int'l. Symp. on Pers., Indoor, and Mobile Radio Commun. (PIMRC '93), Yokohama, Japan, Oct. 1993, pp. 292-96.
[53] U. Mitra and H. V. Poor, "Analysis of an Adaptive Decorrelating Detector for Synchronous CDMA Channels," IEEE Trans. Commun., vol. 44, no. 2, Feb. 1996, pp. 257-68.
[54] S. Moshavi, E. G. Kanterakis, and D. L. Schilling, "Multistage Linear Receivers for DS-CDMA Systems," Int'l. J. Wireless Info. Networks, vol. 3, no. 1, Jan. 1996. (patent pending).
[55] S. Moshavi, "Multistage Linear Detectors for DS-CDMA Communications," Ph.D. dissertation, Dept. Elec. Eng., City Univ. New York, NY, Jan. 1996. (patents pending)
[56] H. Y. Wu and A. Duel-Hallen, "Performance Comparison of Multi-User Detectors with Channel Estimation for Flat Rayleigh Fading CDMA Channels," Wireless Pers. Commun., July/Aug. 1996.
[57] S. D. Gray, M. Kocic, and D. Brady, "Multi-User Detection in Mismatched Multiple- Access Channels," IEEE Trans. Commun., vol. 43, no. 12, Dec. 1995, pp. 3080-89.
[58] R. Kohno, "Spatial and Temporal Filtering for Co-Channel Interference in CDMA," Code Division Multiple Access Communications, S. G. Glisic and P. A. Leppanen, eds., The Netherlands: Kluwer, 1995, pp. 117-46.
[59] J. M. Holtzman, "DS/CDMA Successive Interference Cancellation," Proc. IEEE Int'l. Symp. on Spread Spectrum Techniques and Appl. 1994 (ISSSTA \01494), Oulu, Finland, July 1994, pp. 69-78.
[60] A. J. Viterbi, "Very Low Rate Convolutional Codes for Maximum Theoretical Performance of Spread-Spectrum Multiple-Access Channels," IEEE JSAC, vol. 8, no. 4, May 1990, pp. 641-49.
[61] A. D. Wyner, "Recent Results in the Shannon Theory," IEEE Trans. Info. Theory, vol. IT-20, Jan. 1974, pp. 2-10.
[62] T. M. Cover, "Some Advances in Broadcast Channels," Advances in Communication Systems, A. J. Viterbi, ed., New York: Academic, 1975, pp. 229-60.
[63] A. B. Carleial, "A Case Where Interference Does Not Reduce Capacity," IEEE Trans. Info. Theory, vol. IT-21, Sept. 1975, pp. 569-70.
[64] I. Seskar, "Practical Implementation of Successive Interference Cancellation," presentation, WINLAB Semi-Annual Res. Rev., Rutgers Univ., NJ, Apr. 26, 1996.
[65] P. Patel and J. Holtzman, "Analysis of a Simple Successive Interference Cancellation Scheme in a DS/CDMA System," IEEE JSAC, vol. 12, no. 5, June 1994, pp. 796-807.
[66] M. Ewerbring, B. Gudmundson, G. Larsson, and P. Teder, "CDMA with Interference Cancellation: A Technique for High Capacity Wireless Systems," Proc. ICC '93, Geneva, Switzerland, 1993, pp. 1901-6.
[67] M. K. Varanasi and B. Aazhang, "Multistage Detection in Asynchronous Code- Division Multiple-Access Communications," IEEE Trans. Commun., vol. 38, no. 4, Apr. 1990, pp. 509-19.
[68] R. Kohno et al., "Combination of an Adaptive Array Antenna and a Canceller of Interference for Direct-Sequence Spread-Spectrum Multiple-Access System," IEEE JSAC, vol. 8, no. 4, May 1990, pp. 675-82.
[69] R. Kohno et al., "An Adaptive Canceller of Cochannel Interference for Spread- Spectrum Multiple-Access Communication Networks in a Power Line," IEEE JSAC, vol. 8, no. 4, May 1990, pp. 691-99.
[70] M. K. Varanasi and B. Aazhang, "Near-Optimum Detection in Synchronous Code- Division Multiple-Access Systems," IEEE Trans. Commun., vol. 39, no. 5, May 1991, pp. 725-36.
[71] U. Fawer and B. Aazhang, "A Multi-User Receiver for Code Division Multiple Access Communications over Multipath Channels," IEEE Trans. Commun., vol. 43, no. 2/3/4, Feb./Mar./Apr. 1995, pp. 1556-65.
[72] P. Patel and J. Holtzman, "Performance Comparison of a DS/CDMA System Using a Successive Interference Cancellation (IC) Scheme and a Parallel IC Scheme under Fading," Proc. ICC '94, New Orleans, LA, May 1994, pp. 510-14.
[73] B. Zhu, N. Ansari, and Z. Siveski, "Convergence and Stability Analysis of a Synchronous Adaptive CDMA Receiver," IEEE Trans. Commun., vol. 43, no. 12, Dec. 1995, pp. 3073-79.
[74] T. R. Giallorenzi and S. G. Wilson, "Decision Feedback Multi-User Receivers for Asynchronous CDMA Systems," Proc. IEEE Globecom '93, Houston, TX, Dec. 1993, pp. 1677-82.
[75] B. S. Abrams, A. E. Zeger, and T. E. Jones, "Efficiently Structured CDMA Receiver with Near-Far Immunity," IEEE Trans. Vehic. Tech., vol. 44, no. 1, Feb. 1995, pp. 1- 13.
[76] D. Divsalar and M. Simon, "Improved CDMA Performance Using Parallel Interference Cancellation," JPL pub. 95-21, Oct. 1995 (patent pending).
[77] A. Duel-Hallen, "Decorrelating Decision-Feedback Multi-User Detector for Synchronous Code-Division Multiple Access Channel," IEEE Trans. Commun., vol. 41, no. 2, Feb. 1993, pp. 285-90.
[78] A. Duel-Hallen, "A Family of Multi-User Decision-Feedback Detectors for Asynchronous Code-Division Multiple Access Channels," IEEE Trans. Commun., vol. 43, no. 2/3/4, Feb./Mar./Apr. 1995, pp. 421-34.
[79] A. Klein, G. K. Kaleh, and P. W. Baier, "Zero Forcing and Minimum Mean-Square- Error Equalization for Multi-User Detection in Code-Division Multiple-Access Channels," IEEE Trans. Vehic. Tech., vol. 45, no. 2, May 1996, pp. 276-87.
[80] G. K. Kaleh, "Channel Equalization for Block Transmission Systems," IEEE JSAC, vol. 13, no. 1, Jan. 1995, pp. 110-21.
[81] P. Jung and J. Blanz, "Joint Detection with Coherent Receiver Antenna Diversity in CDMA Mobile Radio Systems," IEEE Trans. Vehic. Tech., vol. 44, no. 1, Feb. 1995, pp. 76-88.
[82] L. Wei and C. Schlegel, "Synchronous DS-SSMA System with Improved Decorrelating Decision Feedback Multi-User Detection," IEEE Trans. Vehic. Tech., vol. 43, no. 3, Aug. 1994, pp. 767-72.
[83] G. W. Stewart, Introduction to Matrix Computations, New York: Academic, 1973.
[84] M. Honig, U. Madhow, and S. Verdu, "Blind Adaptive Multiuser Detection," IEEE Trans. Info. Theory, vol. 41, no. 4, July 1995, pp. 944-60.
[85] U. Madhow and M. L. Honig, "MMSE Interference Suppression for Direct Sequence Spread-Spectrum CDMA," IEEE Trans. Commun. vol. 42, no. 12, Dec. 1994, pp. 3178- 88.
[86] R. M. Buehrer and B. D. Woerner, "Analysis of Adaptive Multistage Interference Cancellation for CDMA Using an Improved Gaussian Approximation," Proc. IEEE MILCOM '95, San Diego, CA, Nov. 1995, pp. 1195-99.
[87] A. J. Viterbi, CDMA: Principles of Spread Spectrum Communciation, Reading, MA: Addison-Wesley, 1995.
[88] H. Taub and D. L. Schilling, Principles of Communication Systems, 2nd ed., New York: McGraw-Hill, 1986.

Endnotes
1 These properties include: frequency reuse of one, resistance to multipath fading, multipath diversity combining (RAKE reception), soft capacity, soft handoff, natural usageof the voice activity cycle (VAC), ability to overlay on existing systems, ability to use forward error correction coding without overhead penalty, natural exploitation of sectored antennas and adaptive beamforming, ease of frequency management, low probability of detection and intercept (LPD and LPI), and jam resistance. See [1-4] for details. 2 Note that we focus here only on the effect of MAI, and not on the effect of narrowband (NB) interference. A good survey of work dealing with CDMA in the presence of NB interference can be found in[6]. See also [7] where multiuser detection is proposed for eliminating NB inteference.
3 The detector would consist of a band of K matched filters, where each filter is "matched" to a different code waveform. Matched filter detection and correlation detection are equivalent methods of implementing optimal detection where the only interference is from additive white Gaussian noise [8], that is, in a single-user channel.
4 The operation of the conventional detector can also be explained in the frequency domain. All signals arrive at the receiver spread in frequency by the processing gain factor, PG.
This has the effect of reducing the power of each signal over any given narrow band of frequencies. After multiplying the received signal by the code of user k, the signal of user k is de-spread back to the original information bandwidth; the other signals, however, remain spread in frequency (i.e., gi(t)gk(t) is equivalent to some new spreading code waveform).
The integrator then acts as a low pass filter with cut-off at frequencies +-fb. Within this frequency range the de-spread signal is at full power, while the power of the interfering signals has been reduced by an amount proportional to the processing gain [88].
5 A popular approximation of the SNR at the output of the conventional detector is obtained by modeling the MAI as a Gaussian random variable [9]. Thus, for the conventional detector, the MAI can be lumped with the thermal noise for analysis, that is, it raises the noise floor. The resulting equation yields fairly accurate probability of error results for most reasonable system parameters (i.e., for K, PG, and probability of error not too small [10]). This equation is often used in analysis of DS-CDMA systems, e.g., [3, 4].
6 Another important area of research is the design of improved single-user detectors, where the code of only one (desired) user is known. Here detection is optimized in some way for the multi-user channel, where the general structure of the interference is known to be that of other direct-sequence users. As a substitute for the specific knowledge of the interfereing users' code waveforms, these detectors generally rely heavily on adaptive signal processing. They are also sometimes referred to as adaptive multi-user detectors. An overview of the work in this area can be found in [15].
7 Issues dealt with include multipath, fading, noncoherent detection, general modulation schemes, power variation and power control, coding, acquisition and tracking (code synchronization), channel estimation, multiple and adaptive antennas, complexity and cost, efficient suboptimal implementations, application to IS-95, and sensitivity and robustness (e.g., the effects of amplitude and phase estimation errors, delay tracking errors, and quantization errors).
8 Multipath is an important issue in multi-user detection. The bandwidth of a DS-CDMA signal is very wide (or equivalently, the chip duration is very small); hence more than one signal path can generally be resolved at the receiver [8]. This yields what is known as "multipath diversity." The conventional detector in this case takes the form of a bank of RAKE detectors [8], which allows it to take advantage of the availble diversity. The RAKE detector of each user has M "fingers," where each finger detects a different signal path through a matched filter. The RAKE receiver then combines the M outputs in some manner (e.g., maximal ratio or equal gain). The name "RAKE" comes from a similarity of this detector to an ordinary garden rake [8]. There has been much literature on multi-user detection in a multipath environment, e.g., [19-23] (for the decorrelating detector), [24, 25] (for the PIC detector), and [26, 27] (for the MLS detector and the decorrelating detector in a 2 path Rician fading channel). See [16-18] for additional references and discussion.
One approach to multi-user detection in the presence of multipath is to maximal ratio combine the M corresponding signal paths for each user and then perform multi-user detection on the resulting K signals. A more common approach is to treat each path as a separate user with respect to the multi-user detection algorithm. Thus, first multi-user detection is performed on MK signals and then RAKE combining takes place on the corresponding M outputs for each user.
9 We are assuming BPSK modulation and thus coherent detection. However, in the IS-95 standard,a pilot signal is not availble on the uplink (it is available, however, in IS-665). Thus, a coherent reference is not avaialble for tracking the phase, and noncoherent detection is necessary [5]. Two basic works that consider noncoherent multi-user detection (for the decorrelating detector) are [28] for the synchronous channel and [29] for the asynchronous channel; other articles include [19, 21-23, 30] (for the decorrelating detector), and [65] (for the SIC detector). See [16-18] for additional references and discussion.
10 The ability to detect signals from multiple cells is already assumed in IS-95 for the implementation of soft-handoff [1]. Here base stations of neighboring cells may simultaneously transmit to, and receive from the same mobile user. Note that the value of 0.55 given for the spillover ratio in [1] actually already includes soft handoff users [87].
11 By definition, the maximum-likelihood sequence detector chooses d to maximize P(r(t)|d); but if all d vectors are equally probable, this is equivalent to maximizing P(d|r(t)) [8]. Thus, the MLS detector yields the most likely tranmsitted d vector as long as all possible d vectors are equally likely [8]. It can be shown that maximizing the probabilty P(r(t)|d) is equivalent to maximizing the log likelihood function L = 2dTAy - dTARAd where d \021{-1, 1}NK [41]. From this follows the well known result that y (the matched filter output over the whole message) is a sufficient statistic for optimum detection of the transmitted data [31].
12 MLS detection guarantees the most likely sequence (i.e. a global optimum). An alternate optimality crieteria is "minimum probability of error," which results from the maximation of the marginal a posteriori distributions, P(dk,i|r(t)), k = 1\012K, i = 1\012N (locally optimum) [31]. This is more difficult to implement. Fortunately, the bit error rate of the MLS detector turns out to be indistinguishable from the minimum probability of error for SNR regions of interest, that is, where the thermal noise is not dominant [16]; in the limit as the noise goes to zero, the MLS error rate is equivalent to that of the minimum error rate. A 2 user synchronous channel example which illustrates the difference between the MLS ciriteria and the minimum probability of error criteria is given in [16], and repeated here. Assume that the joint posterior probablities P({d1, d2}|r(t)}), are given as P({1, 1}|r(t)) = 0.26, P({-1, 1}|r(t)) = 0.26, P({1, -1}r(t)) = 0.27, and P({-1, -1}|r(t)) = 0.21. The most likely sequence is {1, -1}; however, the most likely value of the second user's bit is 1.
13 Besides yielding the most likely transmitted sequence, this detector is also optimal in terms of the performance measures known as the asymptotic efficiency and the near-far resistance [31, 40, 41]. These metrics are covered in the surveys [16, 18].
14 In [31] a Viterbi implementation is proposed with path metrics that are a function of the user crosscorrelations, and that are similar to that of a single-user periodic time varying ISI channel with memory K - 1; the resulting Viterbi algorithm has 2K - 1 states and a complexity per binary decision on the order of 2K. Unfortunately, no algorithm is known to solve the maximization of the likelihood function L (see Endnote 11) in polynomial time in K (i.e., it is NP-hard) [31]. An illustrative example of MLS detection for an asynchronous 2 user DS-CDMA system is spelled out in [16]. Note that [58] cites two article by Kohno from 1982 and 1983 that also proposes a Viterbi altorithm implementation with a complexity per binary decision on the order of 2K; both of these articles appear only in Japanese. Viterbi implemenations of higher complexity were also proposed in [32, 38].
15 A natural simplification of MLS detection is to replace the Viterbi algorithm with a sequential decoder, as is done for convolutional decoding [33]. Sequential decoding searches for the most likely path based on local metric values; in contrast, the Viterbi algorithm tracks and evaluates all possible paths. Although simpler, sequential decoding for DS-CDMA is still fairly difficult to implement.
16 As is discussed below, the decorrelating detector pays a noise enhancement penalty for eliminating the MAI. Thus, if the MAI is relatively low and the background noise power is relatively high, ignoring the MAI, as does the conventional detctor, may yield better performance [16, 40].
17 In brief, the near-far resistance [31, 40, 41] is a performance measure that indicates performance under worst-case conditions of interfering powers; it provides some quanitfication of the resistance of a detector's error performance to the power of the interfering users. A detector that is near-far resistant (i.e., the metric is not equal to zero), can achieve any given performance level in the multi-user enviroment, no matter how powerful the multi-user interference, provided that the desired user is supplied enough power. Both the maximum likelihood sequence detector and the decorrelating detector are guaranteed to be near-far resistant for linearly independent users (linearly dependent users, however, are not near-far resistant). Both detectors also yield the largest value of this metric for a given set of code waveforms. In contrast, the conventional detector is not near- far resistant, unless all waveforms are orthogonal. For more details on near-far resistance, see [16].
18 Two recent papers treat the decorrelating detector as a special case of what is termed "parallel group detectors" [42, 43]. These detectors bridge the gap in performance and complexity between the decorrelating detector, (which corresponds to the case of one user per group), and the MLS detector (which corresponds to the case of all users in one group).
19 As mentioned above, the decorrelating detector is the optimal sequence detector (linear or nonlinear) when the energies of the users are unknown. If they are known, however, there are linear detectors that provide better probability of error performance. This involves trading off some MAI reduction for less noise enhancement. An example of this is the MMSE detector discussed in the next subsection.
20 Degradation from the ideal decorrelating detector performance results because of the "edge effects" [45, 46]. Some proposals include a form of "edge correction" to mitigate this problem [45, 46]; other proposals involve physically separating the data sub-blocks, to entirely avoid the edge problem [47, 48, 79, 81]. The latter scheme, however, requires some time synchronization among users.
21 It is shown in [40] that for the case of short codes (codes that repeat each bit), and where the message length, N, approaches infinity, the decorrelating detector apporaches a K-input K-output linear time-invariant noncausal infinte memory-length filter. It is further shown in [40] that under mild conditions a stable unique realization of this filter exists. Since the filter has infinite memory-length and is non-causal, a practical implementation would require truncation to a finite length filter, and the insertion of sufficient delay. Since stability requires that the impulse response, h(n), go to zero as n \106 \003, the more remote symbols will count less heavilty. Therefore, the approximation to the exact decorrelating filter will be good for a truncation window (filter memory) of sufficient length [40].
22 See also [50] where an adaptive decorrelating detector is proposed that avoids the need for computations with the correlation matrix.
23 On the other hand, as the noise gets very large, or the MAI amplitudes get very small, LMMSE \011 (2/N0)A2. In this case, performance of the MMSE detector approaches that of the conventional detector [15, 45]. See Endnote 16.
24 For example, in [45] MMSE detection takes place on blocks of subsequences; in [85] "one-shot" MMSE detection is proposed, where detection is based only on observation over one transmission interval. MMSE detection has also received much attention lately because of its ability to be implemented adaptively, where the codes of the interfering users are not known, that is, improved single-user detection (e.g. [84, 85]). For more on this subject, see [15].
25 In this case, the PE detector structure can be thought of as being a K-input K-output linear infinite memory-length filter realization of the decorrelating detector.
26 Note that soft-decision subtractive interference cancellation detectors can usually also mathematically be classified as linear detectors.
27 The Wireless Information Network Laboratory (WINLAB) at Rutgers University, New Jersey, is currently implementing a protoype of the SIC detector which utilizes soft decisions [64]. A soft-decision SIC detector was initially investigated in [65].
28 A distinctly different SIC scheme that does cancellation in the Walsh-Hadamard spectral domain is discussed in [66]. Additional references on this approach can be found in [18].
29 Because of the cancellation order, this detector is most potent when there is significant power variation between each users' received signal. A specific geometric power distribution is derived in [60] that enables each user to see the same level of signal power to interference (+ noise) ratio, and produce the same probability of error. It is also shown in [60] that by using the SIC detector with this power profile, along with very low rate forward error correction (FEC) codes, it is possible for the composite bit rate of all users to approach the Shannon limit.
30 The multistage PIC algorithm is used in [71] as part of a joint parameter estimation and data detection scheme.
31 This detector can be considered to be a special case of the modified parallel group detectors introduced in [42] (corresponding to the case of one user per group).
32 An adaptive version of this detector that does not require explicit estimation of the received amplitudes is proposed in [73] for synchronous systems.
33 In [75] a PIC detector is proposed that is based entirely on feedback cancellation: the outputs of the correlators are continuously fed back during the correlation for cancellation.
34 Note that the cancelation takes place on the post correlation MAI terms. Although both the SIC and PIC detectors were described earlier with "pre-correlation" cancelation, they too can be equivalently implemented through "post-correlation" cancellation [24, 59, 65].
35 The ZF-DF detector can be considered to be a special case of the "sequential group detectors" introduced in [42] (corresponding to the case of one user per group). A general analysis is given there without the assumption that all past decisions are correct.
36 An MMSE-DF detector is proposed in [78, 79, 81] which is analogous to the MMSE- DF equalizer [8]. Here the feed-forward and feedback filters are chosen to minimize the mean square error under the assumption that all past decisions are correct. This detector is similar to the ZF-DF detector except that the feed-forward filter is obtained by Cholesky factoring the matrix [ARA + (N0/2)I]. Like in equalization, the MMSE-DF detector outperforms the ZF-DF detector.
37 An improved ZF-DF detector is proposed for synchronous channels in [82] which feeds back more than one set of likely decision vectors along with their corresponding metrics. The approach of this detector is similar to that of sequential decoding.
38 The "Schur algorithm" with parallel processing is proposed for Cholesky factorization in [80]; it results in a complexity that is linear with the order of the matrix. Looking for Related References?

Biography
Shimon Moshavi received the B.A. degree in physics from Yeshiva University in 1988, the M.S. degree in electrical engineering from City College of New York in 1994, and the Ph.D. degree in electrical engineering from City University of New York in January 1996. Since January 1996 he has been a research scientist at Bell Communications Research (Bellcore) in Red Bank, New Jersey, in the Wireless Systems Research Department (Tel: 908-758-5091, moshavi@bellcore.com). His current interests include communication theory, CDMA, multi-user detection, and wireless networks.