Code-timing synchronization in DS-CDMA systems using space-time diversity

Co de-timing synchronization in DS-CDMA systems using space-time diversity Gonzalo Seco a ,Juan A. Fernandez-Rubio a ; 1 , A. Lee Swindlehurst b a Department of Signal Theory and Communications, Universitat Politecnica de Catalunya. C/Jordi Girona, 1-3, Campus NordUPC, D5. 08034 Barcelona, SPAIN b Department of Electrical and Computer Engineering, Brigham Young University. Provo, UT 84602, USA. Abstract The synchronization of a desired user transmitting a known training sequence in a direct-sequence (DS) asynchronous co de-division multiple-access (CDMA) system is addressed. It is assumed that the receiver consists of an arbitrary antenna arrayand works in a near-far, frequency-nonselective, slowly fading channel. The estimator that we prop ose is derived by applying the maximum likelihood (ML) principle to a signal mo del in which the contribution of all the interfering comp onents ( e.g. ,multiple-access interference, external interference and noise) is mo deled as a Gaussian term with an unknown and arbitrary space-time correlation matrix. The main contribution of this pap er is the fact that the estimator makes eÆcient use of the structure of the signals in b oth the space and time domains. Its p erformance is compared with the Cramer-Rao Bound, and with the p erformance of other metho ds prop osed recently that also employanantenna array but only exploit the structure of the signals in one of the two domains, while using the other simply as a means of path diversity. It is shown that the use of the temp oral and spatial structures is necessary to achieve synchronization in heavily loaded systems or in the presence of directional external interference. Key words: Synchronization; CDMA; Antenna Arrays; Maximum Likeliho o d Estimation; Space-Time Diversity. 1 Corresp onding author: Tel.: +34 934016431; fax: +34 934016447 2 E-mail: [email protected] c.es, [email protected] c.es, [email protected]yu.edu 3 Work supp orted in part by the Catalan and Spanish Governments under grants: CIRIT 2000SGR-00083, TIC98-0703, TIC99-0849, TIC2000-1025, FIT-0700002000-649, and by the US National Science Foundation under grant CCR-99072. Preprint submitted to Elsevier Preprint 9th February 2001 1 INTRODUCTION Multiple-access interference (MAI) is inherent to asynchronous DS-CDMA systems, since orthogonality among the users' co des cannot in general be achieved. The MAI can make the conventional detector ( i.e. , a bank of lters, each matched to a sp ecic user's co de) b ecome useless when the powers of the signals received from dierent users are unequal [1]. This is the so-called near-far problem. One alternative to overcome this problem is the use of power-control schemes. However, these schemes have some limitations b ecause they increase the overall complexity of the system, do not guarantee optimal p erformance ( e.g. , they limit the p erformance of users with go o d channels, and some MAI still o ccurs even though ideal p ower control is used), and there are certain system congurations in whichpower control cannot b e employed. Therefore, in many communications systems the use of multi-user detectors (usually, in combination with power control) is necessary in order to combat the near-far problem. The optimum multi-user receiver prop osed in [2] has been followed by a number of sub-optimum ones (see [3] for areview). All these receivers require knowledge of one or several parameters, such as the users' co de timings, powers and carrier phases. Moreover, in general the co de timing 4 needs to be estimated with high accuracy, since timing errors have a large impact on the p erformance of many detectors [4]. For these reasons, the use of near-far resistant and accurate co de synchronization techniques for acquisition and tracking is essential to achieve go o d p erformance in a DS-CDMA system. This statement is corrob orated by the suggestion in [5] that the capacity of a DS-CDMA system is limited by the ability to achieve co de acquisition. Besides, MAI is not the only typ e of interference that may be encountered. The receiver can be disturb ed by any other intentional or accidental signal, which we will represent in general as external interference. The design of synchronization techniques that are also robust against external interference is of fundamental imp ortance in many situations, such as in military or safety-critical applications. The conventional approaches to timing acquisition and tracking are the sliding correlator and the delay lo ck lo op (DLL) [6]. These schemes are only well suited for an additive white Gaussian noise channel. Extensions of the DLL which are appropriate for a frequency-selectivechannel were develop ed in [7,8]. However, these mo died lo ops are not able to combat MAI. Recently, several near-far resistant timing estimators have b een prop osed in the literature for a single-antenna receiver [9,10,11,12,13,14,15,16]. Some of these are derived from the maximum likeliho o d principle and need training sequences. Others exploit the eigenstructure of the correlation matrix of the received signals. While these 4 We will use the expressions code timing , time delay or code synchronization without distinction, since all of them have b een widely employed in the literature. 2 estimators do not require training sequences, their p erformance is p o orer than that of the ML-based ones. In [11], a large sample ML estimator was prop osed, and a comparison with many other metho ds revealed that the ML estimator is preferred for mo derate or large training sequence lengths. Its accuracy can b e signicantly improved for short training sequences using a structured estimate of the correlation matrix, as suggested in [13]. This approximate ML estimator has b een extended to the case of frequency-selectivechannels in [15]. However, the resulting criterion involves a complex multidimensional search, so iterative optimization algorithms are considered. It is well known that detection p erformance in DS-CDMA can be greatly improved through the use of antenna arrays [17,18]. Similarly, the synchronization problem can also b enet from using multiple antennas, as shown in [19,20,21,22,23]. Moreover, given the p ossible lack of temp oral structure of the external interference, the use of an antenna array is almost mandatory to achieve robustness against this typ e of interference. In this pap er, we prop ose a metho d for estimating the timing of a certain user that transmits a known training sequence. We will fo cus on co de synchronization b ecause there exist a multitude of algorithms for estimating the remaining parameters given reliable estimates of the co de-timings [24]. In fact, the expression of the ML estimates of the amplitudes and phases of the signals will be obtained as a by-pro duct of the derivation of the timing estimator in Section 4.1. We assume that the receiver consists of an arbitrary antenna array that op erates in a frequency-nonselective (or at), slowly fading channel [1]. Actually, the estimator prop osed herein could also b e used in frequency-selective channels, but we will restrict ourselves to the nonselective case for the sake of simplicity. Flat-fading channels are common in situations where the distance b etween the users and the base station is relatively small ( e.g. , in a micro cell), or when the multipath is due to lo cal scatterers near the remote user or the base station. Note that the availability of a training sequence is not a stringent assumption, since most communications systems transmit these sequences during certain intervals. Besides, once a reliable estimate of the timing is formed, the estimator can b e switched to a decision-directed mo de. The fact that the metho d estimates the parameters of only one user while retaining near-far resistance is also of interest, b ecause it leads to decentralized implementations and dramatically reduces the complexity with resp ect to metho ds that estimate the parameters of all users simultaneously (see, e.g. , [10]). Following an approach that has already been applied successfully to this and other problems, all signals except that of the desired user are mo deled together as a Gaussian comp onent with arbitrary and unknown correlation matrix. This idea has b een used for the problem at hand in [11,13,19,21,22] among others, for Doppler and direction-of-arrival estimation in radar systems in [25], and for time-delay estimation in navigation systems in [26]. An extension of [11] for a multiple-sensor receiver can b e found in [20]. However, this approach assumes 3 that the interfering signals are uncorrelated among antennas, and reduces to several single-sensor estimators applied in parallel to several indep endent channels. Hence the eect of the antenna array is only to increase the signalto-noise ratio (SNR) and provide diversityto combat the fading of the signal of the desired user at dierent antennas ( i.e. , maximal ratio combining); the array is not used to cancel the interfering signals relying on their directional prop erties. Indeed, as p ointed out by the authors themselves, the p erformance of the estimator in [20] cannot be signicantly improved by increasing the number of antennas, when for fair comparisons with single-antenna metho ds, the interference p ower is prop ortional to the numb er of sensors used in the receiver. In a slowly fading environment, the assumption of uncorrelation among antennas is not appropriate at all, b ecause the signals p ossess denite spatial signatures, as will be justied in the next section. This fact is exploited by the estimator prop osed in [19]. Nevertheless, this estimator assumes that the interfering signals are white in the temp oral domain, so only the spatial structure of the MAI is used to combat it. As a result, a prohibitively large number of antennas maybe needed to achieve near-far resistance. The signicance of this pap er lies in that we consider a space-time correlation matrix for the interfering signals, whichallows both the temp oral (provided by the co des) and spatial (provided bytheantenna array) structure of the received signals to be exploited. The benets in symbol detection of exploiting the joint space-time signature have b een analyzed thoroughly in [27]. Notwithstanding, the use of the space-time signature in synchronization is an op en issue. The metho d prop osed herein extends and outp erforms those presented in previous work. It will be shown that the use of the spatial and temp oral structure of the interference is indisp ensable in achieving co de synchronization in some scenarios, and this can be accomplished with a small number of antennas. The technique in [22] also takes into account the spatial and temp oral structure of the interference. But it considers a frequency-selective channel and is limited to estimating the overall channel resp onse, since the estimation of the time delays is computationally to o complex. This pap er is organized as follows. In Section 2, the signal mo del is intro duced. Section 3 justies the essential assumption on whichthe estimator relies and compares it with the assumptions made in related work. The derivation of the ML estimator and some alternatives to improve the estimate of the correlation matrix are presented in Section 4. Section 5 is concerned with the CramerRao Bound for the problem at hand. Finally, numerical results are analyzed in Section 6, and Section 7 summarizes our conclusions. 4 2 SIGNAL MODEL Consider an asynchronous DS-CDMA system with K users and an arbitrary receive antenna array of L sensors, which satises the standard narrow-band array condition common to many array signal pro cessing problems ( i.e. , the time required for a signal to propagate across the arrayis muchsmaller than the recipro cal of its bandwidth). We assume a at-fading channel, whichmeans that for each user the time-delay dierences between dierent propagation paths are negligible compared with the recipro cal of the signal bandwidth [1]. For this channel, the received complex baseband signal at the l th sensor is after down-conversion and chip-matched ltering (see Figure 1) y l ( t )= K X k =1  l;k s k ( t   k )+ n l ( t ) l =1 ; 2 ;:::;L ; (1) where  l;k is the complex fading co eÆcient for the k th user at the l th antenna,  k is the delay asso ciated with the k th user, and n l ( t ) represents the thermal noise and all other external interferences. Note that the signal mo del do es not presume the use of p ower control. The expression in (1) and the development b elowwould also b e valid for the received signal b efore chip-matched ltering. However, we have not considered this case for consistency with the existing literature, and b ecause dealing with the signals after ltering allows us to work with rectangular transmitted chip-pulses in a natural way [10]. The term in (1) corresp onding to the k th user's signal is: s k ( t )= M  1 X m =  1 d k ( m ) c k ( t  mT ) ; (2) where c k ( t )= N  1 X n =0 g k ( n ) p ( t  nT c ) (3) is the spreading waveform. Wehave assumed that the summation in (2) starts at m =  1 only for the sake of notational convenience in subsequent definitions. The symb ols d k ( m ) are transmitted at a rate 1 =T and constitute an i.i.d. sequence with variance  2 d . The length of the chip sequence g k ( n ) is N = T=T c , the chip rate is 1 =T c and p ( t ) represents an arbitrary chipshaping waveform. The signal is observed during an interval of M + 1 symbols ( T obs =( M +1) T ), which is the length of the training sequence. The co eÆcients  l;k include the eects of the propagation, transmitted p ower, carrier phase and Doppler frequency. Their temp oral evolution is characterized by the coherence time T coh ,which is dened as the time interval during which 5 agiven fading co eÆcient is highly correlated with itself, and is in general inversely prop ortional to the maximum Doppler frequency [1]. Since we consider a slowly fading channel ( i.e. , T coh  T obs ), for the estimator derivation wewill assume that the fading co eÆcients are constant during the observation interval, as done in many other pap ers ( e.g. ,[21,15]). This assumption is primarily for mathematical convenience, and it will be shown that the p erformance of the prop osed estimator is also highly satisfactory in more realistic scenarios. The condition for slow fading imp oses some restrictions on the length of the training sequence M and on the maximum allowable Doppler frequency.However, these are mild restrictions, which are satised by the parameters in a large ma jority of practical situations and do not represent a signicant limitation of our approach, as shown in the numerical examples of Section 7. The relevant implication of having fairly constant fading co eÆcients during T obs is that the signals p ossess rather denite spatial signatures, whichcan be used to dierentiate the desired user's signal from the MAI and external interference. It is imp ortant to remark that this prop erty holds indep endently of the statistical correlation b etween the fading co eÆcients at dierent antennas. The signals in (1) are sampled at the rate 1 =T s = Q=T c ,where Q is an integer and is referred to as the oversampling factor. Each set of NQ consecutive samples received at the l th antenna is stacked into a column vector 5 : y l ( m )=  y l ( mT + T s ) ::: y l ( mT + NQT s )  T : (4) The sampling is assumed to be completely asynchronous, the only condition b eing that bit synchronization of the desired user has b een previously achieved, i.e. ,  1 2 [0 ;T ), where without loss of generality we have assumed that the rst user is the desired one. If the duration of the transmitted chip-shaping waveform is T c or smaller, only two consecutive symb ols from the desired user contribute to y l ( m ). For instance, this o ccurs with rectangular chip-shaping pulses and is a go o d approximation for other pulse typ es. In any case, if the adjacent bits are also presentinthatvector due to the tails of the chip-shaping pulse, then their tiny contribution will b e lump ed together in the noise term, as justied in [28]. Therefore, the signal contribution of the rst (desired) user to the vector y l ( m ) can be expressed as follows y l; 1 ( m )=  l; 1 A (1) (  1 ) d 1 ( m ) ; (5) 5 The transp ose, conjugate and conjugate transp ose op erations are represented by (  ) T ,(  ) c and (  ) H , resp ectively.The i th elementofavector is represented by[  ] i . 6 where d 1 ( m )=  d 1 ( m ) d 1 ( m  1)  T (6) A (1) (  1 )=  a (1) + (  1 ) a (1)  (  1 )  (7) h a (1) + (  1 ) i i = c 1 ( iT s   1 ) i =1 ;:::;NQ (8) h a (1)  (  1 ) i i = c 1 ( iT s + T   1 ) i =1 ;:::;NQ : (9) The matrix A (1) (  1 )contains the temp oral signatures of the desired user. Note that the mo del ab ove is also valid for users other than the rst one as well. To simplify our notation, in the sequel we will drop the the sup erscript that indexes the users. At this point, we can write the received NQ  1 vector at the l th sensor as y l ( m )=  l; 1 A (  1 ) d 1 ( m )+ e l ( m ) m =0 ; 1 ;:::;M  1 : (10) The vector e l ( m ) includes the MAI, the thermal noise and all other sources of interference. 3GAUSSIAN ASSUMPTION If the temp oral vectors received from every antenna are stacked into a LN Q  1 space-time vector: y ( m )=  y T 1 ( m ) y T 2 ( m ) ::: y T L ( m )  T ; (11) then equation (10) can b e rewritten in a compact form as y ( m )=(   A (  1 )) d 1 ( m )+ e ( m ) ; (12) where  denotes the Kronecker pro duct, e ( m ) is formed similarly to y ( m ) and  =   1 ; 1  2 ; 1 :::  L; 1  T (13) is the spatial signature of the rst user. As outlined in the intro duction, we mo del e ( m ) as a zero-mean, circularly complex Gaussian LN Q  1 vector, which is indep endentof d 1 ( m ) and indep endent for dierent samples, and has an arbitrary and unknown space-time covariance matrix: E f e ( m ) g = 0 E n e ( m ) e ( n ) H o = Q Æ m;n : (14) 7 There is no doubt that this mo del is only approximate. Nevertheless, it gathers the most signicant eects of all the interfering signals, and allows us to derive tractable algorithms. The problem addressed in this pap er may be stated as follows. Estimate  1 , given the set of samples Y =  y (0) y (1)  y ( M  1)  (15) and assuming that the spreading sequence f g 1 ( n ) g N  1 n =0 and the training bit sequence f d 1 ( m ) g M  1 m =  1 for the desired user are available. Estimates of  and Q , which are taken as deterministic and unstructured parameters, will also be derived. Although we do not parameterize the spatial signature in terms of one or several directions-of-arrival and amplitudes, the array maintains its ability to discriminate the signals in the spatial domain. Assuming an unstructured  eliminates the need for a calibrated antenna array, and allows us to mo del a cluster of coherent arrivals that share the same time delay, without estimating the individual parameters of each arrival. A detailed discussion of the advantages of this assumption can be found in [23]. It is well known that the assumption of temp orally white MAI is unrealistic [29] and leads to non near-far resistant estimators because it neglects the structure of the MAI. However, the estimator prop osed herein, though mo deling the interference as Gaussian, do es not suer from the same problem since it retains the structure of the MAI in the matrix Q ,and so it is near-far resistant. Actually, it is the fact that an unknown correlation matrix Q is considered for the equivalent noise e ( m ) that makes the estimator able to attenuate anyinterfering signal that exhibits a certain structure in the temp oral and/or spatial domains. In this pap er, we present the estimator that results from an arbitrary matrix Q , in contrast to previous work that has solved the problem stated herein for simplied structures of that matrix. We will also see in Section 4.2 that imp osing a very simple and natural structure on Q allows us to estimate it without using excessively large training sequences. The signal mo del prop osed in [19] may seem at rst glance rather dierentto the one prop osed ab ove. Nonetheless, it can be shown that they are related by realizing that in [19] it is implicitly assumed that the space-time correlation matrix can b e decomp osed as Q = Q sp  I NQ , where Q sp is an arbitrary L  L matrix that corresp onds to the spatial correlation of the interference. It is apparent that the estimator in [19] yields sub optimal p erformance since it ignores the inherent temp oral structure of the CDMA signals. A dual decomp osition is considered in [20]. In this case, the matrix Q is expressed as Q = I L  Q te , where Q te is a NQ  NQ matrix representing the temp oral structure of the interference. This mo del amounts to presuming that the fading co eÆcients  l;k for a given user are uncorrelated between dierent antennas and that the observation interval is long enough (compared to T coh ) to apply ergo dicity, but this last condition is not satised in the case of slow fading. 8 4 MAXIMUM LIKELIHOOD ESTIMATOR In this section, the estimator of the co de-timing of the desired user is derived by applying the ML principle [30] to the signal mo del describ ed ab ove. Next, several techniques that may serve to improve the quality of the estimate of the noise-plus-interference correlation matrix are discussed. 4.1 Derivation The probability density function of Y is p ( Y j  1 ;  ; Q )= 1 LN QM j Q j M  exp (  M  1 X m =0  y ( m )  Dd 1 ( m )  H Q  1  y ( m )  Dd 1 ( m )  ) ; (16) where jj denotes the determinant, and the matrix D (  1 ;  ) =   A (  1 ) is the joint space-time signature of the desired user. The dep endence of D on the parameters is omitted from our notation whenever there is no risk of confusion. The negative log-likeliho o d function 6 of the observed data Y is easily shown to be  1 (  1 ;  ; Q )=ln j Q j +Tr n Q  1 C (  1 ;  ) o ; (17) where Tr fg denotes the trace of a matrix, and C (  1 ;  )= 1 M M  1 X m =0  y ( m )  Dd 1 ( m )  y ( m )  Dd 1 ( m )  H : (18) The ML estimates of  1 ,  and Q are the values that minimize (17). Using standard matrix calculus results [31] and without imp osing any structure on Q , it is immediate that the gradient of (17) with resp ect to Q is @  1 (  1 ;  ; Q ) @ Q = Q  1  Q  1 C (  1 ;  ) Q  1 : (19) The value of Q that nulls (19) is ^ Q (  1 ;  )= C (  1 ;  ) : (20) provided that C (  1 ;  )is non-singular (refer to Section 4.2 for conditions on the minimum value of M ). The ML estimate of Q , denoted by ^ Q ML ,is 6 In the sequel, all parameter-indep endent additive or multiplicative constants of the likeliho o d functions will b e neglected. 9 It is p ossible to compute the asymptotic values of (46)-(48). Recalling that ^ R dd !  2 d I , it is not hard to verify that F a 1 = M lim M !1 F 1 M = M 2 d   I L  a H + (  1 )  Q  1  I L  a + (  1 )  + +  I L  a H  (  1 )  Q  1  I L  a  (  1 )   (50) F a 2 = M lim M !1 F 2 M = M 2 d   I L  a H + (  1 )  Q  1  I L  b + (  1 )  + +  I L  a H  (  1 )  Q  1  I L  b  (  1 )   (51) F a 3 = M lim M !1 F 3 M = M 2 d   I L  b H + (  1 )  Q  1  I L  b + (  1 )  + +  I L  b H  (  1 )  Q  1  I L  b  (  1 )   : (52) When these values are substituted into (45), an asymptotic expression for the CRB is obtained. The asymptotic CRB is usually preferred b ecause it do es not dep end on the particular value of the training sequence, and is the one plotted in the gures of the next section. 6 SIMULATION RESULTS In this section we compare the p erformance of our estimator, referred to as the \space-time diversity" (STD) estimator, with two of the techniques prop osed to date that in most cases givethe b est results. Namely, we consider the metho ds presented in [19] and [20], which we will denote as \space-diversity" (SD) and \time-diversity" (TD) estimators, resp ectively. In these two pap ers and also in [11], the SD and TD metho ds are compared with a number of dierent estimators prop osed in the literature. Note that the comparison with these two approaches is fair since they also use an antenna array in reception. The computational complexity of the SD and TD metho ds is smaller than that of the STD estimator, b ecause they work with the space-only and the timeonly correlation matrices of the interfering signals, resp ectively. The size of these two matrices is obviously smaller than that of the space-time correlation matrix employed in the the STD approach. Here, we analyze two p erformance measures:  Probability of acquisition ( P ac ). We dene a correct acquisition to have o ccurred when the delay estimate is within a half-chip of the true value, i.e. , j ^  1 ; ML  ~  1 j <T c = 2. 16  The ro ot mean squared error (RMSE) given correct acquisition, i.e. , RMSE (  1 )= r E n j ^  1 ; ML  ~  1 j 2    j ^  1 ; ML  ~  1 j <T c = 2 o (53) This measure is relevant for the tracking op eration of the estimators. A metho d is considered to have failed when P ac  0 : 5, due to the large number of outliers. The RMSE is not plotted in this case. We have observed that the three estimators under consideration are essentially unbiased (their biases are much smaller than their standard deviations). Therefore, the RMSEs are for all practical purp oses identical to the standard deviations. All results are obtained from 1000 Monte Carlo realizations. The simulation conditions, except when one of them is varied, are as follows:  (pseudo-)Gold co des with length N =15 chips and BPSK mo dulation.  rectangular chip-shap ed pulses and oversampling factor Q =1.  Energy per bit to white-noise sp ectral density ratio (Eb/No) equal to 4dB per antenna for the desired user.  uniform linear array with L =4 antennas spaced 0 : 5wavelengths apart.  K = 10 users, M = 80 training bits.  The p ower of the signal from eachinterfering user is distributed log-normally with mean 10dB (with resp ect to the desired user) and standard deviation 10dB. This distribution mo dels the log-normal fading caused by largedistance reectors.  The delays of the users, the mean directions-of-arrival (DOA) of the users and the external interference are randomly chosen from the range of all p ossible values and xed throughout the Monte Carlo realizations. The near-far ratio (NFR) is dened as the ratio between the mean power of each interfering user and that of the desired user. The structured estimate of the correlation matrix ^ W s is used in the implementation of the STD estimator. We simulate two dierent channels. The rst, referred to as the static channel , is a channel that remains constant during the observation interval. This corresp onds to the situation that wehave considered in the signal mo del of Section 2. There is no angular spreading, so each user has a unique spatial signature. Since the Doppler frequency f d is assumed equal to 0, the signals do not suer from multiplicative distortion (or fast-fading), only log-normal fading. The amplitude and phase of each user's signal are held xed during the observation interval, but are varied for each Monte Carlo run in order to mo del the log-normal fading. The second channel is a realistic mobile channel for the uplink. It is generated according to the spatio-temp oral mo del describ ed in [42]. Each signal arrives at the array through several rays, all of them with the same delay. The number of rays follows a truncated Poisson law with mean and maximum 17 values equal to 25 and 50 rays, resp ectively. The directions of arrival of the rays are generated according to a Gaussian distribution with agiven mean and a standard deviation of 5 degrees. This is the value that characterizes the angular spread of the signals. The total p ower of each signal is divided among its propagation rays following a Laplacian law conditioned on the separation between the DOA of eachray and the mean DOA of the signal (see [42] for details). The Doppler sp ectrum has the classical Clarke's bath-shap e [1], obtained by assuming multiple and randomly lo cated reectors near the mobile, with normalized maximum Doppler frequency equal to f d T =2  10  3 . Therefore, the multiplicative distortion intro duced bythechannel has approximately a correlation duration of 1 =f d T = 500 symbols. This value for the factor f d T corresp onds to a system with an typical set of parameters, such as 900MHz carrier frequency, 50kb = s data rate and 120km = h sp eed, or 1800MHz carrier frequency, 100kb = s data rate and 120km = h sp eed. Note that for a p edestrian channel the sp eed is ab out 3km = h, and therefore the value of f d T is much smaller. We rst consider the eect of the length of the training sequence M . The results are shown in Figure 2. The estimator prop osed in this pap er is the only one that attains the CRB for the static channel, even though the Gaussian assumption is only an approximate one. This fact corrob orates the explanation in Section 3 stating that the Gaussian mo del with space-time correlation is reasonable and mo dels the most signicant eects of the MAI. The CRB is achieved for lengths of the training sequence larger than 250 bits. For smaller values, there is a very slight degradation with resp ect to the CRB, which causes the dierence between the RMSE and the CRB present in all the subsequent gures. As exp ected, the p erformance of all the estimators deteriorates in the mobile channel, where the RMSE can not b e further reduced by increasing M . This impairment should not b e interpreted as a failure of the estimators, but only as the eect of working in a much more adverse environment, and it will b e visible in all the following results. As M increases, the multiplicative distortion blurs the signal of the desired user. Then, the eective length of the training sequence is no longer equal to M , but is b ounded by the temp oral correlation of the channel. Also in the mobile channel the STD estimator outp erforms the other two approaches. The SD metho d p ossesses the largest RMSE and the lowest P ac , since it is the approach with the smallest number of degrees of freedom. Figure 2(b) demonstrates the ability of our algorithm to acquire the desired user's delay. As shown in Figure 2(a), RMS errors between 0 : 1 and 0 : 01 chips can b e achieved with windows of less than 100 bits, indicating that the algorithm can b e used for tracking slowly time-varying parameters in decision-directed mo de. In Figure 3, we investigate the eect of varying the number of users. This has sp ecial interest for a base station that uses spatial-division multiple-access (SDMA), since such systems mayhave more users than the length of the co des. 18 Again the STD estimator gives b etter results than the other two metho ds b oth in RMSE and P ac . The SD and TD approaches exp erience a serious deterioration, sp ecially in their probabilities of acquisition, when the number of users exceeds the length of the co de ( i.e. , K>N ), and they completely fail when K > 2 N in the scenario under consideration. On the other hand, using the space-time estimator the number of users maybeincreased beyond twice the co de length without an excessive degradation. For instance, note that for a static channel with K = 40 users the probability of acquisition remains virtually equal to 1, and only go es down to 0 : 82 for the mobile channel. Next, the eect of a wide-band external interference is analyzed in Figure 4. Because of its large bandwidth, the interference do es not show any temp oral structure, so it can be exclusively mitigated in the spatial domain. Only the STD and SD estimators provide adequate p erformance when the desired signal-to-interference ratio (SIR) is small ( e.g. , smaller than <  15dB). Their p erformance is nearly insensitive to the SIR except for extremely lowSIR in the mobile channel. Despite everything, the former gives b etter results than the latter in all cases. Moreover, the SD estimator is not near-far resistant for the system parameters that we have considered. In Figure 5 the near-far resistance of the dierent estimators is compared. In the static channel, the CRB and the RMSE and P ac of the estimator prop osed herein are totally insensitive to the MAI level, whereas those of the TD and SD schemes are not. With regard to the probability of acquisition, the STD estimator p erforms satisfactorily in the mobile channel up to a NFR equal to 35dB, which is an improvement of ab out 8dB and 18dB over the TD and SD metho ds, resp ectively. Further insight into the near-far p erformance is gained by observing Figure 6. An estimator can be considered to be near-far resistant when the RMSE tends to zero and the P ac tends to one as the Eb/No increases, even in the presence of arbitrarily strong MAI. This prop erty is only satised by our STD estimator, at least in the static channel. The RMSEs of the other two estimators ( i.e. , the SD and TD metho ds) have p erformance o ors due to the MAI that cannot be surpassed by reducing the power of the background white noise. In Figure 7, we examine the relationship b etween the probability of acquisition and the RMSE with the normalized Doppler f d T . These results are obtained for an angular spread with standard deviation equal to 8 degrees. The STD estimator p erforms b etter than the other twoforallvalues of f d T considered. The dierence b etween the RMSEs of the dierent metho ds is roughly constant as the Doppler is increased. On the other hand, the probability of acquisition of the STD estimator is less sensitive to the Doppler than that of the SD and TD approaches. This gure shows that the p erformance of the estimator prop osed herein is not critically aected by the Doppler spread of the channel. For instance, P ac for our metho d is approximately 0.92 when f d T =0 : 01. This is an excellent result, since the correlation length of the channel is ab out 100 19 symb ols, and hence on the orderoftheobservation interval. Our last set of results involves analyzing the p erformance achieved with different estimates of the correlation matrix. In Figure 8, we compare the RMSEs obtained with the structured estimate ^ W  1 s (the one employed in all the simulations ab ove), the pseudo-inverse ^ W # and the diagonally loaded estimate ^ W  1 d . The diagonal loading factor is set equal to the p ower of the white noise. As predicted and justied by the theoretical study in Section 4.2, the p erformance with the pseudo-inverse is always worse than with the other two estimates, and undergo es a severe degradation for short lengths of the training sequence. The RMSEs obtained with the diagonally loaded and the structured matrix estimates, which are nearly coincident, are b etter discerned in Figure 9. This gure shows that the RMSE of the former is noticeably greater than that of the latter for small loading factors. When the loading factor is equal to or greater than the white-noise power, they p erform similarly, but there is always a certain advantage in favor of the structured estimate, esp ecially for the mobile channel. 7 CONCLUSIONS A co de-timing synchronization technique for DS-CDMA systems that op erates in near-far, frequency-nonselective, slowly fading channels and employs an arbitrary antenna array for reception has b een derived by applying the ML principle. As such the technique is a single-user, near-far resistant estimator and would be applicable in a system employing multiuser detection without power control. It is assumed for the derivation that the desired user transmits aknown training sequence, and all other received comp onents are mo deled as Gaussian with unknown space-time correlation. This approach fully exploits the spatial and temp oral structure of the interfering signals in order to cancel them, and diers from other metho ds put forward to date that, while also employing antenna arrays, only exploit the structure of the signals in one of the domains. As a result, the prop osed technique outp erforms existing synchronization metho ds for reasonable lengths of the training sequence. The use of a structured estimate of the correlation matrix or diagonal loading allows one to reduce the required size of the observation window. The RMSE and the acquisition probabilityof the prop osed algorithm have been evaluated numerically in twotyp es of channels. Although the estimator is applied in a multiple-access channel, the RMSE attains the CRB derived under the Gaussian assumption, which conrms the validity of the starting mo del. The results of this pap er show that the eÆcient use of space-time diversity is indisp ensable for accurate acquisition and tracking of the synchronization parameters in heavily loaded systems and/or in the presence of external interference. 20 References [1] J. Proakis, Digital Communciations .New York: McGraw-Hill, 3rd ed., 1995. [2] S. Verd u, \Minimum Probability of Error for Asynchronous Gaussian MultipleAccess Channels," IEEE Trans. on Information Theory ,vol. 32, pp. 85{96, Jan. 1986. [3] S. Verd u, Multiuser Detection .Cambridge University Press, 1998. [4] S. Parkvall, E. Strom, and B. Ottersten, \The Impact of Timing Errors on the Performance of Linear DS-CDMA Receivers," IEEE Journal on Selected Areas on Communications , vol. 14, pp. 1660{1668, Oct. 1996. [5] U. Madhow and M. B. Pursley, \Acquisition-Based Capacity of Direct-Sequence Spread-Sp ectrum Communication Networks," in Proc. of the Conferenceof Information Sciences and Systems , pp. 1186{1189, March 1991. [6] J. K. Holmes, Coherent Spread Spectrum Systems . Krieger Press, 1990. [7] W. H. Sheen and G. L. St ub er, \A New Tracking Lo op for Spread-Sp ectrum Systems on Frequency-Selective Fading Channels," IEEE Trans. on COM , vol. 43, pp. 3063{3072, Dec. 1995. [8] W. H. Sheen and C. H. Tai, \A Noncoherent Tracking Lo op With Diversity and Multipath Interference Cancellation for Direct-Sequence Spread-Sp ectrum Systems," IEEE Trans. on COM ,vol. 46, pp. 1516{1524, Nov. 1998. [9] R. F. Smith and S. L. Miller, \Co de Timing Estimation in a NearFar Environment for Direct-Sequence Co de-Division Multiple-Access," in Proc. IEEE Military Conf. , pp. 47{51, 1994. [10] E. Strom, S. Parkvall, S. Miller, and B. Ottersten, \Propagation Delay Estimation in Asynchronous Direct-Sequence Co de-Division Multiple Access Systems," IEEE Trans. on COM ,vol. 44, pp. 84{93, Jan. 1996. [11] D. Zheng, J. Li, S. Miller, and E. Strom, \An EÆcient Co de-Timing Estimator for DS-CDMA Signals," IEEE Trans. SP ,vol. 45, pp. 82{89, Jan. 1997. [12] S. Bensley and B. Aazhang, \Subspace-Based Channel Estimation for CDMA Communication Systems," IEEE Trans. Commun. , pp. 1009{1020, Aug. 1996. [13] S. Bensley and B. Aazhang, \Maximum-Likeliho o d Synchronization of a Single User for Co de-Division Multiple-Access Communication Systems," IEEE Trans. on COM ,vol. 46, pp. 392{399, March 1998. [14] T.  Ostman, S. Parkvall, and B. Ottersten, \An Improved MUSIC Algorithm for Estimation of Time Delays in Asynchronous DS-CDMA Systems," IEEE Trans. on COM ,vol. 47, pp. 1628{1631, Nov. 1999. [15] E. Ertin, U. Mitra, and S. Siwamogsatham, \Maximum-Likeliho o d Based Multipath Channel Estimation for Co de-Division Multiple-Access Systems." Accepted for publication in IEEE Trans. on COM, 2000. 21 [16] J. Romero-Garca, R. D. Gaudenzi, F. Giannetti, and M. Luise, \A Frequency Error Resistant Blind CDMA Detector," IEEE Trans. COM ,vol. 48, pp. 1070{ 1076, July 2000. [17] A. Paulra j and C. Papadias, \Space-Time Pro cessing for Wireless Communications," IEEE Signal Processing Magazine , vol. 14, pp. 49{83, Nov. 1997. [18] K. Molnar and G. Bottomley, \Adaptive Array Pro cessing MLSE Receivers for TDMA Digital Cellular/PCS Communications," IEEE J. Select. Areas Commun. ,vol. 16, pp. 1340{1351, Oct. 1998. [19] Z.-S. Liu, J. Li, and S. Miller, \A Receiver Diversity Based Co de-Timing Estimator for Asynchronous DS-CDMA Systems," in Proc. ICASSP , vol. VI, (Seattle, WA), pp. 3245{3248, 1998. [20] Z.-S. Liu, J. Li, and S. Miller, \An EÆcient Co de-Timing Estimator for Receiver Diversity DS-CDMA Systems," IEEE Trans. COM ,vol. 46, pp. 826{835, June 1998. [21] A. Jakobsson, A. Swindlehurst, D. Astely, and C. Tidestav, \A Blind Frequency Domain Metho d for DS-CDMA Synchronization Using Antenna Arrays," in Proc. 32nd Asilomar Conf. on Signals, Systems and Computers , (Pacic Gro ove, CA), Nov. 1998. [22] C. Sengupta, J. R. Cavallaro, and B. Aazhang, \Maximum Likelihood Multipath Channel Parameter Estimation in CDMA Systems Using Antenna Arrays," in Proc. PIMRC ,1998. [23] G. Seco, A. L. Swindlehurst, and D. Astely, \Exploting Antenna Arrays for Synchronization," in Signal Processing Advances in Wireless Communications (G. B. Giannakis, Y. Hua, P. Stoica, and L. Tong, eds.), vol. I I: Trends in Singleand Multi-User Systems, ch. 10, Prentice-Hall, 2000. [24] Z. Xie, C. K. Rushforth, R. T. Short, and T. K. Mo on, \Joint Signal Detection and Parameter Estimation in Multiuser Communications," IEEE Trans. on COM ,vol. 41, pp. 1208{1215, Aug. 1993. [25] A. Swindlehurst and P. Stoica, \Maximum Likeliho o d Metho ds in Radar Array Signal Pro cessing," Proceedings of the IEEE ,vol. 86, pp. 421{441, Feb. 1998. [26] G. Seco and J. Fernandez-Rubio, \Maximum Likeliho o d Propagation-Delay Estimation in Unknown Correlated Noise using Antenna Arrays: Application to Global Navigation Satellite Systems," in Proc. ICASSP , vol. IV, (Seattle, WA), pp. 2065{2068, May 1998. [27] D. Astely, Spatial and Spatio-Temporal Processing with Antenna Arrays in Wireless Systems . PhD thesis, Royal Institute of Technology, KTH, Sto ckholm, Sweden, 1999. [28] U. Madhow, \Blind Adaptive Interference Suppression for the Near-Far Resistant Acquisition and Demo dulation of Direct-Sequence CDMA Signals," IEEE Trans. on SP ,vol. 45, pp. 124{136, Jan. 1997. 22 [29] S. Verd u, \Demo dulation in the Presence of Multiuser Interference: Progress and Misconceptions," in Intel ligent Methods in Signal Processing and Communications (D. Do camp o, A. Figueiras-Vidal, and F. Perez-Gonzalez, eds.), pp. 15{44, Birkhauseer, Boston, MA, 1997. [30] L. L. Scharf, Statistical Signal Processing, Detection, Estimation, and Time Series Analysis . Addison-Wesley, 1990. [31] J. R. Magnus and H. Neudecker, Matrix Dierential Calculus with Applications in Statistics and Econometrics . John Wiley & Sons, 1999. [32] P. J. Bro ckwell and R. A. Davis, Time Series: Theory and Methods .New York: Springer-Verlag, 2 ed., 1991. [33] S. Parkvall, Near-Far Resistant DS-CDMA Systems: Parameter Estimation and Data Detection .PhD thesis, Royal Institute of Technology, KTH, Sto ckholm, Sweden, 1996. [34] J. Rissanen, \Mo deling by Shortest Data Description," Automatica , vol. 14, pp. 465{471, 1978. [35] H. Akaike, \A New Lo ok at Statistical Mo del Identication," IEEE Trans. on Automatic Control , vol. 19, pp. 716{723, 1974. [36] M. Wax and T. Kailath, \Detection of Signals by Information Theoretic Criteria," IEEE Trans. on ASSP ,vol. 33, pp. 387{392, April 1985. [37] K. Harmanc, J. Tabrikian, and J. L. Krolik, \Relationships Between Adaptive Minimum Variance Beamforming and Optimal Source Lo cation," IEEE Trans. on SP ,vol. 48, pp. 1{12, Jan. 2000. [38] B. D. Carlson, \Covariance Matrix Estimation Errors and Diagonal Loading in AdaptiveArrays," IEEE Trans. on AES ,vol. 24, pp. 397{401, July 1988. [39] T. Soderstrom and P. Stoica, System Identication . London, UK: Prentice Hall International, 1989. [40] E. L. Lehmann, Theory of Point Estimation .New York: Wiley, 1983. [41] S. M. Kay, Fundamentals of Statistical Signal Processing. Estimation Theory . Prentice Hall, 1993. [42] K. Pedersen, P. Mogensen, and B. Fleury,\AStochastic Mo del of the Temp oral and Azimuthal Disp ersion Seen at the Base Station in Outdo or Propagation Environments," IEEE Trans. on Vehicular Technology , vol. 49, pp. 437{447, May 2000. 23 Front-end filter 2c jft epChip-matched filter l-th antenna () l yn / c TQ Buffer NQ samples () lmy Down-conversion Figure 1. Demo dulator blo ck diagram. 24 0 50 100 150 200 250 300 350 400 450 500 10−2 10−1 M, Length of the training sequence (bits) Timing RMSE (chips) Space−Time div. fdT=0 Time div. fdT=0 Space div. fdT=0 CRB Space−Time div. fdT=2e−3 Time div. fdT=2e−3 Space div. fdT=2e−3 (a) RMSE 0 50 100 150 200 250 300 350 400 450 500 0.6 0.65 0.7 0.75 0.8 0.85 0.9 0.95 1 M, Length of the training sequence (bits) Probability of acquisition Space−Time div. fdT=0 Time div. fdT=0 Space div. fdT=0 Space−Time div. fdT=2e−3 Time div. fdT=2e−3 Space div. fdT=2e−3 (b) Probability of acquisition Figure 2. Performance of the STD, TD and SD estimators as a function of the length of the training sequence M in two dierent channels. K =10 ; N =15 ; L =4 ; Eb = No = 4dB p er antenna, NFR = 10dB. 25