Abstract:
A method and apparatus for low delay recursive filter design. The method includes determining a predefined filter template with higher magnitude specification than a target filter design, determining at least one relaxation bound on the filter specification utilizing the predefined filter template, specifying at least one constraint for the target filter design utilizing the at least one relaxation bound, and determining a low delay recursive filter design for minimizing the average group delay of the filter utilizing the at least one constraint.

Description:
CROSS-REFERENCE TO RELATED APPLICATIONS 
       [0001]    This application claims benefit of U.S. provisional patent application Ser. No. 61/228,066, filed Jul. 23, 2009, which is herein incorporated by reference. 
     
    
     BACKGROUND OF THE INVENTION 
       [0002]    1. Field of the Invention 
         [0003]    Embodiments of the present invention generally relate to a method and apparatus for a low delay recursive filter design. 
         [0004]    2. Description of the Related Art 
         [0005]    In many real-time applications, the filter delay is a critical system performance issue. For example, in adaptive noise cancelation systems, fast tracking of the reference signal is crucial for noise cancelation. For these systems, the standard filter design techniques are generally not sufficient, and extra effort is needed to minimize the filter delay in the pass band. The standard filter design techniques, e.g., Butterworth and Chebechev filters, focus on the magnitude response, and the delay/phase issues are usually ignored. 
       SUMMARY OF THE INVENTION 
       [0006]    Embodiments of the present invention relate to a method and apparatus for low delay recursive filter design. The method includes determining a predefined filter template with higher specification than a target filter design, determining at least one relaxation bound on the filter specification utilizing the predefined filter template, specifying at least one constraint for the target filter design utilizing the at least one relaxation bound, and determining a low delay recursive filter design for minimizing the average group delay of the filter utilizing the at least one constraint. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0007]    So that the manner in which the above recited features of the present invention can be understood in detail, a more particular description of the invention, briefly summarized above, may be had by reference to embodiments, some of which are illustrated in the appended drawings. It is to be noted, however, that the appended drawings illustrate only typical embodiments of this invention and are therefore not to be considered limiting of its scope, for the invention may admit to other equally effective embodiments. 
           [0008]      FIG. 1  is an embodiment of a delay minimization of a sixth order low pass elliptic filter using three design variation OPT 1 , OPT 2  and OPT 3 ; 
           [0009]      FIG. 2  is an exemplary embodiment of a group delay minimization; and 
           [0010]      FIG. 3  is a flow diagram depicting an embodiment of a method for low delay recursive filter design. 
       
    
    
     DETAILED DESCRIPTION 
       [0011]    We propose a novel algorithm to design a low-delay IIR filter from a predesigned filter template. The filter template can have arbitrary magnitude and phase response and may be designed using standard filter design techniques. The problem is formulated as a nonlinear optimization problem of minimizing the average group delay over the pass band under constraints on stability and magnitude response. 
         [0012]    We propose a novel algorithm to design a low-delay IIR filter from a predesigned filter template. The filter template can have arbitrary magnitude and phase response and may be designed using standard filter design techniques. The problem is formulated as a nonlinear optimization problem of minimizing the average group delay over the pass band under constraints on stability and magnitude response. 
         [0013]    The proposed work focuses on minimizing the filter group delay in the pass band starting from a predesigned filter template, which may be designed using standard filter design techniques. We formulate a nonlinear optimization problem whose objective is to minimize the average group delay under constraints on magnitude response and filter stability. The problem is solved using standard techniques for constrained nonlinear optimization problems, e.g., log-barrier technique. Unlike earlier approaches, we do not specify the behavior of the group delay in the pass band. Rather, the objective is to minimize the average group delay. The proposed approach is shown to be effective in reducing the filter delay with reasonable magnitude distortion. 
         [0014]    we will use the following notations: 
         [0015]    ρ i , and φ i : amplitude and frequency of the i-th zero z i . 
         [0016]    r i  and θ i : amplitude and frequency of the i-th pole p i . 
         [0017]    H(e iω ): filter frequency response. 
         [0018]    A(ω): amplitude response. 
         [0019]    Φ(ω)): phase response 
         [0020]    τ(ω)): group delay 
         [0021]    Ω p , Ω t , and Ω s ,: passband, transition band, and stopband (respectively). 
         [0022]    G: filter gain 
         [0023]    In one embodiment of this invention, both poles and zeros occur in conjugate pairs. Without loss of generality, we assume that the filter order is even and the numerator order equals the denominator order. If the number of biquads is M, then we have: 
         [0000]    
       
         
           
             
               H 
                
               
                 ( 
                 z 
                 ) 
               
             
             = 
             
               G 
                
               
                 
                   ∏ 
                   
                     i 
                     = 
                     1 
                   
                   M 
                 
                  
                 
                     
                 
                  
                 
                   
                     1 
                     - 
                     
                       2 
                        
                       
                           
                       
                        
                       
                         ρ 
                         i 
                       
                        
                       cos 
                        
                       
                           
                       
                        
                       
                         φ 
                         i 
                       
                        
                       
                         z 
                         
                           - 
                           1 
                         
                       
                     
                     + 
                     
                       
                         ρ 
                         i 
                         2 
                       
                        
                       
                         z 
                         
                           - 
                           2 
                         
                       
                     
                   
                   
                     1 
                     - 
                     
                       2 
                        
                       
                           
                       
                        
                       
                         r 
                         i 
                       
                        
                       cos 
                        
                       
                           
                       
                        
                       
                         θ 
                         i 
                       
                        
                       
                         z 
                         
                           - 
                           1 
                         
                       
                     
                     + 
                     
                       
                         r 
                         i 
                         2 
                       
                        
                       
                         z 
                         
                           - 
                           2 
                         
                       
                     
                   
                 
               
             
           
         
       
     
         [0024]    By straightforward substitution, we get 
         [0000]    
       
         
           
             
               A 
                
               
                 ( 
                 ω 
                 ) 
               
             
             = 
             
               
                 G 
                 2 
               
                
               
                 
                   ∏ 
                   
                     i 
                     = 
                     1 
                   
                   M 
                 
                  
                 
                     
                 
                  
                 
                   
                     Γ 
                      
                     
                       ( 
                       
                         ω 
                         , 
                         
                           ρ 
                           i 
                         
                         , 
                         
                           φ 
                           i 
                         
                       
                       ) 
                     
                   
                   
                     Γ 
                      
                     
                       ( 
                       
                         ω 
                         , 
                         
                           r 
                           i 
                         
                         , 
                         
                           θ 
                           i 
                         
                       
                       ) 
                     
                   
                 
               
             
           
         
       
       
         
           where 
         
       
       
         
           
             
               Γ 
                
               
                 ( 
                 
                   ω 
                   , 
                   x 
                   , 
                   y 
                 
                 ) 
               
             
             = 
             
               
                 
                   ( 
                   
                     1 
                     + 
                     
                       x 
                       2 
                     
                   
                   ) 
                 
                 2 
               
               - 
               
                 4 
                  
                 
                     
                 
                  
                 
                   x 
                    
                   
                     ( 
                     
                       1 
                       + 
                       
                         x 
                         2 
                       
                     
                     ) 
                   
                 
                  
                 cos 
                  
                 
                     
                 
                  
                 ω 
                  
                 
                     
                 
                  
                 cos 
                  
                 
                     
                 
                  
                 y 
               
               + 
               
                 2 
                  
                 
                     
                 
                  
                 
                   
                     x 
                     2 
                   
                    
                   
                     ( 
                     
                       
                         cos 
                          
                         
                             
                         
                          
                         2 
                          
                         
                             
                         
                          
                         ω 
                       
                       + 
                       
                         cos 
                          
                         
                             
                         
                          
                         2 
                          
                         
                             
                         
                          
                         y 
                       
                     
                     ) 
                   
                 
               
             
           
         
       
     
         [0025]    An explicit expression for τ(ω)) is 
         [0000]    
       
         
           
             
               τ 
                
               
                 ( 
                 ω 
                 ) 
               
             
             = 
             
               
                 
                   ∑ 
                   
                     i 
                     = 
                     1 
                   
                   M 
                 
                  
                 
                   Λ 
                    
                   
                     ( 
                     
                       ω 
                       , 
                       
                         r 
                         i 
                       
                       , 
                       
                         θ 
                         i 
                       
                     
                     ) 
                   
                 
               
               - 
               
                 Λ 
                  
                 
                   ( 
                   
                     ω 
                     , 
                     
                       ρ 
                       i 
                     
                     , 
                     
                       φ 
                       i 
                     
                   
                   ) 
                 
               
             
           
         
       
       
         
           where 
         
       
       
         
           
             
               Λ 
                
               
                 ( 
                 
                   ω 
                   , 
                   x 
                   , 
                   y 
                 
                 ) 
               
             
             = 
             
               
                 
                   1 
                   - 
                   
                     x 
                      
                     
                         
                     
                      
                     
                       cos 
                        
                       
                         ( 
                         
                           ω 
                           - 
                           y 
                         
                         ) 
                       
                     
                   
                 
                 
                   1 
                   + 
                   
                     x 
                     2 
                   
                   - 
                   
                     2 
                      
                     
                         
                     
                      
                     x 
                      
                     
                         
                     
                      
                     
                       cos 
                        
                       
                         ( 
                         
                           ω 
                           - 
                           y 
                         
                         ) 
                       
                     
                   
                 
               
               + 
               
                 
                   1 
                   - 
                   
                     x 
                      
                     
                         
                     
                      
                     
                       cos 
                        
                       
                         ( 
                         
                           ω 
                           + 
                           y 
                         
                         ) 
                       
                     
                   
                 
                 
                   1 
                   + 
                   
                     x 
                     2 
                   
                   - 
                   
                     2 
                      
                     
                         
                     
                      
                     x 
                      
                     
                         
                     
                      
                     
                       cos 
                        
                       
                         ( 
                         
                           ω 
                           + 
                           y 
                         
                         ) 
                       
                     
                   
                 
               
             
           
         
       
     
         [0026]    We define the average group delay over the frequency band Ω as: 
         [0000]    
       
         
           
             
               
                 τ 
                 _ 
               
                
               
                 ( 
                 ω 
                 ) 
               
             
             = 
             
               
                 1 
                 
                    
                   Ω 
                    
                 
               
                
               
                 
                   ∫ 
                   Ω 
                 
                  
                 
                   
                     τ 
                      
                     
                       ( 
                       ω 
                       ) 
                     
                   
                    
                   
                       
                   
                    
                   
                      
                     ω 
                   
                 
               
             
           
         
       
       
         
           
             
               where 
                
               
                   
               
                
               
                  
                 Ω 
                  
               
             
             = 
             
               
                 ∫ 
                 
                   ω 
                   ∈ 
                   Ω 
                 
               
                
               
                   
               
                
               
                 
                    
                   ω 
                 
                 . 
               
             
           
         
       
     
         [0027]    The low delay filter design problem aims at minimizing the average group delay in the pass band under constraints on the magnitude distortion in both the pass band and stop band compared to a predesigned filter amplitude response A T (ω)). Moreover, any feasible solution should be stable. The decision variables of the optimization problem are the poles and zeros of the transfer function in addition to the filter gain. 
         [0028]    Define a set of decision variables, 
         [0000]          u =r   1   , . . . , r   M ,θ 1 , . . . , θ M ,ρ 1 , . . . , ρ m ,φ m   ,G )
 
         [0029]    The objective function of the filter design is to minimize the average group delay: 
         [0000]        Q (   u   )=  τ (Ω p   , u   )
 
         [0030]    The constraints on the optimization problem are: 
         [0000]    1) Stability constraints: 
         [0000]      r i &lt;1 for i=1,2, . . . , M. 
         [0000]    2) Gain constraint: 
         [0000]      G&gt;0 
         [0000]    3) Magnitude constraints: 
         [0000]      δ p2   A (ω,   u   )≦δ p1  for ωεΩ p  
 
         [0000]        A (ω,   u   )≦δ s  for ωεΩ s  
 
         [0000]        A (ω,   u   )≦δ p2  for ωεΩ t  
       The first constraint gives an equiripple pass band specification. The third constraint seems trivial, however,   it is added to circumvent spurious peaks that are frequently encountered in the transition band of the final solution after numerical optimization. The thresholds in the above inequalities are derived from the initial filter template.
 
4) Positive group delay (optional):
       
 
         [0000]      τ(ω)&gt;0ωεΩ p  
 
         [0033]    This constraint may be added to prevent possible negative group delay that may not be appropriate in some applications. 
         [0034]    This problem is a constrained nonlinear optimization problem. To solve it, we need to digitize the frequency ω such that the magnitude constraints can be put in a standard form. In this case, the magnitude constraints can be written as: 
         [0000]        g   i   (p) (   u   )=δ p1   −A (ω i   , u   )≦0 for 0 for ω i εΩ p  
 
         [0000]        f   i   (p) (   u   )= A (ω i   , u   )−δ p1 ≦0 for ω i εΩ p  
 
         [0000]        g   i   (s) (   u   )=δ s   A (ω i   , u   )0 for ω i εΩ s  
 
         [0000]        g   i   (t) (   u   )=δ p2   −A (ω i   , u   )0 for ω i εΩ t  
 
         [0035]    Now, the optimization problem is a standard constrained nonlinear optimization problem which can be solved using standard techniques. If we digitize the frequency to N p , N s , and N t  points in the passband, stopband and transition band respectively, then the total number of constraints is N c =M+1+2N p +N s +N t . 
         [0036]    In some embodiments, many filter design algorithms result in a peak in the group delay near the passband edges. The effect of the group delay peak on the average group delay is more prominent for filters with narrow passband. Therefore, in our design example we use a narrowband lowpass elliptic filter. The filter specifications are as follow: 
         [0037]    Passband gain=0 dB, stopband attenuation=60 dB 
         [0038]    Passband ripple=1 dB 
         [0039]    Ω p =[0,0.02π] 
         [0040]    |Ω t |≦0.01 π 
         [0041]    This results in a sixth order filter. The average passband group delay of the template filter is 105 samples. The minimization of the group delay can be achieved by relaxing at least one of the three filter specifications: stopband attenuation, passband ripple, or transition bandwidth. In the following we consider three design procedures, each relaxing one of the filter specifications. 
         [0042]    First we consider reducing the stopband attenuation to 50 dB (rather than 60 dB in the template filter). In this case we have δ p1  and δ p2  have the same values of the template filter, δ s =10 −5 . In the second design, we increase the passband ripple to 3 dB (rather than 1 dB in the template filter). In this case we have δ p1 =δ p2 /2≈1, and δ s =10 −6 . In the third design, we increase the transition band by 50%. In this case we have δ p1 , δ p2 , and δ s  have the same values as the template filter. We only change the boundaries of Ω t  and Ω s . The outputs of the three optimization criteria are illustrated in  FIG. 1 . 
         [0043]    Note that, most of the group delay minimization takes place at the passband edge where the group delay peaks in the template filter. Therefore the reduction of the peak group delay is reduced much more than the average group delay. Moreover, the variation in the group delay in the passband is much less and this results in reducing the phase distortion. If we combine the three above relaxations to optimize the filter design the optimized filter is as shown in  FIG. 2 . 
         [0044]    It should be mentioned that, the frequency band upon which the average group delay is minimized is not necessarily the entire Ω p . In some practical applications, e.g., multi-stage decimation/interpolation filters, we are interested in only a subset of Ω p . This case can be handled straightforwardly in the proposed framework. In this case, the frequency band in the objective function and the constraints are modified to the frequency band of interest. In  FIG. 2 , we give an example using the previous template filter with the group delay minimized over the frequency band [0, 0.01π], i.e., half the passband. We use the same optimization thresholds that are used in the last design example. Note that, the optimization is over the flat part of the group delay which gives relatively uniform minimization over the frequency band. 
         [0045]    We presented a novel algorithm for minimizing the group delay in the pass band of a predesigned filter with constraints on the magnitude distortion. The problem is formulated as a constrained nonlinear optimization problem which is solved using standard techniques. The effectiveness of the proposed algorithm is verified using several design examples. We did not set any assumption of the predesigned template and the proposed algorithm works for all initial designs. 
         [0046]    Although the optimization problem was formulated for group delay minimization, the proposed framework can be used for other phase optimization criteria. For example, linear phase optimization can be formulated within the same framework. Many variations of the optimization model could be added within the same framework. For example, the delay function could be optimized in a least-square fashion where we could make all the thresholds frequency-dependent to have arbitrary shaping of the magnitude spectrum without any increase the complexity of the optimization problem. 
         [0047]      FIG. 3  is a flow diagram depicting an embodiment of a method  300  for low delay recursive filter design. The method  300  starts at step  302  and proceeds to step  304 . At step  304 , the method  300  determines predefined filter template with higher specification than the target filter. At step  306 , the method  300  determines the relaxation bounds on the filter specification. At step  308 , the method  300  specifies the constraints for the target filter design. At step  310 , the method  300  minimizes the average group delay of the filter under the set constraints by solving the corresponding optimization problem. The method  300  ends at step  312 . 
         [0048]    While the foregoing is directed to embodiments of the present invention, other and further embodiments of the invention may be devised without departing from the basic scope thereof, and the scope thereof is determined by the claims that follow.