An efficient arithmetic Sum-of-Product (SOP) based multiplication approach for FIR filters and DFT

In this paper, we present an arithmetic Sum-of-Product (SOP) based approach to implement an efficient Discrete Fourier Transform (DFT) as well as an FIR filter circuit. Our SOP based DFT engine uses an improved column compression algorithm, and also handles the sign of the input efficiently. The partial products of the computation are compressed down to 2 operands, which are then added using a single hybrid adder (which is comprised of a ripple carry adder for the early-arriving lower-order bits, a Kogge-Stone adder for the slower middle bits, and a carry-select adder for the early-arriving higher order bits). The DFT can also be cast as an instance of the Multiple Constant Multiplication (MCM) problem. We compare our SOP-based DFT implementation with the RAG-n approach, the best in-class existing implementation for the MCM problem. RAG-n utilizes a cascade of adders, and attempts to heuristically minimize the number of adders by sharing them across different computations of the DFT. We implemented both approaches using a 45 nm cell library, and demonstrate that our approach yields a faster DFT engine (by about 12-13%), with a small (about 5%) area penalty and a significantly better algorithmic runtime. Our approach is able to complete for DFT problems with a much higher bit precision than the RAG-n approach. The approach of our paper is generalized to implement digital filters as well, and we demonstrate that our approach realizes FIR filters with hard-to-implement coefficients with a 4× speedup and 1.4× area penalty compared to two recent adder-cascade based approaches [1].