A new non-linear system for estimating and suppressing narrowband interference in PN spread spectrum modulation

A NEW NON-LINEAR SYSTEM FOR ESTIMATING AND SUPPRESSING NARROWBAND INTERFERENCE IN PN SPREAD SPECTRUM MODULATION A. I. Pkrez-Neira, J. Roca, Ad A. Lagunas' Universitat Politecnica de Catalunya. Dept. Signal Theory and Comm. C1 Jordi Girona, 1-3. Campus Nord UPC. Edificio D-5 08034 BarcelonaSPAIN ABSTRACT This work develops a novel dynamic fuzzy logic system that, based on a fuzzy basis function expansion, successfully solves the non-linear problem of narrowband interference prediction and rejection in DS-SS. A fuzzy basis function representation provides a natural framework for combining both numerical and linguistic information in a uniform fashion. The result is a low complexity non-linear adaptive line enhancer, which offers a faster convergence rate and an overall better performance over other well-known non-linear line enhancers. 1. 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. 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 [ 11. In the case where a single antenna is used and the statistics of the interferent signals are unknown, the rejection filter is usually a transversal adaptive filter (adaptive line enhancer or ALE) and relies on both, the pseudo-white properties of the SS signal and the predictability of the narrowband interference, both present in the received signal z(t). The received signal z(t) consists of 3 additive componenets: the SS transmitted signal s(t), the wide-band noise n(t), and the narrow-band (NB) interference i(t) z(f) = s(f) + n(t) + i(t) (1) s(t) = A c(t) d(t) cos(w,t) (2) The signal s(t) is a modulated wideband signal given by where A is a constant amplitude, W, is the carrier frequency, d(t) is the information, a binary data sequence taking on the equiprobable values of f 1 each of which lasts for T seconds, and c(t) is the spreading sequence, usually a pseudorandom noise (PN) code o chip sequence, which also takes the values of fl but which lasts for Tc seconds, where T,.c<T In reception, to recover the information d(t), z(t) is chip-matched and sampled at the chip rate of the PN sequence. We thus have zk = sk +nk + ik (3) where (st}, (nt} and (it} are the discrete-time sequences from (s(t)), (n(t)) and (i(t)] respectively. (sk}, (nt} 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 Inc. Finally, since the PN sequence is random, we can assume (sk}, to be a sequence of i.i.d. random variables taking values of k 1 with equal probability. In equation (3), (st), and (nt} 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 highty 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 nonlinear. Only if the SS signal lies below the noise floor, then the Gaussian assumption for sl;+nk is more reasonable and a linear filter achieves good results [l]. In [2], Masreliez developed an Approximate Conditional Mean or ACM filter, with a structure similar to that of the Kalman filter, in order to estimate the state of a linear system with nonGaussian observation noise. Vijayan and Poor [3] employed this algorithm to solve the NB interference suppression problem in the DS-SS. When the AR parameters are unknown, Vijayan and Poor also developed an adaptive nonlinear LMS algorithm based on the ACM filtering algorithm. This algorithm was later modified by Rush and Poor [4] and Wu [5]. All these non-linear algorithms depart from the state-space representation of the system i, = (Pi,-, + w, (44 Z, = hi, +v, (4.b) where the interference has been modeled as a Gaussian AR process of order P. The state vector is ik=[ik. it.,,.. it-p+,] and is generated by the Gaussian process wk=[wk 0 ... of, and the matrix @, formed by the AR parameters. The observation vector is h=[l 0 ... 01 and the measurement noise is the non-Gaussian sequence vk= sk+nk. This work has been supported by National Research Plan of Spain CICYT under grant number TIC-96-0500-C10-01 3261 0-7803-4428-6/98 $10.00 0 1998 IEEE Neural Network and Radial Basis Function systems have also been studied as adaptive line enhancers [6] and [7]. 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, though the nature of the error surface is not known, it is highly likely that there are multiple local minima. Therefore, a gradient search technique cannot be guaranteed to converge to the globally optimum parameter estimates. In this work we depart from the Kalman and ACM filter state space formulation in (4) and design an adaptive fuzzy predictor which outperforms the results of the recent works of [3] and [SI and speeds up the convergence of the adaptation process. Also 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. 2. ADAPTIVE FUZZY LINE ENHANCER The fuzzy rejection filter to design departs from the state space representation formulated in (4). Taking advantage of the relationship equated in (4.b), the fuzzy system predicts the interference sample ik from the observation zk. In contrast to other non-linear interference cancellers, the proposed system does not require the mathematical model of the interference in (4.a): no AR parameters have to be neither known nor estimated. The fuzzy system to design just relies on the slow varying nature of the NB interference in order to model its behavior by means of linguistic IF-THEN rules, which replaces equation (4.a). The interference range is quantized in regions or fizy 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;l is in the region ofpositive high values and ikm2 is in the region of positive high values and ik-, is in the region of positive high values THEN ik is in the region of positive high values". These IF-THEN rules are the core of the fuzzy system to design. Additionally, the statistical knowledge of the measurement noise (vk] and model noise (Wk} can be easily introduced in the design of the proposed system fuzijication stage. A fuzzy system is a functional network (Fig. 1) represented as series expansions of fuzzy basis functions g, (x) M Y = m) = g, (XI ei (6) 1'1 where 6 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=Tk and the input x is the measurement zk and two fee-forwarded interference estimated values: x = [z, jk-3 ik-2]. The most important advantage of using fuzzy basis functions, rather than polynomials, radial basis functions, neural networks, etc., is that a 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. B (.) = r m: I Rule base: matrix R 11 P e Y I I Figure 1. Adaptive fuzzy line enhancer. In fig. 1 we distinguish 4 main parts: the fizzper 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 fiiy 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. 1) to fuzzy sets in the output space Y (i.e. Bi(.) in fig.2). Finally, the defizifer maps the aggregated output fuzzy sets to the single crisp point in the output space, which in our system is the interference estimate of ik to be used by the communication receiver. Next, the design of the proposed fuzzy logic system (FLS) is described. 2.1 The mathematical framework of theory of fuzzy sets provides a natural basis for fuzzy logic, which is a generalization of binary logic. In other words, the logical inferencing using fuzzy sets is known as fuzzy logic [8-111. In fuzzy set theory there is no sharp boundary between those objects that belong to the class and those do not. In addition, an element may also be a member of more than one set. Membership function in a fuzzy set is a matter of degree. 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 3 [0,1]. Thus, a fuzzy set F consists of a generic element U and its grade or membership function; that is, F =((u,p,(u))IuE 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. Due to noise, the measured inputs are vague and, therefore, the system classifies or quantize them in overlapping regions or fuzzy sets Ai(.), to whom the inputs belong with some membership degree (e.g. A3(.) stands for the fuzzy value: " positive high value"). Thus, these sets conform in a natural situation when describing the possible values of the 3 measurements in x. The Four Stages of the FLS 3262 Figure 2. Fuzzy term set for the variable “filter input” Figure 2 plots Gaussian membership functions, however, there are different methods to determine a fuzzy membership function [IO]. 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 (4.b) we know the conditional probability density (f.d.p) function of ik-1. p(ik-l /z~-~). Therefore, if we relate the fuzzy sets AI 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 ikI. This dynamic designed fuzzy sets (dynamic because their position depend on the value of &.I) act as a reference for locating values ik+ ik.3 in a slow varying narrowband. Additionally, to obtain the fuzzy set for zk we note that P(Z, /ik-l) can be assumed to be Gaussian by a reasoning equivalent to the one used by Masreliez in [2] 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.2. Finally, the output fuzzy sets B(.), which quantized in a fuzzy way the possible values of the estimated interference values fk , 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.2, however, they can be modified by a LMS type algorithm as we comment later in this section 2. 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 fuuifier maps a crisp measurement or value into a fuzzy set. The most widely used fuzzifier is the singleton fuzzifier: the crisp point xi is mapped into a fuzzy set F with support x where pF(x)=6(x-x,~. We note however that in cases when the signal-to-noise ratio (SNR) is low or there is high input uncertainty, non-singleton fuzzy sets [8] are more useful as the simulations in this paper show. The fuzzy rule base consists of a set of linguistic rules in the form of “IF a set of conditions are satisfied, THEN a set of conseqiiences are inferred”. Suppose we have a rule base consisting of M fuzzy if-then rules R, (m=1 ... M) R, : IF iL-, is A,, and lk-? is A,, and where {0,+1,+2,+3}. The predictor of interference ik 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 is A,, THEN fk is B, is PRm(X?y)=PAm,(X)*PAw (‘)*PAd (’)*PB,(Y)’ where the most commonly used operations for “*” are “product” and ‘“in’’ [8]. 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 72 rules by avoiding those irrelevant rules for slow varying interferences such as: R, : IF t-, is A-, and t-, is A, and z, is A-, THEN is B.! The fuw inference engine or fuzzy associative memories 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 com osition [81: singleton fuzzification pF (x) = 6(x - x, ) and results in pFoRm (y) = SUPE,y bF (XI *pRm (x, YIP 1’ the case of p,G.Rm (y) = PA, (k-3)*/’!AM (L-2)*pAk (2k)*/’!Bm(y) = wm(x)*p8m (r) where w, is the firing strength or weight of the mth rule. In summary, all the M rules of the FAM’s are activated parallely and imply a fixed number of sums and multiplications. At instant of time “k”, the result of the inference of each rule can be expressed as a matrix multiplication [ 111 (fig. 1). Finally, the individual statement solutions are aggregated to provide the overall solution After the fuzzy inference, the defuuifier 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 domain “y” in a Bayesian sense (see eq. (8)). m=l where 7, = centroid {B, (y)} and 8, = F,,, Note that we have finally come to the functional expression (6). which depends linearly on the output parameter 8,. Therefore, we propose to use an LMS (least mean square) type algorithm in order to adjust 0, and refine the fuzzy system result. This LMS is modified to incorporate the approximate conditional mean non linearity exactly in the same way as done in [3]. That is the adaptive algorithm is applied to each fuzzy system output ik in order to minimize ( zk - i”, - sign ( zk - i; )II* . II 3. SIMULATIONS In this section, we report on simulations carried out to evaluate the performance of the proposed algorithms. We follow the commonly used SNR improvement, defined in [3-51. The SNR at the input was varied by changing the power of the interfering examples studied in [3] and [SI. Our performance measure is the 3263 signal. The variance of the background thermal noise was kept constant at a * = 0.01. The SS processing gain is 10. AH results were obtained based on 10 trials and, for each trial, 3000 data points were computed. Table I summarizes the results of the 3 sets of simulations. It can be seen that adaptive non linear filtering fuzzy techniques offer considerable improvement over conventional linear filters (i.e. TS-LMS: Two Sided Least Mean Square filter) and the non linear algorithm designed in [5]. We note that, if to simplify computation triangular membership functions are used instead of Gaussian ones, the results just degrade in 1 dB. 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, for high SNR ratios the performance is not so good as in [5]. 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. Other point to remark is that the LMS adaptation is even not needed in the case of the AR interference. In any case, the LMS converges in few samples (fig. 3) due to the good rule initialization and the good properties of the FBF. Finally, we have also carried out a study for noisy scenarios. As nothing is said in [3-5] for this case, we compare our algorithm with the linear ALE of 4 taps reported in [l]. Figure 4 shows the performance of the proposed algorithm when no LMS adaptation is carried out. The best results are for the non-singleton fuzzy filter, which is more suitable for noisy scenarios 181. 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. 4. CONCLUSIONS 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 convergence, 0.1. 0.s.J 0.3 O.t6 0.Z 0.16 0.7 0.0s 5. REFERENCES J.Ketchum, J.Proakis, “Adaptive algorithms for estimating and suppressing narrowband interference in PN SS systems,” IEEE Trans. Comm. Vol. 30, May 1982. C.J.Masreliez, “Approximate non-Gaussian filtering with linear state and observation relations,” IEEE Trans. Aut. Cont., Feb. 1975. R.Vijayan, H.V.Poor, “Nonlinear techniques for interference suppression in SS systems,” IEEE Trans. on Comm. Vol. 38, July 90 L. Rush, V.Poor, “Narrowband interference suppression in CDMA SS comm.,” IEEE Trans. On comm., vol. 42, Feb./MarchlApril 1994 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. . . . 1 [6] R.Bijjani, P.K.Das, “Rejection of Narrowband interference in PN SS systems, using neural networks,” Proceed Of ICASSP’90 Conference., pp. 1037-1040 [7] I.Cha, S.A.Kassam, “Interference cancellation using radial basis function networks,” Signal Processing 47, Elseviefl5. [8] L.Wang, J.M.Mende1, “Fuzzy Basis Functions, Universal Approximation, and Orthogonal Least-Squares Learning,” IEEE Trans. on Neural Network, vol. 3, no.5, Sept. 1992. [9] Zadeh, L.A., “Outlined of a new approach to analysis of complex systems and decision processes,” IEEE Trans. 0 Systems, Man and Cybernetics, vol. 3, no. 1, January 1973. [lo] Nakajima S. and Hamada H. “Automatic generation of synthesis units based on context oriented clustering”. Proceed. ICASSP. New York, April 1988, pages 659-662. [ 1 I] B.Kosko, Fuzzy Engineering, Prentice-Hall, 1997. -ASingleton Filter Figure 4.BER after despreader for 100 tones. The signalto-interference ratio per chip is -20 dB. AR interference I TS-LMS/DR2D [SI I 26.9/37 I 22.3132.6 I 17.6/28.1 1 13/23.4 I I Fuzzy I 35.7 I 31.6 I 26.8 I 21.9 I Sinusoidal interference (1 tone), fnor=O. 15 -1 Sinusoidal interference (100 tones in Table 1. SNR improvement (dB) for singleton fuzzification. 3264