Blind multiuser identification and detection in cdma systems

BLIND MULTIUSER IDENTIFICATION AND DETECTION IN CDMA SYSTEMS Javier R. Fonollosat, Jose' A. R. Fonollosat, Zoran Zvonar;tand Josep Vidalt tuniversitat Politkcnica de Catalunya Department of Signal Theory and Communications $Analog Devices Communications Division 08034 Barcelona, SPAIN fonoet sc. upc.es ABSTRACT Multiuser detection in Code Division Multiple Access systems usually requires either knowledge of the transmitted signature sequences and channel state information or use of a known training sequence for adaptation. In this paper we develop a scheme that can be employed for the joint adaptive blind multiuser identification and detection in asynchronous CDMA systems. This scheme relies on a multiuser Viterbi .ilgorithm that incorporates an adaptive estimation of the overall channel impulse responses, given by the convolution of the signature sequences of the users and corresponding physical channels impulse responses. Once the overall channel responses are estimated, the blind multiuser detection algorithm performs like the maximumlikelihood sequence estimator. Results are provided to illustrate the convergence of the blind multiuser approach, near-far resistance and sensitivity to the algorithm initialization. 1. INTRODUCTION Increasing interest in the multiuser detection area was initiated by the work on the optimal structures and the performance bounds for the Gaussian noise channel [l]. The optimal multiuser detector employs a bank of matched filters (one for each active user) followed by a multiuser maximum-likelihood sequence estimator (MLSE). Its complexity is exponential in the number of active users and it requires knowledge of the transmitted signature sequences and channel state information. Consequently, suboptimal nearfar resistant receivers of linear complexity were developed that still provide significant performance gain over the conventional single user receiver [2]. In addition, multiuser receivers were designed for fading and multipath channels [3]. Recently, adaptive multiuser receivers have gained considerable attention [4]. The requirement of trainThis work was supportedby CICYT of Spain, Grant number TIC92-0800-C05-05. Wilmington MA 01887-1024, USA [email protected] 0-7803-2431 45/95 $4.00 0 1995 IEEE 1876 ing sequences for adaptive multiuser reception, or previous knowledge of the users signatures and channels for the centralized multiuser receivers mentioned above, represents an important drawback for efficient multiuser communications. This motivates the development of multiuser receiver structures that can be adapted blindly, i. e. without the need of training sequences [4]. In this paper we present a scheme for the joint blind identification and detection of multiuser signals which has the following features: e No knowledge of the signature waveform of any user is required (although their approximate knowledge speeds up the convergence). 0 Training sequences are not required. e No timing information of any user needs to be known or acquired a priori. e No channel state information is required. e The blind multiuser detector is near-far resistant. e It provides an estimate of the signature sequence of each user convolved with its physical channel impulse response, and its ML transmitted sequence estimate after the convergence. This approach is motivated by the bandwidth efficient multiuser systems which utilize small spreading ratio, burst transmissions and relatively large SNR [5]. 2. SYSTEM MODEL We consider the asynchronous CDMA white Gaussian noise channel, where h,(t - nT) t) is the overall complex channel impulse response, given by the convolution of the signature sequence, physical channel and the receiving filter impulse responses. It incorporates t8he amplitude and the delay for user IC, and its duration is assumed to be smaller or equal to L symbols, i.e. hk(7,t) = 0,~ < 0,~ > LT, Vt. The total number of active users is K and their transmitted sequences are binary independent symbols bk[n] E (1, -1}. The symbol rate is 1/T and w(t) is normalized white Gaussian noise. The CDMA channel is sampled at a rate M/T = l/T'? to derive the discrete vector sequence r[n] r[n] = [r(n~), r(n~ + T~), . . . r(n~ + (M - I)T,)]~ . (2) The observation r[n] is modeled as a probabilistic M length vector sequence of a state vector s[n] r[n] = 'Fl[n]s[n] + ~[n] . (3) There are N = 2L" possible state vectors corresponding to L binary symbols of K users. We denote the individual states as the KL length vectors {SI, s2,. . . , SN}, si = [Ai(l, l), . . .,Ai(L, 1), . . .,Ai(L,K)IT, Ai(l,k) E {l,-l} and the state at time instant nT as s[n].The (M x KL) matrix %[n] depends of the overall discrete impulse response for all users x[n] = [Hl[n], . . ., HK[n]] HI,[^] = [hko[n], . . . hq~-i)[n]l (4) (5) hk((n. + l)T, nT) [ h((n + l)T + (M - l)Ts, nT) hkl[4 = The normalized noise vector is defined as W[.] = [w(nT),w(nT+T,), . . .,w(nT+(M-l)T,)]T . (7) The probability density function of the observation vector conditioned on a given individual state sj is where mj = 'Fl(nT)sj, 1 5 j 5 N . (9) 3. BLIND IDENTIFICATION AND DETECTION ALGORITHM 3.1. Introduction If the overall impulse response for each user was known, that is if the signature sequence, physical channel impulse response, amplitude and delay corresponding to each user were available, then using this information, the Viterbi algorithm could be employed to determine the multiuser maximum-likelihood sequence. That is, given X(t), and all possible multiuser sequences b = {[bl[n], . . .,b~[n]]~,Vn} the ML transmitted sequence is the one that maximizes the joint posterior distribution p(blr(t), Vt). This maximization, equivalent for equiprobable sequences to p(r(t), Vtlb), can be efficiently computed finding the most likely sequence of states using (8) for cumulative metric calculation and the Viterbi algorithm [l]. 3.2. Algorithm description In the method we present, the Viterbi algorithm is applied with current estimates of the overall impulse responses which are updated recursively. First the algorithm is initialized with an arbitrary impulse responses for each user. The number of users I< is assumed known together with a bound for the impulse response duration that determines L. Then the algorithm is iterated at the symbol rate as in a conventional Viterbi scheme. In this case however, metrics along the trellis are computed using for each state its %wn current estimate of the overall impulse response, Zj[n], j = 1, . . . , N. At each iteration, a ML path is continued for each state selecting the most likely possible predecessor and updating the accumulated metric using (8). Each state shares L - 1 symbols for each user with its set of possible predecessors and thus there are 2K predecessors per state. The channel estimate matrix 6j[n], j = 1, . . . , N is updated for each state modifying the one associated to its most likely predecessor using a standard system identification LMS scheme where the state si is the predecessor to state sj, p is the adaptation constant and the error vector eij[n] is defined as After convergence, the impulse response corresponding to the most likely final state can be employed to yield the ML transmitted sequence for each user as in the conventional multiuser optimal receiver. A similar approach was proposed for the blind equalization of single user channels using the Viterbi algorithm [6] and the Baum-Welch identification algorithm [7]. 3.3. Algorithm convergence We illustrate the convergence of the algorithm in a scenario of 4 users employing Gold sequences of length 7 in stationary AWGN channel. Users' signals are synchronous and their amplitudes are 1, 1.5, 2, and 2.5 respectively. After 300 iterations (symbols) the global 1877 Estimated impulse responses 0 50 100 150 200 250 300 Symbols Figure 1: Learning curve for %MI, estimated impulse response is 2ML = 1.020 1.520 -1.966 -2.511 0.986 -1.477 -1.939 -2.532 -1.002 1.551 -1.967 2.471 -1.033 -1.547 1.991 -2.467 0.989 -1.433 2.038 -2.532 -1.001 1.523 -2.005 -2.467 , 1.013 1.501 -1.993 2.474 whereas the actual X is 3-1= - 1 1.5 -2 -2.5 1 -1.5 -2 -2.5 -1 1.5 -2 2.5 -1 -1.5 2 -2.5 1 -1.5 2 -2.5 -1 1.5 -2 -2.5 - 1 1.5 -2 2.5 After convergence, the final global impulse response could be used to yield a close to optimal demodulation of the received sequence. The algorithm was initialized assuming the amplitude of all users was 1 and the SNR was 10 dB for the weakest user. No symbol errors were observed backtracking the ML path created during adaptation. Fig. 1 illustrates the evolution of the estimation of 3-1 for the ML state at each sample. 4. LOCAL MINIMA EFFECT 4.1. Existence of local minima In practice, this algorithm can be employed without further refinement if an approximate knowledge of the overall impulse response is used for initialization and all users are received with similar power. Otherwise, the adaptation can be easily trapped in local minima as a consequence of the near-far effect. This effect can be better understood in the two users case. When one of the users is characterized by an impulse response of much greater magnitude than the other, the algorithm tends to split the greater impulse response among both users (since this locally maximizes the probability function (8)) and the signal received from the weak user is just taken as part of the noise. The algorithm converges to a good approximation of the strong impulse response and neglects the weak one. The-same effect can happen after random initialization of 'H. This phenomenon, however can be easily detected since the corresponding estimated ML sequences for both users are exactly the same (except for a possible sign change). In the more general case of K users, any of their actual impulse responses, Hk[n] could in principle appear partitioned into an arbitrary number of users, i. e.. Hk[nj N Hk[n] + xj.fHtj [Iz], 6ut still this effect will be reflected in identical estimated ML sequences for these users (k and kj) again except for a possible sign difference. 4.2. Avoiding local minima We propose a simple procedure to overcome the convergence to a local minima. Consider the two synchronous users case with L = 1. An improved implementation of the algorithm checks every P symbols for total coherence of the corresponding ML sequences for each user. The probability of random coincidence of two independent binary sources, except for a possible sign change, is 1/2p-1, and can be made arbitrarily small increasing P. In case this absolute coherence is detected, it is assumed that the algorithm has converged to a local minimum and the impulse responses of each user are added (or subtracted if the sequences were inverse) and assigned arbitrarily to one of them. The other user impulse response is just reset to zero, i. e. h, En] + &1[n3 f fi2[n] &,[.I 60 . This compensation may be necessary until a good estimate of the strong impulse response is obtained which cancels the local minimum. In practice, we observed that one such compensations is necessary approximately for each 10 dB in power difference. In general, for an arbitrary number of users and value of L, a total of (:) = K(K - 1)/2 symbol crosscorrelation functions need to be computed, and each of them for 2L - 1 lags. This cross-correlation functions are defined as I - P-1 I 1878 where bkb] is the ML sequence associated with user k for the previous P symbols. The global impulse response is compensated iterating for each user in ascending order, i.e. k = 1,. . . , I< the following impulse response update K L-1 k’=k+l I’=O and possible reinitialization, k’ = + 1,. . . , I<; I’ = 0,. . . , L - 1. (14) 4.3. Near-far resistance We illustrate the near-far resistance of this blind deconvolution scheme considering the bandwidth efficient case [l] of 2 users using signatures [l, 1,1] and [l, -1,1]. The system is asynchronous and the second user arrives with a delay of T, with respect to the first one. This asynchronism makes L = 2. Their amplitudes are 1000 and 1 respectively (60 dB power difference). After 400 iterations (symbols) and 6 coherence compensations, the global impulse response estimated for the ML sequences compared to the actual 3-1 is 1 1000.0 -0.0763 -0.0199 1.0483 GML = 1000.1 0.0385 0.9352 0.0361 1000.0 -0.0618 -0.9724 0.0163 3-1= 1000 0 [ [ 1000 IOoo 0 O -1 0 1 The number of symbol errors observed are 0 and 94 respectively (again backtracking the ML path created during adaptation and not recalculating the ML sequence with the estimated impulse responses). The algorithm was initialized assuming the amplitudes of all users were 1 and they were synchronous. The SNR was 64.7 and 4.7 dB respectively. Fig. 2 illustrates the evolution of the estimation of 3-1 for the ML state at each sample. The parameter P was set to 30. It can be observed how coherence compensations are necessary until a precise estimate of the strong impulse response is attained, approximately after 180 symbols. Afterwards, the algorithm converges to the global impulse response 3-1. 5. CONCLUSIONS A new near-far resistant technique for the blind deconvolution of multiuser signals has been described. It can accommodate asynchronous multiuser channels with IS1 with a complexity that is exponential in the -4001 I 0 50 100 150 200 250 300 350 400 Symbols Figure 2: Learning curve for ~?ML number of users times the global impulse response duration in symbols. Local minima are avoided calculating cross-correlation functions between estimated ML sequences for each pair of users. The application of this method to fading and multichannel systems and experimental validation of the algorithm on the real data are the topics of further investigation. 6. REFERENCES Verd6, S., “Minimum Probability of Error for Asynchronous Gaussian Multiple-Access Channels,” IEEE Trans. on Information Theory, Vol. IT-3 2 , January 198 6. Lupas, R. and Verdli, S., “Near-Far Resistance of Multiuser Detectors in Asynchronous Channels,” IEEE Trans. on Communications, Vol. COM-38, March 1990. Zvonar, Z. and Brady, D., “Suboptimum Multiuser Detector for Synchronous CDMA FrequencySelective Rayleigh Fading Channels,” IEEE Trans. on Communications, to appear. Verd6, S., “Adaptive Multiuser Detection,” Proc. Third International Symposium on Spread Spectrum Techniques and Applications, Oulu, Finland, July 1994. Zvonar, Z., Brady, D. and Catipovic, J., “An Adaptive Linear Multiuser Receiver for Deep Water Acoustic Local Area Networks,” Proc. IEEE ICASSP-94, April 1994. Seshadri, N., “Joint Data and Channel Estimation using Blind Trellis Search Techniques,” IEEE Trans. on Communications, Vol COM-42, March 1994. Fonollosa, Jose A. R. and Vidal J., “Application of Hidden Markov Models to Blind Channel Characterization and Data Detection,” Proc. IEEE ICASSP-94, April 1994. 1879