A Sum-Of-Product Based Multiplication Approach For FIR Filters And DFT

Discrete Fourier Transform (DFT) and Finite Impulse Response (FIR) filters are extensively used in Digital Signal Processing (DSP) and Image Processing. In this book, an arithmetic Sum-of-Product (SOP) based approach to implement area- and delay-efficient DFT and FIR filter circuits is presented. The proposed SOP based engine uses an improved column compression algorithm, and handles the sign of the input efficiently. The partial products of the computation are compressed down to two operands, which are then added using a single hybrid adder. The problem of synthesizing DFT and FIR filters circuits can also be cast as an instance of the Multiple Constant Multiplication (MCM) problem. RAG-n is one of the best known algorithms for realizing an MCM block with the minimum number of adders. For DFT coefficients, the proposed approach yields faster circuits (by about 12-13%) with low area penalty (about 5%), as compared to RAG-n. Significant speed-ups are also observed for a set of FIR filters with hard-to-implement coefficients.