Multiuser Detection in CDMA

Multiuser Detection in CDMA
Dr.MohitBansal Profile Pic
Published Date:25-10-2017
Your Website URL(Optional)
Multiuser Detection in CDMA Systems In this chapter, the uplink of a coded DS-CDMA system in which a common base station has to detect all incoming signals is considered. This is a major difference compared to the downlink where the mobile generally knows only its own spreading code and is interested only in its own signal. This requires the application of blind or semiblind multiuser detection (MUD) techniques (Honig and Tsatsanis 2000) that is not the focus of this work. A comparison with the detection algorithms for multilayer space-time transmission (Bohnke ¨ et al. 2003; Foschini et al. 1999; Golden et al. 1998; Wubben ¨ et al. 2001) presented in Chapter 6 demonstrates the strong equivalence of CDMA systems and multiple antenna systems when used for multilayer transmission. The next section starts with optimum MUD strategies. Since they are generally infeasible for practical implementations, linear joint detection techniques are derived in Section 5.2. Efficient approximations are obtained with multistage detectors such as iterative parallel and successive interference cancellation (SIC) schemes. A further performance improvement is derived in Section 5.3 by exploiting the discrete nature of the signal alphabet leading to nonlinear iterative MUD algorithms. Finally, the combination of linear joint detection and nonlinear interference cancellation is discussed in Section 5.4. The chapter closes with a summary of the main results. 5.1 Optimum Detection With regard to the uplink, each user maps a word d consisting of k information bits by u  appropriate forward error correction (FEC) encoding onto a code word b = b 0··· b u u u  n− 1 . After subsequent linear phase shift keying (PSK) or quadrature amplitude modu- lation (QAM) modulation delivering the sequence a , each symbol a  is spread with a u u spreading code c . Since we look at the generally asynchronous uplink, random spread- u ing codes are assumed. In short code CDMA systems, c  is independent of the time index u  while it varies from symbol to symbol in long code systems. The obtained sequence x u ¨228 MULTIUSER DETECTION IN CDMA SYSTEMS is transmitted over the individual channel with impulse response h . At the receiver, u that is, a common base station, all transmitted signals are superimposed and additive white Gaussian noise (AWGN) n is added resulting in y= H· x+ n= S· a+ n. (5.1)   In (5.1), H= T ,...,T represents a concatenation of several user-specific convolu- h h 1 N u tion matrices T (Kammeyer 2004) that cover all time instants of the considered sequence. h u   T T T The vector x= x ,...,x comprises the spread sequences of all users. According to N 1 u (4.4) on page 176, the convolution of spreading code c  and channel impulse response u h  can be expressed by the signature s . This leads to the second part of (5.1) where u u S comprises the signatures of all users and a the modulated symbols (cf. Section 4.1.2). 5.1.1 Optimum Joint Sequence Detection In this section, we assume perfect knowledge of the channel impulse responses and the spreading codes. As already mentioned in Section 1.3, the optimum detector performs a joint maximum a posteriori detection including FEC decoding for all users based on the received sequence y. Mathematically, this can be expressed by map ˆ ˜ ˜ d = argmax Prd S,y= argmaxp (y)· Prd, (5.2) ˜ Yd,S ˜ ˜ d d where the second equality is obtained by applying the Bayes rule and exploiting the fact ˜ that p (y) is independent of the hypothesis d and, therefore, does not affect the decision. YS ˜ As already explained in Section 1.3, the hypotheses d are generally uniformly distributed ˜ ˜ or the probabilities Prd are not known a priori at the receiver. In these cases, Prd is not available and the joint maximum likelihood detector has to be applied mld ˆ d = argmax p (y). (5.3) ˜ Yd,S ˜ d The conditional probability density function in (5.3) has the form / 0     1 H −1 ˜ ˜ p (y)= · exp − y− S· a(d)  y− S· a(d) (5.4) ˜ Yd,S NN det(π ) NN ˜ ˜ where a(d) denotes the modulated sequence associated with the hypothesis d. Inserting ˜ (5.4) into (5.3), neglecting all terms independent of the hypothesis d, and applying the 2 natural logarithm, we obtain with  = σ I NN N     H ˜ ˜ y− Sa(d) y− Sa(d) mld ˆ d = argmax log exp − 2 σ ˜ d N 5 5 2 5 ˜ 5 = argmin y− S· a(d) . (5.5) ˜ d From (5.5), we recognize that the joint maximum likelihood detector searches for that ˜ hypothesis d which minimizes the squared Euclidian distance between the received sequence ˜ y and S· a(d).Since d consists of discrete values, gradient-based methods cannot beMULTIUSER DETECTION IN CDMA SYSTEMS 229 applied and an exhaustive search is necessary. Obviously, even for medium-sized sys- tems the required computational complexity is far too high for practical implementations because it grows exponentially with the number of users as well as the lengths of the sequences. Contrary to the joint detection, each user can also be individually detected (Verdu 1998). Individual MAP detection of a certain user u can be expressed by map ˆ ˜ ˜ d = argmax Prd S,y= argmaxp (y)· Prd . (5.6) u ˜ u u Yd ,S u ˜ ˜ d d u u Equivalently to (5.3), the individual ML detector is obtained by mld ˆ d = argmax p (y). (5.7) ˜ u Yd ,S u ˜ d u Individual and joint detections do not always lead to the same result as described in (5.2), which has already been illustrated by the simple example on page 19. 5.1.2 Joint Preprocessing and Subsequent Separate Decoding The first step toward a reduced complexity receiver is to separate FEC decoding and MUD. To exploit as much information as possible, a hard decision multiuser detector must ˆ be avoided. Instead, the joint preprocessor should deliver log-likelihood ratios L(b  u y) of the coded bits b  for each user u that can be directly processed by the FEC u decoders. For the sake of notational simplicity, we restrict to synchronous single carrier CDMA systems in frequency-nonselective environments and OFDM-CDMA systems for frequency- selective channels assuming a coarse synchronization (Kuhn ¨ 2003) (cf. Section 4.2). In these scenarios, the system matrix S is block diagonal and can be split into several N × s N matrices S. Hence, symbol-wise preprocessing is optimal and we omit the time u variable . However, the derivation can generally be extended to the asynchronous case. Furthermore, we consider only binary phase shift keying (BPSK) modulation so that no 1 soft-output demodulation is required. In this case, b ∈0, 1 and a ∈+1, −1 can be u u used equivalently. The resulting structure is shown in Figure 5.1. Each transmitter consists of an FEC encoder including the BPSK mapping and a user-specific interleaver  (Bruck et al. u 2000). Spreading with the codes c  and the transmission over the channels h are u u embraced in the blocks denoted by the signatures s . Finally, the received signal yis u obtained by summing up all transmit signals and the background noise n. At the receiver, the processing for y= y at time instant  starts with the calculation of the log-likelihood ratios p (y)· Pra =+1 Pra =+1 y Ya =+1 u u u L(aˆ y)= log = log (5.8) u Pra =−1 y p (y)· Pra =−1 u Ya =−1 u u = L(yˆ a )+ L (a ). u a u 1 In the case of QPSK, a soft-output demodulator demultiplexes inphase and quadrature components into a single data stream. For M-ary modulation schemes withM 4, appropriate soft-output demodulation algorithms have to be employed.230 MULTIUSER DETECTION IN CDMA SYSTEMS n L(a  y) 1 ˆ d i a  d i 1 1 1 FEC −1 FEC cc   s  1 1 1 enc. dec. joint y pre- processor L(a  y) N u a  N u ˆ d i d i N N u u FEC −1 FEC s    N N u N u u enc. dec. Figure 5.1 CDMA system with joint preprocessing and individual FEC decoding Extending a in the numerator and denominator of L(yˆ a ) to a and summing up all u u 2 possible combinations of a yields with  = σ · I ν=u NN N s N p (y)· Pra Ya a,a =+1 u L(aˆ y)= log u p (y)· Pra Ya a,a =−1 u   2 2 exp −y− S· a /σ · Pra a,a =+1 u N = log   . (5.9) 2 2 exp −y− S· a /σ · Pra a,a =−1 u N The probabilities Pra in (5.9) are generally not known a priori so that they are not con- sidered for the moment. However, we will come back to them when talking about iterative schemes. Performing some manipulations on the squared magnitudes in the numerator and denominator and dropping all terms that do not depend on a results in   2 H H H H −y− S· a ⇒ 2· Re a · S · y − a · S · S· a   H H = 2· Re a · r − a · R· a. (5.10) H We recognize that the matched filtered signal r= S · y is correlated with the hypothesis    H a. In the case of BPSK, a and r = Re S · y are real-valued and (5.10) simplifies to 2 T  T  −y− S· a ⇒ 2a r − a R a (5.11)  with R = ReR. The output of the matched filter represents a sufficient statistics, that is, it contains the same mutual information as the channel output y, and subsequent processing stages can still provide optimal log-likelihood ratios. We obtain   T  T  2 exp 2a r − a R a /(2σ )  a,a =+1 N  u L(rˆ a )= log   . (5.12) u 2 T  T  exp 2a r − a R a /(2σ )  a,a =−1 u N Obviously, the computational complexity still depends exponentially on the number of users (and the alphabet size). A modest complexity reduction can be achieved by applying theMULTIUSER DETECTION IN CDMA SYSTEMS 231 already known approximation of (3.70) resulting in   1  T  T  L(rˆ a )≈ · max 2a r − a R a (5.13) u 2 a,a =+1 2σ u  N   1 T  T  − · max 2a r − a R a . 2 a,a =−1 2σ u  N 5.1.3 Turbo Detection with Joint Preprocessing and Separate Decoding In the next step, individual de-interleaving and FEC decoding is performed. According to the turbo-principle, it is possible to give feedback information to the preprocessor so that an iterative process arises (Hagenauer 1996a; Lampe and Huber 2002; Reed et al. 1998). If soft-output decoding algorithms like the (BCJR) algorithm explained in Section 3.4.3 are employed in delivering the LLRs L(aˆ )= L (a ), these LLRs can be used to calculate a u a u priori probabilities L (a )/2 a u e a L (a )/2 u a u Pra= · e (5.14) u L (a ) a u 1+ e that can be inserted into (5.9). Because of individual interleavers, the LLRs L (a ) are a u assumed to be statistically independent so that N u L (a )/2 7 a u e a L (a )/2 u a u Pra= · e (5.15) L (a ) a u 1+ e u=1 holds. Using the results for BPSK from (5.11) and inserting (5.15) into (5.9) results in   T  T  2  L (a )/2 a µ 2a r−a R a /(2σ ) N  u e a L (a )/2 µ a µ N e · e a,a =+1 L (a ) µ=1 a µ u 1+e L(aˆ r)= log   u 2 T  T   L (a )/2 a µ 2a r−a R a /(2σ ) N u e  a L (a )/2 µ a µ N e · e L (a ) a,a =−1 µ=1 a µ u 1+e   N T  T  2 u 2a r−a R a /(2σ )+ a L (a )/2 µ a µ  N µ=1 e a,a =+1 u   = log . (5.16) N T  T  2 u 2a r−a R a /(2σ )+ a L (a )/2  µ a µ µ=1 N e a,a =−1 u L (a )/2 L (a ) a µ a µ The terms e /(1+ e ) are independent of the hypotheses a within the summa- tions and, therefore, are identical in the numerator and denominator so that they can be cancelled. Furthermore, the u-th contribution in the inner sums of numerator and denom- inator in (5.16) is constant due to the restrictions of the outer summations over a with a =+1or a =−1. Hence, we can extract the common factor expL (a ) from the ratio u u a u and obtain L(aˆ r)= L (a )+ L (aˆ ) (5.17a) u a u e u with   N T  T  2 u 2a r−a R a /(2σ )+ a L (a )/2  µ a µ µ=1 N µ=u e a,a =+1 u   L (aˆ )= log . (5.17b) e u N T  T  2 u 2a r−a R a /(2σ )+ a L (a )/2 µ a µ  µ=1 N µ=u e a,a =−1 u232 MULTIUSER DETECTION IN CDMA SYSTEMS The approximation already known from (5.13) becomes   N u T  T     2a r − a R a 1   L(aˆ r)≈ L (a )+ max + a L (a ) u a u µ a µ  2  a,a =+1 u 2σ 2  N µ=1 µ=u   N u T  T     2a r − a R a 1   − max + a L (a ) . (5.18) µ a µ  2  a,a =−1 2 u 2σ  N µ=1 µ=u The receiver structure depicted in Figure 5.2 illustrates how to calculate the solutions pre- sented in (5.16) and (5.18). In the first iteration, no a priori information is available and only the terms given in (5.11) have to be calculated. They remain constant during subse- quent iteration steps and are to be determined only once. After having performed the FEC decoding for the first time, the LLRs L (b ) can be used as a priori information according a u to (5.15) to improve the estimates L(aˆ r). u As already mentioned, the complexity of the joint preprocessor still grows exponen- tially with the number of users while the decoding part depends linearly on N . For a u small OFDM-CDMA system with a spreading factor N = 4, some results are shown s in Figure 5.3. They have been obtained for a 4-path Rayleigh fading channel with uni- form power delay profile and random spreading codes. A half-rate convolutional code with L = 3 and generators g = 5 , g = 7 was employed. At the receiver, perfect LLRs from c 1 8 2 8 (5.16) as well as for the approximation of (5.18) have been used. Obviously, the error rate can be significantly reduced with the second iteration. Subse- quent iterations not shown here do not lead to substantial additional improvements because we are already close to the single-user bound (SUB). This lower bound is reached at a signal-to-noise ratio (SNR) of 7 dB for β=1aswellas β= 2. Only for small SNRs, the L (a ) a 1  1 L (aˆ ) e 1 SISO −1 cc  1 decoder ˆ d 1 joint y pre- processor ˆ L (aˆ ) d e N u N u SISO −1  N u decoder  N u L (a ) a N u Figure 5.2 Turbo receiver for joint preprocessing and individual FEC decodingMULTIUSER DETECTION IN CDMA SYSTEMS 233 b) β= 2 a) β= 1 0 0 10 10 SUB SUB perf. LLR perf. LLR −1 −1 10 10 app. LLR app. LLR −2 −2 10 10 −3 −3 10 10 −4 −4 10 10 −5 −5 10 10 0 2 4 6 8 10 0 2 4 6 8 10 E /N in dB→ E /N in dB→ b 0 b 0 Figure 5.3 Performance of optimum multiuser detection with subsequent decoding for the first two iterations (first iteration:◦ and×, second iteration: and+) loss compared with the SUB amounts to 0.2 dB for β= 1 and 0.5 dB for β= 2. Moreover, the approximate solution (× and+) performs nearly as well as the optimum solution. 5.2 Linear Multiuser Detection A further reduction of the computational complexity can be achieved by applying only linear joint preprocessing. A common property of all linear techniques is that they do not exploit the knowledge of the finite signal alphabet but assume continuously distributed transmit signals. Therefore, we have only a polynomial complexity with respect to the number of active users instead of an exponential relationship. The following approaches are related to simple linear algebra, that is, the linear equation system y= Sa+ n has to be solved with respect to a, that is, we look for a matrix W with aˆ= W· y. For simplicity, we first restrict to the uncoded case and the system matrix S consists of N columns and N rows. u s 5.2.1 Decorrelator (Zero-Forcing, ZF) First, we consider the decorrelator being equivalent to the zero-forcing (ZF) equalizer (Honig and Tsatsanis 2000; Moshavi 1996). It searches for the unconstrained vector a˜ ∈ ZF N u C that minimizes the squared Euclidean distance to the received vector y according to 5 5 2 5 5 a˜ = argmin y− Sa˜ . (5.19) ZF N u a˜∈C The multiplication of a˜ with S leads to the best reconstruction of y. Although (5.19) ZF looks very similar to the maximum likelihood solution, the search space is not restricted to a finite alphabet (unconstrained) but comprises the entire N -dimensional space of complex u numbers. Therefore, the final detection requires a scalar hard decision aˆ =Q(a˜ ) of the ZF ZF soft values in a˜ . Nevertheless, the decorrelator represents the joint maximum likelihood ZF BER→ BER→234 MULTIUSER DETECTION IN CDMA SYSTEMS detector for continuously distributed signal alphabets. Without the exploitation of the finite signal space there is no combinatorial problem and the optimization is solved by setting H the derivative of the squared Euclidean distance in (5.19) with respect to a˜ , to zero. With H the relation ∂a˜/∂a˜ = 0 (Fischer 2002), we obtain the Wirtinger derivative    ∂ ∂ H H H H H H H y− Sa˜ · y− Sa˜ = y y− y Sa˜− a˜ S y+ a˜ S Sa˜ H H ∂a˜ ∂a˜ H H ˜ =−S y+ S Sa= 0 (5.20) whose solution is obviously (Verdu 1998)  −1 H H H −1 a˜ = W · y= S S · S · y= R · r (5.21) ZF ZF  −1 H with W = S· S S . We recognize that the decorrelator starts again with a bank of ZF H matched filters (multiplying y with S ). Afterwards, the intermediate results in r are decor- −1 related with R , that is, the correlations between the matched filter outputs are removed. If S consists of linear independent columns which are generally fulfilled for N ≤ N ,the u s H correlation matrix R= S S has full rank and its inverse exists. Inserting the structure of y into (5.21) leads to  −1 H −1 H H a˜ = R S · Sa+ n = a+ R S · n= a+ W · n. (5.22) ZF ZF The output of the decorrelator consists of the desired symbol vector a and a modified noise term. Therefore, as already mentioned in Section 4.4.3, the interference can be totally suppressed. However, the background noise is multiplied with the inverse of the correlation matrix R leading, especially for high loads β, to a strong noise amplification and, hence, to low SNRs. This drawback is also indicated by the error covariance matrix , -   H  = E a˜ − a a˜ − a ZF ZF ZF , -     H H H H H = E a+ W n− a a+ W n− a = W E nn W ZF ZF ZF ZF 2 H 2 −1 H −1 2 −1 = σ W W = σ R S SR = σ R . (5.23) ZF ZF N N N It contains on its diagonal, the mean squared error (MSE) for each user and equals the 2 inverse of the correlation matrix R multiplied with the noise power σ . N Real-Valued Modulation Schemes For real-valued modulation schemes such as BPSK or M-ary amplitude shift keying (ASK), significant improvements can be achieved by the following modification. Since we know that real symbols have been transmitted, only the real part of the matched filter outputs    H r = Re S y is of interest. Consequently, the inverse has to be determined only from    H R = Re S S and we obtain     −1 H H −1  a˜ = Re S S · Re S · y = R · r . (5.24) ZF The advantage of (5.24) becomes obvious when the received signal is described only by real matrices. Splitting up real and imaginary parts doubles the sizes of all vectors andMULTIUSER DETECTION IN CDMA SYSTEMS 235 matrices leading to + + + + + +        y S −S a n S n r  r  r ˜ y = = · + = · a + = S a + n . (5.25)        y S S a n S n  Since a = 0 holds for real-valued modulation schemes, only the first N columns of the u real-valued system matrix influence the channel output. This halves the effective interference r ˜ so that S is better conditioned than S and the background noise is less amplified. Moore-Penrose Pseudo Inverse Next, we have to discuss the case when R is singular and its inverse does not exist. Since we assume binary spreading codes, this situation occurs for N N and requires the pseudo u s inverse or Moore-Penrose inverse. It is obtained from the singular-value decomposition of S (Golub and van Loan 1996) (see also Appendix C) + + 2  0  0 H 0 H H H 0 S= UV = U V ⇒ R= U U = UU , (5.26) 00 00 N×N N ×N s s u u where U∈ C and V∈C are unitary matrices. The diagonal matrix  contains 0 all nonzero singular values of S. With this definition, we obtain the pseudo inverses that also include the nonsingular case  + −1 H H −1 S S S rank(S)= N  0 u † † H H 0 S = V U = V U =  (5.27a) −1 H H 00 S SS rank(S)= N s and  + −1 −2 H   S S rank(S)= N †  0 u † H H 0 R = S S = V V =  (5.27b) −2 H H 00 S SS S rank(S)= N . s H † Using (5.27a) and (5.27b), we obtain the general result W = S . ZF Near-Far Scenarios In scenarios with near-far effects (cf. page 183), the received signal can be expressed as 1/2 y= SP a+ n. The corresponding decorrelating filter is H −1/2 † W = P S , (5.28) ZF † that is, it consists of the already known decorrelator S with successive scalar weighting of the filter outputs. Since the decorrelator totally removes the interference, weak users do not suffer from strong users and the decorrelator is called near-far resistant. Figure 5.4a shows the bit error rate (BER) performance of the decorrelator for BPSK. Although the multiple access interference can be totally suppressed, the performance degrades with increased load. Only for very low β the SUB can be reached. The rea- son for this behavior is the amplification of the background noise that becomes larger with growing load. For β= 2, a reliable transmission is not possible. However, except for low SNR and extremely high loads, the decorrelator performs better than the simple matched filter represented by dashed lines.236 MULTIUSER DETECTION IN CDMA SYSTEMS b) error rate versus β a) error rate versus E /N s 0 0 0 10 10 0dB −1 −1 10 10 5dB −2 −2 10 10 10 dB −3 N=2 −3 u 10 10 N=16 u N=32 u −4 −4 N=48 15 dB u 10 10 N=64 u 20 dB SUB −5 −5 10 10 0 4 8 12 16 20 0 0.5 1 1.5 2 E /N in dB→ β→ b 0 Figure 5.4 Error rate performance of decorrelator for different loads and uncoded OFDM- CDMA system with BPSK, processing gain G = 32, and 4-path Rayleigh fading channel p (dashed lines: matched filter) This can also be observed in Figure 5.4b showing the error rate performance versus β for different SNRs E /N . While the error rate degrades dramatically for the matched filter s 0 even for moderate loads, the BER increases more slowly for the decorrelator. Nevertheless, the noise amplification leads to a weak performance at high SNRs, the error rate approaches 0.5 when β tends to 2. It has to be emphasized that the example assumes independent fading channels for all users (see uplink transmission in Section 4.2) so that the interference is distributed in the complex plane. Since we use real-valued BPSK, only half of the interference power affects the transmission. Otherwise, the error rate of 0.5 would have already been reached for β= 1. Figure 5.5 compares the performance of the decorrelator with that of a simple matched filter. It depicts the gain E /N b 0 MF γ = 10 log (5.29) ZF−MF 10 E /N b 0 ZF of the decorrelator for different target error rates P , that is, the logarithmic ratio of required t SNRs to achieve the bit error rate P . Obviously, γ grows with β and the slope t ZF−MF becomes higher for low target error rates. Note that the matched filter cannot reach certain target error rates if the load is too high, resulting in infinite large gains. For small SNRs and if β approaches 2, the decorrelator performs worse than the matched filter as can be seen from Figure 5.4. 5.2.2 Minimum Mean Squared Error Receiver (MMSE) So far, we considered two extreme linear detectors: The matched filter in Chapter 4 that addresses only the background noise and, therefore, suffers severely from multiuser interfer- ence and the decorrelator of the preceding section that concentrates only on the interference neglecting the influence of the noise. A compromise between both is obtained with the BER→ BER→MULTIUSER DETECTION IN CDMA SYSTEMS 237 10 −1 P = 10 t −2 P = 5· 10 t −2 8 P = 10 t −3 P = 5· 10 t 6 4 2 0 0 0.2 0.4 0.6 0.8 1 β→ Figure 5.5 Gain of decorrelator compared to MF for different loads and uncoded OFDM- CDMA system with BPSK and 4-path Rayleigh fading channel minimum mean squared error (MMSE) detector W minimizing the average squared MMSE H Euclidean distance between the estimate a˜ = W · y and the true data vector a. MMSE MMSE , - 5 5 2 H H 5B 5 aˆ = W · y with W = argmin E W y− a . (5.30) MMSE MMSE MMSE B N ×N u s W∈C Again, a solution of the problem defined in (5.30) is found by setting the partial derivative of H ˜ B B the squared Euclidean distance with respect to W, to zero. With the relation ∂W /∂W= 0 (Fischer 2002), we obtain    ∂ H H H B B E tr (W y− a)(W y− a) B ∂W 1 2 ∂ H H B B B B = tr W  W− W  −  W+  YY YA AY AA B ∂W H B = W  −  = 0 (5.31) YY AY leading to the well-known Wiener solution H −1 W =  ·  . (5.32) AY MMSE YY To determine the covariance matrices in (5.32), some general assumptions are made that are fulfilled in most practical communication systems. First, the AWGN channel adds white noise, that is, successive noise samples are uncorrelated. Second, the data symbols a of u different users are statistically independent. Furthermore, the data symbols are independent from the noise samples leading to the following set of equations. H 2  = Enn = σ · I (5.33a) NN N s N H 2  = Eaa = σ · I (5.33b) AA N A u H  = Ean = 0. (5.33c) AN γ in dB ZF−MF238 MULTIUSER DETECTION IN CDMA SYSTEMS These results deliver the covariance matrix of the received samples H H 2 H 2  = Eyy = S S +  = σ · SS + σ · I (5.34) YY AA N NN A N s and the crosscovariance matrix H H 2 H  = Eay =  S +  = σ · S . (5.35) AY AA AN A Inserting (5.34) and (5.35) into (5.32), we obtain the MMSE filter 2 σ   −1 −1 N H 2 H 2 H 2 H H W = σ S σ SS + σ I = S SS + I (5.36) N N MMSE A A s s N 2 σ A 2 which can be shown to be equivalent to −1 & ' 2 −1 σ N 0 H H N H H W = S S+ I · S = R+ I · S . (5.37) N N MMSE u u 2 E σ s A Analyzing the result in (5.37), we see that the MMSE detector starts like the decorrelator with a matched filter bank. Moreover, W represents a compromise between matched MMSE 2 filter and decorrelator. For σ → 0, that is, infinitely large SNR, the identity matrix in the N inverse is cancelled and we obtain the decorrelator in (5.21) suppressing the interference 2 perfectly. On the contrary, the identity matrix dominates the inverse for σ →∞ so that N R can be neglected. In this case, we simply obtain the matched filter that addresses only the noise (Muller ¨ 1998). The MMSE detector does not suppress the multiuser interference perfectly and some residual interference still disturbs the transmission. Moreover, the estimate is biased. The error covariance matrix with (5.1) and (5.37) now becomes , -   H  = E a˜ − a a˜ − a MMSE MMSE MMSE   −1 −1 2 2 σ σ N N 2 2   = σ I − R+ I R = σ R+ I . (5.38) N N N u u u A N 2 2 σ σ A A The normalized MSE per user can be easily calculated and amounts to   −1 2 2 σ σ 1 1 N H N   tr  = tr UU + I MMSE N u 2 2 2 N σ N σ σ u u A A A rank(S)  1 N /E 0 s = , (5.39) N λ + N /E u µ 0 s µ=1 where λ denotes the µ-th nonzero eigenvalue of the correlation matrix R. Hence, the µ average error depends on the singular-value distribution of S.For largeSNR E /N →∞, s 0 the error diminishes; for E /N → 0, it becomes 1. s 0 2 H H 2 A simple way to derive (5.37) is to start with a matched filter bank and minimizing W S y− a = H 2 W r− a .MULTIUSER DETECTION IN CDMA SYSTEMS 239 Real-Valued Modulation Schemes Looking again at a BPSK transmission, the performance can be improved by concentrating on the important real parts. Similar to the derivation for the decorrelator we obtain & ' −1 N 0   a˜ = R + I · r . (5.40) MMSE N u 2E s Note that the noise power in (5.40) is halved compared to the complex-valued case Near-Far Scenarios In near-far scenarios, the MMSE filter has to be adapted to the different power levels among 1/2 the users (Feuersanger ¨ and Kuhn ¨ 2001). Substituting S with SP , it becomes  −1 1/2 H H 2 W = P S SPS + σ I (5.41a) MMSE N N s  −1 1/2 H 2 H = P S SP+ σ I S . (5.41b) N u N From (5.41a) and (5.41b), we observe that the power levels affect the behavior of the MMSE filter. If the SNR grows without bound, the influence of the background noise vanishes and the MMSE filter concentrates on the interference suppression. Hence, the MMSE detector approaches the decorrelator, and is asymptotically near-far resistant (Verdu 1998). However, for finite SNR weak users suffer more from strong users than in the case of the decorrelator, that is, near-far resistance is not generally given. Figure 5.6a shows the BER performance of the MMSE detector for an OFDM-CDMA system and a 4-path Rayleigh fading channel. Similar to the decorrelator, performance degrades for increased system load β. However, the comparison with the decorrelator in Figure 5.6b illustrates that the degradation is much smaller than for the ZF solution. The b) error rate versus β a) error rate versus E /N s 0 0 0 10 10 0dB −1 −1 10 10 5dB −2 −2 10 10 10 dB β≈ 0 −3 −3 10 10 β= 0.5 β= 1 −4 −4 15 dB β= 1.5 10 10 β= 2 20 dB SUB −5 −5 10 10 0 4 8 12 16 20 0 0.5 1 1.5 2 E /N in dB→ β→ b 0 Figure 5.6 Error rate performance of MMSE filter for different loads and OFDM-CDMA system with 4-path Rayleigh fading channel (dashed line: decorrelator) BER→ BER→240 MULTIUSER DETECTION IN CDMA SYSTEMS 6 −1 P = 10 t −2 P = 10 t 5 −3 P = 10 t −4 P = 10 t 4 3 2 1 0 0 0.5 1 1.5 2 β→ Figure 5.7 Gain of MMSE filter compared to decorrelator for different loads and an uncoded OFDM-CDMA system with BPSK and 4-path Rayleigh fading channel MMSE filter outperforms the decorrelator for all loads β and all SNRs and the gain grows with the system load. This is also confirmed by Figure 5.7. Concluding, we can state that linear MUD techniques reduce multiple access interference efficiently. Especially, the MMSE filter outperforms the simple matched filter for all SNRs. Although the computational complexity of the described linear detectors is much lower than that of the optimum multiuser detector, it still grows cubically with the system size. Hence, calculating the pseudo inverse of S becomes a demanding task for large systems. The next subsections describe some iterative schemes approximating the ZF and MMSE solutions with lower computational costs. 5.2.3 Linear Parallel Interference Cancellation (PIC) By calculating the pseudo inverse of the system matrix S, we basically solve a linear equation system. From linear algebra (Golub and van Loan 1996) we know that the solution can be obtained iteratively. Starting with a matched filter bank, we have to process the signal H H r= Ra+ S n ⇒ a˜= W · r ⇔ M· a˜= r. (5.42) Instead of looking in (5.42) for a matrix W that leads to a good estimate a˜, we can describe the problem as solving the linear equation system M· a˜= r. The matrix M will be determined later. A single row of this linear equation system can be presented in the form u−1 N u   r = M a˜ + M a˜ + M a˜ , (5.43) u u,u u u,v v u,v v v=1 v=u+1 that is, the received value r consists of the superposition of the scaled desired symbol a˜ u u and the weighted interfering symbols a˜ . An iterative solution of the equation system is v=u obtained by using the weighted matched filter outputs of the interfering symbols as initial γ in dB ZF−MFMULTIUSER DETECTION IN CDMA SYSTEMS 241 (0) (1) (2) N a˜ N a˜ u r u a˜ 1 1 1 (0) (1) 1 M a˜ Mcc a˜ 1,u u 1,u u −1 −1 −1 u=2 u=2 M M M 1,1 1,1 1,1 matched y filter bank (0) (1) (2) N −1 a˜ N −1 a˜ u a˜ r u N N N N u u u u (0) (1) M a˜ M a˜ N ,u u N ,u u u u −1 −1 −1 u=1 u=1 M M M N ,N N ,N N ,N u u u u u u second stage first stage Figure 5.8 Structure of multistage detector for iterative parallel interference cancellation (0) soft estimates aˆ = r /M . Subtracting them from r leads to an improved estimate v=u v,v u v=u (1) a˜ after the first iteration. The interference cancellation is simultaneously applied to all u (µ) users and repeated with updated estimates a˜ in subsequent iterations. In the µ-th iteration, u the u-th symbol becomes 3 4 N u−1 u   (µ) −1 (µ−1) (µ−1) a˜ = M · r − M a˜ − M a˜ . (5.44) u u,v u,v u u,u v v v=1 v=u+1 The simultaneous application of (5.44) for all symbols a ,1≤ u≤ N , is also called Jacobi u u algorithm and known as linear parallel interference cancellation (PIC). An implementation leads directly to a multistage detector depicted in Figure 5.8 (Honig and Tsatsanis 2000; Moshavi 1996). Several identical modules highlighted by the gray shaded areas are serially concatenated. Each module represents one iteration step so that we need m stages for m iterations. The choice of the matrix M determines the kind of detector that is approximated. For M= R, we approximate the decorrelator, and the coefficients M = R used in u,v u,v (5.44) equal the elements of the correlation matrix. The MMSE filter is approximated 2 2 for M= R+ σ /σ · I . Hence, the diagonal elements of M have to be replaced with N A u N M = R + N /E . u,u u,u 0 s Convergence Behavior of Decorrelator Approximation The convergence properties of this iterative algorithm depend on the eigenvalue distribution of M. Therefore, (5.44) is described using vector notations. The matrix A= diag(diag(R)) is diagonal and contains the diagonal elements of the correlation matrix R. The PIC approx- imating the decorrelator delivers (0) −1 a˜ = A · r ZF 1 2     (1) (0) −1 −1/2 −1/2 −1/2 −1/2 a˜ = A r− R− A a˜ = A I − A R− A A A r N ZF ZF u242 MULTIUSER DETECTION IN CDMA SYSTEMS 1 2  (2) (1) −1 a˜ = A r− R− A a˜ ZF ZF + / 0 2   −1/2 −1/2 −1/2 −1/2 −1/2 −1/2 = A I − A R− A A + A R− A A A r N u . . . m     µ (m) −1/2 −1/2 −1/2 −1/2 a˜ = A A A− R A A r. (5.45) ZF µ=0 The output after the m-th iteration in (5.45) represents the m-th order Taylor series approx- −1 imation of R (Muller ¨ and Verdu 2001). Rewriting it with the normalized correlation −1/2 −1/2 ¯ matrix R= A RA yields m   µ (m) −1/2 −1/2 ¯ a˜ = A I − R A r. (5.46) N ZF u µ=0 This series only converges to the true inverse of R if the magnitudes of all eigenvalues of ¯ ¯ I − R are smaller than 1. This condition is equivalent to λ (R) 2. Since λ tends N max max u √ 2 asymptotically to (1+ β) (Muller ¨ 1998), we obtain an approximation of the maximum load below which the Jacobi algorithm will converge. √ N U,max 2 β = ( 2− 1) ≈ 0.17. (5.47) max N s Obviously, the Jacobi algorithm or, equivalently, the linear PIC converges toward the true decorrelator only for very low loads. Hence, this technique is not suited for highly loaded systems. Convergence Behavior of MMSE Approximation According to the last section, we have to replace the diagonal matrix A with the matrix 2 2 D= A+ σ /σ I to approximate the MMSE detector. With this substitution, we obtain N u N A the following estimates after different iterations. (0) −1 a˜ = D · r MMSE 1 2  (1) (0) −1 a˜ = D r− R− A a˜ MMSE MMSE    −1/2 −1/2 −1/2 −1/2 = D I − D R− A D D r N u 1 2  (2) −1 (1) a˜ = D r− R− A a˜ MMSE MMSE + / 0 2   −1/2 −1/2 −1/2 −1/2 −1/2 −1/2 = D I − D R− A D + D R− A D D r N u . . . m     µ (m) −1/2 −1/2 −1/2 −1/2 a˜ = D D A− R D D r. (5.48) MMSE µ=0MULTIUSER DETECTION IN CDMA SYSTEMS 243 To determine the convergence properties concerning the MMSE filter, (5.48) can be trans- formed into the form of (5.46) 3 4 µ m 2  σ (m) −1/2 −1/2 N −1/2 −1/2 a˜ = D I − D R+ I D D r. (5.49) N N u u MMSE 2 σ A µ=0 Now, the same argumentation as for the decorrelator can be applied and the condition for convergence becomes (Grant and Schlegel 2001) C  2 D 2 2 2 2 D A λ + σ /σ σ u u,u N A N E   max 2 ⇒ β min 2+ − 1 . 2 2 2 2 2 u=1...N u=1...N A + σ /σ u A σ u u,u u,u N A A The first difference compared to the decorrelator is that the maximum load β depends on 2 2 the SNR σ /σ = N /E . This term increases the convergence area a little bit. However, 0 s A N 2 2 for high SNR σ /σ becomes small and both decorrelator and MMSE filter are approached N A only for low loads. This behavior is illustrated in Figure 5.9a showing the results for the first five iterations 2 2 and a load β= 0.5. Only for very low SNR (large σ /σ ) the iterative approximation A N reaches the true MMSE filter. For higher SNRs, β= 0.5 is beyond the convergence region and the PIC performs even worse than the matched filter. Figure 5.9b shows the results for E /N = 10 dB versus β. Again, it is confirmed that convergence can be ensured only for b 0 low load. 5.2.4 Linear Successive Interference Cancellation (SIC) The poor convergence properties of the linear PIC can be substantially improved. Imagine that the interference cancellation described in (5.44) is carried out successively for different b) E /N = 10 dB a) β= 0.5 b 0 0 0 10 10 −1 10 −2 −1 10 10 −3 10 −4 −2 1 iteration 10 10 2 iterations −5 3 iterations 10 4 iterations 5 iterations −6 −3 10 10 0 5 10 15 20 0 0.5 1 1.5 2 β→ E /N in dB→ b 0 Figure 5.9 Performance of linear PIC approximating the MMSE filter (upper dashed line: matched filter; lower dashed line: true MMSE filter) BER→ BER→244 MULTIUSER DETECTION IN CDMA SYSTEMS users starting with u= 1 and ending with u= N . Considering the µ-th iteration for user u, u (µ−1) only estimates a˜ of the previous iteration µ− 1 are used. However, updated estimates v=u (µ) a˜ of the µ-th iteration are already available for users 1≤vu. Replacing all old vu (µ−1) (µ) estimates a˜ in (5.44) with their updated versions a˜ of the current iteration results vu vu in the Gauss-Seidel algorithm 3 4 u−1 N u   (µ) −1 (µ) (µ−1) a˜ = M · r − M a˜ − M a˜ . (5.50) u u,v u,v u u,u v v v=1 v=u+1 Besides improved convergence properties another advantage is the in-place implementation, that is, updated estimates can directly overwrite old values because they are not used any longer, thereby saving valuable memory. The analysis of the convergence behavior is not as easy as for the PIC. In Golub and van Loan (1996) it is shown that the algorithm always converges for Hermitian positive definite matrices M. Fortunately, in the context of our CDMA system M represents the 2 2 correlation matrix R or R+ σ /σ I . Hence, M can be assumed to be Hermitian and N u N A positive definite so that the Gauss-Seidel algorithm always converges. Figure 5.10a confirms the promised convergence properties. Considering a half-loaded system, five iterations suffice to approach the true MMSE filter. At low SNRs, the perfor- mance of the MMSE filter is reached with even less iterations. Figure 5.10b shows that with increasing load more iterations are needed. For loads above β= 1, the first iteration can perform even worse than the matched filter. However, successive iterations substantially improve the performance. Comparing the computational costs of a direct matrix inversion with the iterative approx- imations in terms of number of multiplications, we see from (5.50) that N multiplications u 2 per iteration and user are needed. For m iterations, this leads to mN multiplications u b) E /N = 10 dB a) β= 0.5 b 0 0 0 10 10 −1 10 −2 −1 10 10 −3 10 −4 −2 1 iteration 10 10 2 iterations −5 3 iterations 10 4 iterations 5 iterations −6 −3 10 10 0 5 10 15 20 0 0.5 1 1.5 2 β→ E /N in dB→ b 0 Figure 5.10 Performance of linear SIC approximating the MMSE filter (upper dashed line: matched filter, lower dashed line: true MMSE filter) BER→ BER→MULTIUSER DETECTION IN CDMA SYSTEMS 245 3 compared to a complexity of O(N ) for the direct matrix inversion. Hence, as long as u the number of iterations is smaller than N , we save computational costs. u Besides parallel and SIC strategies, there exist further iterative approaches like the conjugate gradient method and a general polynomial series expansion of the inverse (Muller ¨ 1998). These approaches are not pursued here. All linear techniques described so far do not reach the SUB, that is, interference remains in the system after filtering. The information theoretic analysis in Section 4.3 showed that the optimum detector performs much better than linear techniques. Therefore, we have to look for nonlinear approaches that come closer to the optimum solution. These techniques exploit the finite signal alphabet to improve the MUD. 5.3 Nonlinear Iterative Multiuser Detection A major drawback of the previously introduced linear detectors is not exploiting the discrete nature of the transmit signals. This shortcoming can be easily overcome by introducing nonlinear devices into the multistage structure to exploit the discrete alphabets. This means (µ) that the signals a˜ in (5.44) or (5.50) are passed through a suited nonlinear device before v= u they are used for interference cancellation. For simplicity, we restrict the analysis to a normalized BPSK, that is, we transmit x=±1. An extension to quaternary phase shift keying (QPSK) that treats real and imaginary parts separately is straightforward while schemes with more levels need more sophisticated methods. 5.3.1 Nonlinear Devices The simplest nonlinearity is naturally a hard decision, that is, determining the sign of a signal Q (y)= sgn(y). (5.51) HD If the tentative decision is correct, the interference can be cancelled perfectly. However, if the decision is wrong, which may be very likely in the early stages of the detection process, especially for large β, interference is not reduced but in fact increased and the situation becomes worse. Therefore, more sophisticated functions taking into account the reliability of the signals should be preferred. A selection analysed by Kuhn ¨ et al. (2002) is depicted in Figure 5.11. To keep the influence of wrong decisions as small as possible, it is advantageous not to decide on unreliable small samples but to keep them small. Obviously, interference is generally not perfectly cancelled by these approaches, but the error made by wrong decision is remarkably reduced. The simplest form that follows this strategy is the clipper or limiter. It has a linear shape fory≤ 1 and outputs±1 for larger inputsy 1  −1for y−1  Q (y)= (5.52) y fory≤ 1 clip   +1for y+1. 3 Hence, the clipper exploits the fact that the transmitted signals cannot be larger than 1. Interference is totally cancelled if the signal has the correct sign and a magnitude larger 3 For notational simplicity, we assume the normalization to E /T = 1. s s246 MULTIUSER DETECTION IN CDMA SYSTEMS HD clipper tanh 11 1 -1 1 -1 1 -1 -1 -1 NL1 NL2 11 α α α -111 -1 α -1 -1 Figure 5.11 Examples for nonlinear devices than 1. For small values, the reliability is low and the interference can only be partly reduced. In case of a wrong sign, the degradation is not as large as for the hard decision. A smooth version of the clipper is obtained with the tanh-function avoiding sharp edges. We know from Section 3.4 on page 110 that the expectation of a bit is obtained from its log-likelihood ratio L by tanh(L/2). However, the LLR can be determined only if the signal to interference plus noise ratio (SINR) is perfectly known. This represents a big difficulty because we do not know the exact interference level in each iteration. Therefore, we introduce a parameter α according to Q (y)= tanh(αy) (5.53) tanh that depends on the SNR as well as the effective interference and has to be optimized with respect to a minimum error rate. Figure 5.12 compares the tanh-function for different α with the hard decision and the clipper. For small α, the tanh is very smooth and its output is pretended to be unreliable even for large inputs. On the contrary, α= 1 comes close to the clipper in the nearly linear area around the origin and large α 1 approach the hard decision. Next, two further nonlinear functions are proposed. The first one (NL 1) has a linear shape around the origin and hops to±1 for values larger than a certain threshold α  −1for y−α  Q (y)= (5.54) y fory≤ α NL1   +1for yα. The difference compared to the clipper is that this nonlinearity starts to totally remove the interference for values smaller than 1. The parameter α has to be optimized according to the load and the SNR. The second function (NL 2) avoids any cancellation for unreliable

Advise: Why You Wasting Money in Costly SEO Tools, Use World's Best Free SEO Tool Ubersuggest.