Cdma blind channel equalization: a weighted subsface a proach

CDMA BLIND CHANNEL EQUALIZATION: A WEIGHTED SUBSPACE APPROACH Rafael Ruiz, Margarita Cabrera Department of Signal Theory and Communication Universitat Politecnica de Catalunya C/ Sor Eulalia de Anzizu, dn. 08034 Barcelona, SPAIN e-mail: [email protected], [email protected] Abstract - This paper considers the problem of blind demodulation of multiuser information symbols in a direct-sequence code-division multiple access (DSCDMA) environment, Channel estimation and symbol detection in presence of both multiple access interference (MAI) and intersymbol interference (ISI) is carried out with second order statistics methods from the received data. This problem is similar to Direction Of Arrival (DOA) estimation, where many solutions like the MUSIC algorithm or “weighted” techniques (as Deterministic Maximum Likelihood or Weighted Subspace Fitting method) have been developed. In this proposal these techniques are extended to blind DSCDMA channel identification problem in an unified framework known as Subspace Fitting. In this framework the estimated and the received data are “fitting” through the subspaces in a least square sense. Then, in order to achieve a better estimation of the channel, a modified Gauss-Newton type algorithm is suggested. Simulations are carried out comparing the proposed solutions with a classical signal subspacebased blind channel identification scheme. I. INTRODUCTION There is actually a growing interest in the design of high-rate DS-CDMA networks. This kind of digital communications are subjected to intersymbol interference (ISI) (due to channels with multipath phenomena) and multiple-access interference (MAI) (which is inherent to any nonorthogonal CDMA system). This problems can be so severe that correct reception of the transmitted symbols is not feasible anymore. It is necessary therefore to equalize the channel, suppressing jointly both MAI and ISI. This work is partially supported by the National Research Plan of Spain, CICYT, TIC96-0500-C10-01, TIC98-0412, TIC98-0703 and by the Generalitat of Catalonia, CIRIT, 1998SGR-0008 1. Since Tong, Xu and Kailath showed in [l] that it is possible to obtain an estimation of the channel from a second order statistic of the received signal, second order statistics have showed its useful in channel estimation. Subspace-based methods are based on the singular value decomposition (SVD) of a matrix constructed from the observed signal, which provides a robust discrimination between desired and disturbing signals in terms of signal and noise subspaces. In particular, several works (see [2] and references therein) have addressed the use of MUSIC-type methods for parameter estimation in CDMA systems. The general objective is to find a low-rank subspace with a shift structure that has minimal distance to the true signal space, or equivalently, that is as orthogonal to the noise subspace as possible. Viberg and Ottersten formulate in [4] different methods in a common subspace fitting based hmework, providing an overview of the DOA estimation problem and clarifying the algebraic relations between the algorithms. In this contribution we focus on MUSIC [3], WSF [4] and MDL [6] algorithms. These methods are summarized and adapted to blind channel identification in a subspace fitting approach. The paper is organized as follows. In Section II signal model of a DS/SS CDMA system and its subspace approach are formulated. Blind channel identification method for DS-CDMA proposed by [2] is also outlined. In Section UI we extend the subspace-fitting fiamework proposed by Viberg [4] to blind DS-CDMA channel identification. The cost hctions whose miniizationl maximization will allow estimating the channel are then formulated. After that, the Gauss-Newton algorithm for blind channel identification [8] is outlined. In section IV some simulation results are presented and discussed. Finally, we present some conclusions and outline future work in section V. 0-7803-5565-2/99/$10.00 0 1999 IEEE 2373 11. PROBLEM FORMULATION Hw= Signal Model H(L) -.e H(0) 0 i 0 ... Consider a K-user binary communication system through a Gaussian channel. Let sk(n) denote the kth user transmitted symbol at time nT (where T is the symbol duration) and {Cko)} be the signature sequence of M fl 's assigned to the user. The transmitted signal due to the kth user is: Ns-l M Xk (0 = 4 * CSk (n)CCk (A. P(t - nT -jTc - 5k) n=O j=1 OltlT (1) Where Ns is the number of transmitted symbols, M is the processing gain, p(t) is a normalized chip waveform of duration T, = TIM and Ak and Tk denote, respectively, the amplitude and delay of kth user. The resulting signal thorough a time-invariant channel hk(0 is: Ns-1 M ~k(t) = A, * CS~ (~)CC, (j)-Zk(t - nT - jT,) n=O j4 OltlT (2) With &(t)=p(t-7k)*hk(t); zL(t)sO t/tEIO,Lk .TI. The signal is filtered with the chip-matched filter and sampled at the chip rate T,. The resulting discrete-time signal component due to the kth user at the ith chip period of the nth symbol interval will be: Lh ~,+(n)=Cs,(n-~).h,,(~) i = z..M;~= Z..K (3) I=O With fL (m) = s," E++ (t + m~, 1. p(t)dt Olml(L, +l).M-l (4) M (j) = h, (IM + i> ; hk(m) = 'cck(j)*fk (m-j) J=1 Olml(L,+l).M (5) The received discrete-time signal at the ith chip period of the nth symbol interval is then: r, (n) = Y, (n) + v, (n) K Y, (n) = C Y,k (n) (6) With i;(n) the filtered AWGN noise. Defining the following matrix and vectors [2]: k=l r(n) = ; y(n) = ; v(n) = H(n) = ; s(n)= (7) By stacking W successive samples of the received data we have the MWxZ vectors: Subspace Approach The additive noise c(n) is modeled as a Gaussian, stationary, white and zero mean random process. The covariance matrix of the received signal is: (13) C, =Ebw .RF]=Hw .Hi +021M, 2374 Where the function E[*L denotes mathematical expectation and superscript is the hermitic operator. We assume that each user's information symbols are independently identically distributed and the symbol streams of different users are independent: .Ew .s;]= I, with r = K(w+L). The signal subspace is defined as the space spanned by columns of Hw, and the noise subspace is its orthogonal complement. Both subspaces can be obtained from the SVD of covariance matrix: CRR = UAU" = [U, U,]. p *)Js uor (14) With A, = diag(il1 ... &), Aid for i=l, ..., r (signal eigenvalues) and A, =diag(&+I ... ,IMw), A+=d for i=r+l, ..., MW (noise eigenvalues). The MW x Y matrix U, and the MW x MW-r matrix U, are: U, =[ul e.. U,]; U, =b,+, urn] (15) Since columns of U, span the signal subspace and columns of U, the noise subspace, orthogonality between subspaces provides: U: .Hw =O for i=Z,..,MW-(W+L) (16) Blind channel estimation in DS-CDMA The following subspace algorithm is an extension of the method developed in [3] to multiple input signals. Let U," ... U;], where U: is the ith (MW-r)xA4 partition of U," , we define the M(L+Z)xK matrix H and the (MW-r)(W+L) xM(L+l) matrix G as: Then (1 6) can be rewitten as: If G has more rows than columns, then its right null subspace specifies H up to a nonsingular ambiguity XXK matrix factor, Le: H = H.D . To further solve this ambiguity, the finite alphabet property of the input data has to be exploited, which is prohibitively expensive. In order to overcome this problem, Wang incorporated in [2] the spreading signatures. Let denote the M(L+Z) x mf matrix of the composite signature of the kth user Ck as: U,H*HIY=O e G*H=O (18) (19) .. With mf the channel response length of &(m) in (4); having that H=[hl ht ... h,], we cm rewrite (5) as: h, =A,C,f, With f,, = [ fk? ] (20) fk ("J - 1) m,x, Then, from (1 8) we have that: And therefore, the right null vector of G . C, is fk up to an ambiguity scalar factor. G.H=O*G*hk =Ak*G*ck*fk =o (21) 111. WEIGTED SUBSPACE FITTING Cost functions Since covariance matrix Cm is in practice estimated from a limited amount of received data, only an approximation of Cm is available. Then, (21) has to be solved in a least square sense. Adapting to blind channel identification the basic subspace fitting problem in DOA estimation proposed by Viberg & Ottersen [4], we have that, given some representation of the data M, we should to find an estimation of H and T such that H,T = arg 2~11~ -H, (H).TII: (22) Where [diis the quadratic Froebius norm. This is a separable problem, and substituting the solution of the first part, T = Hw+.M into (22) (the superscript denotes the pseudoinverse operator), this gives the generic subspace fitting cost function: H = arg m$V(H) with V(H)=/(I-P,,).MII: =T&.M.M") (23) Where P"=Hw-Hw+ is the LS projector onto the column space of Hw, P; = I - P,, is the orthogonal LS projector and Tr(*) denotes the trace operator. As M is a representation of the data, different choices of M will provide different cost functions (criterions). MUSIC criterion. The MUSIC criterion is based on orthogonality between signal and noise subspaces. The cost function derived from ( 16) can be written as: 2375 This is the MUSIC cost function. Since in DOA problem (24) does not give accurate results when the signals are highly correlated, Schmidt Error! Unknown switch argument. introduced a normalization matrix (HF .Hw)-' into (24), resulting the Multi-Dimensional (MO) MUSIC algorithm: H = arg minV, (H) v,(H) = Trb; -H,)I.Hg .UiT,-Uf .H,}= = TrkH .U,. U:)= Tr(p, -b - Us -U:)} (25) As the trace of a projection operator is equal to the dimension of the subspace onto which it projects, minimizing VI@) gives the same result that maximizing V (H) = Tr$ -6, .U:)= Tr[I - Pi)-Us .U:}, and the cost function of MD-MUSIC algorithm will be: H = arg minVM,_,,, (H) m Thus, the MD-MUSIC algorithm is a subspace fitting method where the representation of data is directly given by the signal subspace, M =Us . Deterministic ML criterion. Described by Biihme [6], this method try to maximize the log likelihood of the received data Y with respect to Hw and S (the columns of the MW x Ne matrix Y are the Ne snapshots y(n) with n=I..Ne, and the columns of the (W+L) x Ne matrix S are the Ne transmitted symbol vectors s(n)). This is equivalent to minimize the cost function VMDL (H) = 11 Y -H, .S 11: . The solution of the first part is S = Hk -Y and the cost function becomes: fi = WgmZvMDL(H) with vMDL(H)= Tv(& -c,} (27) Connection with subspace fitting can be made using asymptotic arguments (see [4]). For large Ne, we have A, +021, C, -+ U, .i*Ur +02 .I and A = A, -0' .I. As the trace of ozPi is a constant, the cost function is asymptotically (large Ne) equivalent to: Therefore, the deterministic ML method is a subspace fitting technique where the data are represented by its weighted signal subspace M = U, W,& ; wMDL = A. WSF criterion. The deterministic ML method allows to us to introduce the weighted subspace-fitting concept. This is: H = arg m,fnv.ssF (H) with V,,(H)= Tr{PkUsWwsFU:} (29) Where Wmp is a positive definite Weighting matrix. The question is to find a weighting matrix Wmp that makes the estimation statistically (for large Ne) efficient, i. e., that makes the WSF estimates asymptotically achieve the Cramer-Rao lower bound on the variance of the estimator error. Viberg and Ottersten [4] have shown that the optimal choice for WmF is W,,, =x2A;'. Thus, the WSF criterion can be expressed in (23) when the representation of the data is M = U, WzF. Modified Variable Projection Algorithm The proposed technique in [8] is the Modified Variable Projection (MVP) method (see [7] and references therein) applied to (one user) blind channel identification. The criterion function in (23) must be minimized over the vector h (for one emitter, matrix H is a column vector). Consider the nonlinear least square problem given by (23); in the damped Newton scheme, h is iteratively estimated with: hk+' =hk-,Uk.G-'.V' (30) With ,uk the step length, G the Hessian matrix of the cost function and v' the gradient. Every iteration the Hessian and the gradient are evaluated in hk. If h is well initialized, the Newton method guarantees an ultimate quadratic convergence to h . Consider fast the gradient of the cost function. The ith element of the gradient yields: Consider now the Hessian matrix, the 0th component of the approximate (a Kaufmanns's modification is applied to the algorithm, see [7]) Hessian matrix is: G, =2Tr{[(HLT .Hf .Pi .HY .H&].M-M"} (32) Then, (30), (31) and (32) give the MVP algorithm (derivation of (31) and (32) can be found in [7] and [SI). In order to obtain a good initialization of the estimates, we can use the MUSIC algorithm, which will allow to achieve a global minimum. The step length 2376 factor should be chosen in order to guarantee global convergence. It is known that quadratic convergence of Newton-type algorithms is only achieved if the step length factor converges to unity. IV. SIMULATION RESULTS A 50 Monte Carlo simulation is carried out in order to evaluate the performance of the weighted subspace algorithms in a digital DS-CDMA communication system. The K=5 users emit a burst of Ns=128 BPSK symbols. The Gold signature sequence has M=25 rtl ‘s (i.e. Tc=T/15). The highest order of the channels (ISI) is set to L=2 and the width of the temporal window is W=4. Each user has At=l(O dB MAI) and we consider the asynchronous CDMA channel. The performance measure plotted here is the mean of the probability of bit error computed for each user in a given signal-tonoise ratio (SNR) defined as A: /oz. Preliminary results can be seen in Fig. 1. WSF and MDL methods give virtually the same results, slightly worst than the MUSIC method. Since 50 Monte Carlo simulations do not provide a sufficient statistics, we can expect the same result than in case of one emitter, where the three methods proposed here give the same performance. Bit Em Rata J 1 2 3 4 5 6 SNR Figure 1. Bit error rate. V. CONCLUSIONS A Monte Carlo simulation is carried out in order to evaluate the different weighted subspace algorithms. As it is shown in the figures, weighted subspace methods provide the same accurate results than the MUSIC method developed by Moulines et al. in [3] and extended to DS-CDMA by Wang in [2]. As was shown in [8], the Mod$ed Variable Projection algorithm developed and applied in a blind channel identification context can improve the MUSIC results in a single user context when weighted subspace methods are involved. It can be expected that this algorithm can be applied to DS-CDMA systems with same results. On the other hand, the weighting matrices in MDL and WSF methods were defined for DOA problem; as channel estimation is not the same problem another weighting matrix can be derived for this specific situation. Another simulations have been carried out in order to test the behavior of weighted algorithms with. larger bursts. Results have shown that at larger sample size, less difference in Mean Square Error (MSE) exists between MUSIC and the proposed algorithms. Therefore we can conclude that the weighting matrices defined in MDL and WSF criterions are usefbl in low sample sizes. REFERENCES [ 13 Tong, L., Xu G. and Kailath T. “A new approach to blind identification and equalization of multipath channels”. Proc. 2Sth Asilomar Con$ On Signals, Systems and Computers, pp. 856-860, Pacific Grove, CA., Nov. 1991. [2] X. Wang and H. Vicent Poor, “Blind Equalization and Multiuser Detection in Dispersive CDMA Channels”, IEEE Trans. On Commun., Vol. 46, pp. 91103. Jan. 1998. [3] E. Moulines, P. Dohamel, J. Cardoso & S. Mayrargue, ”Subspace Methods for the blind identification of multichannel FIR filters”, IEEE Trans. On Signal Processing, Vol. SP-43, pp. 516-525, Feb. 1995. [4] M. Viberg and B. Ottersten, “Sensor Array Processing based on subspace fitting”, IEEE Trans. On Signal Processing, Vol. 39, pp. 1 1 101 12 1, May 1 99 1. [5] R. 0. Schmith, “A signal subspace approach to multiple emitter location and spectral estimation”, Ph. D. dissertation, Stanford University, Stanford, CA, 1981. [6] J. F. BOhme, “Estimation of Spectral parameters of correlated signals in wavefields”, Signal Processing, Vol. 11, pp. 329-337. Dec. 1986. [7] M. Viberg, B. Ottersten, “Detection and Estimation in Sensor Arrays Using Weighted Subspace Fitting”, IEEE Trans. On Signal Processing, Vol. 39, pp. 24362449. Nov. 1991. [8] R. Ruiz and M. Cabrera, “Weighted Subspace Methods for Blind Channel Identification”, in Proc. ICASSP’99, Phoenix (Arizona), Mar. 1999. 2377