Very Low-Complexity Digital Filters Based On Computational Redundancy Reduction

We present computation reduction t,echniques which can be used to obtain multiplierless implementations of finite impulse response (FIR.) digital filters. The ideas presented in this work are also applicable to infinite i~!pulsere sponse (IIR) digital filters. The main idea is to remove computational redundancy by reordering computation. Hence, the frequency response of the desired filter is unaltered. Various approaches are presented which consider normal, diflerential and hybrid coefficients. It is shown that the reordering prl2blem can be formulated using a graph in which vertices represent the coefficients and edges represent resources required in a computation involving the coefficient. We present variou:: schemes which reduce filter c:omplexity by specifically targeting computational redundancy inherent in normal filter implementation,~. S imple polynomial run time algorithms are presented and their power and potential is derllonstratecl by presenting results for large (up to 600 tap) filters which show significant reduction in the number of add operations per coefficient. We also consider filter implementations i~n which shifted values of computations can be obtained using simple interconnects without incurring extra computation. We present a, methodology using which such computation can be re-used in subsequent computations and show such operations further reduce computational redundancy resulting in extremelly simple filters. It is shown that as low as 0.1 adders per filter coefficient are required to implement the multipliers in such filters. Ilence, such filters can be used in very high-speed applications. Alternatively, using voltage scaling, one can significantly reduce the power consumption of such filters for any desired, performance