This is to certify that the thesis entitled ADVANCED RECEIVERS FOR WCDMA DOWNLINK presented by KEYUR DESAI has been accepted towards fulfillment of the requirements for the MS. degree in Electrical and Computer Engineering Date MSU is an Affirmative Action/Equal Opportunity Institution ‘. 0‘ *‘ -2 ' ‘2 ' ' 1"“ - .3 O' Q 4 v‘ 'v v V' LlBR Ry Michigan State L University ‘— PLACE IN RETURN BOX to remove this checkout from your record. TO AVOID FINES return on or before date due. MAY BE RECALLED with earlier due date if requested. DATE DUE DATE DUE DATE DUE 6/01 c:/CIRC/Date0ue p65-pt 15 ADVANCED RECEIVERS FOR WCDMA DOWNLINK By Keyur Desai A THESIS Submitted to Michigan State University in partial fulfillment of the requirements for the degree of MASTER OF SCIENCE ELECTRICAL AND COMPUTER ENGINEERING 2004 ABSTRACT ADVANCED RECEIVERS FOR WCDMA DOWNLINK By Keyur Desai In this master’s thesis, the issue of signal detection in the downlink of Code Division Mul- tiple Access (CDMA) is addressed. First, we observe the CDMA downlink in a frequency- selective slow fading channel as a linear combination of convolved independent symbol sequences and develop a higher order statistics (HOS) based novel symbol estimation method. We call this method as Blind Multiuser Seperation (BMUS), which inherently benefits from quasi-orthogonality of the user spreading codes and the independence among transmitted user, and evaluate its applicability in a ”short code” limited knowledge CDMA scenario. Later we develop 3G WCDMA downlink specific chip-level space-time equaliz- ers capable of providing uncoded BER of g 10’3 in fast time varying frequency-selective Rayleigh faded wireless channels. An adaptive version of linear minimum mean-square error (LMMSE) equalizer based on conjugate gradient algorithm (CGA), which avoids the direct estimation of inverse correlation matrix, is derived in the generalized framework of multiple receive antennas for very high speed mobile receivers (2 120 kmph). The sin- gleuser channel estimate obtained using common code-multiplexed pilot channel (CPICH) is further refined by exploitation of time correlations among samples of any single multi- path via weighted sliding window approach. An adaptive MMSE method based on CGA for handling soft hand-off is also developed. Simulation results suggest that even in the events of very high spectral loading the performance of CGA based adaptive MMSE equalizer with moderate computational load is close to that of the LMMSE equalizer employing ma- trix inversion and it is a possible solution of much labored problem of multiuser detection in WCDMA downlink with ”long codes”. To my grandparents iii ACKNOWLEDGEMENTS It is all about communication, connecting people. I would especially like to express my gratitude for communication with and connection to the following people. My sincere thanks to my thesis advisor Professor Fathi M. Salem for his constant guid- ance, support and encouragement. Sincere gratitude is extended to the members of my thesis committee Dr. Tongtong Li and Dr. Ning Xi from the department of electrical and computer engineering for their valuable service on my committee. I also take this op- portunity to thank my teachers at Michigan State University in whose classes I learnt the concepts necessary to meet this research challenge. I would also like to thank my col- leagues at CSANN Lab for many helpful and stimulating discussions during the course of this research. My Sincere thanks to my parents and my family for their invaluable support, uncon— ditional love and constant encouragement. Last, but not least, I would like to express my appreciation to all my friends here at MSU and from M. S. University of Baroda for pro- viding intellectually stimulating and motivating environment. iv TABLE OF CONTENTS Page List of Tables ...................................... vi List of Figures ...................................... vii Chapters: 1. Blind Multiuser Separation in CDMA ...................... 1 1.1 Motivation for BMUS in CDMA ...................... 2 1.2 Downlink Receiver Signal Model ..................... 3 1.3 Natural Gradient based BMUS algorithms ................. 6 1.3.1 Demixing Structures ........................ 8 1.4 Computer Simulations ........................... 11 1.5 BMUS Applicabilities and Shortcomings ................. 12 2. Adaptive MMSE Equalizers for WCDMA Downlink .............. 15 2.1 Background ................................. 16 2.2 Channel and Data Models ......................... 19 2.2.1 Rayleigh Faded Multipath Channel ................ 19 2.2.2 WCDMA Downlink Signal Structure ............... 20 2.3 Adaptive equalizers ............................. 22 2.3.1 Space-Time MMSE chip-level equalization ............ 23 2.3.2 Time varying form of MMSE equalizer .............. 25 2.3.3 Conjugate Gradient Algorithm based MMSE Solution ...... 25 2.3.4 Convergence of CG algorithms in CDMA ............. 27 2.4 Soft Hand-off Mode ............................ 28 2.5 Channel Estimation ............................. 30 2.6 Complexity Analysis ............................ 33 2.7 Performance Evaluation .......................... 34 2.7.1 Channel Estimation Accuracy ................... 36 2.7.2 Without Inter-cell Interference ................... 39 2.7.3 With Inter-cell Interference .................... 40 2.7.4 Soft Hand-off Mode ........................ 43 2.8 Conclusion ................................. 43 Bibliography ...................................... 49 LIST OF TABLES Table Page 2.1 Complexity per Information Symbol ..................... 33 2.2 Channel parameters for simulations ..................... 35 vi LIST OF FIGURES Figure 1.1 1.2 1.3 1.3 2.1 2.2 2.3 2.4 Blind Multiuser Separation in a QPSK DS-CDMA system ......... Feedback demixing structure ......................... Feedforward Demixing Structure ....................... (a) signal constellation after channel propagation and recovery by BMUS (b) BER K=4 users (c) BER K=8 users (d) BER K=12 users ........ LMMSE receiver using CGA algorithm: (1) Form various antenna channels- matched filtering and sampling (2) Channel and noise power estimation (3) Correlation Matrix computation and LMMSE filter update based on CGA (4) Filtering using time varying filters (5) descrambling and despreading. . . LMMSE receiver using CGA algorithm operating in soft hand-off mode. Desired user data is transmitted by two base stations - BS1 and BSZ ..... The performance of CPICH based channel estimation in fast fading chan- nel. Parameters are: (a) CPICH poweF-IO dB of total power, SNR=10 dB, Tap powergains= {-4 -7 -7 -10 - 10 -13]dB (b) CPICH power=-10 dB of total power, SNR=20 dB, Tap powergains= [-4 -7 -7 -10 -10 -13]dB. . . . . The performance of CPICH based channel estimation in a fast fading chan- nel in terms of autocorrelation among channel samples. Smaller difference between the estimated and theoretical autocorrelation represents the superi- ority of algorithm in statistical sense. Parameters are: (a) CPICH powem— 10 dB of total power, SNR=10 dB, Tap powergain= -4.0 dB (b) CPICH powet=-10 dB of total power, SNR=20 dB, Tap powergain= -4.0 dB ..... vii 10 10 26 31 37 38 2.5 2.6 2.7 comparison of various detection methods in terms of average BER perfor- mance vs. SNR(dB): (a) heavily loaded spectrum; [1, 2, 4, 6] number of user codes corresponding to the lengths [4, 8, 16, 32] are active, (b) less loaded spectrum; [0, l, 2, 2] number of user codes corresponding to the lengths [4, 8, 16, 32] are active. n1 and n2 correspond to 2 and 4 itera- tions of CGA respectively. Short and Long correspond to the equalizers of length 11 and 31 respectively. The cases of channel estimated and channel know are marked with hestimated and hknown respectively. MMSE and CGA denote mmse equalizer implementation via direct matrix inversion and CGA method respectively. ........................ SNR gain obtained by various detection methods in a heavy spectral load ing scenario (both with channel estimation and perfect knowledge) at the targeted BER compared to short (N = 11) CGA equalizer with channel estimation and -2 CGA iterations: (a) Comparison of matrix inversion and CGA method. When the targeted BER is g 10-3 the short CGA equal- izer with channel estimation is within 2 dB range of MMSE equalizer with matrix inversion and perfect channel knowledge. (b) Comparison as a func- tion of CGA iterations and channel knowledge. With estimated channel 2 iterations are suffice for any targeted BER. At very low targeted BER the channel estimation becomes crucial. Minimum 4 iterations are required with pefect channel knowledge with very low targeted BER. ........ comparision of various detection methods in terms of average BER per- formance vs. SNR(dB) when second BS is an equal power interfere : (a) heavily loaded spectrum; [1, 2, 4, 6] number of user codes corresponding to the lengths [4, 8, 16, 32] are active, (b) less loaded spectrum; [0, l, 2, 2] number of user codes corresponding to the lengths [4, 8, 16, 32] are ac- tive. n1 and n2 correspond to 2 and 4 iterations of CGA respectively. Short and Long correspond to the equalizers of length 11 and 31 respectively. The cases of channel estimated and channel know are marked with hesti- mated and hknown respectively. MMSE and CGA denote mmse equalizer implementation via direct matrix inversion and CGA method respectively. The maximum achievable BER is in the range of 10“3 with perfect channel knowledge and long MMSE equalizer. .................... viii 41 .44 2.8 Two BSs are active and second BS is an interferer. SNR gain obtained by various detection methods in a heavy spectral loading scenario (both with channel estimation and perfect knowledge) at the targeted BER com- pared to short (N8 = 11) CGA equalizer with channel estimation and 2 CGA iterations: (a) Comparison of matrix inversion and CGA method. At the targeted BER of z 10‘2 long CGA equalizer with channel estimation and 2 CG iterations has performance within 3 dB range of long MMSE equalizer with perfect channel knowledge. (b) Comparison as a function of CG iterations and channel knowledge for short CGA equalizers. Channel knowledge is critical in case of short CGA equalizer. Long CGA equalizer is necessary to achieve good performance with channel estimation ...... 45 2.9 comparision of various CGA equalizers in terms of average BER perfor- mance vs. SNR(dB) when soft hand-off mode is used. (a) In lightly loaded spectrum ( [0, l, 2, 2] number of user codes corresponding to the lengths [4, 8, 16, 32] are active)long CGA equalizer with channel estimation can deliver the performance of x 10-4. Soft hand-off mode offers clear gain in performance. (b) With heavily loaded spectrum ([1, 2, 4, 6] number of user codes corresponding to the lengths [4, 8, 16, 32] are active) the soft hand-off mode offers almost 10 dB of gain at the targeted BER of x 10‘2. . 46 ix CHAPTER 1 Blind Multiuser Separation in CDMA In this thesis chapter a higher order statistics (HOS) based novel method for symbol es- timation in the Downlink (the link from base station to mobile receiver) of Direct Sequence- Code Division Multiple Access (DS-CDMA) is developed. We call our method Blind Multi User Separation (BMUS). The observation that a slowly fading multipath CDMA environ- ment may be conveniently represented as a linear combination of convolved independent symbol sequences, has motivated our approach. In BMUS the chip rate sampled received signal is passed through an adaptive network (algebraic structure) that maximizes the signal entropy at its output. The proposed network is implemented both in feedforward and feed- back symbol recovery structures based on Natural Gradient-Blind Source Recovery (BSR) techniques. Interestingly these algorithms do not require any prior knowledge of multipath channel and/or active user codes. However the recovered symbol sequences are in arbi- trary fashion, which is identified as a peculiarity of BSR, and small amount of training is necessary for the identification purpose of the desired user sequence among the separated sequences. Performance of BMUS algorithms is compared with the conventional matched filter (MF) and sub-space based minimum mean square error (MMSE) receivers (i.e. re- ceivers requiring no further knowledge other than desired user code) via MATLAB simula- tions. Simulation results suggest the superiority of BMUS over other methods of its class. We attribute this performance gain to the inherent exploitation of ”quasi-orthogonality” of the spreading codes and the independence among transmitted user symbol sequences by BMUS approach. In chapter summary section we highlight the immediate applicability and shortcomings of BMUS method. 1.1 Motivation for BMUS in CDMA Code Division Multiple Access (CDMA) is an efficient spread spectrum technique in which multiple users share the same temporal and spectral resources [19]. In the downlink signal processing, each user is identified by a unique code, which is chosen to be quasi- orthogonal to the codes allotted to other users in the system. DS-CDMA is a promising data transmission technique capable of providing high data rates and immunity to channel impairments and noise. Other advantageous features of CDMA include soft capacity limit, graceful degradation, high cell frequency reuse factor, soft handover mode etc. Wide band- width CDMA will be a dominant technology for the third generation (3G) wireless com- munication systems and forms an integral part of the UMTS/IMT-ZOOO and CDMA2000 standards [4]. Hence complex but computationally efficient receiver structures capable of providing better performance than conventional receivers have recently emerged as one of the most active research areas in the communication and signal processing community. Unlike the uplink communication channel, where all user codes are known and the base station possesses much higher signal processing capabilities, the downlink channel has a different set of constraints. The receiver (e.g., a mobile phone) just has the knowledge of a single self-identification code, and also has limited computational resources. The detector at the receiving end can be setup as either a single-user or a multi-user detector. While a single-user receiver basically estimates the signal for a desired user by modeling all the interfering users and disturbances as noise. A multi-user detector (MUD) [28] includes all the users in the signal model, which significantly improves the performance. However the optimal MUD [27] is computationally intensive and requires several system parameters to be known. In typical downlink signal processing, where many of the system parameters are unknown including the active user codes and perfect channel information, one can use the blind techniques for better estimate of the user signal [32]. In the conventional detec- tion techniques for CDMA signals, only the second order statistics among the user codes is exploited but in most practical situations the user data symbols among themselves are independent. This is a powerful assumption, which enables one to apply the existing blind source recovery techniques to solve the detection problem in the multi user environment. Blind Source Recovery (BSR) in this context is the process of estimating the original in- dependent user-specific symbol sequences independent of, and in the absence of precise system identification [22, 23]. The received CDMA signal can be considered as a set of non-gaussian random variables generated by the linear convolute transformation of statis- tically independent component variables [6, 7, 29]. This linear transformation accounts for the user codes, multiple channel paths and slowly fading channel’s symbol memory. Our goal is to estimate another linear transformation such that it counters, as best as possible, the effects of the first transformation resulting in the recovery of the original signal. A similar blind deconvolution approach for BPSK signals has been earlier described in [6, 7]. However, their proposed algorithm does not represent the class of natural gradient algo- rithms [3, 22, 23] and motivates our development of BMUS algorithms. 1.2 Downlink Receiver Signal Model We consider the synchronous CDMA downlink in a wide sense stationary slowly fad- ing, multipath, additive white Gaussian noise (AWGN) channel with symbol memory. This symbol memory exists in the CDMA system due to the presence of previously transmitted symbol in the receiver environment. The received data in this case can be modeled as a multipath generalization of the signal model in [19] as: r(t) =s(t)+n(t) (1.1) where n(z) represents the channel additive white gaussian noise and 3(1) represents the channel corrupted transmitted signal which can be written as: N L—l W) = 2 2bk(n)@20k(1)8k(f—nT—Tz) (1.2) [=0 n=lk=l I 810) b User 1 Data + '(I) Q "'* "3 g,(t) I 122(1) ‘ Multipath : 2 ~ A WGN I : Channel 1 | 8,“) User n Data + hm) Q—ixj J. Blind Multi-user Detection (BMUD) Algorithm l l---- l 1310) 132(1) 13.0) Figure 1.1: Blind Multiuser Separation in a QPSK DS-CDMA system where, N represents the total number of symbols during the observation interval; K is the total number of active users; L represents the total number of transmission paths; bk(n) rep- resents the n’h QPSK symbol for the k’h user; 8]", represents the signal energy of n'hsymbol of km user (used for power control); ak(l) represents the fading coefficient of 1‘” trans- mission path; and 1'; is the corresponding transmission delay for the 1’” transmission path satisfying the condition 0 _<_ 1:, S T and assumed to be constant during the observation interval. Here, gk(t) denotes the signature code for the k’h user, generated by M—l gm) = 2 at(m)p(r—mTc) (1.3) m=0 where, ak(m);0 g m _<_ M — 1 : is a pseudo-noise (PN) code sequence for the H” user containing M chips, ak(m) E {:tl}, p(t) is a chipping pulse of duration 7} and T is the total code time, given by T = M Tc. We consider a realistic scenario for DS-CDMA systems, where at any instant of time the transmission medium comprises the current transmitted symbol as well as weakened versions of prior symbols corrupting the reception of the current symbol. We sample the received signal envelope at chip rate after passing it through a chip-matched filter and collect it in a vector of length M. In this case the n'” received symbol will be corrupted by J previously transmitted symbols as: K L—l r[n] = 2 bk(n)\/£; 2 ak(l)gk(t—nT — 1:1) +n[n] k=l [=0 H (1.4) J K + Z 2 bttn—j),/—et(,.-,-) 2 at<1>gk(t— j=lk=l (=0 where, for a fading channel , /€k(,,_j) 2 , /Ek(,,_j_,); V j 2 O. For the sake of clarity we restrict ourselves to the case where the existing symbol is corrupted by only one previously transmitted symbol, i.e., we assume that the effect of symbols transmitted prior to the previ- ous symbol is negligible due to its temporal dispersion and absorption in the environment. K L—l L—l Yin] = Z [bknx/Ekn 2 Guild +bk.n—l \/€k.n—l Z dial/t1 +n[n] (1-5) k=l [=0 [=0 where T ik1=[0 0 8km gkiM—Tii] and T zkl: I: gk[M—T[+I] gk[M] gk[1] ng—‘CdJ and 121 is the discrete delay still satisfying the constraint 0 S 121 g T. Altemately we can represent the model in a more compact matrix-vector form as rn : HObn +Hlbn—l +1111 (16) where b,, and b,,_1 are the K -d vectors of current and previous symbol for all the K users. H0 and H1 are M x K mixing matrices given by H0: [ Hon Hot Hex] H1: [ H1.0 Hm H1,K ] such that, L—l H0Jc = \/8_0 2 Olaf/ti (1.7) 1:0 L—l Hl.k = \/8_1 2 aklzkl (1.8) [=0 and so and £1 (80 2 81 > 0) represents the energy of the current and the previous symbol respectively at the instant of observation. 1.3 Natural Gradient based BMUS algorithms The received signal comprises a noise-corrupted linear mixture of delayed and con- volved user symbol sequences. It is reasonable to assume that the various transmitted symbol sequences are mutually independent as they are generated by independent sources. Assuming no preamble transmission to the receiver, both the transmitted sequence and the mixing matrices in the model (1.6) are unknown to the user. The only known entity to the user is its own PN code. Other available prior information is the nature of trans- mitted data, which is QPSK constellation corrupted by the multipath channel effects and AWGN noise, i.e., it falls in the class of quaternary sub-gaussian distributions. We have enough information to apply the Blind Source Recovery (BSR) algorithms for BMUS in this case [22, 23, 29]. We assume that the DS-CDMA channel is not over-saturated and K g M. The proposed BSR algorithms do not require any pre-whitening of received data. However, in the most modern CDMA versions, M is chosen to be very large and in general K < M. There- fore, it is computationally advantageous to pre-process the data for dimension reduction to K which is the actual number of principal independent symbol components in the received data. The process of pre-whitening will also remove the second order dependence among the chip rate sampled received data samples and some of the additive noise [21]. The data pre-whitening can be achieved either online using adaptive principal component analysis (PCA) algorithms or it may be done using an algebraic PCA estimate over a large batch (say Ncomplex samples) of received data, i.e., R: 1‘1 1'2 l‘N—i I‘N with the correlation matrix 1 Then whitening is achieved using the filtering matrix w = D-iv” where, D represents the K -dim matrix of principle eigenvalues of the data correlation matrix Ac and V represents the K x Mmatrix of principal eigen vectors of the data correlation matrix AC. H denotes the Herrnitian transpose operator. The whitened version of (6) is given by: r: = W(H0b,, +H1bn_1+n,,) g Hobn+fi1b,,-, (1.10) where, r: represents the K -d received data at the if” sampling instant and H0, H1 are the equivalent square K -d mixing matrices for the current and the delayed symbols. 1.3.1 Demixing Structures The natural gradient BMUS network for such a problem can either be implemented in the feedforward or the feedback configuration [23]. We present the update laws for both cases and analyze the performance similar to [6, 29]. 1) FEEDBACK BMUS CONFIGURATION: In the feedback configuration the output is estimated by: K yn:W6'l (Fr—Zwkyn—k> (L11) k=l This soft estimate y" is passed through a hard-decision block to obtain the actual esti- mate of transmitted data. 13,, =v(yn) (1.12) where w(.): represents the (nonlinear) decision stage. The update laws for this structure using the natural gradient have been derived in [23]. The update laws for the feedforward matrix W0 are given by AWO °< —Wo (1 — I M: 1 - 1 10.6 l l 1 I I I 1 l I -10 -8 -6 -4 -2 O 2 4 6 8 10 SNR (in 68) ((c» 0 BER vs. SNR Ctaracten‘stics for 12 QPSK users 10 I I I T r r I I I > -e- no” 1 r New I M d w 1 1o 1dF-9——9— 0——e—— a i a a t 5 . a: m l m to” r 10': 1 1 1 1 1 1 1 1 1 -10 -e -6 4 -2 o 2 4 e a 10 SNR an d8) ((d)) Figure 1.3: (a) Signal constellation after channel propagation and recovery by BMUS (b) BER K=4 users (c) BER K=8 users ((1) BER K=12 users 14 CHAPTER 2 Adaptive MMSE Equalizers for WCDMA Downlink Recently, in the downlink of wideband CDMA the chip-level linear equalizers based on Minimum Mean Square Error (MMSE) criterion are shown to significantly outperform the conventional Rake receiver. However the direct linear MMSE solution of such an equalizer requires matrix inversion and hence involves excessive computational complexity while tracking the fast time varying fading channels. In this thesis chapter an adaptive version of LMMSE equalizer based on conjugate gradient algorithm (CGA) is derived for the gen- eralized framework of multiple receiving antennas. The single user channel estimate is derived from common code-multiplexed pilot channel, which is further refined by exploit- ing the time correlation among samples of any single multipath via weighted sliding win- dow approach. An adaptive MMSE method based on CGA for handling soft hand-off is also developed. Performance of these adaptive receivers in terms of BER, SNR gain and convergence speed/number of iterations is evaluated via computer simulations employing the UMTS specified downlink signal structure and ITU channel specifications. Simulation results suggest that even in the events of very high spectral loading the performance of CGA based adaptive MMSE equalizers with moderate computational load is close to that of the LMMSE equalizer employing matrix inversion. The work presented in this chapter advocates that the CGA based adaptive MMSE chip-level equalizer in the existing form or modified for implementation case is the possible solution of much labored problem of multiuser detection in CDMA downlink with ”long codes”. 15 2.1 Background Code-division multiple access (CDMA) in one form or another is going to be at the heart of cellular wireless communication networks proposed in the third generation stan- dard (3G) and beyond. Once the successful deployment of 3G networks is achieved in terms of coverage, over time the capacity enhancement and high-data rate services will be of central focus (e.g. recently, the 3GPP WCDMA release 5 proposes High Speed Down- link Packet Access (HSDPA) whose main target is to increase user peak data rates and quality of service, and to generally improve Spectral efficiency for downlink asymmetrical and bursty packet data services [2]). As data rates in the downlink are likely to be higher than uplink, the downlink dominates the total system capacity. Downlink receivers are ex- pected to provide the uncoded bit-error rate (BER) of < 10‘3, in the harsh time-varying frequency-selective wireless channels typically experienced by mobile receivers, to min- imize the energy-bandwidth cost per bit with multiple receive antennas and/or multiple poly-phasic channels (to gain space-time diversity) and extended computational resource at their disposal. The downlink of WCDMA uses Orthogonal Variable Spreading Factor (OVSF) chan- nelization codes and a base station (BS) dependent scrambling code or ”long code” to provide separation at the user and cell level respectively. In the frequency-selective chan- nels the orthogonality of the OVSF codes is lost at the receiver and significant multiuser interference (MUI) is introduced. Commonly employed matched filter (Rake receiver), which treats MUI as additional white noise, combines energy from multiple paths across time and space (if Spatial or polarization diversity is employed). Rake receiver inherently suffers from MUI and its performance deteriorates significantly for high spectral loading. Approaches which model MUI separately from additive noise are called multiuser detec- tion methods and several optimal and suboptimal multiuser detection schemes have been proposed in literature [28]. In the time varying channels these multiuser detectors also take a time varying form and are generally realized using adaptive algorithms [18]. Many 16 symbol-level adaptive algorithms exploiting the symbol level cyclostationarity of CDMA signal were proposed before the finalization of 3G standard [17, 31]. In 3G long scram- bling codes are used because the interference experienced by successive symbols (of a given user) changes and one may expect that in average all users will experience similar levels of interference and hence the quality of service (QOS) of the user can be controlled mere by the means of energy per bit, however this causes the WCDMA downlink Signal to be non-cyclostationary at symbol level. Hence chip-level equalizers are preferred over symbol level adaptive algorithms. Chip-level MMSE equalizers that minimize the mean-square error between the syn- chronous sum signal of all active users transmitted from the BS under consideration and its estimate at the mobile receiver were proposed independently by Ghauri [12] and Frank [9]. In [33] linear MMSE (LMMSE) receiver was shown to significantly outperform other lin- ear chip-level equalizers, namely the least square (LS) detector, the best linear unbiased estimator (BLUE) detector and the Rake receiver. In [16] LMMSE receiver was general- ized for multiple receive antennas and/or multiple poly-phasic channels and soft hand-off mode was developed. In the same publication exhaustive analysis of their performance in time-invariant frequency-selective channels with the perfect channel knowledge was given to provide the informative upper bound, which established the clear superiority of the LMMSE receivers over zero-forcing (ZF) detectors and Rake in case of multiple re- ceive antennas too. When channel coherence time (0}) is of the order of frame-length (10ms for UMTS) LMMSE equalizer requires one matrix inversion per frame in its direct implementation. However in rapidly changing channels the minimum of cost surface also changes and its tracking by updating the LMMSE equalizer within a time slot of length S O'c with direct matrix inversion presents prohibitive computational complexity and adap- tive algorithms with good tracking ability and convergence speed are desired. In [5] LMMSE adaptation based on conjugate gradient algorithms (CGA) was proposed for slow fading channels. In [14] the frame error rate of CGA MMSE was computed for 17 slowly changing frequency-selective fading channels with the assumption of perfect chan- nel knowledge. In this paper we evaluate the performance of these MMSE CGA detectors in the fast fading channel with common pilot channel (CPICH) based channel estimation scheme. Our formulation of the MMSE CGA algorithm is for multiple receive antennas and except the code-level synchronization no further assumptions are made. We develop and analyze two variants of MMSE CGA equalizer. In (i) the correlation matrix is estimated using received samples similar to [14] (ii) the correlation matrix is determined using the estimate of channel and noise power. The channel estimate is obtained by single user detection of CPICH, which is further refined by the sliding window approach proposed in [8]. Noise covariance knowledge is assumed to be available Similar to the assumption made in [16]. We consider three different cases based on the desired users location: (i) near one BS case where out-of—cell interference is negligible (ii) middle-of-cell case where the mobile experience significant out-of-cell interference and (iii) the edge-of- cell case where either mobile is operating in the soft hand-off mode in which the desired users data is transmitted from two base-stations or typical mode where the second BS present excessive interference. We assess the case of one and two receive antenna and compare them. Further, we analyze the BER as a function of equalizer length and the number of iteration used in CGA. We focus on ITU specified vehicular channel- A (120 km/h) and UMTS specified QPSK signal constellation and spreading. The rest of the chapter is organized as follows. Section II describes the signal structure for a multi-rate CDMA system and channels models. Section III presents the MMSE CGA equalizers, while channel estimation algorithm is discussed in section IV. section V devel- ops the soft hand-off mode based on CGA equalizers. The performance of these algorithms via numerical simulations is illustrated in section VI. In section VH concluding remarks are drawn. 18 2.2 Channel and Data Models 2.2.1 Rayleigh Faded Multipath Channel The impulse response for i’h antenna channel, between the k’h BS transmitter and the mobile receiver is N,,' _ 125*)(1) = 2 2 “IAI(")ejel(n)Prc(t — rt — nTc) (2.1) n [:1 where p,c(t) is the composite chip waveform (including both the transmit pulse shaping and receive chip-matched filters respectively) which has a raised-cosine spectrum. Nm is the total number of multipaths with or, is the attenuation of 1’” multipath and at-a-time only Six ous are non-zero giving rise to a six-path Rayleigh fading. For any sampling index the discrete-time fading random variables (RVs) {A1};V=”'1|,, are equal power and independent of each other. RVs belonging to a common multipath () represent the envelope of a complex Gaussian process with unit variance in each quadrature component and are cor- related. In (2.1) RVs {OJ-(n)};‘i_’fl are the phases introduced by the fading phenomenon and are assumed uniform over [0, 21:) and independent. This fading process is considered sta- tionary within each data frame (i.e. Doppler spread does not change within a frame period which is 10 ms for UMTS) and the first-order probability density function of its envelope is given by f1. (x)lt = fillet...) (x) (2.2) such that E [14,2] 2 2. Here, [,4 (x) is the indicator function whose value is one when x E A and zero, otherwise. {1,}[21 represent time delays of various multipaths and for simplicity are assumed to be constant throughout each data frame and also restricted to be integer 19 multiples of chip period (Tc) with maximum multipath delay is no more than 10 chip peri- ods (i.e. N = 10). The power spectrum of either the real or imaginary part of this fading process is modeled by Jakes spectrum [15] S(f)= ”M” :W lf|< (2.3) 0 elsewhere where fm = (1)," / (1)5 is the maximum Doppler frequency normalized by the sampling rate (4),) and the parameter 4),, is the maximum Doppler frequency in Hertz, given by q)”, = v/A, where v is the vehicle velocity in meters/second and A is the carrier wavelength in meters. The discrete-time autocorrelation function of this fading process is given by 10(21tfmldl) [1 l], where Jo(-) is the zeroth-order Bessel function of the first kind and Id | is the sample separation. The method provided in [20, 34] is used for the generation of (2.1). The channel model in (2.1) is reasonable for simulations as it defines the worst case scenario for space- time fading that might occur in a real environment [26]. In light of analysis presented in [26] we assume the channels seen by different receive antennas to be uncorrelated with each other. The arrival times at antennas 1 to M associated with the given BS are the same but the channel coefficients are independent. 2.2.2 WCDMA Downlink Signal Structure The mulituser chip symbols transmitted by the k” BS, are given by —l 1 k)[n]_ Cbsk)[n]2;1N:0 mbgkw k(n_1vjm) (2.4) J: "I: where various terms are defined as: k is the BS index; Cg) is the k’h BS’s long scrambling code; Nék) is the number of users served by BS k; N3,- is the k’h BS’s j’h user’s total number 20 of data symbols; N j is the k’h BS’s j’h user’s spreading gain; by) is the 16" BS’s j’h user’s data/symbol sequence; and W} is the k’h BS’s j’h user’s channelization code (Walsh code). In (2.4) the normalization by the factor J17] means that during a burst, the chip energy is different for different spreading factors and that the energy per symbols is the same for all users even if the symbol duration is different. In the analysis presented in this paper we assume that each BS has one transmit antenna. If the mobile station receives K BSS, then the received burst at I” antenna of this mobile station may be written as Ma 2s") [n]h(") (t—nn) +n(t) (2.5) k n l where n(t) is the additive Gaussian noise which is assumed to be white with power Spectral density N0 / 2 prior to colorization by chip-level matched filter. When the mobile operates in the ”soft hand—off” mode, (2.5) is used to derive the chip—level estimators. When the BSs other than that of interest are treated as interference then (2.5) can be represented in a more convinient form with kd denoting the BS of interest. 25(kd)[n]h§)(tkd —nT) 22$“ )[n]h(k) (t—nT) yt(t)= "—,,___.« + km" Y - +n(t) (2.6) signal of interest co-cell interference In our analysis we restrict ourselves to the case of two BSs (K = 2) and in practice maximum three BSS will be received [16]. We assume two receive antennas; extension to the case of more than two antennas is straightforward. We use M to denote the total number of chip-spaced channels due to antenna diversity and/or over-sampling. In our case M will take maximum value of 2. Further, the received signal-to-noise ratio (SNR) is defined as Eb/No where Eb is the desired signal energy received per data bit, which is assumed to be the same for all the bits of all users and N0 is the power spectral density of incident noise. 21 In the case of ideal AWGN channel and absence of co-cell interference above definition of SNR will cause each CDMA user to achieve the theoretical QPSK BER. 2.3 Adaptive equalizers First we conveniently represent the signal vector and channel matrices in the dimensions of equalizer length Ng- With larger Ng performance will be better as the MMSE solution has more degrees of freedom though with increased computational load. The received signal in (2.6) is passed through chip matched filters at different receive antennas and accumulated in a vector y[n] = [y] [n],y2 [n], . . . ,yM [12]] of length MNg x 1, where subscript on y denotes the antenna channel and n denotes the time index or sample index. Though individual vectors y;[n]s (length N3) are obtained through independent multipath channels, they are inherently correlated because of their common source and the combine MMSE solution is essential to benefit from space-time diversity. Using the same notations as in (2.5) we can express y as: y = 2H(k)s(k) [n] + n[n] (2.7) k where k is the BS index, s(k)[n] = [5“) [n],s(k)[n — 1],. . . ,s[1vg + L — 1]] (2.8) and Hfi") I Hl") = g (2.9) Hf]? 22 where h§k)[0] 11$")[1] h§k)[L—1] 0 o (k) (t) o h. 1 h. L—l o o HEM: I I] I I I (2.10) o o -- '- o o o Wm] hfklm kWh—1] is the channel convolution matrix of size Ng x (Ng + L — I) experienced by 1” receive antenna due to k’h BS. In time varying channel this matrix also takes time varying form however with a reasonable assumption that within time slot of length O'C it does not change. 2.3.1 Space-Time MMSE chip-level equalization The chip-level equalizing filter obtained by MMSE criterion provides the delayed esti- mate of synchronous sum signal pertinent to the k’h BS, i.e. 50‘) (n — D) = g(k)”y[n], where the filter go‘) is obtained by solving the unconstrained optimization problem: gm 2 argmé'n E[|g(k)H(ZH(k)s(k)[n] + n[n]) — 80s“) [n]|2] (2.11) k where SD is a vector of length (Ng +L — 1) with all zeros except for unity in (D + 1)” position. The basic philosophy of MMSE equalizer in this case is to partially restore the lost orthogonality among synchronous sum signals while not allowing for too much of noise gain. These equalized chip samples are further used for descrambling and despread- ing (using cell-Specific long scrambling code and OVSF channelization code respectively) followed by summation to arrive at the soft estimate of transmitted symbol sequence b", i.e., A k) (n+1)Nj k) bj. [n]: 2 C§s*[i]w;(1—nN,-)§[1—D] (2.12) 1::an 23 where (-)* denotes complex conjugate operation. Solving (2.11) is a state forward exercise and we readily obtain: g“) = C“‘H""50 (2.13) The correlation matrix (C), which is a positive-definite hermitian matrix, can be estimated by time averaging as: C(n) = Oty(n)yH(n) + (1 — Ot)C(n — l) (2.14) where or is a small forgetting factor balancing the past and the present signal information. In (2.14) no channel knowledge is needed for estimating C, however channel estimate has to be obtained for channels pertaining to the signal from k’h BS for (2.13). If channels from all the base stations can be estimated, one may take an alternative but more efficient approach for estimating C. In (2.4) the channelization code matrix (W) is orthogonal and the data sequences {bn} are assumed to be i.i.ds. Further, we can model the BS dependent scrambling code (Cbs) as a sequence of uncorrelated RVs, which is a reasonable assumption in practice. In the light of above assumptions we have chip-level symbols in (2.4) as i.i.ds, i.e. E (s(")s(")” ) = 631, where o, is the power of chip-level symbols. Then one may obtain the correlation matrix (C) in (2.13) as C 2 63211001100” + 0,211 (2.15) It Further, in [16] it was suggested to minimize (2.13) also as a function of delay D. The delay yielding the smallest MMSE can be computed by optimizing the following equation. MMSE = 1 — SDH(")”C“H(")SD (2.16) 24 2.3.2 Time varying form of MMSE equalizer In time varying channels MMSE equalizer (gMMSE) also changes with time and the equalization structure has the added task of tracking the MMSE solution. One possible approach to this problem is to employ Least Mean Square (LMS) types of algorithms with CPICH based training as suggested in [10]. Due to their limited tracking capabilities and lesser allocation of total signal power (10%) to CPICH in 36, such adaptive algorithms inevitably fails in very fast changing channels. In [24] adaptation is carried out in the ”Decision Directed Mode” which significantly enhances the performance . But such an ap- proach dictates the additional burden of knowing all the active user codes and hence limits its applicability in the typical 3G scenario where such a knowledge is not available. Rather more obvious solution is the frequent updation of the correlation matrix followed by direct computation of gMMSE according to (2.13). However, the direct implementation of (2.13) requires one inverse computation of a matrix of size MNg x MM, and hence presents pro- hibitive computational complexity. In fact, Conjugate Gradient (CG) method which avoids the direct estimation of C“1 can be applied to this filtering problem to obtain the near same performance of MMSE equalizer in (2. 13) with manageable computational complexity. 2.3.3 Conjugate Gradient Algorithm based MMSE Solution We can write the cost function (2.11) and the MMSE equalizer expression (2.13) in a more convenient form: 0? gut) = mg"? %g(k)HCg(k) _5DH(k)Hglk> + 7 (2.17) CgU‘) = HWSD a H(")(:,D) (2.18) The CG method is effective for solving the quadratic optimization problems of form: f(x) = éxTAx —bx+c (2.19) 25 Noise variance Scrambling 8- . and Spreading code ' Channel Estimation generator Correlation matrix estimation and Filter update usinngGA y] 4 . > g —.\ + I I ' I Correlator A" yM _—H ......................... ...> g bj Figure 2.1: LMMSE receiver using CGA algorithm: (1) Form various antenna channels- matched filtering and sampling (2) Channel and noise power estimation (3) Correlation Ma- trix computation and LMMSE filter update based on CGA (4) Filtering using time varying filters (5) descrambling and despreading. where A is a matrix, x and b are vectors and c is a scalar. One can show that if A is herrrritian and positive-definite then f (x) is rninirrrized by solving the linear system of the form Ax = b. This suggests the immediate applicability of CG method to the optimization problem in (2.18). Given the correlation matrix C and the D-shifted channel vector b = HU‘) (z, D), the CG algorithm is applied to solve (2.18) iteratively at each 1’” slot. Let [i] denote iteration index, vector r[i] the residual vector and d[i] the current search direction vector used in updating 26 the iterates and residual. The following algorithm is repeated for N iterations. Initialization: r10] = b—Cglk’IOI d[0] = r[O] 8mm. 2 r[0]r[0] 80 = 8new For i=1,2,...N. Do: quI = Cdli-ll a _ 5,... _ (iii-110111 gf")[t'] = gf"’[i—1]+ad[i—1] STOP if i==N r[i] = r[i-ll-Cgi")lil 8old : 8new Onew = r[1]r[z] SneW B 2 5old d[i] = r[i]+[3d[i—l] 2.3.4 Convergence of CG algorithms in CDMA The CG algorithm is guaranteed to converge in 11 steps (in our case n is the length of the equalizer) and converges more quickly if the eigenvalues of the space-time correlation matrix C are clustered together than when they are irregularly distributed between 1mm and AW. However, in our case the exact solution of (2.18) is seldom demanded and algorithm is stopped within few iterations << n and hence the speed of convergence becomes crucial. 27 The convergence properties depend on the spectral condition number of the signal correla- tion matrix C, defined to be k = Amm/Amin. The error term at each iteration of the CGA is given as [25]: fl—I i i|e(i)“A S (W;+1 Ile(o)||A (2-20) where cm is the error vector at the i‘h iteration of CG and “e” A = (eAe)5 is defined to be the energy norm of error. In the case of multiple receive antennas the space-time correlation matrix C may have a large eigenvalue spread which dampens the speed of convergence. Then preconditioned CG method can be used, which acts by improving the spectral con- dition of the linear system in (2.18), however with added computational complexity. In a typical low SNR scenario the condition number of C is usually lower due to the added weight on its diagonal ( please see (2.15) ) and hence convergence is faster. One can in fact solve (2.18) for lower SNR value than actual one to improve the convergence speed but this would be a degraded MMSE solution and a trade-off is desired. This issue is discussed in more detail in the simulations section. We also observe during our simulations that the use of equalizer estimate from the previous ( (l — l)”' ) block as the initial guess of g(") in (2. 18) improves the speed of convergence significantly. 2.4 Soft Hand-off Mode Soft hand-off is one of the most attractive features of CDMA, which eliminates the frequent switching of mobile receiver between two BSs when it is on the edge of two cells. For soft hand-off mode, the desired user’s data symbols are modulated onto one of the channelization codes at each base station. Generally two base stations are involved in the hand-off procedure and here we denote them by l and 2. While operating in the soft hand-off mode two equalizers are designed at the mobile receiver, one for each BS. In the soft hand-off mode, both s(')[n] and 8(2) [n] (please refer to (2.4) ) contain the useful 28 information for the user Uk. In the context of chip-level equalization we attempt to estimate chip sequences S(‘)[n] and S(2)[n] corresponding to base stations 1 and 2 respectively and while doing so each equalizer treats the BS other than that of its interest as an interferer. The equalized chip-level signal available at the output of both the equalizers are further descrambled by BS specific scrambling code (C31,) and appropriate channelization code (Cch) to generate two symbol-level soft estimates: [3|[m] = a1b1[m]+m (2.21) I32[m] = (12b2[m]+T]2 (2.22) where, a1 and a; are the effective scaling factors experienced by the original symbols and m and n2 is the MUI still left due to partial orthogonality restoration. Later, these two es- timates are optimally combined in the LMMSE sense to produce the eventual soft estimate of desired user symbol h[m] = A] h] [m] + 3.2132 [m] where his are the optimum weights that minimize the cost function: E [12»le [m] + A282 [m] - b[m]|2] (2.23) The composite channel formed by the convolution of channel and equalizer and summed together is treated as a time invariant SISO (single-input single—output) FIR system of length L +Ng — 1 in any 1’” block. Let this impulse response, for the channel between the q’h BS and the equalizer tuned to the k’h BS’S channel, be denoted by hi3,” [n] similar to the notations used in [16]: k M L-l k 125% )[n] = 2 Z 12$")ng )*, n = 0,...,L+Ng —2 (2.24) i=1 [=0 . 29 Further, this composite response is decomposed in a delay D term and an ”181” term be- cause MMSE does not try to attain the perfect equalization. 1181;") [n] = 115.3") [D]5[n — D] + i235") [n] (2.25) One can in fact use (2.25) and (2.4) to derive the following: a, = 2 Nchfig’)[D] (2.26) at = 2Nc(2||5§2i)lnll|2+2|lh££i>lnl||2+g"’”R,mg“)) (2.27) where, i,j = {1,2} with i 3e j and Oi, = E[|7l.,-|2]. And optimum weights in (2.23) are given by: A] _ l 010%2 (2 28) 7»2 (“I + Oil ) (a2 + (5%,) — (61102)2 “26%. ' I For detailed derivations one is referred to [16]. In time varying channels the optimum weights are needed to be updated in each 1’” block. In (2.22) A] and M are not independent in strict sense but with heavily loaded spectrum and i.i.d scrambling codes, their correlation may be ignored in practice. While computing the equalizers ”tuned” to BS 1 and BS 2 the correlation matrix C can be shared. However, solving (2.18) for k = 1,2 is necessary. A soft hand-off mode receiver which minimizes the required computations is diagrammed in Figure 2.2. 2.5 Channel Estimation The Singleuser channel estimate obtained by despreading of CPICH is further refined by least-square (LS) filtering. Here, LS filtering acts as the optimal curve fitting mechanisam 30 \ (l)H O I g1 . . . : . /® Correlator 1 I; . (l)H ' l > gM f A . E ; Equalizer tuned to BS#1 : Y1 _ ‘ A . + . Correlation matrix update, channel Scrambling 8. MMSE b : : estimation, Noise variance estimation e - . Spreading code combiner _. and filter update using CGA generator YM H T A i E \ (2 )H t r , gl —\‘ - : i <9 Correlator 2 A - (21H ' b - > gM / 2 Equalizer tuned to BS#2 Figure 2.2: LMMSE receiver using CGA algorithm operating in soft hand-off mode. De- sired user data is transmitted by two base stations - BS] and BS2. 31 over the samples of Singleuser channel estimate. The modified channel estimate is [8], l h: P 1+22p=1xp (Apfip_P + . . . + Alfipq + 6P + A113,,“ + . . . + Apfip+p) (2.29) where hq, q = p — P, . . . , p + P is the Singleuser channel estimate over the P-th data block +1 L —l . * . . . . . . computed as: fiEE-(lquivw r[JISCPICHI-II r[J] = [yl(1)...y/t,(})]T and sap/cub] Is the j-th chip of CPICH. The channel estimates of the central block p are calculated by using sliding window over the 2P + 1 blocks surrounding p. The optimal weights minimizing the estimation error in the LS sense are obtained by optimizing the following cost function: e = Z ||hp(1.1,...,i.p) — 13an (2.30) p The solution of (2.30) is obtained as: A: [A]A2...AP] = (9i{AHA})_'SR{A”w} (2.31) where, A is the data matrix given by: A: [11_1+1”11 —2ho,...,h_p+hp—2ho] (2.32) and w = (h1— h,) (2.33) For detailed derivations one is referred to [13]. ho is the channel impulse response averag- ing over the central block (p = 0). In practice, this quantity is not known making the on-line computation of (2.31) unrealizable. One possible way out of this is to perform Monte Carlo simulations to obtain the sub-optimal solution. This leads to a filter of length 2P + 1 that in average minimizes the (2.30). Despite being a sub-optimal solution this filter performs 32 very well. These sub-optimal weights also depend on the velocity (doppler frequency) and filter-length (P). This LS curve fitting approach dramatically improves the second order statistics of channel estimates and proves to be of sufficient quality in acheiving the BER close the perfect channel knowledge cases, especially in the SNR range of g 10 dB. 2.6 Complexity Analysis The receiver involves mainly four types of operations: (i) channel estimation (ii) equal- izer design (iii) channel equalization (iv) despreading. Below, we tabulate the reciever complexity in terms of combined multiplication-addition operations per information sym- bol. Function Operation Complexity Channel estimation K x M x L x G, x Sl/Scoh Construction with inverse 0((MNg)3) /Scoh Construction with CGA n x 0(M x Ng x L) /Smh Equalization M x (N8 + 1) Despreading M x G, Table 2.1: Complexity per Information Symbol For convinience some of the notations are repeated again. Here, M is the number of receive antenna diversity and K is the number of BSs included in the signal processing. L is the number of multipaths and N8 is the equalizer length. Gs is the spreading gain per symbol. Sm), is the number of symbols for which the channel is assumed to be invariant. S, is the length of LS filter used for optimum curve fitting. The CG equalizer reduces the cubic complexity of LMMSE equalizer with direct inverse to the linear complexity with the number of non-zero elements of C. 33 2.7 Performance Evaluation A WCDMA downlink similar to the one specified in 3’d generation partnership proposal of spreading and modulation [1] was simulated. The transmission is considered at the chip rate of 1 /Tc = 3.84 MHz and baseband simulations are performed. The data symbol for each user is QPSK as specified in 3G [1]. Power control for each user is practiced in such a way that the energy per QPSK symbol and so energy per bit (Eb) for all the users is the same and hence all users are provided with equal quality of service (QOS). Our choices of various parameters pertaining to 3G WCDMA downlink are: e For the channelization codes, we use Walsh codes with arbitrary spreading factors [4,8,16,...] similar to ones defined in [1]. However, the codes are selected in such a way that no other codes lie in the path from any of the code to root (i.e. OVSF codes). Such a choice of channelization codes give rise to the VSF multirate CDMA. In some of our simulations we choose all the user codes to be of equal length (of length 64 unless otherwise mentioned) corresponding to multi-code CDMA (MC- CDMA). We also compare the VSF-CDMA technique to MC-CDMA technique in the almost identical spectral loading and multipath fading scenario. 0 Each BS specific scrambling code (C51,) is a Gold code of length 218 — 1 chips trun- cated to 38400 chips which corresponds to a radio frame of length 10 ms. All the users of the same BS are synchronized and share the same scrambling code. The Gold code is generated by modulo 2 sum of two m-sequences constructed using the primitive polynomials (over GF(2)) 1 +X7 +X18 and 1 +X5 +X7 +X'0 +X18 one for each. Each BS chooses a scrambling code number different from other 38s. 0 Each chip sample of synchronous sum signal is pulse shaped using a square root raised cosine filter of roll-off factor (beta) 0.22. At the receiver the same root raised cosine filter is used as chip matched filter. In order to perform accurate chip matched filtering an over-sampling factor of eight is used. 34 e The pulse shaped chip-level synchronous sum signal is passed through a channel similar to the ITU recommended Vehicular A channel. For the simplicity multipath delays are chosen to be the multiples of Tc. The channel tap weights are generated using the IFFI' method given in [20, 34]. A typical power delay profile we use in our simulations is given in the Table 2.7. In all the results presented we use six paths and all of them are estimated while performing channel estimation. The quality of generated Rayleigh fading samples is thoroughly checked using the autocorrelation method given in [34] (please refer to channel model section). Each antenna channel at mobile receiver is assumed to be independent of others but with the similar power delay profile. We use carrier frequency of 2.15 GHz and the mobile speed of 120 kmph, which translates to the Doppler frequency of 238 Hz. Tap delay(chips) Average power (dB) 1 0 -4.0 2 l -7.0 3 2 -7.0 4 3 - 10.0 5 4 -10.0 6 5 - 13.0 Table 2.2: Channel parameters for simulations 0 The code-multiplexed CPICH contains 10% of total transmitted power. The CPICH has a constant spreading factor of 256 and all one channelization code. All the CPICH symbols are 1 — j. Below, we first provide our results for channel and noise power estimation. This is fol- lowed by the discussion of performance in various scenarios of different interference levels. Here, different types of plots are provided: (i) the spectral load is fixed and noise power is varied (ii) improvement in SNR with the channel estimate quality and equalizer length (iii) 35 improvement in SNR varying CGA iterations. Results presented here are averaged over 100 different channels for an arbitrary user with specified code length. 2.7 .1 Channel Estimation Accuracy All the channels between i’h BS and j’h antenna were estimated using the CPICH based estimation method described in section 2.5. In the case of two BSs total of four chan- nels are required to be estimated (2 corresponding to each of the two receive antennas). In the case of no inter-cell interference only two channels need to be estimated. All the active paths of a channel are estimated and perfect chip delay knowledge is assumed. The block Size to derive single user channel estimate is selected as 256 chips which is also the length of the channelization code for CPICH. This single user channel estimate is further filtered by a symmetric non-causal filter of length 15 (please see section 2.6). The optimal filter taps for the mobile velocity of 120 kmph obtained by Monte Carlo simulations are: it = [0.22,0.28,0.39,0.56,0.69,0.8, 0.89, 1] . The tracking behavior of the channel estima- tion algorithm for the two different SNRS lOdB and 20 dB is provided in the Figure 2.3 for all of the taps of a typical six-tap Rayleigh fading channel (120 kmph) generated for a lOms long WCDMA data frame. The statistical quality of the estimated channel samples can be evaluated by the direct comparison of its autocorrelation with that of the original channel. The theoretical autocorrelation (please see section 2.2) and estimated autocorre- lation corresponding to the same fading envelope in Figure 2.3 are given in the Figure 2.4. The single user channel estimate, which is inherently MUI limited, is tuned by the filter in such a way that at the output of the filter it approximates the autocorrelation of original channel as close as possible. With better SNR this property improves. However, it was observed during the Simulations and as will be explained in the later sections, this channel estimate at low SNR is of sufficient statistical quality to achieve the desired performance in MMSE sense. This in fact suggests that the performance is more governed by the noise than the imperfect knowledge of the channel in the low SNR regime. 36 0.9 0.8 O .7 .0 or Path Gain .0 - - Estimated —' Original 0.004 Time (second) (a) .0 Path Gain .0 - - Estimated — Original Figure 2.3: The performance of CPICH based channel estimation in fast fading channel. Parameters are: (a) CPICH power—=10 dB of total power, SNR=10 dB, Tap powergains= [-4 -7 -7 ~10 -10 -l3]dB (b) CPICH power=-10 dB of total power, SNR=20 dB, Tap pow- ergains= [-4 -7 -7 - 0.008 0.006 Time (second) (b) 10-10-13]dB. 37 \ T I I . . .\ '- " ESIINIBIIOO 't ~—- Theoretical \ -. I a“ \ .\ ." 0.5 " \ 1 .. .‘ ,2 8 ". g. ‘-\i ’/ \ I ‘ ,_ E “y // \ I") ."\. /// \\ ‘1“ // \k\' I Pry \ O ’ ‘ / I \ / \ \ ;, \‘. / \ " \ I “‘ I \ / ‘ 1‘). ‘1 I I \\ / \‘t 1‘ I \/ Q“ ,I' I )‘x / I” \f / ,' _o.5 1 1 1 L 0 0.002 0.004 0.006 0.008 0.01 Time index (seconds) (a) 1 U r r l 1 - — Estimation ((1 --—-—— Theoretical \‘a .\ “q 1. ‘ “l I. 0.5 r \ Amplitude \ \ i I A ‘. .\ "t / \\ // \\ ‘. I) I" // \‘ \ / ’ . — . ~ \\ o. t . / s ,4» I \ 1' \\ _/ ‘.\ '1‘ j '1 ~\\\ [5/ \ \ II/r’ \_ \\\'_,,’/ \ I r \ \\ .. 4" ‘. I -0. 5 4‘ ’ I 1 1 1 0 0.002 0.004 0.006 0.008 0.01 Time index (seconds) Figure 2.4: The performance of CPICH based channel estimation in a fast fading channel in terms of autocorrelation among channel samples. Smaller difference between the estimated and theoretical autocorrelation represents the superiority of algorithm in statistical sense. Parameters are: (a) CPICH power=-10 dB of total power, SNR=10 dB, Tap powergain= -4.0 dB (b) CPICH power=-10 dB of total power, SNR=20 dB, Tap powergain= -4.0 dB. 38 2.7.2 Without Inter-cell Interference In this scenario the user of interest is assumed to be near the BS and the inter-cell inter- ference is negligible. Two antenna system with no over-sampling is used. The case of heavy spectral loading is analyzed in greater detail. Figure 2.5 provides the BER performance for both saturated and lightly loaded CDMA scenario. Two different equalizer lengths are evaluated (N8 = 11 and N8 = 31) as the representative of short and long equalizer classes respectively. Results for two cases, the perfect channel knowledge and estimated channel, are presented. The MMSE receiver implemented with direct inverse computation uses the optimal delay that minimize the MSE but the CGA implementation conveniently chooses the delay (N3 + 1) / 2. The long MMSE equalizer with the perfect channel knowledge provides the best per- formance as expected and serves as the benchmark for the other equalizers. However, all the equalizers (Rake is not included) achieves BER of S 10‘4 at the SNR of 20 dB. In the low SNR regime (S 10dB) all the equalizer perform very close and channel estimation error does not cause much of a degradation in the performance. Even the CGA equalizer with 2 CG iterations converges fairly and provides close performance to their direct ma- trix inverse counterparts (MMSE). This in fact may be explained as follows: In the low SNR regime the channel estimation errors are not the significant source of performance degradation, rather noise becomes critical. The high amount of AWGN noise increases the diagonal weight of the correlation matrix C. This causes the precondition number of C to go down and speeds up convergence and hence CGA equalizer with just 2 CG iterations achieves very close performance to the long MMSE equalizer. In Figure 2.7.2(a) the improvement in SNR for a targeted BER while going from the short CGA equalizer with channel estimation to the long MMSE equalizer with perfect channel knowledge is plotted. With targeted BER not less than 10‘3 all the equalizers pro- vides the similar performance. However, with lower and lower targeted BER either better 39 channel estimate and more iterations of CG (with short length) are needed or the equal- izer length has to be increased. The correlation matrix C has higher precondition number with shorter equalizer length and hence either increase in equalizer length (which actually causes the precondition number of C to go lower) or more iterations of CG becomes nec- essary. In a lightly loaded scenario ( Figure 2.5(b) ) both MUI in the channel estimate and the precondition number of C are lower and even a short CGA equalizer with channel esti- mate achieves nearly the same performance as the long MMSE equalizer with the channel knowledge. The Rake receiver inherently suffers from MUI in heavy spectral loading. However performance improves when the spectrum is lightly loaded. While in the case of MMSE and its derivatives (including CGA) the degradation with increased load is relatively less. Hence in both the cases the i.i.d sequence assumption for the scrambling code in (2.15) is proved to be valid. 2.7.3 With Inter-cell Interference In this scenario the mobile is assumed to be near the boundary of the cell and receives two equal power signals from two BSs. Results for both the saturated cell and lightly loaded cell are presented in the Figure 2.7.3. In both the cases the Rake receiver’s performance fattens out at high SNR due to the MUI. This effect is more severe when many users are active; the BER lower than 0.1 is not achievable even in the case of lightly loaded cell. In the range of SNR g 10dB all of the versions of MMSE and CGA perform very closely and maximum achievable BER is near 10’2. However, with increase in SNR the equalizers based on channel estimate starts performing inferior to their known channel counterparts. In the Figure 2.7.3(a) the gain in SNR for a targeted BER, while going from short CGA equalizer with channel estimate to the long MMSE equalizer with the perfect channel knowledge is provided. The SNR gain increases exponentially for all the ”long” equaliz- ers and suggests the criticalness of equalizer length when both inter-cell and intra-cell are 40 Average BER sw‘reesshortrhknhwntrtii- ‘ . *- ~ : e. CGAIcn‘g:hl‘5 . . . . .‘ 34;: 32" dQGAisfiottthmwMfii) ,. " ‘ ' ‘ “ " ., i'c I.CGAIoTtrg.-..hkncwniin1) . . 1" _3 -+ CGA short hestimated (n1) ‘ " 10 ._ .CGAlqagJ- hestmate¢(nt) , . a; ' 3:2 ‘4’ CGASW" 0030mm.“ ([12). ' ' ‘E '4 CGAshort hknown (n) ‘_ . . _ 10-4 ° CGAlon -hknown_ (n2) _ ., _ . .. 1'9¥*CGA[009 most-111mm”) ‘ , E- i? -3 v MMSEshort--h . ., y .: :33 - ~ —9— MMSEiong hknown 10'5 »+RAKE hknown . Fe—MMSEfihb'rt-h'est: "3 .' . , -. :.—,.— MMSEb'ng‘I—h'egfim'fihd, g ' 4'— RAKthesnmatea' . ~ 1 10—10 -5 0 15 SNR(dB) (b) Figure 2.5: comparison of various detection methods in terms of average BER performance vs. SNR(dB): (a) heavily loaded spectrum; [1, 2, 4, 6] number of user codes corresponding to the lengths [4, 8, 16, 32] are active, (b) less loaded spectrum; [0, l, 2, 2] number of user codes corresponding to the lengths [4, 8, 16, 32] are active. n1 and n2 correspond to 2 and 4 iterations of CGA respectively. Short and Long correspond to the equalizers of length 11 and 31 respectively. The cases of channel estimated and channel know are marked with hestimated and hknown respectively. MMSE and CGA denote mmse equalizer implementation via direct matrix inversion and CGA method respectively. 41 "'iims'uoétfiheettotated T777777 " T . CGALoneheshmated i'iir'fi- 2 -;:i ? 5 :30- CGALonghknown ‘5 ".f " ‘f : f‘ j‘j:j§ . ‘ + MMSE Long hknown; " . : g 3 -, 4 + MMSEShorthknown .gtr . 3 ..;.;..-..;_ .3 .4 .. a ceAsrtonhImown; g 3 /; U a??? s “‘r-ir ‘ 05:30: ’ “ 524'?- . g 314?? .. 2+3 :-:~ 0 .32 01" -t _2 .0; A A ; A L A l:;.. A A A . Iii. ; - L A A 1:23; A - A - A .4 10 10 10 10 10 TergetedBER (a) 377"7YI I IIYIYYIY Y IIIYITI I I IIIIIY.’ I ; 3 sCGA4Iterations- ahestimated ; ; ggggggg ;) 2.5.3 + 0684mmtrons hknown .2 ..;;;.§; 3' ,t: , i""CGA2IIOt3IlOflS hknown } : A 2i? ' ' 31.5": ' .._. ‘1 :3 f " 5 1... 3g ,. - 5 §? 371i i §O.5". g if i623 i E 0*? [5'23 9- 0 -. :::~: ; -0-5~i: :iéa +7 . _1.5;..1;;. 1;-.. .. ; $.41. ; :11--- 1. 10° 10'1 10'2 10" 10" TargetedBER Figure 2.6: SNR gain obtained by various detection methods in a heavy spectral loading scenario (both with channel estimation and perfect knowledge) at the targeted BER com- pared to short (Ng- — ll) CGA equalizer with channel estimation and 2 CGA iterations: (a) Comparison of matrix inversion and CGA method. When the targeted BER rs < 10 3 the short CGA equalizer with channel estimation is within 2 dB range of MMSE equal- izer with matrix inversion and perfect channel knowledge. (b) Comparison as a function of CGA iterations and channel knowledge. With estimated channel 2 iterations are suffice for any targeted BER. At very low targeted BER the channel estimation becomes crucial. Minimum 4 iterations are required with pefect channel knowledge with very low targeted BER 42 present. In the Figure 2.7.3(b) the gain in SNR for CG iterations is given. Combine in- terpretation of Figures 2.7.3 (a) and (b) advocates the necessity of ”long” equalizer and/or better channel knowledge. 2.7.4 Soft Hand-off Mode In the soft hand-off mode two long chip-level CGA equalizers based on channel esti- mate and channel knowledge are designed as shown in the Figure 2.2. The symbol esti- mates at the correlator corresponding to each of these equalizers are further weighted and summed to obtain the final symbol estimate according to the method developed in section 2.5. Figure 2.7.4 the average BER curves for these CGA equalizers in soft hand-off mode to the ones in the inter-cell interference scenario. A clear SNR gain of 2 10dB can be observed for both the heavy and lightly loaded cells. For the CGA equalizers operating in the soft hand-off mode BER of z 10'3 with moderate SNRs becomes achievable. 2.8 Conclusion The problem of CDMA downlink space-time equalization for the mobile receivers in very fast fading wireless channels was considered. The prohibitive computational com- plexity presented by the direct LMMSE solution, due to the matrix inversion involved, was avoided by the CG algorithm based implementation of LMMSE chip-level equalizer. A novel channel estimation scheme, based on the refinement of the CPICH single user channel estimate, was developed and incorporated in the CGA equalizer implementations. Performance bounds in the practical scenarios where, channel estimation errors are difficult to avoid, were derived via computer simulations and compared to the ideal LMMSE solu- tion with perfect channel knowledge. The convergence of CGA algorithm was shown to be dependent on the preconditioned number of the received signal correlation matrix. Based 43 Average BER .' .: '::.:' : :t ..*. I CGAShort.-Qhknown.(n1). . , f \ ........ '1’: CGA'I . -..hknown . , . ,, -z -3 CGA short-hestimated (m), 10 f .;°>-' Mlqwsimtimatfids5(n?):3;;'Iev-- -- “ . a»: -.- ' ;» :---;, ;-u- cummimrimataqinzy. :. 3‘ 3'::3 3’ -. CGAshortv-hkriown (””52). .' .' ' . Average BER v ’CGAIO‘n’g-‘hknown '(n2) ' ' ' 4;, +-‘CGA;|om'-”hestimated(n2) ,. ,. . ....... . 104. *7 MMSE short.- hlsncwn. ,. , 3’ “Q“‘MMSEIbng'fhW :,',:3 ',: ’ . «h. . — m. , . —9— MMSEs'hOrt -.he'st. ' . . + MMSEJong - hestimated. . + RAKE - hestimated -10 -5 swims) (b) Figure 2.7: comparision of various detection methods in terms of average BER perfor- mance vs. SNR(dB) when second BS is an equal power interfere : (a) heavily loaded spectrum; [1, 2, 4, 6] number of user codes corresponding to the lengths [4, 8, 16, 32] are active, (b) less loaded spectrum; [0, l, 2, 2] number of user codes corresponding to the lengths [4, 8, 16, 32] are active. n1 and n2 correspond to 2 and 4 iterations of CGA respectively. Short and Long correspond to the equalizers of length 11 and 31 respectively. The cases of channel estirrrated and channel know are marked with hestimated and hknown respectively. MMSE and CGA denote mmse equalizer implementation via direct matrix inversion and CGA method respectively. The maximum achievable BER is in the range of 10‘3 with perfect channel knowledge and long MMSE equalizer. 44 Difference in SNR (dB) Difference in SNR (dB) 3‘0 3 MMSE Long hestimated -~ CGA Long hestimated ’ ’-T&’- CGA Long hkno Mn 9 ‘9‘ MMSE Long hknown . 3h _. s1 - MMSE ShOrt hknown . . . . . . , ,. + CGA Short hknown ' l0 ‘4 O) 0| 1 b r (A, I N v _- r . At?" ' A.‘ AM" L ' C3 10 10" Targeted BER (a) 0 CGA4 Iterations - hestimated 3 e 4 CGA 4 Iterations - hknown .l _ _-0- CGA 2 Iterations - hknown A v (a) r N v 0 1 0-1 Targeted BER (b) 45 Figure 2.8: Two 883 are active and second BS is an interferer. SNR gain obtained by var- ious detection methods in a heavy spectral loading scenario (both with channel estimation and perfect knowledge) at the targeted BER compared to short (Ng : 11) CGA equalizer with channel estimation and 2 CGA iterations: (3) Comparison of matrix inversion and CGA method. At the targeted BER of z 10'2 long CGA equalizer with channel estima- tion and 2 CG iterations has performance within 3 dB range of long MMSE equalizer with perfect channel knowledge. (b) Comparison as a function of CG iterations and channel knowledge for short CGA equalizers. Channel knowledge is critical in case of short CGA equalizer. Long CGA equalizer is necessary to achieve good performance with channel Average BER 31 CGAInterierenee hknown c CGA Imerterencee hestimated 3 + Soft-Handofl‘CGA—‘nknown _5 —<'— Sofl-HahdoftCGA- hestimated ' ‘- __ -10 -5 05SNR(dB) (a) Average BER o CGAinterference- hkn ..t. . 3 CGA Interference hesttimeted + Sofi—Ha'ndoffCGA- hknown 04 —<— Sofi-Handoff CGA - hestimated 1 L . -10 -5 0 5 1.0 15 SNR(dB) (b) Figure 2.9: comparision of various CGA equalizers in terms of average BER performance vs. SNR(dB) when soft hand—ofi‘ mode is used. (a) In lightly loaded spectrum ( [0, l, 2, 2] number of user codes corresponding to the lengths [4, 8, 16, 32] are active)long CGA equalizer with channel estimation can deliver the performance of z 10". Soft hand-off mode ofi‘ers clear gain in performance. (b) With heavily loaded spectrum ([1, 2, 4, 6] number of user codes corresponding to the lengths [4, 8, 16, 32] are active) the soft hand- off mode offers almost 10 dB of gain at the targeted BER of x 10‘2. 46 on this, the interplay between the equalizer length, number of CGA iterations, channel es- timations quality, targeted BER and the available SNR was described. The CGA equalizers using the estimated channel were shown to achieve the BER of S 10‘3 or better in the case of soft hand-off mode as well as the normal operation mode. The inherent complexity- performance trade-off capability of CGA equalizers can be a valuable feature in meeting the time changing constraints of bandwidth, power and performance in mobile terminals. This research suggests that the chip-level equalizer based on MMSE criterion have a great potential of increasing the CDMA downlink capacity in the fast fading wireless channels. We advocate that the CGA based adaptive MMSE chip-level equalizer in the existing form or modified for implementation case can be the possible solution of much labored problem of multiuser detection in CDMA downlink with ”long code”. 47 MATLAB code availability A copy of this thesis and the MATLAB subroutines written as the part of the performance evaluation are made available at www.egnmsu.edu/desaikey/CDMA. Any questions or com- ments will be gladly received at desaikey@egr:msu.edu! 48 BIBLIOGRAPHY [1] 3rd Generation Partnership Project. 3g ts 25.213 v5.0.0 - spreading and modulation (fdd), 2002-03. [2] 3rd Generation Partnership Project. Overview of 3gpp release 5, June 2003. [3] S. Amari, S.C. Douglas, A. Cichocki, and H.H. Yang. Multichannel blind decon- volution and equalization using the natural gradient. In Proc. of IEEE International Workshop on Wireless Communication, pages 101—104, Paris, France, April 1997. [4] CDGORG. [5] S. Chowdhury and M. Zoltowski. Application of conjugate gradient methods in mmse equalization for the forward link of ds-cdma. In Proc. IEEE Vehicular Technology Conference Fall, October 2001. [6] R. Cristescu, T. Ristaniemi, J. Joutsensalo, and J. Karhunen. Blind separation of convolved mixtures for cdma systems. In Proc. of the European Signal Processing Conference, Tampere, Finland, September 2000. [7] R. Cristescu, T. Ristaniemi, J. Joutsensalo, and J. Karhunen. Cdma delay estimation using fast ica algorithm. In Proc. of the International Symposium on Personal, Indoor and Mobile Radio Communications, London, UK, September 2000. [8] A. de Baynast, P. Radosavljevic, and B. Aazhang. Chip level LMMSE Equalization for Downlink MIMO CDMA in fast fading environments. 2004. Preprint. [9] C. D. Frank and E. Visotsky. Adaptive interference suppression for direct-sequence cdma systems with long spreading codes. In Proc. 36th Allerton Conf. on Communi- cation, Control, and Computing, Monticello, IL, September 1998. [10] C. D. Frank, E. Visotsky, and U. Madhow. Adaptive interference suppression for the downlink of a direct sequence cdma system with long spreading sequences. Journal of VLSI Signal Processing, 30(1):273—29l, January 2002. [11] M. J. Gans. A power-spectral theory of propagation in the mobile-radio environment. IEEE Trans. Veh. Technol, VT-21127—38, February 1972. [12] I. Ghauri and DTM. slock. Linear receivers for the ds-cdma downlink exploiting orthogonality of spreading sequences. In Conf Rec. 32rd Asilomar Conf on Signals, Systems, and Computers, Pacific Grove, CA, November 1998. [13] Simon Haykin. Adaptive Filter Theory. Printice-Hall, fourth edition, 2001. 49 [14] M. Heikkilla, K. Routsallainen, and J. Lilleberg. Space-time equalization using conjugate-gradient algorithm in wcdma downlink. In Proc. Personal, Indoor and Mobile Radio Communications, September 2002. [15] W. C. Jakes. Microwave Propagation. John-Wiley, New York, 1971. [16] T. P. Krauss, W. J. Hillery, and M. D. Zolotowski. Downlink specific linear equaliza- tion fro frequency selective cdma cellular systems. Journal of VLSI Signal Processing, 30(1), March 2002. [17] U. Madhow. Blind adaptive interference suppression for direct-sequence cdma. Proc. IEEE, 86(10):2049—2069, October 1998. [18] Vincent Poor. Wireless Communication Systems: Advanced Techniques for Signal Reception. Prentice-Hall, 2004. [19] John G. Proakis. Digital Communications. MCGraw-I-Iill, fourth edition, 2001. [20] Theodere S. Rappaport. Wireless Communications: Principles & Practice. Printice- Hall, 2002. [21] T. Ristanierrri and J. Joutsensalo. Advanced ica-based receivers for block fading ds- cdma channels. Signal Processing, 82(3):4l7-43l, 2002. [22] F. M. Salam, G. Erten, and K. Waheed. Blind source recovery: Algorithms for static and dynamic environments. In Proc. of the INNS-IEEE Intl Joint Conference on Neu- ral Networks, volume 2, pages 902—907, September 2001. [23] F. M. Salam and K. Waheed. State-space feedforward and feedback structures for blind source recovery. In Proc. 3rd International Conference on Independent Compo- nent Analysis and Blind Signal Separation, pages 248—253, San Diego, CA, Decem- ber 2001. [24] P. Schniter and AR. Margetts. Adaptive chip-rate equalization of downlink multirate wideband cdma. In Proc. Asilomar Conf on Signals, Systems, and Computers, Pacific Grove, CA, November 2002. [25] J. R. Shewchuk. An introduction to the conjugate gradient method without the agoniz- ing pain. Technical Report CMU—CS-94-125, School of Computer Science, Carnegie Mellon University, Pittsburgh, PA, March 1994. [26] M. Stege, J. Jelitto, M. Bronze], , and G. P. Fettweis. A multiple input - multiple output channel model for simulation of tx- and rx-diversity wireless systems. In Proc. IEEE Vehicular Technology Conference Fall, Boston, MA, September 2000. [27] S. Verdu. Minimum probability of error for asynchronous gaussian multipleaccess channels. IEEE Transactions on Information Theory, 32(l)z85—96, January 1886. 50 [28] Sergio Verdu. Multiuser Detection. Cambridge University Press, 1998. [29] K. Waheed, K. Desai, and F. M. Salem. Blind multi user detection in ds-cdma systems using natural gradient based symbol recovery structures. In Proc. 4th lntemational Conference on Independent Component Analysis and Blind Signal Separation, Nara, Japan, April 2003. [30] K. Waheed and F. M. Salem. New hyperbolic models for blind source recovery score functions. In Proc. of Intemation Symposium on Circuits and Systems, Bangkok, Thailand, May 2003. [31] X. Wang and H. V. Poor. Blind adaptive multiuser detection in multipath cdma chan- nels based on subspace tracking. IEEE Trans. Signal Processing, 46(11):3030—3044, November 1998. [32] X. Wang and H. V. Poor. Blind equalization and multiuser detection in dispersive cdma channels. IEEE Transactions on Communications, 46(1):91—103, January 1998. [33] Stefan Werner and Jorma Lilleberg. Downlink channel decorrelation in cdma systems with long codes. In Proc. IEEE 49th Vehicular Technology Conf., Houston, Tx, May 1999. [34] D. Young and N. Beaulieu. The generation of correlated rayleigh random vari- ates by inverse discrete fourier transform. IEEE Transactions on Communications, 48(7):1114—1127, 2000. 51 uiijiiiiiiljjiijjjjijil[[11]]