Nonlinear adaptive filter
BACKGROUND OF THE INVENTION 
     The present invention relates to signal processors for correcting signal distortion by shaping the frequency spectrum and/or the amplitude-density function of the signal. 
     Signals transmitted from one point to another are subject to a number of distortion mechanisms. 
     One classical distortion mechanism is linear, or convolutional, distortion. A linear method of correction, called predictive deconvolution, has been developed to remove convolutional distortion from the signal by whitening the frequency spectrum of the signal. This method is described in U.S. Pat. No. 4,000,369, entitled &#34;Analog Signal Channel Equalization With Signal-in-Noise Embodiment&#34; (James E. Paul Jr. et al., Dec. 28, 1976) and U.S. Pat. No. 4,052,559, entitled &#34;Noise Filtering Device&#34; (James E. Paul Jr. et al., Oct. 4, 1977). In the method described in the second of those patents, additional spectrum shaping is done by a fixed passive filter in tandem with the predictive deconvolver to restore a natural shape to the spectrum. U.S. Pat. No. 4,507,741, &#34;Adaptive Spectrum Shaping Filter&#34; (Stanley A. White, Mar. 26, 1985) describes a more powerful filter for actively shaping the frequency spectrum of an input signal from any given initial form to any desired output form. Such processing is also linear. 
     A second distortion mechanism that can severely corrupt a transmitted signal is nonlinear distortion. U.S Pat. No. 4,315,319, &#34;Nonlinear Signal Processor&#34; (Stanley A. White and V. A. Vitols Feb. 9, 1982) describes a nonlinear signal-processing technique to combat the problem of nonlinear distortion by mapping an input signal having any given amplitude-density function into a new signal with any desired amplitude-density function, subject only to the constraint that the distorting mechanism be a single-valued nonlinear function, the slope of which is everywhere positive. The nonlinear signal-processing technique of that patent has been successfully applied to both speech and image-restoration problems. 
     Nevertheless, some problems in actual signal transmission remain. Most signals are in fact subjected to both convolutional (linear) and nonlinear distortion. Yet, it has been found that attempting to restore the signal by coupling two correction devices together in series has not worked successfully. A linear filter followed by a nonlinear filter shapes the frequency spectrum first, then corrects the amplitude-density function. Unfortunately, shaping the amplitude-density function changes the frequency spectrum established by the linear filter. A nonlinear filter followed by a linear filter corrects the amplitude-density function first, then shapes the frequency spectrum. However, the frequency-shaping function of the linear filter modifies the desired amplitude-density function established by the nonlinear filter, except in the case of a Gaussian-shaped density function. 
     SUMMARY OF THE INVENTION 
     The nonlinear adaptive filter of the present invention shapes both the frequency spectrum and the amplitude-density function essentially simultaneously. 
     The present invention is a signal processor having an input and an output. The signal processor includes a nonlinear filter and a linear filter connected serially between the processor input and the processor output. The parameters for the linear filter are derived from signals on the processor output and signals on the processor input. 
     The parameters for the linear filter are preferably computed by a parameter computer connected to the processor input and to the processor output. A linear filter is preferably connected between the processor output and the parameter computer. 
     In one preferred embodiment of the signal processor, the input of the linear filter is connected to the processor input and the input of the nonlinear filter is connected to the output of the linear filter. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     FIG. 1 is a simplified block diagram of a preferred embodiment of the signal-shaping processor of the invention. 
     FIG. 2 is a block diagram of the memoryless adjustable single-valued nonlinear signal-processor portion of the processor shown in FIG. 1. 
     FIG. 3 is a block diagram showing in greater detail a preferred form of the adaptive nonlinear filter of the invention. 
     FIG. 4 is a block diagram of a signal-shaping processor for producing an output signal having a uniform amplitude-density function. 
     FIG. 5 is a block diagram of a maximum-entropy encoder for producing an output signal having a uniform amplitude-density function and a uniform power spectrum. 
     FIG. 6 shows a signal processor similar to a maximum entropy encoder, but in which the filter performs arbitrary shaping of the output amplitude-density functions and produces an output signal having a uniform power spectrum. 
     FIG. 7 is a block diagram of an adaptive spectrum-shaping filter derived from a signal processor constructed according to the invention when the nonlinear processor functions are unitary. 
     FIG. 8 is a block diagram of an adaptive predictive deconvolver formed from the signal-shaping processor of the invention when all the processor functions are unitary. 
    
    
     DESCRIPTION OF THE PREFERRED EMBODIMENTS 
     A preferred embodiment of the nonlinear adaptive filter signal processor of the invention is shown generally in the block diagram of FIG. 1. An input signal x n  is input to a first signal processor such as adjustable linear filter 12. The output from this adjustable linear filter, y n , is input to a second signal processor such as a NONLINEAR PROCESSOR 14. The output signals from the NONLINEAR PROCESSOR 14 are designated u n , the output signal; and p n , a feedback control signal. 
     The control signals for the adjustable linear filter 12 are the input signal, x n  ; the feedback control signal u n  ; and a third signal which is derived from the output signal u n  to enable the ADJUSTABLE LINEAR FILTER 12 to shape the spectrum of the output signal u n  through the NONLINEAR PROCESSOR 14. The tap weight inputs for ADJUSTABLE LINEAR FILTER 12 are controlled by PARAMETER COMPUTER 16. The PARAMETER COMPUTER 16 is fed by a third signal v n , which is the output of a LINEAR FILTER 18 coupled to output signal u n . 
     The ADJUSTABLE LINEAR FILTER 12 may be of a type known in the art. One particularly advantageous transversal filter and associated parameter computer for spectral whitening and suppression is described in U.S. Pat. No. 4,000,369, issued Dec. 28, 1976 to James E. Paul, Jr., et al and entitled &#34;Analog Signal Channel Equalization with Signal-in-Noise Embodiment&#34;. The adjustable linear filter 12 is described by the input/output characteristic for convolution sum: ##EQU1## and is sometimes referred to as a transversal or FIR filter. Thus, the ADJUSTABLE LINEAR FILTER 12 has a coefficient or parameter vector 
     
         a=[a.sub.o, a.sub.1, . . . a.sub.N-1 ].sup.T               (2) 
    
     which may be adjusted by an amount Δa in one sample time. 
     The NONLINEAR PROCESSOR 14 coupled to the output of the linear filter causes the amplitude-density/distribution function of the output signal u n  to have a prescribed form, without respect to the frequency spectrum. The shaping process is reversible. 
     Referring now to FIG. 2, the NONLINEAR PROCESSOR 14 may be conceptualized as a pair of processors 20, 22 performing tandem functions F and G to first give the signal a uniform amplitude-density function, then to shape the signal to have the desired amplitude-density function. The output y n  from the adjustable linear filter 12 that is input to the NONLINEAR PROCESSOR 14 has an arbitrary amplitude-density/distribution function. The FIRST PROCESSOR 26 of the NONLINEAR PROCESSOR 14 operates as an amplitude density/distribution function computer and stores the actual amplitude-distribution function of y, F(y) into RAM 20 in order, to generate a signal e n  =F(y n ) having a uniform, or flat, amplitude-density function. The first processor 26 preferably comprises a random-access memory such as RAM 20 for storing the amplitude-distribution function F(y). The intermediate signal e n  addresses a ROM, such as ROM 22 for shaping the amplitude-density function. ROM 22 is pre-programmed to contain function G(e), a function which is the inverse of the desired output amplitude-distribution function, G(e). The output signal u n  from the ROM 22 has the prescribed amplitude-density/distribution function. 
     FIRST PROCESSOR 26 forms the amplitude-density function, in real time, of y n , called f(y). The amplitude-density function f(y) is stored in a second random-access memory 24. The integral of f(y), called F(y), is formed in FIRST PROCESSOR 26. The integral of f(y), i.e. F(y) is the accumulation of the real-time histogram of the sequence {y n  }, as described in U.S. Pat. No. 4,315,319, issued Feb. 9, 1982 to V. A. Vitols and S. A. White for a &#34;Nonlinear Signal Processor&#34;. A further refinement of the technique is described in U.S. Pat. No. 4,507,741, issued Mar. 26, 1985 to Stanley A. White for a &#34;Computing Device&#34;. 
     The integral function F(y) is stored in the first random-access memory 20 of the NONLINEAR PROCESSOR 14. This random-access memory then contains the actual amplitude-distribution function of the input signal y. The function F(y) is used as a nonlinear map to form the intermediate signal e n . Signal e n  functions as a series of addresses for ROM 22 and ROM 28. The input y n  is the address for SECOND RAM 24, FIRST RAM 20, from which the output e n  =F(y n ) is read, and is the input to FIRST PROCESSOR 26. 
     Each output signal e n  from the FIRST RAM is used to address FIRST ROM 22 memory location containing the inverse of the amplitude-distribution function desired for the output signal u n . A second ROM 28 contains the derivative function dG/de the derivative of the inverse of the desired output amplitude distribution function. The technique of performing these functions is also described in the just-referenced U.S. Pat. Nos. 4,315,319 and 4,507,741. The purpose of the derivative function will be explained below. 
     Referring now to FIG. 3, the PARAMETER COMPUTER 16 of FIG. 1 is shown in greater detail, with the control loops for adjusting the parameters of the adjustable linear filter. Input signal x n  enters the linear filter 12, which, at a given time has a tap weight vector a=[a 0 , a 1  . . . , a N-1  ] T . The tap weights or parameters of the linear filter are calculated by the parameter computer. 
     The parameter computer 16 calculates, in each sample time, the change Δa 0 , Δa 1 , . . . , Δa N-1  to be made in each filter parameter a 0 , a 1  . . . , a N-1 , respectively. These new values of the parameters are calculated based in part on the output signal u n  in a manner designed to provide the desired frequency spectrum. 
     The PARAMETER COMPUTER 16 uses as its inputs the system input signal x n , the product of the actual amplitude-density function f(y n ) and the derivative g(e n ) of the desired amplitude-distribution function G(e n ), and a signal v n  that is obtained by filtering the output u n  through the linear filter H(z) 18. The computation process is here described. 
     In the parameter computer 16, the input signal x n  is applied to a delay line comprising a series of delay elements 30. At the output of each delay element, and at the input to the first delay element, the signal is tapped. Each tapped signal from the delay lines is multiplied together in a first signal combiner or multiplier 32 with a signal p n  obtained by multiplying the actual amplitude-density function of y, f(y n ), and the derivative of the inverse of the desired amplitude-distribution function, g(e n ), in a combiner 34 coupled to the nonlinear filter 14. 
     The product output from each multiplier 32 is processed by a linear filter H(z) 36. The filtered output is multiplied with a signal w n , which is derived from the output signal u n . The signal w n  is obtained from the NONLINEAR PROCESSOR 14 output u n  by filtering the output signal u n  through a linear filter H(z) 18 to obtain a signal v n . Signal v n  is applied to a processor 38. Processor 38 applies an adjustment-rate parameter and the derivative of the functional J(v n ) with respect to v to v n  to obtain w n . 
     The signal w n , obtained from the output signal u n , is combined in a plurality of second signal combiners 40 with the outputs of the filters H(z) 36 within the parameter computer to form the parameter adjustments Δa 0 , Δa 1 , . . . , Δa l , . . . Δa N-1 . Adjustment parameters Δa 0 , Δa 1 , . . . Δa l , . . . Δa N-1  are summed in summers 44 with the preexisting parameters a 0 , a 1 , . . . a l , . . . a N-1 , delayed the proper time by delay elements 42 to produce new filter parameters for the new sample time. 
     If the function H(z) of the filter 18 is properly related to the desired output power spectrum, and the signal v n  has the proper power spectrum, the output signal u n  will have the desired spectrum. 
     In one exemplary form, the desired output power spectrum, within the allowable frequency range 
     
         0≦ω≦(ω.sub.s /2)                 (3) 
    
     where ω s  is the sampling frequency, may be defined as 
     
         |D(ω)|.sup.2 =|H(e.sup.jωT)|.sup.-2            (4) 
    
     in which H(z) is a stable filter and h n  =z -1  [H(z)]. Passing the sequence {u n  } through the filter H(z) forms the sequence {v n  } as follows: 
     
         v.sub.n =u.sub.n *h.sub.n                                  (5) 
    
     in which * is the convolution operator. If the power spectrum of {v n  } has a uniform, or white, power spectrum, then {u n  } will have the desired spectrum because of the way in which H(e j ωT) is defined. 
     A processor produces w n  by applying to the signal v n  the function ##EQU2## where J n  is the functional J(v n ). The spectrum of the signal v n  is whitened when {v n  } is minimized in some sense such that the functional J(v n ) is minimized. 
     As only the parameters a 0 , a 1 , . . . a N-1  of the linear filter may be adjusted, the functional J(v n ) is minimized over the vector a by applying the standard gradient approach using the steepest-descent criterion, i.e.: 
     
         Δa=-μJ(v.sub.n)                                   (7) 
    
     where Δa is the adjustment to the linear-filter-parameter vector 
     a=[a 0 , a 1 , . . . a N-1  ] T  in one sample time, -μ is the adjustment-rate parameter, and the gradient vector is ##EQU3## By the chain rule, expression (8) may be written in terms of a measurable parameter, v n  : ##EQU4## if the linear filter H(z) is defined as a general linear recursive filter: ##EQU5## 
     Therefore, the signal v n , which is the output signal u n  processed by the filter H(z), is ##EQU6## 
     The vector gradient of expression (11), is ##EQU7## Because the output signal u n  is the output of the function G(e n ), the function g(e n ) is the derivative of the function G(e n ), and the signal e n  in the nonlinear filter is the output of the function F(y), then 
     
         u.sub.n =G(e.sub.n)                                        (13) 
    
     and 
     
         e.sub.n =F(y.sub.n)                                        (14) 
    
     The gradients of the output signal u n  and the nonlinear filter intermediate signal e n  are: ##EQU8## 
     The relationship between the gradients of the output signal u n  and the output of the adjustable linear filter is: ##EQU9## 
     As stated above in Expression (1), the adjustable linear filter is of the form ##EQU10## 
     Therefore, the partial derivative of the signal y n  with respect to a given linear filter parameter a l  is ##EQU11## From expressions (17) and (18) it follows that: ##EQU12## 
     From expressions (7), (8), and (9), the change Δa l  for a linear filter parameter a l  is: ##EQU13## 
     As noted above in Expression (6): ##EQU14## 
     Simple functions for (dJ n )/(dv n ) and their interpretation are well known and are discussed in S. A. White, &#34;Digital Adaptive Element Building Blocks for MOS Large-Scale Integration&#34;, IEEE Trans., Vol. C-18, No. 8, Aug. 1969, pp. 699-706, and S. A. White, &#34;An Adaptive Recursive Digital Filter&#34;, Proc. 9th Asilomar Conference on Circuits, Systems, and Computers, Pacific Grove, CA, Nov. 1975, pp. 21-25. 
     From the above, it is seen that the adaptive filter of FIG. 3 correctly shapes both the frequency (power) spectrum of the output signal u n  and also applies the proper amplitude-density function. 
     Several special application embodiments of the signal-shaping processor of the invention are possible for specific applications in which one or more of the processor functions F(y), G(e), or H(z) may be unitary. 
     One special application filter generates an output signal u n  having a uniform amplitude-density function. The inverse of the amplitude-distribution function desired for the output signal u n  (G(e)) is unitary, but the actual amplitude-distribution function F(y) of the signal y and the filter function H(z) are nontrivial. In this case, the filter can take the form shown in FIG. 4. The output signal u n  is the same as the signal e n  output from the amplitude-distribution function F(y). The output power spectrum will be |H(e j ωT)| -2 . 
     A second special case arises when both the inverse of the desired amplitude-distribution function (G(e)) and the filter function H(z) are unitary, but the actual amplitude-distribution function F(y) of the output y n  from the linear filter is nontrivial. The filters H(z) on the adjustment lines for the linear filter can be eliminated. The resulting structure is shown in FIG. 5. The circuit is a maximum entropy encoder, for which both the amplitude-density function and the power spectrum of the output signal u n  are uniform. The tapped delay line of the parameter computer 16 need not be a separate structure. The delayed values of x n  may be obtained from within the adjustable linear filter 12 itself, in the same fashion that conventional adaptive FIR filters are mechanized. Because of the unitary filter function H(z), the input signals x n , x n-1 , . . . x n- (N-1) tapped from the delay line of the adjustable linear filter 12 may be combined directly in the combiners 40 with the signal w n  from the processor 38 and with the signal p n  directly from the processor 24. 
     A third special case arises when the filter function H(z) is unitary, but the nonlinear signal-processor functions F(y) and G(e) are nontrivial. The resulting filter, shown in FIG. 6, bears some similarity to the maximum-entropy encoder, but includes arbitrary shaping of the output amplitude-density functions through the nonlinear processor G(e) 22. Because the filter function H(z) is unitary, the signal v n  is the same as the output signal u n . Also, the delayed values of the input signal x n  may be obtained from within the adjustable linear filter 12, without the need for a separate input delay line in the parameter computer 16. The input signals x n , x n-1 , . . . x.sub.(N-1) from the delay line of the adjustable linear filter 12 may be supplied directly to the combiner 40 for combination with the signal w n  and the signal p n . 
     Another special case shows that the general signal processor of the invention reduces to a conventional linear filter when the two nonlinear processor functions F(y) and G(e) 20, 22 of the nonlinear signal processor 14 are both unitary, and the filter function H(z) is nontrivial. The resulting filter signal processor is shown in FIG. 7. With the unitary functions F(y) and G(e), no nonlinear amplitude shaping is required on the filter, and the output signal u n  is the same as the output y n  from the linear filter. Owing to the removal of the nonlinear functions and the control shaping multiplier p n , all the filter element H(z) may be combined with the delay operators as described in U.S. Pat. No. 4,524,424, issued June 18, 1985 to S. A. White for an &#34;Adaptive Spectrum Shaping Filter&#34;. 
     The final special case arises when all the functions F(y), G(e), H(z) are all unitary. In this case, the filter obtains the structure shown in FIG. 8, which is similar to the maximum-entropy encoder of FIG. 5. The signal processor of FIG. 8 is a classic adaptive predictive deconvolver.