An adaptative fuzzy logic enhancer for rejection of narrowband interference in DS-Spread Spectrum

AN ADAPTIVE FUZZY LOGIC ENHANCER OWBAND INTERFERENCE IN D.S-S Ana PCrez-Neira, Carles Ant6n-Haro, Miguel A. Lagunas Dpt. of Signal Theory and Communications - Universitat Politbcnica de Catalunya c/ Gran Capith s/n. Campus Nord UPC. Edifici D5 - 08034 Barcelona (SPAIN) Fax: +34-3-4016447 e-mail: { anuska,miguel} @gps.tsc.upc.es Abstract’: This work develops a novel adaptive fuzzy line enhancer that, based on a fuzzy basis function expansion, successfully solves the non-linear problem of narrowband interference estimation and rejection in DS-SS in nonstationary environments. A fuzzy basis function representation provides a natural framework for combining both numerical and linguistic information in a uniform fashion and towards a least-mean-square objective. The result is a low complexity non-linear adaptive line enhancer (ALE), which presents a fast acquisition time and a better SNR improvement than other well-known non-linear ALE’S. I. INTRODUCTION Spread Spectrum (SS) communications offer a promising solution to an overcrowded frequency spectrum amid growing demand for mobile and personal communication services. The proposed applications for commercial use of spread-spectrum involve the overlaying of spread spectrum signals on existing narrowband (NB) users, thus, implying strong interference for the SS system [l]. While SS has inherent noise suppression capability, system performance can be further enhanced at the decision device if an interference rejection filter or line enhancer is used before despreading [2]. In the case where a single antenna is used and the statistics of the interference signals are unknown, the rejection filter is usually a transversal adaptive filter (adaptive line enhancer or ALE). Relying on the pseudo-white properties of the received SS signal, this filter predicts the narrowband (NB) interference, which is also present in the received signal. Due to the SS signal this predictiodfiltering of the NB interference is a non-Gaussian problem. Since the 1990’s nonlinear prediction filters have been proposed with significant SNR improvement over the linear filters. In order to obtain the optimum estimatiodprediction (i.e. in the least-mean-square error sense) with non-Gaussian observation noise, Masreliez [3] developed an Approximate Conditional Mean or ACM filter. Vijayan and Poor first [4] employed this algorithm to solve the NE3 interference suppression problem in the DS-SS. For the case of interference with unknown mathematical model, they also developed an adaptive nonlinear LMS This work was partially supported by the National Plan of Spain, CICYT, TIC96-0500-C10-01. 0-7803-4320-4/98/$5.00 0 1998 EEE algorithm based on the ACM filtering algorithm. This algorithm was later modified by Rush and Poor [5] and Wu [6]. However, the general problem of non-linear predictors is that they require greater complexity than its linear counterpart, which is typically encompassed in a single DSP chip. Additionally, for non-linear filtering, as the nature of the error surface is not known, it is highly likely that there are multiple local minima. Therefore, a gradient search technique used in ALE’S cannot be guaranteed to converge to the globally optimum parameter estimates. Finally, non-linear ALE’S are very sensitive to the noise level. In this work we design an adaptive fuzzy predictor which overcomes the problems mentioned above and outperforms the results of the recent works of [SI and [6]. The proposed technique presents an attractive parallel algorithmic structure, where, at each instant of time, just a fixed number of products and sums and one division are needed to produce the output. 11. PROBLEM FORMULATION The low-pass equivalent of a DS-SS modulation waveform is given by (1) k=O where Nc is the number of PN chips per message bit, Tc is the chip interval, ck is the kh chip of the PN sequence and q(t) is a rectangular pulse of duration Tc. The transmitted signal is expressed as where { bk} is the binary information sequence and Tb=NcTc is the bit duration. The received signal is defined by z(t)=s(t)+i(t)+n(t). Where n(t) is wideband noise and i(t) is narrow-band interference. Suppose that the received signal is chip-matched and sampled at the chip rate of the PN sequence. We thus have (3) where {sk}, Ink} and {ik} are assumed to be mutually independent. We have assumed that n(t) is bandlimited and becomes white after sampling. For the interference, we have considered that its bandwidth is small compared with l/Tc. Finally, since the PN sequence is random, we can assume { sk}, zk = sk + nk + i, 1598 VTC ‘98 to be a sequence of i.i.d. random variables taking values of k 1 with equal probability. In eq.(3), {sk}, and {nk} are wideband signals and are poorly correlated when sampled at the chipping rate. Therefore when the ALE tries to estimate the next sample of the signal, it would succeed only in estimating the highly correlated interference and consequently manages to suppress it. Note, however, that the sequence { sk} is highly non-Gaussian. Thus, the optimum filter for predicting a narrow-band process in the presence of such a sequence will, in general, be non-linear. Fig. 1 shows the non-linear ALE architecture derived in [5-71, which is a feed-back Decision Directed structure (the error that controls the FIR can be either taken at point 1 or at point 2). Only if the SS signal lies below the noise floor, then the Gaussian assumption for sk+nk is more reasonable and a linear filter achieves good results tanh(.) sign(.) DS-SS Fig. 1 : Non-linear Adaptive Line Enhancer architecture This work develops a new non-linear ALE. As Fig. 2 depicts, this ALE is based on a fuzzy logic system with feed-back that is is able to introduce the generic or vague narrowband knowledge of the interference to improve its estimation with respect to the architecture in fig. 1. Additionally, no Decision Directed learning is necessary, thus making the proposed system more robust in front of noise and with less computational complexity. =k I I System DS-SS Q-qg Fig. 2: Adaptive Fuzzy Line Enhancer with memory. 111. DYNAMIC FUZZY LOGIC FILTER A fuzzy system is a functional network (Fig. 3) represented as series expansions of fuzzy basis functions g, (x) (4) where 0, E R are constants. Using the Stone-Weierstrass theorem, linear combination of fuzzy basis functions prove to be capable of uniformly approximate any real continuous function on a compact set to arbitrary accuracy [8]. In our case y=lk and the input x is the measurement zk and two fedbackward interference estimated values: x = [zk ik-3 ik-2]. Therefore, the proposed system has memory and is referred as a dynamic system. The most important adtantage of using fuzzy basis functions, rather than polynomiials, radial basis functions, neural networks, etc., is that (3 linguistic IF-THEN rule is naturally related to a fuzzy basis function (FBF). In other words, the FBF provide a general framework to translate abstract concepts into computable entities. Fig.3: The Dynamic Fuzzy ALE as a functional network In contrast to other non-linear interference cancellers (e.g. those based on the ACIM filter), the proposed system does not require the mathematical model of the interference. The fuzzy system to design just relies on the slow varying nature of the NB interference in orcler to model its behavior by means of linguistic IF-THEN rules. The interference range is quantized in regions or fuzzy sets and, from a reference point, the evolution of the interference among this regions is followed by means of linguistic IF-THEN rules of the type: “IF ik-3 is in the region of positive high values and ik-2 is in the region of positive high values and ik-, is in the region of positive high values THEN ik is in tho region ofpositive high values”. These IF-THEN rules are the core of the fuzzy system to design. Additionally, the statistical knowledge of the measurement noise {nk} can be easily introduced in the design of the proposed system fuzzijkation stage. In fig. 3 we distinguish 4 main components: the fuzzijier maps the crisp inputs x to fuzzy sets defined on the input space; the set of statements comprise the fuzzy rule base, which is a vital part of a Fuzzy Logic System, the fuzzy inference engine combines the statements in the rule base according to approximate reasoning theory to produce a mapping from fuzzy sets in the input space X (i.e. Ai(.) in fig. 3) to fuzzy sets in the output space Y (i.e. Bi(.) in fig.3). Finally, the defuzzziJer maps the aggregated output fuzzy sets to the single 0-78034320-4/98/%5.00 0 1998 EEE 1599 VTC ‘98 crisp point in the output space, which in our system is the interference estimate of ik to be used by the communication receiver. Within each component, there are many different choices that can be made and many combinations of these choices result in different fuzzy logic systems or FLS. Next, the design of the proposed FLS is described. A. Fuzzy Sets and FuzziJcation The mathematical framework of theory of fuzzy sets provides a natural basis for fuzzy logic, which is a generalization of binary logic. A fuzzy set F in a universe of discourse, U, is characterized by a membership function pF, which takes values in the interval [O,l]; that is, pF : U -+ [0,1]. Thus, a fuzzy set F consists of a generic element U and its grade or membership function; that is, F = tu, pp E U}. A fuzzy variable is characterized by a term set or set of fuzzy sets (i.e. of linguistic or fuzzy values) of U. In this work A(.) and x will be used for the input term set and the input variable, respectively. Also B(.) and y will be used for the output term set and the output variable, respectively. Fig. 4 shows the overlapping regions or fuzzy sets Ai(.) designed in this work (e.g. As(.) stands for the fuzzy value: “positive high value”). As explained later in this section, the fuzzy system uses these sets to classify or quantize the measured inputs. We note that due to the noise, these inputs are vague and, therefore, the fuzzy sets conform in a natural situation when describing the possible values of the 3 measurements in x. Fig. 4. Fuzzy term set for the variable “filter input” There are different methods to determine a fuzzy membership function. It is worth noting that a membership function may be subjective, but not arbitrary. Since our problem employs statistical inputs, the design based on their probability density functions shall be appropriate. In this way, we relate the fuzzy membership functions to physical properties of the system. From eq. (3) we know the conditional probability density (f.d.p) function of ik-l, p(ik-l /z~-~). Therefore, if we relate the fuzzy sets A,, with this f.d.p., we can say that whenever the input falls inside these fuzzy sets, this input will be related to some degree with ik1. This dynamic designed fuzzy sets (dynamic because their position depend on the value of q.1) act as a reference for locating values ik-2, ik.3 in a slow varying narrowband signal. Additionally, to obtain the fuzzy set for zk we note that p(z, / jk-,) can be assumed to be Gaussian by a reasoning equivalent to the one used by Masreliez in [3] to develop the ACM filter. Thus, the fuzzification of zk is done by means of the same fuzzy set term A(.) as the one depicted in fig.4. A specific feature of the designed fuzzy sets is that their reference position is zk-1 . In this way the input range and, consequently, the number of fuzzy sets and fuzzy rules can be considerably reduced in comparison to considering x = [zk zk-l ik-3 ik-2] and the fuzzy sets centered at a static reference point. Finally, the output fuzzy sets B(.), which quantized in a fuzzy way the possible values of the estimated interference values i; , have been designed as M Gaussian functions normalized to 1 and of equal variance. M is the number of IF-THEN rules. Their means are initially the same as those in fig.4, however, they can be modified by a LMS type algorithm as we comment later in this section. We note two general design considerations: 1) because of the relationship between f.d.p and membership functions, the more noise present, the wider the fuzzy sets have to be; 2) to save computation the input fuzzy sets of fig. 2 and the output fuzzy sets can be designed as triangles with the same width as the Gaussian noise variance. Once the input fuzzy sets are designed, the fuzz$.. maps a crisp measurement or value into a fuzzy set. The most widely used fuzzifier is the singleton fuzzifier: the crisp point x, is mapped into a fuzzy set F with support x where P&)=4X-XX,). B. Fuzzy Rule Base The fuzzy rule base consists of a set of linguistic rules in the form of “IF a set of conditions are satisJed, THEN a set of consequences are inferred”. Suppose we have a rule base consisting of M fuzzy if-then rules R,,, (m=1 ... M) The fuzzy rule base consists of a set of linguistic rules in the form of “IF a set of conditions are satis$ed, THEN a set of consequences are inferred”. Suppose we have a rule base consisting of M fuzzy if-then rules R,,, (m=1 ... M) R, :IF ;h-3 is A,, and ;h-2 is A,, and zh is A, THEN ?, is B, where ij,k E {O,+l,k2,+3}. The predictor of interference ik is constructed based on the M rules. Each rule R, can be viewed as a fuzzy implication which is a fuzzy set R,,,(.) in XxY with commonly used operations for “*” in engineering are “product” and ‘“in” [8-91. In this work we have used the “product” operation. The fuzzy rules can be sistematically derived by considering all the possible combinations among the 7 membership functions (73=343). However, in this work, this rule explotion is dramatically reduced to less than 75 rules by avoiding those that, for slow varying interferences, are impossible such as: R,,, : IF {-? is A-, and {+ is 4 and z, is A+ THEN { is B, PRm(x> v) = PA,, (x> * /’!Am, (x> * PAmk (x> * pB, (y) ’ where the most or controversial such as: R,,, : IF {-? is A, and {-2 is A, and z, is A, THEN is B, 0-7803-4320-4/98/$5.00 0 1998 IEEE 1600 vTc*‘98 As an example of irrelevant rules, Fig. 5 depicts an example of the activity of the 343 rules when the system estimates a 100 tone interference that occupies 20% of the SS band. This graph represents in % the number of times out of 1000 samples that each rule activates. Rule aCtlVatlon lor SlnusoldaI Interference (1 00 tones) 12, (7) From Parzen’s work on estimation of a p.d.f, it can be demonstrated [ 8-91 that the centroid defuzzification of eq.(7) maps to a conditional mean estimate E[Y/X=x] and thus presents an alternative 1.0 the ACM estimator of [3]. However, in contrast to [3], the fuzzy system does not need any mathematical model for the interference. By substituting eq.(5) and eq.(6) in eq.(7) we come to Fig. 5. Number of times that each of the 343 rules activate in the estimation of a 100 tone interference. Another important point is the easy initialization of the consequents of the rule base or FAM’s (Fuzzy Associative Memories). Just some expert reasoning that takes into account the slowly varying nature of the interference is needed. An example is the following rule: R,,, : IF L-3 is A-, and ik-, is A, and zk is A, THEN L is B2 C. Fuzzy inference engine The fuzzy inference engine is decision making logic which employs fuzzy rules from the fuzzy rule base to determine a mapping from the fuzzy sets in the input space X to the fuzzy sets in the outputs space Y. Let F be a fuzzy set in X; then each R, determines a fuzzy set FOR, in Y based on the sup-star composition [81: pF,Rm (v> = supx,=, bF (x> * pRm (x, Y>]- In the case of singleton fuzzification pF (x) = b (X -x, ) and results in (Y) = PA,, (C-JPA~, G-~).PA~~ G,~).PB~(Y) = wm(x).~Bm (Y) (5) where w, is the firing strength or weight of the mth rule. In summary, all the M rules of the FM’s are activated parallely and imply a fixed number of sums and multiplications (i.e. at instant of time “k”, the result of the inference of each rule can be expressed as a matrix multiplication [9] (fig.3)). Finally, the individual statement solutions are aggregated to provide the overall solution M PB = WmPBm m =1 D. Defuzzijier After the fuzzy inference, the defuzzi fier performs a mapping from the fuzzy sets in Y to crisp points in Y. The following centroid or center of mass defuzzifier [8] is the most commonly used method. It uses all and only the information in the output set B in its domainy in a Bayesian sense From eq. (8) we note thlat the developed fuzzy ALE computes: 3M multiplications (i.e. input vector x has 3 components and the rule base has M rules), 2M additions and 1 division at each time “k”. In contrast to the non-linear ALE of fig. 2, no sign(.) or tanh(.) function has to be carry out for detection of the SS signal sk. Note that eq. (8) is a functional expression which, as eq. (4), depends linearly on the output parameter 0,. Therefore, if computational complexity is not mandatory, we propose to use a LMS (least mean square) type algorithm in order to adjust 0, and refine the fuzzy system result towards E[Y/X=x]. This LMS is modified to incorporate the approximate conditional mean non linearity exactly in the same way as done in [6] (i.e. fig. 1). That is the adaptive algorithm is applied to each fuzzy system output i; in order to minimize the instantaneous error II( zI - i; ) - ( zb - i; )11* . Due to the good rule initialization the LMS converges in few samples and also avoids the problem of local minima. IV. SIMULATIONS In this section, we report on simulations carried out to evaluate the performance of the proposed algorithms. First, fig.6 shows the temporal acquisition and tracking of a non-stationary interference. The interference alternates between a 100 tone interference and an AR one. We note the almost instantaneous acquisition. We follow the examples studied in [4] and [6]. Our performance measure is the commonly used SNR improvement, defined in [3-51 as a measure of interference rejection. The SNR at the input was varied by changing the power of the interfering signal. The variance of the background thermal noise was kept constant at o = 0.01. The SS processing gain is 10. All results were obtained based on 10 trials and, foir each trial, 3000 data points were computed. Table I summarizes the results for 3 types of interference and compares them with the conventional linear 0-7803-4320-4/98/$5.00 0 1998 IEEE 1601 VTC ‘98 filter (i.e. TS-LMS: Two Sided Least Mean Square filter) and the non linear algorithm DR2D designed in [5]. We note that, if to simplify computation triangular membership functions are used instead of Gaussian ones and no LMS adjustment is done, the results just degrade in 1 dB for the AR interference. Also, in the case of AR interference no difference exists if the 72 rules are reduced to 32. In the case of single tone sinusoidal interference the performance is not so good as in [6]. This fact is due to the quickly speed of change of the value of the interfering signal. If we wish better results, we have to assign more membership functions to the inputs to cover the variations of the interfering signal. When the LMS adjustment is used (with p=l), however, it can be seen that adaptive non-linear filtering fuzzy techniques offer considerable improvement over TS-LMS and DR2D. Finally, we have also carried out a study for noisy scenarios. As nothing is said in [4-61 for this case, we compare our algorithm with the linear ALE of 4 taps reported in [2]. Table I1 shows the performance of the proposed algorithm when no LMS adaptation is carried out. Logically, the performance of the linear filter is improved for low noise. For high noise, the designed system improves the linear predictor LP and obtains BER of the same order of magnitude than the LP with matched filter. We note that in the linear simulations AR parameters are considered known, while in the fuzzy system no interference knowledge is assumed. V. CONCLUSIONS AND FUTURE WORK In this work we have addressed the problem of interference rejection in SS systems. We present a low computational algorithm that improves the performance obtained with recent non-linear algorithms. Just the slow varying nature of the NB interference is assumed and used for the rule initialization, which helps to avoid local minima and to speed up acquisition time. Additionally, by increasing the fuzziness of the enhancer inputs, the proposed fuzzy system is being further developed in order to improve the robustness for low SNR channels. Finally, we comment that the idea of non-linear fuzzy filtering is being extended to the joint eslimation of co-channel signals. VI. REFERENCES [l] T.Widdowson, “A CDMA data overlay of the GSM network,” Proc. of PIMRC 97, Helsinki, Finland, September 1997. [2] JXetchum, J.Proakis, “Adaptive algorithms for estimating and suppressing narrowband interference in PN SS [3] C.J.Masreliez, “Approximate non-Gaussian filtering with linear state and observation relations,” IEEE Trans. Aut. Cont., Feb. 1975 [4] R.Vijayan, H.V.Poor, “Nonlinear techniques for interference suppression in SS systems,” IEEE Trans. on Comm. Vol. 38, July 90. systems,” IEEE Trans. Comm. Vol. 30, May 1982. 0-7803-4320-4/98/$5.00 0 1998 IEEE [SI L. Rush, V.Poor, “Narrowband interference suppression in CDMA SS comm.,” IEEE Trans. On comm., vol. 42, Feb./March/April 1994. [6] W.Wu, F.Yu, “New nonlinear algorithms for estimating and suppressing narrowband interference in DS-SS systems,” IEEE Trans. on Comm. Vol. 44, April 1996. [7] J.Ketchum, J.Proakis, “Adaptive algorithms for estimating and suppressing narrowband interference in PN SS systems,” IEEE Trans. Comm. Vol. 30, May 1982. [8] L.Wang, J.M.Mende1, “Fuzzy Basis Functions, Universal Approximation, and Orthogonal Least-Squares Learning,” IEEE Trans. on Neural Networks, vol. 3, no.5, Sept. 1992 [9] B.Kosko, Fuzzy Engineering, Prentice-Hall, 1997 Real & Predicted interference - Real Interference -“- . Predicted Interference 0 100 200 300 400 500 600 700 800 Epoch number Error In the SS-Signal Estlmatlon 3-20 100 200 300 400 500 600 700 800 Epoch number Fig.6. Fuzzy ALE without LMS: non-stationary interference tracking, SIR=-20 dB, 0~=0.01, Eb/N0=27 dB Table 2. Comparative BER after despreader for 100 tone interference. The SIR per chip is -20 dB. 1602 VTC ‘96