5.4 Linear Space-Time Multiuser Detection

As seen in Section 5.3, the optimal space-time multiuser detection algorithm typically has a prohibitive computational complexity. In this section we discuss linear space-time multiuser detection techniques that mitigate this complexity significantly. To consider such detectors we will assume for now that the receiver has knowledge of the spreading waveforms and the channel parameters of all users. The method discussed here is based on iterative interference cancellation and has a low computational complexity. For comparison, we also discuss single- user -based linear space-time processing methods .

5.4.1 Linear Multiuser Detection via Iterative Interference Cancellation

From (5.56) we can write the expression for the sufficient statistic vector y in matrix form as

Equation 5.65

where by (5.57), v ~ N _c ( , s ² H ). Recall that in linear multiuser detection, a linear transformation is applied to the sufficient statistic vector y , followed by local decisions for each user. That is, the multiuser data bits are demodulated according to

Equation 5.66

where W is an MK x MK complex matrix. As discussed in Chapter 2, two popular linear multiuser detectors are the linear decorrelating (i.e., zero-forcing) detector, which chooses the weight matrix W to eliminate the interference completely (at the expense of enhancing the noise), and the linear MMSE detector, which chooses the weight matrix W to minimize the mean-square error between the transmitted symbols and the outputs of the linear transformation (i.e., E { A b “ W y ² }). The corresponding weight matrices for these two linear multiuser detectors are given, respectively, by

Equation 5.67

Equation 5.68

Since the frame length M is typically large, direct inversion of the MK x MK matrices above is too costly for practical purposes. Moreover, the complexity cannot generally be mitigated over multiple frames , since the matrices H and A may vary from frame to frame due to mobility, aperiodic spreading codes, and so on. This complexity can be mitigated, however, by using iterative methods of equation solving, which we now discuss. We first consider Gauss “Seidel iteration to obtain the linear multiuser detector output. This method effectively performs serial interference cancellation on the sufficient statistic vector y and recursively refines the estimates of the multiuser signals . Denote such an estimate at the m th iteration as . Also denote and . The algorithm is listed in Table 5.1.

The convergence properties of this serial interference cancellation algorithm are characterized by the following result.

Proposition 5.5: (1) If and if H is positive definite, then x ^m W _{d y} , as m ; (2) if , then x ^m W _{m y} , as m .

Proof: Consider the following system of linear equations:

Equation 5.69

The Gauss “Seidel procedure [598] for iteratively solving x from (5.69) is given by

Equation 5.70

Substituting in (5.70) the notations for k = 1, . . ., K, i = 0, . . ., M “ 1, and the elements of the matrix H given in (5.59), it then follows that the serial interference cancellation procedure in Table 5.1 is the same as the Gauss “Seidel iteration (5.70) if we choose . Then by the Ostrowski “Reich theorem [598], a sufficient condition for the Gauss “Seidel iteration (5.70) to converge to the solution of (5.69) (i.e., the output of the linear decorrelating detector, is that H be positive definite.

Table 5.1. Iterative Implementation of Linear Space-Time Multiuser Detection Using Serial Interference Cancellation

Similarly, consider the system of linear equations

Equation 5.71

The corresponding Gauss “Seidel iteration is given by

Equation 5.72

which is the same as the serial interference cancellation procedure in Table 5.1 with . It is seen from (5.58) that the matrix H is positive semidefinite, as dt = x ^H H x 0, where . Therefore, ( H + s ² A ^“2 ) is positive definite, and by the Ostrowski “Reich theorem, iteration (5.72) converges to the solution to (5.71) [i.e., the output of the linear MMSE detector, x ^m ( H + s ² A ^“2 ) ^“1 ].

The computational complexity of the iterative serial interference cancellation algorithm above per user per bit is , where is the total number of iterations. The complexity per user per bit of direct inversion of the matrices in (5.67) or (5.68) is ( K ³ M ³ / KM ) = ( K ² M ² ). By exploiting the Hermitian (2 D + 1)-block Toeplitz structure of the matrix H , this complexity can be reduced to ( K ² M D ) [324]. Since in practice the number of iterations is a small number (e.g., ), the iterative method for linear multiuser detection above achieves significant complexity reduction over the direct matrix inversion method.

A natural alternative to the serial interference cancellation method is the following parallel interference cancellation method ,

Equation 5.73

Unlike the serial method, in which the new estimate is used to update the subsequent estimates as soon as it is available, in the parallel method, at the m th iteration, is updated using the estimates only from the previous iteration. Parallel interference cancellation corresponds to Jacobi's method [598] for solving the linear system (5.69) or (5.71):

Equation 5.74

with g [ i ']= H [ i ', i '] or g [ i '] = H [ i ', i ']+ s ² / A [ i ', i '] ² . However, the convergence of Jacobi's method (5.74) and hence that of the parallel interference cancellation method (5.73) is not guaranteed in general. To see this, for example, let D be the diagonal matrix containing the diagonal elements of H and let H = D + B be the splitting of H into its diagonal and off-diagonal elements. Suppose that H = D + B is positive definite; then a necessary and sufficient condition for the convergence of Jacobi's iteration is that D - B be positive definite [598]. In general, this condition may not be satisfied, and hence the parallel interference cancellation method (5.74) is not guaranteed to produce the linear multiuser detector output. An analysis of parallel interference cancellation is found in [53]. Other iterative methods for solving (5.71), such as conjugate-gradient techniques, are described in [92].

5.4.2 Single-User Linear Space-Time Detection

In what follows we consider several single-user-based linear space-time processing methods. These methods have been advocated in the recent literature, as they lead to several space-time adaptive receiver structures [34, 273, 348, 574]. We derive the exact forms of these single-user detectors in terms of multiuser channel parameters. We then compare the performance of these single-user space-time receivers with that of the multiuser space-time receivers discussed in Section 5.4.1.

Denote r _p ( t ) as the received signal at the p th antenna element [i.e., the p th element of the received vector signal r ( t ) in (5.45)]:

Equation 5.75

Suppose that the user of interest is the k th user. In the single-user approach, in order to demodulate the i th symbol of the k th user, that user's matched-filter output corresponding to each path at each antenna element is first computed:

Equation 5.76

where { n _l,k,p [ i ]} are zero-mean complex Gaussian random sequences with covariance

Equation 5.77

Note that z _l,k,p [ i ] is the p th element of the vector z _l,k [ i ] defined in (5.49). Denote ^[3]

^[3] Notation: R [ i : i ₁ , j : j ₁ ] denotes the submatrix of R consisting of rows i to i ₁ and columns j to j ₁ .

Then we can write (5.76) in the following matrix form:

Equation 5.78

where by (5.77) the complex Gaussian vector sequence { ± _kp [ i ]} has the following covariance matrix:

Equation 5.79

From (5.78) we then have

Equation 5.80

where, by (5.79), n _k [ i ] ~ N _c ( ).

In the single-user-based linear space-time processing methods, the k th user's i th bit is demodulated according to the following rule:

Equation 5.81

where w _k . We next consider three choices of the weight vector w _k according to different criteria.

Space-Time Matched Filter

The simplest linear combining strategy is the space-time matched filter, which chooses the weight vector as

Equation 5.82

Note that the output of this space-time matched filter is , a quantity that first appeared in (5.49).

Linear Minimum Mean-Square Error Combiner

In linear MMSE combining, the weight vector is chosen to minimize the mean-square error between the k th user's transmitted signal and the output of the linear combiner:

Equation 5.83

where using (5.80), we have

Equation 5.84

Equation 5.85

with e _k a K -vector of all zeros except for the k th entry, which is 1.

Maximum Signal-to-Interference Ratio Combiner

In MSIR combining, the weight vector w _k is chosen to maximize the signal-to-interference ratio,

Equation 5.86

The solution to (5.86) is then given by the generalized eigenvector associated with the largest generalized eigenvalue of the matrix pencil ( ):

Equation 5.87

From (5.87) it is immediate that the largest generalized eigenvalue is , and the corresponding generalized eigenvector is , with some scalar constant a . Since scaling the combining weight by a positive constant does not affect the decision (5.81), the MSIR weight vector is the same as the MMSE weight vector (5.83).

The space-time matched filter is data independent ( assuming that the array responses and the multipath gains are known) and the single-user MMSE (MSIR) method is data dependent. Hence, in general, the latter outperforms the former. In essence the single-user MMSE method exploits the spatial signatures introduced into the different user signals by the array responses and the multipath gains to suppress the interference. For example, such a spatial signature for the k th user is given by (5.82). The k th user's MMSE receiver then correlates the signal vector z _k [ i ] along a direction in the space spanned by such spatial signatures of all users, such that the SIR of the k th user is maximized. Moreover, this approach admits several interesting blind adaptive implementations , even for systems that employ aperiodic spreading sequences [273, 574].

However, the interference suppression capability of such a single-user approach is limited, since it does not exploit the inherent signal structure induced by the multiuser spreading waveforms. This method can still suffer from the near “far problem, as in matched-filter detection, because the degree of freedom provided by the spatial signature is limited. Furthermore, since users' signals are originally designed to separate from each other by their spreading waveforms, the multiuser space-time approach, which exploits the structure of users' signals in terms of both spreading waveforms and spatial signatures, can significantly outperform the single-user approach. This is illustrated later by simulation examples.

5.4.3 Combined Single-User/Multiuser Linear Detection

The linear space-time multiuser detection methods discussed in Section 5.4.1 are based on the assumption that the receiver has knowledge of the spreading signatures and channel parameters (multipath delays and gains, array responses) of all users. In a practical cellular system, however, there might be a few external interfering signals (e.g., signals from other cells ), whose spreading waveforms and channel parameters are not known to the receiver. In this section we consider space-time processing in such a scenario by combining the single-user and multiuser approaches. The basic strategy is first to suppress the known interferers' signals through the iterative interference cancellation technique discussed in Section 5.4.1, and then to apply the single-user MMSE method discussed in Section 5.4.2 to the residual signal to further suppress the unknown interfering signals. Thus these procedures are group space-time multiuser detectors.

Consider the received signal model (5.45). Assume that the users of interest are users k = 1, . . . , < K and that the spreading waveforms as well as the channel parameters of these users are known to the receiver. Users k = + 1, . . . , K are unknown external interferers whose data are not to be demodulated. For each user of interest, the receiver first computes the LP -vectors of matched-filter outputs, z _k [ i ], 1 k , i = 0, . . . , M “ 1, [cf. (5.80)]. The space-time matched-filter outputs y _k [ i ] [cf. (5.49)] are then computed by correlating z _k [ i ] with the space-time matched filter given in (5.82).

Next, the iterative serial interference cancellation algorithm discussed in Section 4.1 (here the total number of users K is replaced by the total number of users of interest ) is applied to the data { y _k [ i ] : 1 k , i = 0, . . . , M “ 1} to suppress interference from known users. This is equivalent to implementing a linear multiuser detector assuming only (instead of K ) users present. As a result, only the known interferers' signals are suppressed at the detector output. Denote by the converged estimate of the k th user's signal (i.e., , 1 k , i = 0, . . . , M “ 1). Note that contains the desired user's signal, the unknown interferers' signals, and the ambient noise. Using these estimates and based on the signal model (5.80), we next cancel the known interferers' signals from the vector z _k [ i ] to obtain

Equation 5.88

Finally, a single-user combining weight w _k is applied to the vector and the decision rule is given by

Equation 5.89

If the weight vector w _k is chosen to be a scaled version of the matched filter (5.82) [i.e., w _k = (1/ g _k ) h _k ], the output of this matched filter is simply (i.e., (1/ g _k ) ). To see this, first using (5.80) and (5.82), we have the following identity:

Equation 5.90

Now apply the matched filter (5.82) to both sides of (5.88); we have

Equation 5.91

Equation 5.92

where (5.91) follows from (5.90) and , and (5.92) follows from the fact that are the converged outputs of the iterative serial interference cancellation algorithm.

On the other hand, if the combining weight is chosen according to the MMSE criterion, it is given by

Equation 5.93

It is clear from the discussion above that in this combined approach, interference due to the known users is suppressed by serial multiuser interference cancellation, whereas the residual interference due to the unknown users is suppressed by the single-user MMSE combiner.

Simulation Examples

In what follows we use computer simulations to assess the performance of the various multiuser and single-user space-time processing methods discussed in this section. We first outline the simulated system in Examples 1, 2, and 3. It consists of eight users ( K = 8) with a spreading gain 16 ( N = 16). Each user's propagation channel consists of three paths ( L = 3). The receiver employs a linear antenna array with three elements ( P = 3) and half-wavelength spacing. Let the direction of arrival (DOA) of the k th user's signal along the l th path with respect to the antenna array be f _l,k ; then, assuming a uniform linear array with half-wavelength space [i.e., (1.17) with d = l /2], the array response is given by

Equation 5.94

The spreading sequences, multipath delays, complex gains, and DOAs of all user signals in the simulated system are tabulated in Table 5.2. These parameters are randomly generated and kept fixed for all the simulations. All users have equal transmitted power (i.e., A ₁ = · · · = A _K ). However, the received signal powers are unequal, due to the unequal strength of the multipath gain for each user. The total strength of each user's multipath channel, measured by the norm of the channel gain vector g _k , is also listed in Table 5.2. Note that this system has a near “far situation (i.e., user 3 is the weakest user and user 6 is the strongest).

Example 1: Performance Comparison of Multiuser versus Single-User Space-Time Processing We first compare the BER performance of the multiuser linear space-time detector and that of the single-user linear space-time detector. Three receivers are considered : the single-user space-time matched filter given by (5.82), the single-user space-time MMSE receiver given by (5.83), and the multiuser MMSE receiver implemented by the iterative interference cancellation algorithm (5.70) (five iterations are used). Figure 5.5 shows the performance of the weak users (users 1, 3, 4, and 8). It is seen that, in general, the single-user MMSE receiver outperforms the matched-filter receiver. (Interestingly though, for user 1 the matched filter actually slightly outperforms the single-user MMSE receiver. This is not surprising, since due to the interference, the detector output distribution is not Gaussian, and minimizing the mean-square error does not necessarily lead to minimum bit-error probability.) It is also evident that the multiuser approach offers substantial performance improvement over single-user methods.

Figure 5.5. Comparisons of the BER performance of three receivers: single-user space-time matched-filter, single-user space-time MMSE receiver, and multiuser space-time MMSE receiver. (a) User 1; (b) user 3; (c) user 4; (d) user 8.

Table 5.2. Simulated Multipath CDMA System for Examples 1, 2, 3, 6, and 8

	Signature { c k ( j )}	Delay ( T c )			DOA ( °)				Multipath Gain
k		t k 1	t k 2	t k 3	a k 1	a k 2	a k 3	g k 1	g k 2	g k 3	g k
1	0011011100000011		2	3	34	“16	“14	0.193 “ j 0.714	0.131 “ j 0.189	0.353 “ j 0.079	0.85
2	1101011100011101	1	4	5	2	42	“9	0.508 “ j 0.113	“0.103 + j 0.807	0.143 + j 0.013	0.98
3	1110110000110001	2	3	6	“33	“13	35	0.125 “ j 0.064	0.187 “ j 0.249	“0.196 + j 0.092	0.41
4	0100001101111100	2	4	5	58	13	61	0.354 “ j 0.121	0.141 “ j 0.455	“0.618 + j 0.004	0.87
5	0011101101100000	4	6	7	“72	69	1	0.597 + j 0.395	0.470 + j 0.115	“0.069 + j 0.255	0.90
6	1111111001100001	5	7	8	3	18	“55	0.084 + j 1.205	0.106 “ j 0.181	0.167 + j 0.007	1.24
7	1110010000010010	6	8	9	“79	“53	70	“0.428 + j 0.188	“0.711 + j 0.064	0.562 “ j 0.111	1.03
8	1101101001011000	8	9	12	53	25	“20	“0.575 + j 0.018	“0.320 + j 0.081	“0.139 + j 0.199	0.70

Example 2: Convergence of the Iterative Interference Cancellation Method This example serves to illustrate the convergence behavior of the iterative interference cancellation method (5.70). The BER performance corresponding to the first four iterations for users 4 and 8 is shown in Fig. 5.6. It is seen that the algorithm converges within four or five iterations. It is also seen that the most significant performance improvement occurs at the second iteration.

Figure 5.6. BER performance of the iterative interference cancellation method (first four iterations). (a) User 4; (b) user 8.

Example 3: Performance of the Combined Multiuser/Single-User Space-Time Processing In this example it is assumed that users 7 and 8 are external interferers and that their signature waveforms and channel parameters are not known to the receiver. Therefore, the combined multiuser/single-user space-time processing method discussed in Section 5.4.3 is employed at the receiver. Figure 5.7 illustrates the BER performance of users 3 and 4. Four methods are considered here: the single-user matched filter (5.82), single-user MMSE receiver (5.83), and partial interference cancellation followed by a matched-filter or single-user MMSE receiver. It is seen that the combined multiuser/single-user space-time processing achieves the best performance among the four methods.

Figure 5.7. BER performance of four receivers in the presence of unknown interferers. (a) User 3; (b) user 4.

Example 4: Performance versus Number of Antennas/Number of Users Next, we illustrate how performance varies with the number of users and receive antennas for both the multiuser space-time detector and single-user space-time detector. The simulated system has K = 16 users and the processing gain N = 16. The number of paths for each user is L = 3. The performance of user 5 in this system using the single-user MMSE receiver and that using the multiuser MMSE receiver are plotted in Fig. 5.8, with the number of antennas P = 2, 4, and 6. It is seen that whereas in the single-user approach, the performance improvement due to the increasing number of receive antennas is only marginal, such performance improvement in the multiuser approach is of orders of magnitude. Next, we fix the number of antennas as P = 4 and vary the number of users in the system. The processing gain is still N = 16 and the number of paths for each user is L = 3. The performance of the single-user MMSE receiver and the multiuser receiver for user 2 is plotted in Fig. 5.9, with the number of users N = 10, 20, and 30. Again we see that in all these cases the multiuser method significantly outperforms the single-user method.

Figure 5.8. Single-user and multiuser receiver performance under a different number of antennas K = 16, N = 16. (a) Single-user MMSE receiver, user 5; (b) multiuser MMSE receiver, user 5.

Figure 5.9. Single-user and multiuser receiver performance under different number of users. N = 16, P = 4. (a) Single-user MMSE receiver, user 2; (b) multiuser MMSE receiver, user 2.

Example 5: Performance versus Spreading Gain/Number of Antennas In this example we consider the performance of the single-user and multiuser methods by varying the processing gain N and number of receive antennas P while keeping their product ( NP ) fixed. The simulated system has K = 16 users, and the number of paths for each user is L = 3. Three cases are simulated: N = 64, P = 1; N = 32, P = 2; and N = 16, P = 4. The performance for user 2 is shown in Fig. 5.10. It is seen that in this case, this user's signal is best separated from others when N = 16, P = 4 for both the single-user and multiuser methods. Moreover, the multiuser approach offers orders-of-magnitude performance improvement over the single-user method.

Figure 5.10. Single-user and multiuser receiver performance under different space-time gains. K = 16. (a) Single-user MMSE receiver, user 2; (b) multiuser MMSE receiver, user 2.

In summary, in this and the preceding section we have discussed multiuser space-time receiver structures based on the sufficient statistic, which is illustrated in Fig. 5.11. It is seen that the front end of the receiver consists of a bank of matched filters, followed by a bank of array combiners, followed by a bank of multipath combiners, which produces the sufficient statistic. The maximum- likelihood multiuser sequence detector and linear multiuser detectors based on serial iterative interference cancellation have been derived. Note that since the detection algorithms in Fig. 5.11 operate on the sufficient statistic, their complexities are functions of only the number of users ( K ) and the length of the data block ( M ), not of the number of antennas ( P ).

Figure 5.11. Space-time multiuser receiver structure.