Background of the Invention

[0001] Digital implementations of filters provide many advantages over conventional analog implementations. In a digital implementation of an analog filter that is being applied to an electrical signal, the electrical signal is sampled periodically and the samples are digitized to form a digital stream that is input to a computational circuit that performs the filter computations on the digitized samples to generate an output digital stream that can then be converted back to an analog signal. For the purposes of this discussion, the term filter latency will be defined as the time delay between the entry of a digital sample into the computational engine and the generation of the next output digital sample that depended on the input sample in question.

[0002] This time delay is particularly important for filters that are used in systems that are controlled by feedback loops. A filter can be thought of as lowering or amplifying signal components at chosen frequencies. Alternately , it can be thought of as creating a transfer function of a desired shape in the frequenc domain. If a digitally implemented filter is placed in the control loop, the delay introduced by the filter can cause the control system to become unstable leading to oscillations in the parameter that was to be controlled. In essence, the control system tries to regulate the system based on data that is too old to be valid and hence the control system overcompensates or under compensates the system in question.

[0003] Another problem with digitally implemented filters is the computational accuracy needed by the computational engine to accurately generate the filtered data stream. These problems can be minimized by utilizing computational engines having high precision floatingpoint arithmetic units. However such computational engines are economically unattractive for many applications and often involve significantly more computational latency than fixed point units. Hence implementations that can be carried out in fixed-point arithmetic are preferred. [0004] Both of these problems are intensified in applications in which a plurality of filters must be cascaded to remove the effects of multiple resonances and anti-resonances within the system being controlled. If two filters are cascaded, the latency of the pair of filters is twice that of an individual filter. If the cascaded pair is replaced by a single filter that implements same filtering operation, the length of the single filter is longer than either of the original filters. For example, two cascaded biquad filters would be replaced by a single filter whose numerator and denominator implemented 4th order polynomials. In some cases, the numerical precision required to implement the filter in fixed-point arithmetic increases substantially.

Summary of the Invention

[0005] The present invention includes a filter and method for filtering a signal. The filter is equivalent to a plurality of bi-quad or bilinear filters connected in series, and is implemented on a digital processor that receives a sequence of signal values at a sampling rate characterized by a sampling interval and generates a filtered signal value upon receiving each received signal value. The filter has a latency that is less than the sampling interval. The filtered values can be generated by adding a term to a received signal value and multiplying the sum by a gain constant that depends on the filter constants. The added term does not depend on the current received signal value. The filter can be implemented in fixed-point integer arithmetic.

Brief Description of the Drawings

[0006] Figure 1 illustrates the computational flow of a digital bi-quad filter.

[0007] Figure 2A illustrates a series of bi-quad filters that are cascaded.

[0008] Figure 2B illustrates a filter according to the present invention that is implemented as a cascade of unit direct feedthrough gain bi-quads.

[0009] Figure 2C illustrates another embodiment of a cascaded filter according to the present invention.

[0010] Figure 3 illustrates another embodiment of a filter according to the present invention. [0011] Figure 4 is a flow chart of the computational algorithm used in one embodiment of the present invention.

Detailed Description of the Preferred Embodiments of the Invention

[0012] The manner in which the present invention provides its advantages can be more easily understood with reference to Figure 1, which illustrates the computational flow of a bi- quad filter. Filter 20 receives a sequence of digital signal values u(k) and generates a sequence of filtered digital values y(k). The mathematical computation involved in generating the filtered values can be summarized as follows:

where b ₀ is referred to as the direct feedthrough gain, in that it is the scaling of the input, u(k), which shows up without delay at the output, y(k).

Alternately, Equation (2) can be replaced by

or

The parameters a ₁ , a ₂ , b ₀ , b ₁ , b ₂ are determined by the desired poles and zeros of the digital filter, which in turn provide properties such as the center frequency, etc. In one embodiment, the filter can be specified to be an anti-resonance, resonance pair which will equalize out the effects of a resonance, an ti -resonance pair in the system dynamics. In another embodiment, the filter can be set to be a single lead/lag filter or a double lead/double lag filter. In another embodiment, the filter can be a single or double lag/lead filter, hi a further embodiment, the filter can be shaped to be a band pass or a band stop filter. The manner in which these parameters are chosen will be discussed in more detail below. [0013] It should be noted that the quantity -a ₁ d(k - 1) - ci-,d(k - 2) can be computed as soon as u(k - 1) is received, and hence, the latency in computing d(k) is just the time to perform one addition. Similarly, can be computed as soon as u(k - l) is received,

and can be computed as soon as u(k - 1) is received. Hence, it

can be seen from Equations 2a, 2b, and 3 that the total latency in computing y(k) is the time for one add and one multiply.

[0014] The manner in which the computational method of the present invention provides its advantages can be more easily understood by defining a sequence of delay vectors. For a single bi-quad filter, define the sequence of vectors whose components are given

by

These vectors will be referred to as "D-vectors" in the following discussion. Each time a signal value, u(k) is received, the D- vector is updated as follows: )

and the filtered value is computed according to

The vectors defined by the products can be computed as soon as u(k-l ) is received, and hence, the latency is the time needed for one scalar add and the final multiply to obtain y(k). It should also be noted that the multiple scalar adds can be performed in parallel, and hence, can be performed without increasing the filter latency time.

[0015] A single bi-quad filter provides filtering for one resonance/anti-resonance pair. To filter out multiple pairs or to implement a higher order transfer function, a series of bi-quad filters can be cascaded as shown in Figure 2A. In this example, there are N bi-quad filters;

exemplary filters are shown at 41 -43. The input to the i ^th filter is the output of the (i-l) ^st filter. The input of the first filter is the input stream and the output of the Nth filter is the filtered output from the cascade.

A single bi-quad is represented by the transfer function:

which, as noted above, can be implemented in the time domain as:

In one embodiment, b ₀ is factored out and hence,

In this case,

In the following discussion, a filter having the transfer function form

will be referred to as a unit direct feedthrough gain bi-quad filter because its value for the direct feedthrough gain, bo, is set to 1. Refer now to Figure 2B, which illustrates a filter according to the present invention that is implemented as a chain of bi-quads. Filter 70 is constructed from N unit direct feedthrough gain bi-quads shown at 71-73. The output of the last bi-quad is amplified by a gain stage 74 that adjusts the output to provide the desired overall gain.

[0016] It should be noted that the numerator of Eq. (10) attenuates signals in a frequency band corresponding to the notch. The denominator provides the gain in a second band of frequencies. The coefficients, a ₁ and b ₁ , are related to the properties of these bands. The bo coefficient is, by definition the direct feedthrough gain of the bi-quad. By factoring out the b ₀ term, a cascade of bi-quads having the same (unity) direct feedthrough gain can be implemented followed by a single gain stage. This facilitates implementations in which a general filter processor is provided which will implement the cascade in response to the user inputting the parameters for each bi-quad and the overall gain of the system.

[0017] To simplify the following discussion, in a chain of bi-quads, extra subscripts are utilized to denote the quantities that are associated with the individual bi-quads. The quantities of interest are as follows:

For each d;(k), define two components, d _i,1 (k) and d _i,2 (k) as follows:

The coefficients, a _{i, 1} , a _i,2 , b _i,1 , b _i,2 , and b _i,0 are determined from the desired filter properties as follows. First, for the i ^th filter, denote:

The pai'ameters in question are then related to these filter parameters as follows:

The manner in which the present invention provides its advantages can be more easily understood in terms of a vector.

It can be shown from the above definitions that Here, Mo is a matrix and Co is a constant vector. For example, in the case in which three quads are cascaded, it can be shown that

It should be noted that the matrix product M _D *D(k-1) can be computed as soon as u(k-1 ) is received. Hence, this formulation avoids the increased latency associated with a cascade of bi- quads.

Similarly, define a vector

It can be shown that

Y(k) = M _Y * D(k -1) + u(k) * C _Y (29) Here, Μγ is a matrix and Cy is a constant vector For example, in the case in which three bi-quads are cascaded, it can be shown that

[0018] The matrix product M _Y *D(k-1 ) can be computed as soon as D(k-1) is known. As noted above, D(k-1) can be computed as soon as u(k-l) is received. Assuming that the computations are carried out on a computer that has a cycle time that is much faster than the rate at which samples are received, they can be completed in less time than the time difference between successive samples. Thus, the precalculated portions of the filter are ready and the time to respond to the most recent sample is simply the time for one addition and one multiply. In this regard, it should be noted that the matrix multiplications and adds can be carried out in parallel on a machine having multiple processors or in programmable logic such as a Field

Programmable Gate Array (FPGA).

[0019] It should also be noted that the filter output depends only on , i.e.

, and hence, the output can be computed by adding a term that

depends only on the previously received values of the input sequence to u(k) and then scaling the result to provide the output.

[0020] The actual numeric calculations can be simplified by noting that two quantities for each bi-quad are repeated a number of times in the matrix products, and hence, these quantities can be computed once and used to compute the matrix products, hi particular, the quantities

are useful in reducing the computational complexity in that the matrix D vector products can be written in terms of sums and differences of these quantities. For example, in the case of three cascaded bi-quads,

and

An implementation of the filter shown in Figure 2B using these pre-calculated quantities is shown in Figure 2C.

[0021] If the sample rate is high compared to the frequencies of the dynamics to be filtered (such as the biquad providing a notch/resonance pair), and the computations are carried out in fixed-point integer arithmetic, the sums and differences discussed above can suffer from round-off errors, because, and

For the purposes of this discussion, the sampling rate will be said to be high compared to the frequencies of the dynamics to be filtered if the sampling rate is greater than 10 times the frequency of the lowest frequency notch. Consider the term:

that appears in Eq. (30). This term involves the difference of two quantities that are nearly equal. Hence, the difference in fixed-point arithmetic can be a number with only a few bits of accuracy even when the quantities in question are represented by numbers having 10 or 12 bits.

In one aspect of the present invention, the round-off error problems are significantly reduced by substituting

In terms of precalculated quantities described above, the new form of and p

make use of these coefficients:

where

_and

Here, uses scaled coefficients for more accurate multiplication:

and then the scaling is removed before adding to :

[0022] Here, the coefficient, E _i , is chosen such that the multiplications have the desired precision. Furthermore, it is possible to select a different value of Ei for each coefficient in the equation. Similarly, where

[0023] Refer now to Figure 3, which illustrates one embodiment of a filter according to the present invention. Filter 50 processes an electric or optical signal from source 55. If source 55 provides an analog signal, the signal is digitized by A/D 54. If the source already produces a digital signal, A/D 54 can be omitted. A processor 51 computes the filtered signal from filter coefficients stored in a memory 52. Processor 51 can be implemented in special purpose signal processing hardware or as a conventional computational engine. Each time a new signal value is input to processor 51, processor 51 generates a digital output signal. If the desired output of filter 50 is an analog signal, an D/A converter 53 can be included in filter 52.

[0024] Refer now to Figure 4, which is a flow chart for one embodiment of the processing algorithm of the present invention. Initially, the process loops waiting for the next input value u(k) as shown at 61. When a new value u(k) is received, the processor retrieves the calculated vectors that were generated at the end of the last processing cycle as shown at 62 and generates a new output value, y(k), as shown at 63. The new input value is then used to pre- calculate the vectors needed to process the next input value as shown at 64. These values are then stored and the processor returns to the state in which it waits for the next input value. The processing time for calculating the pre-calculated vectors must be less than the time between samples. As noted above, special purpose hardware such as FPGAs could be utilized to reduce the processing time utilizing a parallel processing arrangement.

[0025] While the above-described embodiments of the present invention are directed to filters that have notches and resonances, the method of the present invention can be applied to the computation of any filter that is equivalent to a series of bi-quad filters. Similarly, any bi- quad stage can be used to implement a bilinear filter (with one pole and one zero) by setting, a _i,2 and to 0. In this case, resulting in coefficient values

b

[0026] The same filter structure as before could now be calculated. However, for improved precision, it is possible to change the computation of the Δ coefficients. For high sample rates compared to the dynamics to be filtered, then

which means that increased accuracy can be obtained by calculating: , and finally

For this bi-quad section: where

where the coefficient, E _i , is chosen such that the multiplications have the desired precision and likewise where

Again, it is possible to select a different value ofな for each coefficient in the equations.

[0027] While embodiments above have discussed a single-input, single output (SISO) filter, it will be understood that this invention can be applied to filters with multiple inputs (MI) , multiple outputs (MO), or both (MIMO).

[0028] The software or logic blocks used to implement the present invention can optimized for state space implementation (such as Equations 28-30) or transfer function form implementations (such as Equations 17-24), or something in between (such as Equations 31-32). It will be clear from the discussion above that these computations can be implemented any of these, or other similar forms.

[0029] The above-described embodiments of the present invention have been provided to illustrate various aspects of the invention. However, it is to be understood that different aspects of the present invention that are shown in different specific embodiments can be combined to provide other embodiments of the present invention. In addition, various modifications to the present invention will become apparent from the foregoing description and accompanying drawings. Accordingly, the present invention is to be limited solely by the scope of the following claims.