Abstract:
The adaptive filtering techniques described herein allow a filter that is operating in a target domain to be trained in another domain, possibly with constraints, using the same adaptation framework used in a standard adaptive filter. As a result, the adaptation engine may be configured to run in a transform domain that is more desirable than the target domain. For example, the transform domain may be less susceptible to noise or may have more impact on the trained filter&#39;s desired results. The filter is trained in the transform domain and then the filter hardware is updated in the target domain.

Description:
TECHNICAL FIELD 
       [0001]    Embodiments of the invention are directed, in general, to training adaptive filters and, more specifically, to training an adaptive filter in one domain and then implementing the filter in another domain. 
       BACKGROUND 
       [0002]    In known systems, signals are filtered in the domain that corresponds to desired filter characteristics. For example, to filter a signal in the frequency domain, the signal must already be in the frequency domain, or it must be transformed to the frequency domain prior to filtering. After filtering, the modified signal may then be transformed to another domain or back to an original domain. Prior art systems related to adaptation of transform domain filters are always implemented in the transform domain. The signal being processed must first be converted from the original domain to the transform domain and then filtered in the transform domain. 
         [0003]    Existing techniques for transform domain adaptation use one of the following methods: (1) implement the filter in the transform domain so that the filter and the adaptation are both implemented in the same domain, or (2) use a separate estimation algorithm to generate the desired filter response in the transform domain and use filter design techniques to generate the desired target domain filter. These techniques are not optimal because they either require transformation of the filtered signal, which might not be possible if the filter hardware already exists in the target domain, or are difficult to implement using an adaptive framework, especially if the filter is nonlinear. 
       SUMMARY 
       [0004]    Embodiments of the invention run the adaptation algorithm in a transform domain but implement the filter in an original domain. This eliminates the need for the processed signal to undergo a transformation between domains, thereby eliminating the need to redesign existing hardware. Embodiments also allow a user to apply constraints in the transform domain even if the filter is implemented in the original domain. The adaptive filters described herein do not require the filter and the adaptation to be implemented in the same domain. 
         [0005]    The adaptive filtering techniques described herein allow a filter that is operating in a target domain to be trained in another domain, possibly with constraints, using the same adaptation framework used in a standard adaptive filter. As a result, the adaptation engine may be configured to run in a transform domain that is more desirable than the target domain. For example, the transform domain may be less susceptible to noise or may have more impact on the trained filter&#39;s desired results. The filter is trained in the transform domain and then the filter hardware is updated in the target domain. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0006]    Having thus described the invention in general terms, reference will now be made to the accompanying drawings, wherein: 
           [0007]      FIG. 1  is a block diagram for an adaptive filter according to one embodiment; 
           [0008]      FIG. 2  is a block diagram of a FIR filter; 
           [0009]      FIG. 3  illustrates desired transform domain coefficients for a FIR filter; 
           [0010]      FIG. 4  illustrates an exemplary trained filter comprising FIR filter hardware and transform adaptation software; and 
           [0011]      FIG. 5  is a flow diagram illustrating a process for updating an adaptive filter according to one embodiment. 
       
    
    
     DETAILED DESCRIPTION 
       [0012]    The invention now will be described more fully hereinafter with reference to the accompanying drawings. This invention may, however, be embodied in many different forms and should not be construed as limited to the embodiments set forth herein. Rather, these embodiments are provided so that this disclosure will be thorough and complete, and will fully convey the scope of the invention to those skilled in the art. One skilled in the art may be able to use the various embodiments of the invention. 
         [0013]      FIG. 1  illustrates a block diagram for an adaptive filter  100 . Adaptation engine  101  observes input signal x and error signal e, which represents the difference between d, the output of the desired system  103 , and y, the output of trained filter  102 . Adaptation engine  101  derives complex filter coefficients w that minimize the error signal e—i.e. train F(w,x) so that e is reduced or minimized. Typically, in a Least Mean Squares (LMS) adaptive filter, for example, the adaptation engine  101  generates coefficients w that minimize the mean square error. 
         [0014]    Adaptation engine  101  could use the steepest descent method to find filter weights w that minimize a cost function, which may be defined function as: 
         [0000]        C ( n )=| e ( n )| 2   =e*  ( n )· e ( n )  Eq. 1
 
         [0000]    where e(n) is the error at the current sample n: 
         [0000]        e ( n )= d ( n )− y ( n )  Eq. 2
 
         [0015]    Applying the LMS algorithm, the update equation for standard adaptive filtering is given by: 
         [0000]        w   n+1   =w   n −μ∇ w*     n     C ( n )  Eq. 3
 
         [0000]    where μ is the step size, ∇ is the gradient operator, and ∇ w*     n   C (n) is a vector pointing toward the steepest ascent of cost function C (n) . Incorporating Equations  1  and  2  into Equation  3  results in the following equations: 
         [0000]        w   n+1   =w   n −μ e ( n )∇ w*     n   ( d* ( n )− y *( n ))  Eq. 4
 
         [0000]        w   n+1   =w   n +μ e ( n )∇ w*     n     F ( w*   n , x* n )  Eq. 5
 
         [0000]    where x n , represents the input vector that is used to generate y(n). 
         [0016]    For the special case in which F(w, x) is associated with a linear Finite Impulse Response (FIR) filter, Equation 5 can be further simplified as: 
         [0000]      w n+1   =w   n +μ e ( n )∇ w*     n     w   n   H   x*   n   Eq. 6
 
         [0000]        w   n+1   =w   n +μ e ( n ) x*   n   Eq. 7
 
         [0000]    Returning to Equation 5, assume w consists of K coefficients 
         [0000]        w ( k ),  k= 1, . . . ,  K   Eq. 8
 
         [0017]    If desired, it is possible to train only a subset of the coefficients by using an adaptation mask. 
         [0000]        k⊂K, K={ 1, . . . ,  K}   Eq. 9
 
         [0000]        k∈k   Eq. 10
 
         [0000]        w ( k ) n+1   =w ( k ) n +μ e ( n )∇ w*     n   ( k ) F ( w*   n   x*   n )  Eq. 11
 
         [0018]    For the FIR case, the k th  coefficient can be trained as 
         [0000]        w(k)   n+1   =w ( k ) n +μ e ( n )∇ w*     n   ( k ) w   n   H   x*   n   Eq. 12
 
         [0000]        w ( k ) n+1   =w ( k ) n +μ e ( n ) x*   n ( k )  Eq. 13
 
         [0019]    In a transform domain adaptation, the coefficients w of the trained filter  102 , which are implemented in one domain, are trained in an alternate domain, possibly with constraints, using the same adaptation framework used by a standard adaptive filter as shown above. The domain of the coefficients w is the target domain, and the domain in which adaptation occurs is the transform domain. Assume H is the transform from the target domain to the transform domain, and H −1  is the inverse transformation. Let b represent the coefficients in the transform domain being trained by the adaptation engine. Then, the coefficients b in the transform domain are related to the coefficients w in the target domain as follows: 
         [0000]        b=H ( w )  Eq. 14
 
         [0020]    The coefficient update equations (Equations 3-5) can be rewritten in the transform domain as: 
         [0000]        b   n+1   =b   n −μ∇ b*     n     C ( n )  Eq. 15
 
         [0000]        b   n+1   =b   n −μ e ( n )∇ b*     n   ( d* ( n )− y* ( n ))  Eq. 16
 
         [0000]        b   n+1   =b   n +μ e ( n )∇ b*     n     F ( w*   n   , x*   n )  Eq. 17
 
         [0021]    Substituting transform domain coefficients b for the remaining target domain coefficients w results in the following equation: 
         [0000]        b   n+1   =b   n +μ e ( n )∇ b*     n     F (( H   −1 ( b   n ))* ,x* n )  Eq. 18
 
         [0000]    where the coefficients written to the filter are given by 
         [0000]        w=H   −1 ( b )  Eq. 19
 
         [0022]    Equation 18 applies to arbitrary filters, potentially nonlinear, and arbitrary domains, it may be simplified further by considering special cases. First, assume that the target domain is the time domain, and the transform domain is the frequency domain. Using a Discrete Fourier Transform (DFT) matrix, represented by the transform operator D, Equation 18 can be simplified as: 
         [0000]        b   n+1   =b   n +μ e ( n )∇ b*     n     F (( D   H b n )*,  x*   n ) Eq. 20
 
         [0000]        b   n+1   =b   n +μ e ( n )∇ b*     n     F ( D   T   b*   n ,  x*   n )  Eq. 21
 
         [0023]    For the special case in which F(w, x) is associated with a linear FIR filter, Equation 21 can be further simplified as: 
         [0000]        b   n+1   =b   n +μ e ( n )∇ b*     n     b   n   H   Dx*   n   Eq. 22
 
         [0000]        b   n+1   =b   n +μ e ( n ) Dx*   n   Eq. 23
 
         [0024]    Returning to Equation 18, assume b consists of M coefficients 
         [0000]        b ( m ),  m= 1, . . . ,  M   Eq. 24
 
         [0025]    If desired, it is possible to train only a subset of the coefficients by using an adaptation mask. 
         [0000]      β⊂ B, B={ 1, . . . ,  M}   Eq. 25
 
         [0000]        m  ∈β  Eq. 26
 
         [0000]        b   n+1 ( m )= b   n ( m )+μ e ( n )∇ b*     n   ( m ) F ((H −1 ( b   n ))*, x* n )  Eq. 27
 
         [0026]    For the special case of a FIR filter and DFT matrix D representing the transform operator from time domain (target domain) to frequency domain (transform domain), the m th  coefficient can be trained as 
         [0000]        b   n+1 ( m )= b   n ( m )+μ e ( n )∇ b*     n   ( m ) b   n   H   Dx*   n   Eq. 28
 
         [0000]        b   n+1 ( m )= b   n ( m )+μ e ( n ) D ( m, :)x* n   Eq. 29
 
         [0027]    Adaptation engine  101  generates trained coefficients b corresponding to a desired response in trained filter  102 . Adaptation engine  101  then transforms the trained coefficients b to target domain coefficients w using the inverse transform given in Equation  19  and writes the target domain coefficients w back to trained filter  102 . 
         [0028]    For simplicity, the examples discussed herein describe a linear FIR filter wherein the target domain is the time domain and the transform domain is the frequency domain. However, this formulation can be extended to nonlinear problems in a variety of domains. For example, the results may be extended to other algorithms, such as Recursive Least Squares (RLS) filters, the Kalman filter, and the like. Applications include, for example, noise cancellation, system identification, digital predistortion of power amplifiers and other systems without limitation. 
         [0029]    The transform domain adaptation process described herein offers various advantages over standard adaptation. For example, transform domain adaptation allows for constrained adaptation in the transform domain. In certain cases, although the filter is implemented in the target domain, constrained adaptation may be desired in the transform domain. For example, consider the case in which the input signal contains energy in a finite range of frequencies f 1 . In this case, the error e is predominantly in the range of frequencies f 1 . If adaptation is performed in the time domain, it would be difficult to constrain the filter&#39;s behavior and, because of numerical sensitivity issues, the trained filter&#39;s response could vary significantly at frequencies outside of f 1 . In many cases, it might be desirable to train the filter such that its response is modified only in the regions where the signal is present. This could be accomplished by training the filter in the frequency domain, and only modifying those filter coefficients that correspond to the frequency bins within f 1  by using a coefficient mask as given in Equation 29. 
         [0030]    After the filter converges, assume the energy in the signal moves to another range of frequencies f 2 . Then the error will be predominantly in the range of frequencies f 2 . If adaptation is performed in the time domain, it would be difficult to constrain the filter&#39;s behavior outside f 2  and the filter response in the range of frequencies f 1  could be disturbed, thereby modifying the previous training results for frequencies f 1 . It is highly desirable to train the filter in the frequency domain, only modifying those filter coefficients that correspond to the frequency bins within f 2  and leave the filter response over f 1  unchanged by using an appropriate coefficient mask as given in Equation 29. 
         [0031]    Embodiments of the novel adaptive filter technique disclosed herein—by which a filter implemented in a target domain is trained in a transform domain—are accomplished by: 
         [0032]    1. Using knowledge available in the transform domain to determine which transform domain coefficients should be trained and which ones should not. 
         [0033]    2. Using a coefficient mask in the transform domain to ensure only the desired transform domain coefficients are trained by the selected adaptation algorithm. 
         [0034]    3. Exploiting the functional relationship between the filter error in the target domain and the coefficients to be trained in the transform domain to generate gradients, Hessians, linear approximations, and the like as required by the selected adaptation algorithm. 
         [0035]    4. Applying the inverse transformation to the trained coefficients in the transform domain before updating the adaptive filter coefficients in the target domain. 
         [0036]      FIG. 2  is a block diagram of FIR filter  200  in which coefficients w i  are selected to achieve a desired shape in the transform domain.  FIG. 3  illustrates desired transform domain coefficients b j . A transform H can be calculated to define the relationship between coefficients w i  and coefficients b j . A corresponding inverse transform H −1  may be calculated to relate coefficients b j  to coefficients w i . In one embodiment, coefficients b j  are trained using Equation 29. Then the inverse transform H −1  is applied to coefficients b j  to generate coefficients w i  to be used in filter  200 . 
         [0037]    Changes in coefficients b j  can be immediately applied to filter  200  by generating coefficients w i  using inverse transform H −1 . Additionally, using a mask, specific coefficients in the transform domain can be trained without modifying others. 
         [0038]      FIG. 4  illustrates an exemplary trained filter  400  comprising FIR filter hardware  401  and transform domain adaptation software. The signals tapped on each side of delay elements  402  are sequentially scaled and summed in elements  403  to generate output y n . Each tap  404  is modified by coefficient block  405 . The value of the coefficients w i  applied to each tap  404  is selected based upon the inverse transform of transform domain coefficients b j    406 . Error signal e n  and input x n  are received in processor  407 , which is running transform adaptation software or firmware. Processor  407  adjusts coefficients b j    406 , which are inverse transformed by software or firmware  408  to generate coefficients w i  that are used in coefficient block  405 . Processor  407  continues to adjust coefficients b j    406  indefinitely, or until error signal e n  is zero or below a predetermined threshold, which indicates that the output y of trained filter  400  is within an acceptable range of a desired system response. 
         [0039]      FIG. 5  is a flow diagram illustrating a process for updating an adaptive filter according to one embodiment. In step  501 , the adaptive filter determines which transform domain coefficients should be trained. In step  502 , using a coefficient mask in the transform domain, the adaptive filter trains the desired transform domain coefficients using a selected adaptation algorithm. In step  503 , the adaptive filter applies an inverse transformation to the trained coefficients in the transform domain to generate coefficients in the target domain. In step  504 , the adaptive filter employs the target domain coefficients generated in step  503 . 
         [0040]    Many modifications and other embodiments of the invention will come to mind to one skilled in the art to which this invention pertains having the benefit of the teachings presented in the foregoing descriptions, and the associated drawings. Therefore, it is to be understood that the invention is not to be limited to the specific embodiments disclosed. Although specific terms are employed herein, they are used in a generic and descriptive sense only and not for purposes of limitation.