6.3 Turbo Multiuser Detection for Synchronous CDMA

6.3 Turbo Multiuser Detection for Synchronous CDMA

6.3.1 Turbo Multiuser Receiver

We consider a convolutionally coded synchronous real-valued CDMA system with k users, employing normalized modulation waveforms s ₁ , s ₂ , ..., s _k , and signaling through an additive white Gaussian noise channel. A block diagram of the transmitter end of such a system is shown in Fig. 6.4. The binary information symbols { d _k [ m ]} _m for user k , k = 1, ..., K, are convolutionally encoded with code rate R _k . A code-bit interleaver is used to reduce the influence of the error bursts at the input of each channel decoder. The interleaved code bits of the k th user are BPSK modulated, yielding data symbols of duration T . Each data symbol b _k [ i ] is then spread by a signature waveform s _k (t) and transmitted through the channel.

As seen from preceding chapters, the received continuous-time signal can be written as

Equation 6.27

where n(t) is a zero-mean white Gaussian noise process with power spectral density s ² and A _k is the amplitude of the k th user.

The turbo receiver structure is shown in Fig. 6.5. It consists of two stages: a soft-input/soft-output (SISO) multiuser detector, followed by k parallel single-user MAP channel decoders. The two stages are separated by deinterleavers and interleavers. The SISO multiuser detector delivers the a posteriori log- likelihood ratio (LLR) of a transmitted "+1" and a transmitted " “1" for every code bit of each user,

Equation 6.28

As before, using Bayes' formula, (6.28) can be written as

Equation 6.29

where the second term in (6.29), denoted by l ₂ [ b _k ( i )], represents the a priori LLR of the code bit b _k [ i ], which is computed by the MAP channel decoder of the k th user in the previous iteration, interleaved and then fed back to the SISO multiuser detector. For the first iteration, assuming equally likely code bits (i.e., no prior information available), we then have l ₂ ( b _k [ i ]) = 0, for 1 k k and 0 i < M . The first term in (6.29), denoted by l ₁ ( b _k [ i ]), represents the extrinsic information delivered by the SISO multiuser detector, based on the received signal r(t) , the structure of the multiuser signal given by (6.27), the prior information about the code bits of all other users, { l ₂ ( b _l [ i ])} _i ; _{l k} , and the prior information about the code bits of the k th user other than the i th bit, { l ₂ ( b _k [ j ])} _{j i} . The extrinsic information { l ₁ ( b _k [ i ])} _i of the k th user, which is not influenced by the a priori information { l ₂ ( b _k [ i ])} _i provided by the MAP channel decoder, is then reverse interleaved and fed into the k th user's channel decoder as the a priori information in the next iteration. Denote the code-bit sequence of the k th user after deinterleaving as { [ i ]} _i .

Based on the prior information { l ₁ ( [ i ])} _i and the trellis structure of the channel code (i.e., the constraints imposed by the code), the k th user's MAP channel decoder computes the a posteriori LLR of each code bit,

Equation 6.30

where the second equality was shown in Section 6.2 [cf. (6.10)]. It is seen from (6.30) that the output of the MAP channel decoder is the sum of the prior information l ₁ ( [ i ]) and the extrinsic information l ₂ ( [ i ]) delivered by the MAP channel decoder. As discussed in Section 6.2, this extrinsic information is the information about the code bit [ i ] gleaned from prior information about the other code bits, { l ₁ ( [ j ])} _{j i} based on the trellis constraint of the code. The MAP channel decoder also computes the a posteriori LLR of every information bit, which is used to make a decision on the decoded bit at the last iteration. After interleaving, the extrinsic information delivered by the k MAP channel decoders { l ₂ ( b _k [ i ])} _i;k is then fed back to the SISO multiuser detector, as the prior information about the code bits of all users, in the next iteration. Note that at the first iteration, the extrinsic information quantities { l ₁ ( b _k [ i ])} _i;k and { l ₂ ( b _k [ i ])} _i;k are statistically independent. But subsequently, since they use the same information indirectly, they will become more and more correlated, and finally, the improvement through iteration will diminish.

6.3.2 Optimal SISO Multiuser Detector

For the synchronous CDMA system (6.27), it is easily seen that a sufficient statistic for demodulating the i th code bits of the k users is given by the K -vector y [ i ] = [ y ₁ [ i ] ... y _K [ i ] ^T , whose k th component is the output of a filter matched to s _k (.) in the i th code-bit interval:

Equation 6.31

This sufficient statistic vector y [ i ] can be written as [520]

Equation 6.32

where R denotes the normalized cross-correlation matrix of the signal set s ₁ , ..., s _K :

Equation 6.33

; b [ i ] =[ b ₁ [ i ] ... b _k [ i ]] ^T ; and n [ i ] ~ N ( , s ² R ) is a Gaussian noise vector, independent of b [ i ].

In what follows , for notational simplicity, we drop the symbol index i whenever possible. Denote

From (6.32), the extrinsic information l ₁ ( b _k ) delivered by the SISO multiuser detector [cf. (6.29)] is then given by

Equation 6.34

where we have used the notation for b _j {+1, “1}. The summations in the numerator (respectively, denominator) in (6.34) are over all the 2 ^K-1 possible vectors b in (respectively, ). We have

Equation 6.35

Note that the first term in (6.35) is independent of b and therefore will be canceled in (6.34). The third term in (6.35) can be written as

Equation 6.36

Equation 6.37

where (6.36) follows from the fact that b _j {+1, “1}. The first term in (6.37) is also independent of b and will be canceled in (6.34). In (6.34) the a priori probabilities of the code bits can be expressed in terms of their LLRs l ₂ ( b _j [ i ]), as follows. Since

after some manipulations, we have for b _j {+1, “1},

Equation 6.38

Equation 6.39

where (6.38) follows from a derivation similar to that of (6.37). Substituting (6.35), (6.37), and (6.39) into (6.34), we obtain

Equation 6.40

It is seen from (6.40) that the extrinsic information l ₁ ( b _k [ i ]) at the output of the SISO multiuser detector consists of two parts ; the first term contains the channel value of the desired user y _k [ i ]}, and the second term is the information extracted from the other users' channel values { y _j [ i ]} _{j k} as well as their prior information { l ₂ ( b ₂ [ i ])} _{j k} .

6.3.3 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 k th element, which is 1. Therefore, [ i ] is obtained from [ i ] by setting the k th 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 ] = , 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 k th 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 k th 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 k th 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 ]} _{j k} 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 2 K 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 k th 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,j 4. 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.