Patent Publication Number: US-11387822-B2

Title: Filter and method with multiplication operation approximation capability

Description:
CROSS REFERENCE TO RELATED APPLICATIONS 
     This application claims the benefits of U.S. Provisional Application No. 63/079,680 filed on Sep. 17, 2020, which are incorporated herein by reference. 
    
    
     BACKGROUND OF THE INVENTION 
     1. Field of the Invention 
     The present application relates to a filter and method for an application-specific integrated circuit (ASIC), and more particularly, to a filter and method capable of approximating multiplication operation for the ASIC. 
     2. Description of the Prior Art 
     A bi-quadratic (BiQuad) filter is a second-order filter commonly employed in signal processing. In the discrete-time domain, the input/output relation of a BiQuad filter may be expressed as equation (Eq.) 1:
 
 y ( n )= b   0   x ( n )+ b   1   x ( n −1)+ b   2   x ( n −2)− a   1   y ( n −1)− a   2   y ( n −2)  Eq. 1
 
     By properly choosing the coefficients [a 1 , a 2 , b 0 , b 1 , b 2 ], a BiQuad filter may function as a low-pass, high-pass, band-pass, peak, notch, low-shelf or high-shelf filter according to a set of specified parameters such as sampling frequency, center/cutoff frequency f c , Q-factor and gain. 
     For example, please refer to  FIG. 1 , which illustrates amplitude response and phase response of a BiQuad filter. As shown in  FIG. 1 , when the discrete-time signals are sampled at a rate of 48 ksps (kilo-samples per second), a BiQuad filter with the coefficients in a table 1 may function as a 2 nd  order low-pass filter with f c =1439.244251 Hz, Q=0.7071 and a unit DC-gain. 
     
       
         
           
               
               
             
               
                   
                 TABLE 1 
               
               
                   
                   
               
             
            
               
                   
                 a 1  = −1.734863758990959 
               
               
                   
                 a 2  = 0.766113758997616 
               
               
                   
                 b 0  = 0.007812500001664 
               
               
                   
                 b 1  = 0.015625000003329 
               
               
                   
                 b 2  = 0.007812500001664 
               
               
                   
                   
               
            
           
         
       
     
     However, the above BiQuad filter may require five multiplications, four additions and register several assignment operations. Floating point multiplication, especially 64-bit double precision floating point numbers required for the expressing coefficients in the table 1, is an expensive operation that not only takes significant amount of hardware resources and computation cycles but also consumes significant amount of power. 
     Therefore, it is necessary to improve the prior art. 
     SUMMARY OF THE INVENTION 
     It is therefore a primary objective of the present application to provide a filter and method capable of approximating multiplication operation, to improve over disadvantages of the prior art. 
     An embodiment of the present application discloses a filter. The filter includes at least one first multiplication approximation unit, for approximating at least one first multiplication operation corresponding to at least one first coefficient with at least one first bit-wise shift operation; and at least one second multiplication approximation unit, for approximating at least one second multiplication operation corresponding to at least one second coefficient with a plurality of second bit-wise shift operations and at least one addition operation. 
     Another embodiment of the present application discloses a method. The method includes approximating at least one first multiplication operation corresponding to at least one first coefficient with at least one first bit-wise shift operation; and approximating at least one second multiplication operation corresponding to at least one second coefficient with a plurality of second bit-wise shift operations and at least one addition operation. 
     Another embodiment of the present application discloses a filter. The filter includes at least one first multiplication approximation unit, for approximating at least one first multiplication operation corresponding to at least one first coefficient with at least one first bit-wise shift operation. 
     These and other objectives of the present invention will no doubt become obvious to those of ordinary skill in the art after reading the following detailed description of the preferred embodiment that is illustrated in the various figures and drawings. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         FIG. 1  illustrates amplitude response and phase response of a BiQuad filter. 
         FIG. 2  is a schematic diagram of a BiQuad filter in Direct Form II. 
         FIG. 3  is a schematic diagram of a BiQuad filter according to an embodiment of the present application. 
         FIG. 4  is a schematic diagram of conversions of multiplication approximation units of the BiQuad filter shown in  FIG. 3  according to an embodiment of the present application. 
         FIG. 5  illustrates amplitude response and phase response of the BiQuad filter shown in  FIG. 3  according to an embodiment of the present application. 
         FIG. 6  is a schematic diagram of a BiQuad filter according to another embodiment of the present application. 
         FIG. 7  is a schematic diagram of an all-pole filter and an all-zero filter. 
     
    
    
     DETAILED DESCRIPTION 
     Since multiple stages of a BiQuad filter may be used in a system, connecting M stages of the BiQuad filter in cascade results in a 2M-order filter. Under such an arrangement, the input of a stage comes from the output of the previous stage while the output is connected to the input of the next stage. 
     Please refer to  FIG. 2 , which is a schematic diagram of a conventional BiQuad filter  20  in Direct Form II. As shown in  FIG. 2 , since x(n) is an input signal, y(n) is an output signal and z −1  is a delay element, the data processing flow of signals of the BiQuad filter  20  may be expressed as: 
     
       
         
           
               
               
             
               
                   
                   
               
             
            
               
                   
                 n = 0 ; 
               
            
           
           
               
               
            
               
                   
                 do { 
               
            
           
           
               
               
            
               
                   
                 s 2 (n) = s 1 (n − 1) ; 
               
               
                   
                 s 1 (n) = u(n − 1) ; 
               
               
                   
                 u(n) = x(n) − a 1 s 1 (n) − a 2  s 2 (n) ; 
               
               
                   
                 y(n) = b 0  u(n) + b 1  s 1 (n) + b 2  s 2 (n) ; 
               
               
                   
                 n = n + 1 ; 
               
            
           
           
               
               
            
               
                   
                 } 
               
               
                   
                   
               
            
           
         
       
     
     Under such a situation, each iteration in the processing of the BiQuad filter  20  requires five multiplications, four additions and several register assignment operations. As mentioned in the above, floating point multiplication is an expensive operation that not only takes significant amount of hardware resources and computation cycles but also consumes significant amount of power. Silicon area, computation cycles and power are all precious resource for digital systems, it is therefore highly desirable to have a realization of a BiQuad filter while minimizing the use of floating point multiplier. 
     When a BiQuad filter is designed in an application-specific integrated circuit (ASIC), arithmetic operations are performed with finite precision. All the variables and constants are represented with finite number of bits. It is inevitable to have errors between the ideal design goal and the actual results produced by a specific digital implementation. Choosing proper precision, or equivalently the number of bits, to represent each of the coefficients existing in the design is critical. The present application aims at the implementations of a BiQuad filter that employ dramatically simplified arithmetic operations and, accordingly, require much less hardware resources while being able to achieve results comparable to that of floating-point arithmetic operations. 
     Please refer to  FIG. 3  and  FIG. 4 .  FIG. 3  is a schematic diagram of a BiQuad filter  30  according to an embodiment of the present application, and  FIG. 4  is a schematic diagram of conversions of multiplication approximation units  300 - 308  of the BiQuad filter  30  according to an embodiment of the present application. As shown in  FIG. 3  and  FIG. 4 , the multiplication approximation units  304 ,  306 ,  308  approximate multiplication operations corresponding to at least one coefficients b 0 , b 1 , b 2  with bit-wise shift operations, respectively, and the multiplication approximation units  300 ,  302  approximate multiplication operations corresponding to at least one coefficients a 1 , a 2  with bit-wise shift operations and addition operations, respectively. As a result, the present application may approximate multiplication operations with bit-wise shift operations to save hardware resources. 
     In detail, by selecting a proper corner frequency (f C ) and a quality factor (Q), multiplication operations by coefficients b 0 , b 1  and b 2  become equivalent to bit-wise shift operations as shown in in a table 2 below (f s  is a sample rate). Since bit-wise shift operations may be realized by wiring in ASIC design, the resulting implementation of multiplication utilizes no logic gates, takes up no silicon space and consumes no power. In other words, this first step of implementing the BiQuad filter  30  involves choosing suitable combinations of the corner frequency f C  and the quality factor Q, and converts the floating point multiplication operations involving the coefficients b 0 , b 1 , b 2  into no-cost bit-wise rewiring in the ASIC. Then, in the 2 nd  step of implementing the BiQuad filter  30 , the coefficients b 0 , b 1 , b 2  are finely tuned, such that each of the two floating-point multiplication operations involving coefficients a 1 , a 2  becomes bit-wise shift operations and 2˜3 fixed point addition operations. 
     
       
         
           
               
               
               
               
               
               
             
               
                 TABLE 2 
               
               
                   
               
               
                 f C  at 
                 f C  at 
                   
                   
                   
                   
               
               
                 3.072 Msps 
                 48 ksps 
                 f C /f s   
                 Q 
                 b 0 , b 2   
                 b 1   
               
               
                   
               
             
            
               
                   
               
            
           
           
               
               
               
               
               
               
            
               
                 293,596.34 
                 4,587.44 
                 0.09557173 
                 0.7071 
                 4 
                 3 
               
               
                 196,647.43 
                 3,072.62 
                 0.06401283 
                 0.7071 
                 5 
                 4 
               
               
                 133,818.77 
                 2,090.92 
                 0.04356080 
                 0.7071 
                 6 
                 5 
               
               
                 92,111.63 
                 1,439.24 
                 0.02998426 
                 0.7071 
                 7 
                 6 
               
               
                 63,915.58 
                 998.681 
                 0.02080585 
                 0.7071 
                 8 
                 7 
               
               
                 44,600.77 
                 696.887 
                 0.01451848 
                 0.7071 
                 9 
                 8 
               
               
                 31,245.41 
                 488.210 
                 0.01017103 
                 0.7071 
                 10 
                 9 
               
               
                 21,949.60 
                 342.963 
                 0.00714505 
                 0.7071 
                 11 
                 10 
               
               
                 32,991.13 
                 2,061.95 
                 0.04295720 
                 0.8409 
                 6 
                 5 
               
               
                 22,800.87 
                 1,425.05 
                 0.02968863 
                 0.8409 
                 7 
                 6 
               
               
                   
               
            
           
         
       
     
     Specifically, considering a case where the corner frequency f C ≈1439.24 Hz at 48 ksps, the quality factor Q≈0.707 with the following approximations of the coefficients of multiplication operations (converting the coefficients of table 1 with 4 th  row of the table 2 by approximating each coefficient by a sum of one term (e.g. b 0 , b 1 , b 2 ) or more terms (e.g. a 1 , a 2 ) with each term containing only one ‘1’ in its binary expression):
 
 a   1 =−1.734863758990959≈−(1.734375)=−(01.101111) b =(0.01) b +(0.000001) b −(010.0) b  
 
 a   2 =0.766113758997616≈0.765625=(0.110001) b =(01.0) b −(0.01) b +(0.000001) b  
 
 b   0 =0.007812500001664≈0.0078125=(0.0000001) b  
 
 b   1 =0.015625000003329≈0.015625=(0.000001) b  
 
 b   2 =0.007812500001664≈0.0078125=(0.0000001) b  
 
where the notation ( ) b  is the two&#39;s-complement binary representation of a number. For example, 1.25=(01.01) b , 0.15625=(0.00101) b , etc.
 
     As shown in  FIG. 4 , instead of a floating-point multiplication operation, the multiplication operation of −a 1 s 1 (n) may be calculated as
 
− a   1   s   1 ( n )= s   1 ( n )×(010.0) b   −s   1 ( n )×(0.01) b   −s   1 ( n )×(0.000001) b =[ s   1 ( n ) binary form shifted to the left by 1 bit]−[ s   1 ( n ) binary form shifted to the right by 2 bits]−[ s   1 ( n ) binary form shifted to the right by 6 bits]
 
     As a result, three no-cost bit-wise rewiring will address the need of any multiplication operation, and it takes only two integer addition operations to approximate the floating point multiplication operation. By the same token, the multiplication operation of −a 2 s 2 (n) in  FIG. 2  can be obtained through two addition operations as shown in  FIG. 4 . 
     For those multiplication operations corresponding to the coefficients b 0 , b 1  and b 2 , since the coefficients b 0 , b 1  and b 2  are respectively approximated by a number with only one ‘1’ in their binary expressions, each of the multiplication operations may be obtained by just one no-cost bit-wise shift operation; for instance, b 0 u(n)≈u(n)×(0.0000001) b =u(n) shifted to the right by 7 bits. Conversions of all six multiplications in a BiQuad filter by shift operations and addition operations are illustrated in  FIG. 4 . 
     As shown in  FIG. 3 , by applying all the approximations of filter coefficients and replacing the multiplications with shift operations and addition operations, the BiQuad filter  20  in  FIG. 2  may be significantly simplified to the BiQuad filter  30  that does not use any multiplier as illustrated in  FIG. 3 . It is worth mentioning that in a hardware implementation, the shift operation does not require any hardware component; it only requires rearranging the wiring of data bus, and therefore occupies no hardware resources and consumes no power. 
     Note that the corner frequency f C ≈1439.24 Hz is relative to 48 Ksps sample rate. The same set of parameters above may produce the corner frequency f C ≈23,028 Hz at 768 Ksps sample rate, the corner frequency f C ≈28,785 Hz at 960 Ksps sample rate, the corner frequency f C ≈46,056 Hz at 1536 Ksps sample rate, or the corner frequency f C ≈92,111.63 Hz at 3072 Ksps sample rate etc. (i.e. with the same f C /f s ). 
     Please refer to  FIG. 5 , which illustrates amplitude response and phase response of the BiQuad filter  30  according to an embodiment of the present application. As shown in  FIG. 5 , simulations of the BiQuad filter  30  using 24-bit fixed-point arithmetic show a frequency response matching well that of the BiQuad filter  20  employing double-precision floating-point arithmetic. The solid curves show the frequency response of the BiQuad filter  20  when all the calculations are carried out in double-precision floating-point arithmetic. The dotted curves display the frequency response of the BiQuad filter  30  employing only shift operations and 24-bit fixed-point addition operations detailed in the above. 
     The precisions employed for the variables in the simulations are 16-bit word-length/15-bit fraction-length for the input and output, and 24-bit word-length/17-bit fraction-length for the states and accumulators. In both amplitude and phase responses, the errors between two curves are negligible. 
     To summarize, the procedures to choose filter coefficients [a 1 , a 2 , b 0 , b 1 , b 2 ] that may significantly simplify the implementation of a digital BiQuad filter involve
         (1) Approximate each coefficient by one term (e.g. b 0 , b 1 , b 2 ) or a sum-of-terms (e.g. a 1 , a 2 ) with each term containing only one ‘1’ in its binary expression.   (2) The sum-of-terms representation should consist as few terms as possible. Each term corresponds to a shift operation in the simplified BiQuad filter  30 .   (3) Verify that the coefficients employed result in a stable filter.       

     Please refer to  FIG. 6 , which is a schematic diagram of a BiQuad filter  60  according to another embodiment of the present application. In this embodiment, to further simplify the realization of a digital BiQuad, different approximations of the filter coefficients a 1  and a 2  are applied as follows (i.e. a different set of shift bit numbers of bit-wise shift operations and addition numbers of addition operations are corresponding to the same specific set of the corner frequency f C ≈1439.24 Hz at 48 ksps and the quality factor Q≈0.707):
 
 a   1 =−1.734863758990959≈−(1.75)=−(01.11) b =(0.01) b −(010.0) b  
 
 a   2 =0.766113758997616≈0.875=(0.111) b =(01.0) b −(0.001) b  
 
     Additionally, to get the BiQuad filter  60  with unit DC-gain, the coefficients b 0 , b 1  and b 2  are scaled by a factor of 4:
 
 b   0 ≈4×0.0078125=(0.00001) b  
 
 b   1 ≈4×0.015625=(0.0001) b  
 
 b   2 ≈4×0.0078125=(0.00001) b  
 
     The multiplication operation corresponding to the coefficient a 1  may be replaced by two shift operations and one addition operation, the multiplication operation corresponding to the coefficient a 2  may be replaced by one shift operation and one addition operation, and each of the multiplication operations corresponding to the coefficients b 0 , b 1  or b 2  may be replaced by 1 shift operation. As shown in  FIG. 6 , the BiQuad filter  60  requires two less addition operations and two less shift operations than the BiQuad filter  30 . 
     Noticeably, the above embodiments are all for a BiQuad filter. Nevertheless, the approach of using approximate filter coefficients to avoid the use of multipliers and simplify the implementation may be applied to other types of filters or digital signal processors that require multiplication operations. For example, by using the similar rationale, the replacement of coefficient multiplication may be applied to all-poles filter, as shown in left portion of  FIG. 7 , or all-zero filter, as shown in right portion of  FIG. 7 , which is also within the scope of the present application. 
     To sum up, the present application approximates multiplication operations with bit-wise shift operations to save hardware resources. 
     Those skilled in the art will readily observe that numerous modifications and alterations of the device and method may be made while retaining the teachings of the invention. Accordingly, the above disclosure should be construed as limited only by the metes and bounds of the appended claims.