Assymptotic performance of hierarchical fuzzy interference cancellers for CDMA

Asymptotic Performance of Hierarchical Fuzzy Interference Suppresors for CDMA Joan Bas Signal Theory and Communications Department, (TSC) Polytechnical University of Catalonia, UPC Barcelona , Spain jb[email protected]sc.upc.es Ana Pérez Neira Signal Theory and Communications Department, (TSC) Polytechnical University of Catalonia, UPC Barcelona, Spain [email protected] Abstract—This paper presents a hierarchical fuzzy logic canceller that suppresses digital and/or analog interference from a CDMA signal. The optimum filter to remove them is the Conditional Mean Estimator (CME) or the MAP detector of the interference. The CME and MAP, however, present a high computational burden which difficult their feasibility. To overcome this drawback, we propose a hierarchical fuzzy canceller that is beneficial in terms of computational load. Finally, asymptotic studies of the Signal to Interference plus Noise Ratio improvement (SINR) and the working region of the fuzzy canceller have been carried out. Keywords-component; Hierarchical Fuzzy Systems, CDMA. I. INTRODUCTION The new standards on wireless communications, e.g. UMTS,IEEE 802.11, demand high capacities to support more users. This situation is especially pronounced in the band of 2.4-2.5GHz, where the IEEE 802.11standard and ISM services share the same spectrum. As a consequence, IEEE 802.11 communications are corrupted by different types of interferences caused by the ISM services. This paper proposes a low complexity fuzzy filter able to estimate either digital interferences or narrowband analog ones. It is organized as follows. Section II presents the signal model. Section III describes a Hierarchical Fuzzy Canceller. Next, Section IV details the asymptotic studies of its SINR improvement. Finally, Section V derives the working region of the fuzzy filter. II. PROBLEM STATEMENT The base-band model of the received signal, k r, in a CDMA scenario with K users can be described as: 444344421 k n K t kN kt tk k kk wPsPisAr ∑ = +++= 2 ,,1 (1) where k s ,1 and kt s , represent the desired and undesired transmitted signal respectively at time instant k, k i is the interference which can be either digital or analog. In the case of analog signals, the classic Auto Regressive (AR) process interference has been considered whereas in the digital case it Fig.1 Decomposition of the fuzzy filter in 2 stages . has been modeled by a binary sequence [1-2]. Finally, the noise signal k nencompasses the conventional Additive White Gaussian Noise (AWGN), k w and the Multiple Access Interferences (MAI). Next section proposes a fuzzy filter in order to estimate and suppress the interference k i. III. H IERARCHICAL F UZZY S YSTEMS In [3] a fuzzy filter has been developed to cancel interferences from a CDMA signal. The designed filter is able to cope with both digital and analog interferences. In particular, the interference is predicted from its previous estimations and from the received signal. Specifically, the proposed fuzzy filter resorts to the estimations of the interference at k-1 and k-2, and the received signals at k and k-1. In order to reduce the computational burden of the fuzzy filter, the received signal at time instant k-1 has been taken as a reference signal. In this way, the input vector to the fuzzy canceller was defined as: [] 11112 −−−−− −−− kkkkkk rrriri . Then, the fuzzy system is based on 3=P input fuzzy variables, being modeled each one of them with 7=F membership functions. In this way, the number of rules of the fuzzy canceller is 3437 3 === P FM . As a consequence, this structure demands high memory requirements. One way to overcome such a problem is to resort to a hierarchical decomposition [4]. Note that if each one of the hierarchical stages is designed with 2= P inputs and one output, then just two stages are necessary (see Fig. 1). The first one has as its inputs the predicted interference at time instant k-1 and k-2 referenced by the received signal at time instant k-1, 1− k r: 121 ˆ −− −= kk rix (2a) 112 ˆ −− −= kk rix (2b) As the output signal we have : 3 x Stage 2 () yxzR ,, 31 1 x 2 x y T1 T1 Stage 1 () 121 ,, zxxR 1 z 0-7803-7954-3/03/$17.00 ©2003 IEEE. 1020 {} 121111 ,| −−−−− −−−= kkkkkk riririz (3) where in (3) 1 z is the prediction of the interference at time k conditioned to the referenced interference estimations at time k-1, 11 ˆ−− −kk ri , and k-2, 12 ˆ−− −kk ri . The second stage has as inputs: 11 − −= kk riz (4a) 13 − −= kk rrx (4b) being the output variable: {} 111 ,| −− −−= kkkk rrzriy (5) where in (5) y is the predicted interference at time k conditioned to 1 z and the referenced received signals at time k and k-1, 1− −kk rr . Hence, the rules that implement the hierarchical stages are: () ( ) ( ) ( ) jjj ZiszthenAisxandAisxifzxxR 1 1 2211 121 ,, → (6a) () ( ) ( ) ( ) jjjj BisythenAisxandZiszifyxzR 331 131 ,, → (6b) where 1 zis the intermediate variable that allows to relate both equations. For a fuzzy system with exponential membership functions, product-sum inference and centroid defuzzification, (6a) is formulated as: ∑∏ ∑∏ == ==      −−      −− =M ji i ji M ji i jij mx mxz z 1 2 1 2 2 1 2 1 2 2 ,1 1 2exp 2exp σ σ (7) Correspondingly, the rules of (6b) are expressed as: ∑ ∑ = =      −−      −−      −−      −− = M j jj z M j jj zj mxmz mxmzy y 1 2 2 3 3 2 2 1 1 2 2 3 3 2 2 1 2exp2exp 2exp2exp ˆ σσ σσ (8) Note that the hierarchical fuzzy system has 2 = P inputs and 7=F fuzzy sets per input variable. Hence, its number of rules is: 9877 22 =+=M which reduces in an important way the memory requirements of the non-hierarchical fuzzy canceller (i.e . )343=M IV. A SYMPTOTIC PERFORMANCE ANALYSIS Due to the presence of random noise signals an interference canceller may suffer important degradation in its performance. Therefore, it is necessary to determine in what scenarios the canceller converges. Once obtained such convergence regions they will be particularized for the designed fuzzy interference canceller. A. Convergence Scenarios of an Interference Canceller. One way of evaluating the performance of the fuzzy filter is by measuring its SINR improvement. This parameter is defined as the ratio between the output and input SINR as: inout inin in out in out SNRSIR SNRSIR SIR SIR SINR SINR SINR + + ⋅== imp (9) where SIR stands for Signal to Interference Ratio and SNR for Signal to Noise Ratio. SNR encompasses the Gaussian and MAI noises as follows: inin inin MAIgauss MAIgauss in SNRSNR SNRSNR SNR + = (10) being in Gauss SNR the input SNR of the Gaussian noise whereas in MAI SNR symbolizes the input SNR due to MAI noise. To compute the SINR improvement we have considered that we may have scenarios with a SIR higher, equal to or lower than the SNR. However, not all scenarios are possible, since the canceller has to suppress the interference signal, it implies that the input SIR has to be much lower than the output SIR. In addition, note that in an estimation/subtraction canceller the inout SNRSNR =, which helps to simplify (9). In this way, the scenarios where the canceller converges are: 1.inin SNRSIR << ,outout SNRSIR >> ⇒ ininimp SIRSNRSINR −≈ 2. inin SNRSIR << ,outout SNRSIR =⇒ 3 −−≈ ininimp SIRSNRSINR 3: inin SNRSIR = and outout SNRSIR >> ⇒ 3 ≈ imp SINR . 4: inin SNRSIR >> , ou t out SNRSIR >> ⇒ 0≈ imp SINR (11) Note that asymptotic performance of the SINR improvement is not exclusive to a fuzzy system. In fact, to obtain (11) we have not imposed any constraint on the structure of the canceller. Next we will combine the convergence regions or scenarios that are formulated in (11) with specific constraints of the fuzzy canceller. B. Maximum SINRimprovement for the fuzzy filter. Fuzzy systems are universal approximators since they satisfy the Stone-Weierstrass theorem. That means, that the maximum error δ in the approximation of a function () xf by means of a fuzzy system () xf fuzzy ˆ is bounded. In addition, if the number of fuzzy sets and rules of the fuzzy system is augmented, then the maximum error tends to zero () () δ <− xfxf fuzzy ˆ (12) Another, important constraint of the Stone-Weierstrass theorem is that the variables of the fuzzy system have to belong to the domain of the approached function () xf . Otherwise, the maximum error δ is not bounded. However, this theorem does not take into account that the function () xf could be corrupted by random noise, which is 0-7803-7954-3/03/$17.00 ©2003 IEEE. 1021 the case of the fuzzy interference estimation. In this work, in order to obtain the working regions of the fuzzy filter we impose constraints on the dynamic range of the power of the inputs and finally we verify the obtained working regions via simulations. In case of the designed fuzzy canceller, we constrain the power of each input fuzzy variable {} 1321 ,,, zxxxxi∈ to be within the designed input range [] maxmin ,∆∆ . { } 2 max 22 min ∆≤≤∆ i xE (13) Note that due to the random nature of the input signal, the instantaneous information is not so relevant as the statistical one. If we consider that the interference and the desired signals are zero mean, we could consider that ∆=∆=∆ maxmin . C. Conditions on the First stage of the Fuzzy filter. Next, we have to compute (13) for each one of the inputs of the fuzzy canceller. In particular, for the first stage of the fuzzy canceller we have substituted (2a) and (2b) into (13). In this way, the expected power of the input variables 1 x and 2 x are : {} { } 22 ,1 222 1 1 2 1∆≤        ++⇒∆≤ SNRSIR sAExE in i kk β (14a) {} { } 22 ,1 222 2 1 1∆≤      +⇒∆≤ SNR sAExE kk (14b) being () ( ) 011 iii RR−= β where () 0 i Rand () 1 i R are the autocorrelation of the interference signal for lags of 0 and 1 respectively. Next, we isolate the SIR and the SNR of (14a) and (14b). In this maner, the maximum SIR and SNR that the variables 1 x and 2 xsupport is: { } {}(){} 2 ,1 22 ,1 22 2 ,1 2 1 1 12 kkkkin kkin iin sAEsAESNR sAESNR SIR x x x−−∆ ≥ β (15a) { } {} 2 ,1 22 2 ,1 2 2 kk kk in sAE sAE SNR x−∆ ≥ (15b) Once the minimum SIR and SNR have been obtained, it is possible to know the maximum SINR improvement of the fuzzy filter. In particular, for the input 1 x we can isolate the 1 x in SIR and the 1 x in SNR from (15a) as follows: {}(){} {}        −−∆ ≤− 2 ,1 2 2 ,1 22 ,1 22 10 2 log10 1 11 kki kkkkin dB in dB in sAE sAEsAESNR SIRSNR x xx β (16) Note that the term dB in dB in xx SIRSNR 11 − is the timprovemen SINR of the fuzzy canceller in the first convergence scenario (see 11). Finally, note that the 1x in SNR and 2x in SIR are by definition positive values. Therefore the denominators of (15a) and (15b) have to be positive too. Thus, imposing the following constraints: { } {} 2 ,1 22 2 ,1 2 1 kk kk in sAE sAE SNR x−∆ ≥ (17a) { } 2 ,1 22 kk sAE>∆ (17b) Once the first stage of the hierarchical system has been evaluated, we have to analyze the second one. D. Conditions on the Second Stage of the Fuzzy Filter. To obtain the conditions on the input variables of the second stage we have to proceed as in the first one. In this way we have replaced (4a) and (4b) into (13). As a result, the constraints on the input SIR are: { } {}(){} 2 ,1 22 ,1 22 2 ,1 2 22 2 3 3 3 kkkkdin kkin iin sAEsAESNR sAESNR SIR x x x−−∆ ≥ β β (18a) { } {}(){} 2 ,1 22 ,1 22 2 ,1 2 1 1 12 kkkkin kkin iin sAEsAESNR sAESNR SIR z z z−−∆ ≥ β (18b) where () ( ) 011 ddd RR−= β and () 0 d Rand () 1 d R are the autocorrelation of the desired signal for lags of 0 and 1 respectively. Note that the 1 z in SIR and 3 x in SIR are by definition positive values. Therefore, the denominators of (18a) and (18b) have to be positive too.It implies the following constraints: { } {} 2 ,1 22 2 ,1 2 2 2 3 kkd kk in sAE sAE SNR x β −∆ ≥ (19a) { } {} 2 ,1 22 2 ,1 2 1 kk kk in sAE sAE SNR z−∆ ≥ (19b) Next, in the same way as in the first stage, it is possible to relate the in SNR and the in SIR to obtain the expression of the timprovemen SINR . In particular, for the first convergence region (see 11) its upper bound is: {}(){} {}        −−∆ ≤2 ,1 2 2 ,1 22 ,1 22 10. 2 22 log10 3 3kki kkkkdin in dB imp sAE sAEsAESNR SINR x x β β (20a) {}(){} {}        −−∆ ≤2 ,1 2 2 ,1 22 ,1 22 10. 2 log10 1 1kki kkkkin in dB imp sAE sAEsAESNR SINR z z β (20b) From the previous conditions we obtain the following constraints from the denominator of (19a) and (19b), in the same way as in (18a),(18b) was done: { } { } 2 ,1 222 ,1 22 2kkkkd sAEsAE >∆>∆ β (21) At this point we have to note that there are different upper bounds for the SINR improvement. However, just the lowest of 0-7803-7954-3/03/$17.00 ©2003 IEEE. 1022 them will be the dominant upper bound. Finally, to obtain the working region we have to compute the parameters d β ,and i β which depend on the desired and the interference signals. E. Correlation of the desired signal d β Next we defined the relationship between the chip time of the desired user d c Tand the sampling time m T as: m c dT T Od = (22) In other words, d Ois the oversampling factor, which it is measured with respect to the chip time of the desired user. Next, if we assume that the expected power of the desired user is constant for all the d O samples, and the desired user has a binary modulation, then the factor d β is equal to: d dO 1 = β (23) Note, that if 0→ d β , then the samples of the desired user are fully correlated () ( ) 01 dd RR ≈.On the contrary, if 1→ d β then the samples of the desired user are uncorrelated () 01 ≈ d R(if we assume that the spreading code of the desired user is uncorrelated or it presents high uncorrelation properties) F. Correlation of the interference signal i β The parameter i β depends on the interference correlation ( () 0 i Rand () 1 i R). In particular, to model a narrow-band signal we have resorted to a second order process AR with two poles at 99.0 1= − z [1-2]. Then, we obtain that i β is equal to [5]: 2 21 1 1 a aa i+ ++ = β (24) where 1 aand 2 aare the coefficients of the AR process of second order. In particular, if the poles of the AR model are 99.0 21 == pp , then its coefficients are: 98.1 1−=aand 9801.0 2=awhereas i β is equal to 6 105.0 − ×. On the other hand for a digital interference the parameter i β is computed in the same way as in the case of d β : i iO 1 = β (25a) m c iT T Oi = (25b) where i Ois the relation between the chip time of the digital interference i c Tand the sampling time m T. V. WORKING REGION OF THE FUZZY CANCELLER Once, we have computed the expressions of the maximum SIR, SNR and SINR improvement, and determined the magnitude of the parameters d β ,and i β we are ready to obtain the working region of the fuzzy canceller. Firstly, we have to assume a particular scenario in terms of SNR, SIR and interference type. Specifically, when the interference is AR with two poles at 99.0 1= − z, then the number of MAI users is 4= K , the processing gain of the desired and MAI users is 11=G. dBSNR in MAI 5=, dBSNR in Gauss 20=, and in SIR is varied in the range from –70 to 10 dB in 2 dB steps, the maximum amplitude of the input fuzzy variables is: 3=∆ .The sampling time of the receiver m T is equal to the chip time of the desired user d c T, then 6 105.0 − ×= i β and 1= d β . In addition, if power of the channel and the desired user is the unity { } 1 2= k AE , { } 1 2 ,1 = k sE , then the constraints on the maximum SNR that are imposed by each one of the inputs are (see(15b),(17a),(19a),(19b)): dBSNRSNRSNR dB in dB in dB in zxx 03.9 121 −≥== (26a) dBSNRdB inx44.5 3−≥ (26b) where the critical SNR is determined by the input variable 3 xsince it needs the highest SNR to work.Note that the total in SNR of the considered scenario is obtained following (10): dB SNRSNR SNRSNR SNR MAIGauss MAIGaussdB in 8.4log10 10 ≅         + × = (27) Therefore, as the total SNR at the input of the fuzzy canceller is higher than dBSNRdB inx44.5 3−≥ , then the fuzzy canceller will be able to supress the interference signal. Next, the associated SIR condition for the first hierarchical stage is (see (15a)): dBSIRdB inx22.59 1−≥ (28) The SINR improvement for the first stage and the first and second convergence regions is (see (16)): dBSINRdB timprovemen regionfirst x66.53 1≤ (29a) dBSINRdB timprovemen regionond x66.50 sec 1≤ (29b) Next, the associated SIR conditions for the second hierarchical stage are (see (18a),(18b)): dBSIRdB inz22.59 1−≥ (30a) dBSIRdB inx49.59 3−≥ (30b) The SINR improvement for the second stage and the first and second convergence regions are (see (20a),(20b)) : dBSIRSNRSINR dB z dBdB imp in regionfirst z66.53 1 1≤−= (31a) dBSIRSNRSINR dB z dB in dB imp regionond z66.503 1 sec 1≤−−= (31b) 0-7803-7954-3/03/$17.00 ©2003 IEEE. 1023 dBSIRSNRSINR dB x dB in dB imp regionfirst x93.53 3 3≤−= (32a) dBSIRSNRSINR dB x dB in dB imp regionond x93.503 3 sec 3≤−−= (32b) Note that, we have different upper bounds for the input SIR and the SINR improvement. However, we just have to consider the input variable that satisfies all the SIR and SNRimprovement inequalities for being an upper bound: ( ) dB x dB z dB x dB SIRSIRSIRSIR 311 ,,min min ≥ (33a) ( ) dB imp dB imp dB imp dB imp xzx SINRSINRSINRSINR 311 min ,,max .≤ (33b) In this way, in the interference canceller cancellation of an AR signal the minimum SIR and SINR improvement will be: () dB x dB SIRSIR 3 49.5949.59,22.59,22.59min min =−=−−−≥ (34a) () dB imp dB imp x SINRSINR 3 min .. 93.5093.50,66.50,66.50max ==≤ (34b) Note that the fuzzy canceller initially works in the first convergence region and after works in the second one. For this reason in (34b) the values of the SINR improvement correspond to the second region of convergence. On the other hand, if the communication scenario is the same as before but the interference is digital, with a processing gain equal to 11=G, the minimum SIR condition given the input SNR of (27) for the first stage (see (15a)): dBSIRdB inx25.16 1−≥ (35) The SINR improvement for the first stage and the first and second convergence regions are (see (16)): dBSINRdB timprovemen regionfirst x69.10 1≤ (36a) dBSINRdB timprovemen regionond x69.7 sec 1≤ (36b) In the same way as the first stage, the minimum SIR conditions for the scond one are (see (18a),(18b)): dBSIRdB inz25.16 1−≥ (37a) dBSIRdB inx52.16 3−≥ (37b) Next, the upper bounds for the SINR improvement in the second stage are (see (20a),(20b)): dBSIRSNRSINR dB z dB in dB imp regionfirst z87.9 1 1≤−= (38a) dBSIRSNRSINR dB z dB in dB imp regionond z87.63 1 sec 1≤−−= (38b) dBSIRSNRSINR dB x dB in dB imp regionfirst x69.10 3 3≤−= (39a) dBSIRSNRSINR dB x dB in dB imp regionond x69.73 3 sec 3≤−−= (39b) Therefore, according to the previous results the upper bound for the SIR and SINR improvement in the first and second convergence scenarios will be (Fig.3): () dB x dB SIRSIR 3 52.1652.16,25.16,25.16min min =−=−−−= (40a) () dB imp dB imp x SINRSINR 3 min .. 69.769.7,87.6,87.6max === (40b) Finally, note that from fig.2 and fig.3 the performances of the Hierarchical and Non-Hierarchical cancellers are very similar, and close to their theoretical SIR and SINR improvement −70 −60 −50 −40 −30 −20 −10 010 −10 0 10 20 30 40 50 60 70 80 Input SIR (dB) SINR improvement (dB) Hierarchical Fuzzy system Non−Hierarchical Fuzzy System SNR−SIR (esc.1) SNR−SIR−3 (esc.2) Upper Bound SINR esc.1 Upper Bound SINR esc.2 Zero Loss Line Fig.2. SINR improvement of the fuzzy canceller when the interference is AR. −30 −25 −20 −15 −10 −5 0 5 10 −10 −5 0 5 10 15 20 25 30 35 Input SIR (dB) SINR improvement (dB) Hierarchical Fuzzy system Non−Hierarchical Fuzzy System SNR−SIR (esc.1) SNR−SIR−3 (esc.2) Upper Bound SINR esc.1 Upper Bound SINR esc.2 Zero Loss Line Fig.3. SINR improvement of the fuzzy canceller when the interference is digital CONLUSIONS The main conclusion from this paper is that it is possible to introduce statistical information in the designing of a fuzzy system. As a result, it is possible to obtain the working region where the fuzzy canceller will be able to suppress an interference signal given SIR, SNR or SINR improvement. REFERENCES [1] L.A.Rush,H.V.Poor, “Narrowband interference suppression in CDMA spread spectrum communications,” in IEEE Trans. Commun., vol.42, Apl. 1994. [2] H.V. Poor, X. Wang “Code-Aide Interference Suppression for DS/CDMA Communications –Part I and II: Interference Suppression Capability and Parallel Adaptive Implementation”, in IEEE Trans. Commun., vol.45,Sep. 1997. [3] J.Bas, Ana P. Neira,”A Fuzzy Logic System for Interference Rejection in Code Division Multiple Access”, in Proceedings of the Fuzz-IEEE Conference, Sant Louis, USA, May 2003. [4] R.Alcalá,F.Herrera,I.Zwir,“Hybridizing and Weighted Linguistic Rules”,in Proce. Of the 17th ACM symposium on Applied Computing, pp. 812,816, March 2002 [5] S.Haykin, “Adaptive Filter Theory”, Fourth Edition, Ed. Prentice-Hall, 2002. dB SIRmin dB SIRmin 0-7803-7954-3/03/$17.00 ©2003 IEEE. 1024