Abstract:
An infinite impulse response (IIR) filter is provided for receiving an input signal and outputting a filtered signal. The filter comprises feedback circuitry for feeding back said filtered signal, the feedback circuitry comprising a first delay element for delaying said filtered signal; and a sub-unit, for receiving said delayed filtered signal, for outputting a summed signal which is the difference between said delayed filtered signal and a further-delayed filtered signal, and for outputting a multiplied signal which is an inverted further-delayed filtered signal multiplied by a first filter coefficient. At least said input signal, said delayed filtered signal, said multiplied signal, and said summed signal are employed to generate said filtered signal.

Description:
[0001]    The present invention relates to IIR filters, and in particular to a method and an architecture for reducing the complexity of multiplying elements in such filters. 
       BACKGROUND 
       [0002]    The Infinite Impulse Response (IIR) digital filter is well known and widely documented. For a given filter specification, it is known that the sample rate has a significant influence on the required numerical accuracy of the implementation, both in terms of the accuracy of the filter coefficients, and in terms of the precision of the multipliers and adders: the higher the sample rate, the more accuracy is required to maintain the same filter performance. This increases the burden on hardware and software implementations, in turn increasing cost. 
         [0003]    In some applications, the signals are intentionally highly over-sampled, meaning that the ratio of the sample rate to highest signal frequency component is high. Although this may at first seem to be inefficient, this does allow a reduction in the number of bits used to represent the signal, and this is often the reason for using over-sampling. For example, it is sometimes appropriate to use only one bit to represent the signal at the over-sampled rate. Thus, there are applications where there are good reasons for an over-sampling situation to exist, and in which it is required to implement an IIR filter. One such example is an ambient noise cancellation system. 
         [0004]    There are several standard implementations of the IIR filter, for example the so-called “Direct Form I” and “Direct Form II” types. It is also common to split a higher-order filter into parallel or cascaded second-order sections, or a combination thereof, and there has been much research over the years on the best way to make this subdivision, taking into account stability, fixed-point issues, numerical ranges, and so on. However, all of these architectures suffer from the same numerical accuracy issues when the signals are over-sampled. 
         [0005]    The present invention is a method of implementing over-sampled IIR filters without requiring such high numerical accuracy. This leads to a lower cost solution, whether implemented in hardware or software. 
         [0006]    Furthermore, it has been found that the feed-forward coefficients of an over-sampled filter are also sensitive to numerical accuracy, and no prior-art method for reducing the computations requirements for this part of the filter has been found. The present invention also includes a method to address this part of the filter. 
       SUMMARY OF INVENTION 
       [0007]    According to a first aspect of the invention, there is provided an infinite impulse response (IIR) filter for receiving an input signal and outputting a filtered signal, said IIR filter comprising: feedback circuitry for feeding back said filtered signal, said feedback circuitry comprising: a first delay element for delaying said filtered signal; and a sub-unit, for receiving said delayed filtered signal, for outputting a summed signal which is the difference between said delayed filtered signal and a further-delayed filtered signal, and for outputting a multiplied signal which is an inverted further-delayed filtered signal multiplied by a first filter coefficient. At least said input signal, said delayed filtered signal, said multiplied signal, and said summed signal are employed to generate said filtered signal. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0008]    For a better understanding of the present invention, and to show more clearly how it may be carried into effect, reference will now be made, by way of example, to the following drawings, in which: 
           [0009]      FIG. 1  shows the feedback part of a standard second-order IIR filter. 
           [0010]      FIG. 2  shows a hardware implementation of a filter according to the present invention. 
           [0011]      FIG. 3  shows the feedback part of a sixth-order IIR filter according to the present invention. 
           [0012]      FIG. 4  shows the feedback part of a fourth-order IIR filter according to the present invention. 
           [0013]      FIG. 5  shows the feedback part of a fourth-order IIR filter arranged in a parallel format, according to the present invention. 
           [0014]      FIG. 6   a  shows a direct implementation of the feed-forward part of a filter according to the present invention. 
           [0015]      FIG. 6   b  shows the filter described in  FIG. 6   a  split into three cascaded second-order sections. 
           [0016]      FIG. 7  shows a sixth-order filter comprising a look-up table according to the present invention. 
           [0017]      FIG. 8  shows another sixth-order IIR filter according to the present invention. 
           [0018]      FIG. 9  shows a further sixth-order IIR filter according to the present invention. 
       
    
    
     DETAILED DESCRIPTION 
       [0019]    The present invention provides an IIR filter architecture that reduces the computational load compared to conventional implementations for over-sampled signals. It can be applied to any order of IIR filter. 
         [0020]      FIG. 1  shows the feedback part of a standard second-order IIR filter  10 , which receives an input signal and outputs a filtered signal. The input is added to a first feedback signal in a first adding element  12 , added to a second feedback signal in a second adding element  14 , and then output from the filter as the filtered signal. The filtered signal is fed back through a first delay element  16 , and multiplied by a first coefficient a 1  in a multiplying element  18  to generate the second feedback signal. The delayed signal output from the first delay element  16  is further output to a second delay element  20 , and multiplied by a second coefficient a 2  in a second multiplier  22  to generate the first feedback signal. 
         [0021]    The inventor observed that the values of the feedback coefficients a 1  and a 2  fall into certain narrow ranges for over-sampled filters. In particular, a 1  is always close to (but greater than) −2, and a 2  is close to (but less than)+1. Thus the values of (a 1 +2) and (1−a 2 ) are positive and much less than one. Furthermore, it was noted that the first of these two values was only slightly larger than the second, so that the difference (a 1 +2)−(1−a 2 ), or 1+a 1 +a 2 , was positive and small compared to either individual term. Thus these coefficients can be represented in a format that only requires these small differences to be used as coefficients, as follows: 
         [0000]        H   0 =2 +a   1    
         [0000]        H   1 =1 +a   1   +a   2    
         [0022]      FIG. 2  shows a hardware implementation of a filter  50  which uses these coefficients. 
         [0023]    The filter  50  receives an input signal, which is added to various fed back signals as follows, and outputs a filtered signal. The filtered signal is fed back through a delay element  52 . The output from the delay element  52  is input to an adding element  54 , where it is added to the input signal. The output from the delay element  52  is also input to a further delay element  56 ; the output from the delay element  56  is inverted in an inverter  58 ; the output from the inverter  58  is multiplied by H 1  in a multiplying element  60 ; and the output from the multiplying element  60  is input to the adding element  54 . The output from the inverter  58  is further input to an adding element  62 , where it is added to the output from the delay element  52 ; the output from the adding element  62  is also to the adder  54 . The output from adding element  62  is further inverted in an inverter  64 ; the output from the inverter  64  is multiplied by H 0  in a multiplying element  66 ; and the output from the multiplying element  66  is also input to the adding element  54 . 
         [0024]    Thus, it can be seen that the filter  50  contains a functional group  70  of components, including the delay element  56 , the inverter  58 , the multiplying element  60  and the adding element  62 . The functional group  70  receives an input signal (in this case the delayed filtered signal output from the delay element  52 ) and outputs an inverted signal multiplied by an H coefficient, and a summed signal. 
         [0025]    The analysis of the z-domain transfer function of the filter  50  is as follows. 
         [0026]    From the diagram, 
         [0000]      out=in+((1 −z   −1 )(1 −H   0 )+1 −H   1   z   −1 ) z   −1 out 
         [0027]    Collecting together like terms, 
         [0000]      (1+( H   0 −2) z   −1 +(1 −H   0   +H   1 ) z   −2 )×out=in 
         [0028]    Substituting the expressions for H0 and H1, 
         [0000]      (1+ a   1   z   −1   +a   2   z   −2 )×out=in 
         [0029]    This is the same as the transfer function of standard second order IIR filter  10  of  FIG. 1 . Thus the architecture of  FIG. 2  performs an identical function to that of  FIG. 1 , but has multiplication operations which require much less precision. 
         [0030]    A second order Butterworth IIR low-pass filter was designed as an example. The coefficients required for the standard filter and for the invention are listed below for various ratios of sampling frequency to filter cut-off frequency. 
         [0000]    
       
         
               
               
               
               
               
             
               
               
               
               
               
             
           
               
                   
               
               
                 Frequency ratio 
                 Coefficient a 1   
                 Coefficient a 2   
                 Coefficient H 0   
                 Coefficient H 1   
               
               
                   
               
             
             
               
                   
               
             
          
           
               
                 10 
                 −1.14298050253 
                 0.412801598096 
                 0.85701949747 
                 0.269821095566 
               
               
                 100 
                 −1.91119706742 
                 0.914975834801 
                 0.08880293257 
                 0.003778767375 
               
               
                 1000 
                 −1.99111429220 
                 0.991153595868 
                 0.00888570779 
                 0.000039303667 
               
               
                 10000 
                 −1.999111423470 
                 0.999111818079 
                 0.00088857652 
                 0.0000003946088 
               
               
                 100000 
                 −1.999911142341 
                 0.999911146288 
                 0.00008885765 
                 0.0000000039476 
               
               
                   
               
             
          
         
       
     
         [0031]    It can be seen that the conventional filter (i.e. that which uses coefficients a 0  and a 1 ) requires increasingly higher precision coefficients as the frequency ratio is increased. In fact, for every increase by a factor of 10 in the frequency ratio, the coefficients need to be approximately 10 times more accurate. In contrast, each increase by a factor of 10 in the frequency ratio simply scales the H 0  and H 1  coefficients of the invention down by a factor of approximately 10. If these coefficients are implemented with a combination of a bit-shift and a multiply, the multiplier itself is unchanged by this scaling. It is therefore a second object of the invention to provide a filter which is easily scalable in the frequency domain by such means. 
         [0032]    To further illustrate the invention, an example of a sixth-order filter  100  will be described. By cascading three second-order sections of the type shown in  FIG. 1  (with different coefficients), the feedback part of the sixth-order filter is created. We define the coefficients of these second-order feedback sections as follows. 
         [0000]    
       
         
               
               
               
             
           
               
                   
               
               
                 Second-order 
                   
                   
               
               
                 section number 
                 Coefficient a 1   
                 Coefficient a 2   
               
               
                   
               
             
             
               
                 1 
                 a 1A   
                 a 2A   
               
               
                 2 
                 a 1B   
                 a 2B   
               
               
                 3 
                 a 1C   
                 a 2C   
               
               
                   
               
             
          
         
       
     
         [0033]      FIG. 3  shows the feedback part of a sixth-order IIR filter  100  according to the present invention. 
         [0034]    The filter  100  comprises five cascaded functional groups  70 A,  70 B,  70 C,  70 D and  70 E for multiplying by the coefficients H 5 , H 4 , H 3 , H 2  and H 1 , respectively. Thus, the filter  100  receives an input signal, which is added to various fed back signals as follows, and outputs a filtered signal. The filtered signal is fed back through a delay element  102 . The output from the delay element  102  is input to an adding element  104 , where it is added to the input signal. The output from the delay element  102  is also input to the first functional group  70 A. The multiplied output of the first functional group  70 A is output to a delay element  106 ; and the summed output of the first functional group  70 A is input to the adding element  104 , as well as the second function group  70 B. The multiplied output of the second functional group  70 B is output to an adding element  108 , where it is added to the output from the delay element  106 ; the summed output of the second functional group  70 B is input to the adding element  104 , as well as the third function group  70 C. The output from the adding element  108  is fed through a delay element  110  to an adding element  112 . The multiplied output of the third functional group  70 C is output to the adding element  112 , where it is added to the output from the delay element  110 ; the summed output of the third functional group  70 C is input to the adding element  104 , as well as the fourth function group  70 D. The output from the adding element  112  is fed through a delay element  114  to an adding element  116 . The multiplied output of the fourth functional group  70 D is output to the adding element  116 , where it is added to the output from the delay element  114 ; the summed output of the fourth functional group  70 D is input to the adding element  104 , as well as the fifth function group  70 E. The output from the adding element  116  is fed through a delay element  118  to an adding element  120 . The multiplied output of the fifth functional group  70 E is output to the adding element  120 , where it is added to the output from the delay element  118 ; the output from the adding element  120  is input to the adding element  104 . Further, the summed output of the fifth functional group  70 E is input to the adding element  104 , as well as an inverter  122 . The output from the inverter  122  is fed to a multiplier  124 , where it is multiplied by a coefficient H 0 , and the output from the multiplier  124  is input to the adding element  104 . 
         [0035]    By following a similar mathematical process to that described above for a second-order filter, it is possible to derive the coefficients H 0  to H 5  as follows: 
         [0000]    
       
      
       H 
       0 
       =A 
       A 
       +A 
       B 
       +A 
       C  
      
     
         [0000]    
       
      
       H 
       1 
       =A 
       A 
       A 
       B 
       +A 
       A 
       A 
       C 
       +A 
       B 
       A 
       C 
       +B 
       A 
       +B 
       B 
       +B 
       C  
      
     
         [0000]        H   2   =A   A   A   B   A   C   +A   A ( B   B   +B   C )+ A   B ( B   A   +B   C )+ A   C ( B   A   +B   B ) 
         [0000]    
       
      
       H 
       3 
       =B 
       A 
       B 
       B 
       +B 
       A 
       B 
       B 
       +B 
       B 
       B 
       C 
       +A 
       A 
       A 
       B 
       B 
       C 
       +A 
       A 
       A 
       C 
       B 
       B 
       +A 
       B 
       A 
       C 
       B 
       A  
      
     
         [0000]    
       
      
       H 
       4 
       =B 
       A 
       B 
       B 
       A 
       C 
       +B 
       A 
       B 
       C 
       A 
       B 
       +B 
       B 
       B 
       C 
       A 
       A  
      
     
         [0000]      H 5 =B A B B B C    
         [0000]      where 
         [0000]        A   A =2 +a   1A    
         [0000]        B   A =1 +a   1A   +a   2A    
         [0000]        A   B =2 +a   1B    
         [0000]        B   B =1 +a   1B   +a   2B    
         [0000]        A   C =2 +a   1C    
         [0000]        B   C =1 +a   1C   +a   2C    
         [0036]    Provided that the sampling rate is high compared to the pole and zero frequencies (i.e. the filter is over-sampled), as described above, the coefficients H 0  to H 5  can be represented by a bit shift and a coefficient with relatively few bits of precision. It can be proven that the architecture of  FIG. 3  is mathematically equivalent to the original cascade of three second-order sections. The advantage of the invention is however clear: there are only six multiplies required, each of which requires a low-precision coefficient. For the same filter performance, the standard arrangement would require much higher multiplier precision. 
         [0037]    It is easy to extend the invention to higher-order or lower-order filters. The H coefficient formulae sum terms of the same order in each case, where the terms such as A A , A B , and A C  are regarded as first-order contributions and the terms such as B A , B B , and B C  are regarded as second-order contributions. Thus, first-order terms are the A X  coefficients, where the subscript X is A, B or C. Second-order terms are the B X  coefficients and products of two different A X  coefficients (i.e. A X .A Y , where the subscripts X and Y are different). Third-order terms are products of three A X  coefficients, or one A X  and one B X  coefficient, and so on. For the sixth-order filter  100  above, H 0  is the sum of the first-order terms, H 1  is the sum of the second-order terms, H 2  is the sum of third-order terms, and so on, up to H 5 , which is the sum of sixth-order terms, of which there is only one. 
         [0038]    It is also easy to see how the architecture extends to other filter orders. As a further example, a fourth-order filter  200  is shown in  FIG. 4 , and requires coefficients calculated according to the following formulae: 
         [0000]    
       
      
       H 
       0 
       =A 
       A 
       +A 
       B  
      
     
         [0000]    
       
      
       H 
       1 
       =A 
       A 
       A 
       B 
       +B 
       A 
       +B 
       B  
      
     
         [0000]    
       
      
       H 
       2 
       =A 
       A 
       B 
       B 
       +A 
       B 
       B 
       A  
      
     
         [0000]      H 3 =B A B B    
         [0000]    where the A x  and B x  values are as defined earlier. 
         [0039]    To demonstrate the advantages of the invention, a real example will be used. A fourth-order Butterworth low-pass filter with a cut-off frequency of 200 Hz and a sample rate of 3.072 MHz was designed using a standard filter design tool. The coefficients were as follows. 
         [0000]        a   1A =−1.999239168990805 
         [0000]      a 2A =0.9992393400955952 
         [0000]        a   1B =−1.999691901686791 
         [0000]      a 2B =0.9996920674391542 
         [0040]    Note that the coefficients would require 10 bits in order to represent the 0.999 part, and depending on the accuracy requirements, possibly a further 16 bits to represent the coefficient in sufficient detail—a total of 26 bits. 
         [0041]    Long data word lengths are usual in a conventional over-sampled filter, and the present invention does not avoid this. In both cases, therefore, as much as a 64-bit data word length may be required throughout the filter. In this case, the multiplier requirement for a conventional filter is therefore 64×26 bit multiplies. 
         [0042]    The values of the H coefficients using the formulae presented earlier are 
         [0000]        H   0 =0.547291813070848×2 −9    
         [0000]        H   1 =0.599×2 −20    
         [0000]        H   2 =0.768054549×2 −32    
         [0000]        H   3 =0.99786479768×2 −45    
         [0043]    Each coefficient requires a different bit-shift to implement the scaling power of 2. It has been found by simulation that the normalised H coefficients can be implemented with 8 or fewer bits without significant loss of filter accuracy. Because of the differing bit shift, the data word length for the multipliers is also reduced. H 3 , for example, only requires a data word length of 64-45, i.e. 19 bits. It therefore requires a 19×8 bit multiplier, a considerable saving on the conventional 64×26 multiply. 
         [0044]    It can be seen that the magnitude of each H coefficient is approximately 212 times smaller than the previous a X  coefficient in this example; thus each successive bit-shift is 12 bits higher than the previous one. This is a result of the over-sampling ratio: the higher the sampling frequency relative to the filter poles, the larger the ratio between H coefficients. This allows a programmable or variable filter to be implemented with a limited or even fixed set of bit-shifts; thus expensive barrel-shifters are not required. Knowledge of these bit-shifts also allows reduced-length adders to be used in some parts of the architecture. 
         [0045]    An alternative to cascading second-order sections as described above is to arrange second-order sections in parallel, with their inputs connected to a common point and their outputs summed to form the filter output. An example of a 4th order filter  300  arranged in this format is shown in  FIG. 5 . 
         [0046]    The filter  300  includes substantially similar first and second second-order units, for multiplying by coefficients H A1  and H A0 , and H B1  and H B0 , respectively. The first unit receives an input signal and outputs a first intermediate filtered signal. The second unit also receives the input signal and generates a second intermediate filtered signal. The first and second intermediate filtered signals are summed in an adding element  302 , to generate the overall filtered output signal. Optionally, an additional gain term G may be required as shown to implement some filters, that is, the input signal may also be input to the adding element  302  via a multiplying element  304 , for multiplying the input signal by a gain term G. 
         [0047]    In the first second-order unit, the first intermediate filtered signal is fed back through a delay element  306 . The output from the delay element  306  is input to an adding element  308 , where it is added to the input signal. The output from the delay element  306  is also input to a first functional group  70 A′. The H A1 -multiplied output of the first functional group  70 A′ is output to the adding element  308 ; the summed output of the first functional group  70 A′ is output to the adding element  308  and an inverter  310 . The output from the inverter  310  is input to a multiplying element  312 , which multiplies it by the coefficient H A0 . The multiplied output from the multiplying element  312  is further input to the adding element  308 . 
         [0048]    In the second second-order unit, the second intermediate filtered signal is fed back through a delay element  314 . The output from the delay element  314  is input to an adding element  316 , where it is added to the input signal. The output from the delay element  314  is also input to a second functional group  70 B′. The H B1 -multiplied output of the second functional group  70 B′ is output to the adding element  316 ; the summed output of the second functional group  70 B′ is output to the adding element  316  and an inverter  318 . The output from the inverter  318  is input to a multiplying element  320 , which multiplies it by the coefficient H B0 . The multiplied output from the multiplying element  320  is further input to the adding element  316 . 
         [0049]    The outputs from the adding elements  306 ,  318  are then input to the adding element  302  as the first and second intermediate filtered signals, respectively. 
         [0050]    The fact that the inputs of all the second-order sections are connected together has useful benefits that are described below. 
         [0051]    The feed-forward part of the IIR filter will now be discussed. 
         [0052]    There are several ways in which the feed-forward part of the filter may be implemented without loss of applicability of the feedback part of the present invention described above. These include the standard methods of direct implementation and a cascade of second-order sections, referred to earlier. 
         [0053]    In addition, there are unconventional techniques which are particularly well suited to over-sampled systems. In many highly over-sampled systems, the data width can be quite low, maybe only one bit. This is possible without loss of signal quality because higher sampling rates can be traded off against word length. The application of an IIR filter to such signals favours the implementation of the feed-forward part of the filter in a single stage, instead of splitting it into cascaded second-order sections, and then this single stage can be further simplified, as explained below. These techniques are also directly applicable to the parallel arrangement of second-order sections. 
         [0054]      FIG. 6   a  shows a direct implementation of the feed-forward part, and  FIG. 6   b  shows it split into three cascaded second-order sections. All the multipliers of  FIG. 6   a  receive the data input, which has only a few bits, or a single bit. The multipliers therefore require relatively few hardware or software resources to implement. In contrast, in  FIG. 6   b , only the first stage has this advantage: the other stages have a long word-length input from the previous stage, and therefore require much larger multiplications. 
         [0055]    The method of  FIG. 6   a  is therefore preferred for these applications. The multipliers can be implemented by a hardware ROM or RAM, or software look-up table, as for example shown in  FIG. 7 . In the parallel arrangement of second-order sections, further savings can be made by sharing the chain of input delay elements between all the second-order sections. 
         [0056]    In the case of a single-bit input, the multipliers can be replaced by selectors (multiplexers) that select either the coefficient or its negated version, as shown in  FIG. 8 , or by switchable negation stages, as shown in  FIG. 9 , thus avoiding the use of any multipliers. 
         [0057]    It will be clear to those skilled in the art that the implementation may take one of several hardware or software forms, and the intention of the invention is to cover all these different forms. 
         [0058]    The skilled person will recognise that the above-described apparatus and methods may be embodied as processor control code, for example on a carrier medium such as a disk, CD- or DVD-ROM, programmed memory such as read only memory (firmware), or on a data carrier such as an optical or electrical signal carrier. For many applications, embodiments of the invention will be implemented on a DSP (digital signal processor), ASIC (application specific integrated circuit) or FPGA (field programmable gate array). Thus the code may comprise conventional program code or microcode or, for example code for setting up or controlling an ASIC or FPGA. The code may also comprise code for dynamically configuring re-configurable apparatus such as re-programmable logic gate arrays. Similarly the code may comprise code for a hardware description language such as Verilog TM or VHDL (very high speed integrated circuit hardware description language). As the skilled person will appreciate, the code may be distributed between a plurality of coupled components in communication with one another. Where appropriate, the embodiments may also be implemented using code running on a field-(re-)programmable analogue array or similar device in order to configure analogue/digital hardware. 
         [0059]    It should be noted that the above-mentioned embodiments illustrate rather than limit the invention, and that those skilled in the art will be able to design many alternative embodiments without departing from the scope of the appended claims. The word “comprising” does not exclude the presence of elements or steps other than those listed in a claim, “a” or “an” does not exclude a plurality, and a single processor or other unit may fulfil the functions of several units recited in the claims. Any reference signs in the claims shall not be construed so as to limit their scope.