Low-Complexity SISO Multiuser Detector

Low-Complexity SISO Multiuser Detector

It is clear from (6.40) that the computational complexity of the optimal SISO multiuser detector is exponential in terms of the number of users K, which is certainly prohibitive for channels with moderate to large numbers of users. In what follows we describe a low-complexity SISO multiuser detector based on a novel technique of combined soft interference cancellation and linear MMSE filtering, which was first developed in [552].

Soft Interference Cancellation and Instantaneous Linear MMSE Filtering

Based on the a priori LLR of the code bits of all users, {l₂(b_k[i])}_k, provided by the MAP channel decoder from the previous iteration, we first form soft estimates of the code bits of all users as

Equation 6.41

Equation 6.42

where (6.41) follows from (6.39). Define

Equation 6.43

Equation 6.44

where e_k denotes a K-vector of all zeros, except for the kth element, which is 1. Therefore, [i] is obtained from [i] by setting the kth element to zero. For each user, a soft interference cancellation is performed on the matched-filter output y[i] in (6.32), to obtain

Equation 6.45

Such a soft interference cancellation scheme was first proposed in [168]. Next, in order to further suppress the residual interference in y_k[i], an instantaneous linear minimum mean-square error (MMSE) filter w_k[i] is applied to y_k[i], to obtain

Equation 6.46

where the filter is chosen to minimize the mean-square error between the code bit b_k[i] and the filter output z_k[i]:

Equation 6.47

where using (6.45), we have

Equation 6.48

Equation 6.49

and in (6.48),

Equation 6.50

because

Equation 6.51

Denote

Equation 6.52

Substituting (6.48) and (6.49) into (6.47), we have

Equation 6.53

Substituting (6.45) and (6.53) into (6.46), we obtain

Equation 6.54

Notice that the term R^-1 y[i] in (6.54) is the output of a linear decorrelating multiuser detector. Next, we consider some special cases of the output z_k[i].

1. No prior information on the code bits of the interfering users; that is, l₂(b_k[i]) = 0 for 1 k K. In this case, [i] = 0, and V_k[i] = A². Then (6.54) becomes

   Equation 6.55

   

   
   

   which is simply the output of the linear MMSE multiuser detector for user k.

2. Perfect prior information on the code bits of the interfering users; that is, l₂(b_k[i]) = ± for 1 k K. In this case,

   

   Substituting these into (6.53), we obtain

   Equation 6.56

   

   
   

   Equation 6.57

   

   
   

   where (6.56) follows from the matrix inversion lemma^[1] and (6.57) follows from the fact that . The output of the soft instantaneous MMSE filter is then given by

   ^[1]

   Equation 6.58

   

   
   

   That is, in this case, the output of the soft instantaneous MMSE filter is a scaled version of the kth user's matched filter output after ideal interference cancellation.

3. In general, the prior information provided by the MAP channel decoder satisfies 0 < |l₂(b_k[i])| < , 1 k K. The signal-to-interference-plus-noise ratio (SINR) at the soft instantaneous MMSE filter output is defined as

   Equation 6.59

   

   
   

   Denote by SINR(z_k[i]) the output SINR when there is no prior information on the code bits of interfering users (i.e., the SINR of the linear MMSE detector). Also denote by (z_k[i]) the output SINR when there is perfect prior information on the code bits of interfering users [i.e., the input signal-to-noise ratio (SNR) for the kth user]. Then we have the following result, whose proof is given in the Appendix (Section 6.9.1).

   Proposition 6.1: If 0 < |l₂(b_k[i])| < for 1 k K, we have

   Equation 6.60

   

   
   

Gaussian Approximation of Linear MMSE Filter Output

It is shown in [386] that the distribution of the residual interference plus noise at the output of a linear MMSE multiuser detector is well approximated by a Gaussian distribution. In what follows, we assume that the output z_k[i] of the instantaneous linear MMSE filter in (6.46) represents the output of an equivalent additive white Gaussian noise channel having b_k[i] as its input symbol. This equivalent channel can be represented as

Equation 6.61

where m_k[i] is the equivalent amplitude of the kth user's signal at the output and h_k[i] ~ N (0, ) is a Gaussian noise sample. Using (6.45) and (6.46), the parameters m_k[i] and can be computed as follows, where the expectation is taken with respect to the code bits of interfering users {b_j[i]}_jk and the channel noise vector n[i]:

Equation 6.62

Equation 6.63

Using (6.61) and (6.63) the extrinsic information delivered by the instantaneous linear MMSE filter is then

Equation 6.64

Recursive Procedure for Computing Soft Output

It is seen from (6.64) that to form the extrinsic LLR l₁(b_k[i]) at the instantaneous linear MMSE filter, we must first compute z_k[i] and m_k[i]. From (6.54) and (6.62) the computation of z_k[i] and m_k[i] involves inverting a K x K matrix:

Equation 6.65

Next we outline a recursive procedure for computing F_k[i]. Define , and

Equation 6.66

Using the matrix inversion lemma, Y^(k) can be computed recursively as

Equation 6.67

Denote . Using the definition of V_k[i] given by (6.52), we can then compute from Y as follows:

Equation 6.68

Finally, we summarize the low-complexity SISO multiuser detection algorithm as follows.

Algorithm 6.2: [Low-complexity SISO multiuser detector—synchronous CDMA]

• Given , form the soft bit vectors and { according to (6.42)–(6.44).

• Compute the matrix inversion , k = 1, ..., K, according to (6.66)–(6.68).

• Compute the extrinsic information according to (6.54), (6.62), and (6.64):

Equation 6.69

Equation 6.70

Equation 6.71

Next we examine the computational complexity of the low-complexity SISO multiuser detector discussed in this section. From the discussion above, it is seen that at each symbol time i, the dominant computation involved in computing the matrix for k = 1, ..., K consists of 2K K-vector outer products [i.e., K outer products in computing Y(^K) as in (6.67), and K outer products in computing as in (6.68)]. From (6.62) and (6.64), in order to obtain the soft output l₁(b_k[i]), we also need to compute the soft instantaneous MMSE filter output z_k[i], which by (6.54), is dominated by two K-vector inner products, one in computing the kth user's decorrelating filter output and another in computing the final z_k[i]. Therefore, in computing the soft output of the SISO multiuser detector, the dominant computation per user per symbol involves two K-vector outer products and two K-vector inner products.

Note that a number of studies have addressed different aspects of turbo multiuser detection in CDMA systems. In particular, in [336], an optimal turbo multiuser detector is derived based on iterative techniques for cross-entropy minimization. Turbo multiuser detection methods based on different interference cancellation schemes are proposed in [13, 14, 88, 129, 157, 200, 265, 397, 409, 410, 471, 552, 576, 608].

An interesting framework that unifies these approaches to iterative multiuser detection is given in [50]. Moreover, techniques for turbo multiuser detection in unknown channels are developed in [540, 593], which are based on the Markov chain Monte Carlo (MCMC) method for Bayesian computation. Application of the low-complexity SISO detection scheme discussed in this section to equalization of ISI channels with long memory is given in [413].

Simulation Examples

In this section we present some simulation examples to illustrate the performance of the turbo multiuser receiver in synchronous CDMA systems. Of particular interest is the receiver that employs the low-complexity SISO multiuser detector of the preceding section. All users employ the same rate-½ constraint-length n = 5 convolutional code (with generators 23 and 35 in octal notation). Each user uses a different interleaver generated randomly. The same set of interleavers is used for all simulations. The block size of the information bits for each user is 128.

First we consider a four-user system with equal cross-correlations r_ij = 0.7, for 1 i,j4. All the users have the same power. In Fig. 6.6 the BER performance of the turbo receiver that employs the optimal SISO multiuser detector (6.40) is shown for the first five iterations. In Fig. 6.7, the BER performance of the turbo receiver that employs the low-complexity SISO multiuser detector is shown for the same channel. In each of the these figures, the single-user BER performance (i.e., r_ij = 0) is also shown. It is seen that the performance of both receivers converges toward single-user performance at high SNR. Moreover, the performance loss due to using the low-complexity SISO multiuser detector is small. Next, we consider a near–far situation, where there are two equal-power strong users and two equal-power weak users. The strong users' powers are 3 dB above the powers of the weak users. The user cross-correlations remain the same. Figures 6.8 and 6.9 show, respectively, the BER performance of strong and weak users under the turbo receiver that employs the low-complexity SISO multiuser detectors. It is seen that in such a near–far situation, the weak users actually benefit from the strong interference, whereas the strong users suffer performance loss from the weak interference, a phenomenon previously also observed in the optimal multiuser detector [518] and the multistage multiuser detector [512]. Note that with (2^K) computational complexity the optimal SISO multiuser detector (6.40) is not feasible for practical implementation in channels with moderate to large numbers of users K, whereas the low-complexity SISO multiuser detector has a reasonable complexity that can be implemented easily even for very large K. Figure 6.10 illustrates the BER performance of the turbo receiver that employs a low-complexity SISO multiuser detector in an eight-user system. The user cross-correlations are still r_ij = 0.7. All users have the same power. Note that the performance of such a receiver after the first iteration corresponds to the performance of a traditional noniterative receiver structure consisting of a linear MMSE multiuser detector followed by K parallel (soft) channel decoders. It is seen from these figures that at a reasonably high SNR, the turbo receiver offers significant performance gain over traditional noniterative receivers.