Non-linear adaptive signal processor

NON-LINEAR ADAPTIVE SIGNAL PKN!I?SSOR M.A.Lagunas,F.Vallverdu,M.E.Santamaria Procesado de Seiial en Camunicaciones E.T.S.I. Telecmunicacion Agio. 30002 08034 Barcelona SPAIN ABSTRACT This paper is a first attempt to give formalism to non-linear system design and in which context, related with similar linear processing techniques, they are located. A smary on the relation-ship of linear objectives and classical adaptive algorithms, in non-linear design problems, introduces the paper; giving the potential of random search techniques in order to open the different problems in non-linear objectives that could be handled with them. After, the similarity between probability distribution functions and per spectral density in linear processing is shown. This is supported by a nice example of non-linear system design. Finally, some prospective work is reported in the problem of adaptive companding design. INTRowcTIcbl The first application reported in non-linear filtering is that one where a memoryless non-linear system of order Q is cascaded with a non-linear channel to be equalized. This case is depicted in fig. 1. L I Fig. 1. Non-linear adaptive equalizer. Because in this situation the objective ( i.e. the quadratic mean-square error between the training sequence and the output) becomes linear in the weigths of the non-linear equalizer, the minimum is solved in a linear way like in a Wiener filter in the linear case. Thus, writing down the formulas for the case under study, the objective will be (1). This work is supported by CAICYT grant number 21096/84 p = E (f (Z)-X)" (1) Where f(z) is a polynomic device without memory as shown in (2). It is easy to prove that the non-mmry constraint in the analysis is not a limitation to the main ideas summaryzed herein. Taking derivatives of (I) with respect the weigths a(q) and sting them to zero, equations (3) results; where /u denotes the n-order ment of the random "aria!%? z , and 0 the espectral value of the cross-product 09 z and x. E =? E [zpx] = Pt4 gP (3.a) Note that the expected value 0 can be rewritten as (4) , where the effect of the non-linear system to be compensated becomes more relevant. INLCp(x) x p(x) dx = gP (4) At the same time the design equations means that (5) holds. If(z) zp p(t) dz = In summary, the design equations check out, in and integral form, the similarity between f(NLC(x)) and x. In other words, is a test of up to what degree f(.) is close to the inverse of NLC(.). Also, it is intersting to remark that this relationship is just to control that the probability distribution fucntion pdf(x) and the pdf(y) are the same. This last point is important because a more interesting design objective would be to reduce the differences between both pdf's instead of minimizing the MSE With respect to the use of non-linear adaptive equalizers, it is worthwhile to note that the high dynamic range, needed in the update equation for the weigths and the non-linear character of the objective, forces to consider random search algorithms as a good candidate for the adaptive algorithm to be used in the non-linear processor. In this sense, it is important to remark that both ED and random search algorithms do not use the snapshot data in the weigths update. In (7) it is denoted the update for a general adaptive algorithm where is the objectiye gradient with respect the weigth vector A = a(l)ra(2),...la(Q) . At this pint, could be computed in two ways: one as a gradient of the objective in (1 ) or as a perturbation measure. In the gradient form it is computed directly frm the objective obtainig (8). being Tnus, the dynamic range of vector 2 in the adaptive loop represents a disadvantage in the hardware implementation of the system. Under a perturbation algorit'm even using gradient like algorithms a perturbation Lj is set for every weigth and the gradient d /da(q) is computed as (10). P Once the global gradient vector is computed, equation (7) is used to update the weigths. men using random search algorithms linear or not the philosophy it is set a randm perturbation and, once the resulting objective is obtained, the error evolution dictates to keep the perturbation as permanent in the random search case: or used in a guided or_ unguided form in a gradient basis update 131 , 147 - This short description of adaptive algorithms proves the potential of random search techniques in non-linear processing. At the same time and when it is decided to go for random search, the quadratic mean square error is no longer a constraint as the only realistic choice for the design objective. In fact, general versions as (11) of the objective could be used together with a random search adaptive algorithm. With p and q integers, it is easy to conclude that if q is high, low dynamic range in the output signal f (z) will receive sligh attention in the update loop. For low q the same will be true €or high dynamic range outputs. With respect parameter p the same reasoning could be made but it will be about the residual signal instead of the non-linear equalizer dynamic range, As the reader can see, starting frm a non-linear system design, the random search algorithms allow the designer to cope with interesting features of the resulting adaptation loop by handling non MSE criteria. In Fig. 2 it can be viewed the NLC used in a test with a non-gaussian input and the corresponding non-linear euqalizer of order 7 together with the learning curve of the adaptive algorithm. Pig. 2. (a) NLC system; (5) non-linear equalizer; (c) learning curve of the adaptive algorithm. PDF CONTROL AND NON-LINERR SYSTEMS This section is devoted to show that the pdf of a random variable in non-linear systems plays almost the same role that the power density function in the linear case. First at all, note that the pdf shares with the pmer spectrum the sam basic features; in other words, p(x) is always positive and describes in the amplitude damin the evolution of a random variable in a distribution form. Because the preliminary character of this work and the limitation in its extent only a few points of the undergoing research will be reported. Seems to be that, keeping in mind the similarities of p(x) with the power spectrum, the first attenp, in working out over p(x), will be to reproduce the whitening processing, which proved to be very useful1 in a better understanding of the structure of a power density. In smary, the problem to be solved is given a p(x) find the non-linear system which produces from x an 114 uniformly distributed random variable u. This situation is depicted in Fig. 3. Fig. 3. The whitening processing in a non-linear scheme. g(.) is a non-linear system without memory. The relationship between p(x), p(u) and the non-linear transfer function g(x) IS shown in (12). mere g(x) is the derivative of p(x) with respect x. Also it is assumed that g(.) is a monotone increasing function. Thus if p(u1 is desired to be constant the desired transfer function is obtained from the integral of the given p(x) as it is shown in (13). or .x (13.a) (13.b) Now, let us assume that we are interested in a parametric version of this transfer fucntion. This will be the case when the system is obtained at the transmiter location and the inverse system (i.e. the system which provides p(x) from an unifrom p.d.f. ) is needed at the receiver location. Thus, in obtaining a parametric version of g(x) we face the problem of a parametric version of p(x) itself. Assuming that p(x) is the function we are looking for, looks clear that some constraints in its design must be set in order to guarantee the similarity with the actual pdf. At this time seems $0 be that the best way is to force that p(x) and p( x) both have the same moments, lets say, up to an order 0.1. These constraints are shown in (14). [$(x)+xq dx =Yq; q=O,Q-1 being = I p(x) x" dk (14. a) (14.b) In selecting the objective many choices can be made, but the only one which guarantees the optimality of a polynomial structure is (15). Solving this variational problem, the solution (16) arises for D(x). where A9(u=O.O-1) are the Lagrange parameters for every constraint (14.a). The set of equations which provide these parameters is shown in (17), and the resulting g(x) is derived after using the integration procedure (18). The identification of the non-linear system weigths is obvious. Tl q This solves the problem of how to modify a given probability density function to obtain a flat pdf r and, of course , the way out to obtain the transfer response which produces a given pdf when the input is uniform. To note the similarity with linear processing problems is interesting to cmpute how flat p(u) is actually. The resulting p(u) is shown in (19) and, as the reader can See, it can be said that the procedure is optimum when a "MA" model is adequate for the p(x) under processing. This new concept reveals that the polynomial character of the pdf to handle will preveal in non-linear processing as pure AR model spectra does in the linear case. Moreover, in some sense the way to obtain the cefficients could be enhanced in a similar way that linear4prediction theory was stated. To do this, let us suppose that we are dealing with a non-linear model which predicts from powers of a T.V. the randm variable itself. X + U Fig. 4. Non-linear "prediction". Minimizing the variance or second order moment of the output u will arise to a different non-linear system than before. men it is desired to have the same pdf at the output of the non-linear system,it is the case where both systems will be the same. From the above the extension of linear prediction theory to the non-linear case is straigforward. In fact, the hard decision for the 115 designer arises when the structure for the optimal estimate E x/data is selected. Once this structure is given, and assuming it is a linear weigthed sum of pwersr greater or equal than one, of past samples, the design can be carried out in the adaptive form using both gradient or random search procedures. THE ADAPTIVE COMPANDING PROBLEM "here is other applications of non-linear processing where the objective is forced to be non-linear also. This is the case of the companding problem where the adaptive non-linear processor is located before the non-linear device to be compensated. This situation is shown in Fig. 5. The first decision is to select which is the rksidual to be minimized in the adaptive processor design. Fig. 5. fie problem of adaptive ccanpanding. The first choice could be to minimize the difference between z and y (i.e. e =y-z the error due to the non-linear device). This residual will prcmote that the compander attemps to reduce the dynamic range of z to the linear range of the transfer response for NLC(z). A more interesting way to describe this effect is to say that the pdf of the input random variable will be concentrated, by the non-linear processor f(x), around the linear range, of NLC(x); or at least, around the minimum distortion range of the non-linear device. An interesting case is when f(.) is designed as an adaptive compander for an one bit uuantizer 1' 31 , Fig. 6. Adaptive compander for one-bit quantizer. When minimizing the residual y-z, seems to be clear that f(x) will concentrate the pdf of x, the positive arguments side, around z equal to . The formulation of the objective to be minimized is as (20). Introducing the polynomic character of f(x) inslde (20) and seting derivatives respect to the weigth to zero, the optimum vector is obtained. The resulting equation have the form of (22) (21) As an example, using an order two equalizer or compayer, the resulting transfer fyction is (4x-l0/3x ) and the quantizer error is b /g, which provides the same error for a (5=0.866 that a optimum quantizer for the sane probability density input (pdf of x). Note that using the compander the signal to noise ratio in the cmunication channel increases due to the difference of the quantizer steep 0.866 in our case and the optimum 0.5 in the classical approach. The distribution of the input random variable was unifrm between -1 and 1. It is worthwhile to mention that, in some cases, under such approach it is needed to avoid the trivial solution of the zero output out of the compander. %cause, in general, NLC(z) provides zero output with a zero input; the previous mentioned solution produces a minimum error but do not fullfil our objective in designing the canpander. In this cases, a dynamic range constraint like f(x )=xmx should be set in the adaptive process. gxsurmnary, it could be said that non-linear objectives would requiere additional constraints in the adaptive random search algorithm in order to avoid undesired solutions or local minima. This last cment is related with the second choice we can set to the problem depicted in Figure 5. This second choice consists in selecting as residual the global difference between the output y and the input x. The solution needs also to be constrained by dynamic range or response range constraints. Taking the same example, of the one bit quantizer, it is well know that the minimum square error between y and x is obtained whenever (23) holds. Under this scheme, (23) is a constraint in the design of f(x), and the objective is to select f(.) such that its inverse g(f(x))=x minimices the noise effects at the receiver. REFERENCES A.Paoulis,"Probability,Random Variables, and Stochastic Procesess",Mc.Graw-Hill,l965. P. Eykhoff, "System identification". J. Wiley & Sons, (1979). L.R. Rabiner R.W. Schafer, "Digital Processing of Speech Signals". Prentice Hall. Monzingo, Miller, "Introduction to Adaptive Arrays". J. Wiley & Sons. 4.3. 116