1. Field of the Invention
This invention pertains to digital filters, and in particular to finite impulse response filters, transversal filters or any other filter involving the calculation of a convolution.
2. Description of the Prior Art
Filtering is one of the most important functions of real time linear signal processing. Among the different types of digital filters there has been a great deal of interest in finite impulse response (FIR) digital filters (also called transversal filter). The reason for this is that powerful and mature optimization theories exist to aid in the filter design. FIR filters can easily be designed to approximate a prescribed magnitude/frequency response to arbitrary accuracy with an exactly linear phase characteristic. The non-recursive FIR filters contain only zeroes in the finite z-plane and hence are always stable. These features make them very attractive for most digital signal processing applications.
The FIR filter is characterized by the input/output relation ##EQU1## where X.sub.n-i =X{t.sub.n -iT.sub.s } is the sampled input signal, Ci is the weighting coefficient and Y=Y{t.sub.n } is the corresponding output signal. T.sub.s is the sampling period, t.sub.n -nT.sub.s are sample instances and f.sub.s =1/T.sub.s is the sample rate. So each output sample is the weighted sum of a finite number of input samples (N in Equation 1).
In classical realization of Equation 1, the weighting of the input samples is accomplished by multipliers (FIG. 1). The multiplier is the most time consuming and expensive building block of the filter, thus there has been a great effort to make the multiplication operation cheaper and faster to increase the overall speed of operation of the filter.
Most authors in this field have approached this problem by severely restricting the coefficient space, many allowing only power of two coefficients to exist. This results in a remarkably simple architecture which requires no multipliers since power of two scaling is performed by simple shifts of the signal samples. However, this restriction also compromises the filter performance, making it very difficult to meet the desired frequency response. This limitation has been dealt with in different ways. In one prior art embodiment, basic building blocks of powers of two filter stages are designed and then combined in cascade and/or parallel with appropriate power of two scaling (on a trial and error basis) to achieve the desired frequency response. Cf. R. C. Aggarwal, R. Sudhakar, "Multiplier-Less Design of FIR Filters", ICASSP 1983, pp. 209-212.
Another proposed technique eliminates the multipliers but the price is paid in having to use oversampling, greater filter lengths and recursive stages. An alternative approach in the so-called power of two FIR filters has been the use of prefilter/compensating technique to compensate for the limitation of the coefficient space. Bateman and Liu "An Approach to Programmable CTD Filters Using Coefficients 0, +1, and -1", IEEE Trans. on CAS, Vol. CAS-27, pp. 451-456, June 1980, proposes filter structures restricting coefficients to 0, 1 and -1 only. The result is extremely long filters, obtained after a complicated design process.
Even though these techniques have shown theoretical promise, they often result in longer filters (a greater number of taps) and extremely complicated design procedures, hence they have limited commercial appeal.
Significant research effort has also been directed toward architectural simplification of the multiplication operation, taking advantage of the expression of Equation 1. A fast but extremely expensive architecture has been proposed using Multi Valued Logic (MVL) and Residue Number System (RNS). Cf. M. A. Soderstand, R. A. Escott, "VLSI Implementation in Multiple-Valued-Logic of an FIR Digital Filter Using Residue Number System Architecture", IEEE Trans. on Circuits and Systems, Vol. CAS-33, No. 1, Jan. 1986. An alternative novel technique has been proposed using an architecture based on implementing Equation 1 on a bit level. Cf. A. J. Greenberger, "Digital Transversal Filter Architecture", Electronics Letters, 31 Jan. 1985, Vol. 21, No. 3. The increased speed came by taking advantage of bit slicing and distributed arithmetic. The technique performs the FIR convolution using accumulators to accumulate products of one bit coefficients with the entire input word length. This requires as many planes of accumulators as bits in the coefficients words. In addition, it needs special control circuitry to perform the operation. It also uses the more complex tri-state buffers increasing the equivalent gate count. The overall architecture is a complicated way of looking at the convolution of Equation (1). All the above features put together result in an architecture which approaches a multiplier implementation of the filter in complexity. This makes it inefficient and uneconomical for VLSI implementation. Some ideas were successful in increasing the speed tremendously, but their implementation/hardware complexity made a practical VLSI implementation prohibitive.
This application discloses an architecture which obtains the same speed of operation as the fastest prior art proposal, but uses substantially less hardware. The architecture of the present invention does not impose any restriction on the coefficient or the data sample space, and requires no special design consideration on the part of the user.
USPTO Backgrounds
USPTO Backgrounds