Discrete Fourier Transform (DFT) and Finite Impulse Response (FIR) filters are extensively used in Digital Signal Processing (DSP) and Image Processing. As a result, there is a strong motivation to come up with area- and delay-efficient hardware realizations of DFT and FIR filters. In this thesis, we propose an arithmetic Sum-of-Product (SOP) based approach to implement area- and delay-efficient Discrete Fourier Transform (DFT) and FIR filter circuits. Our 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 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 and FIR filters can also be cast as instances 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. We compare our SOP-based implementations with the RAG-n algorithm. We implement both approaches using a 45 nm cell library, and demonstrate that our approach yields a faster DFT circuit (by about 12-13%), with a small (about 5%) area penalty and a significantly better algorithmic runtime. We also demonstrate that our approach realizes FIR filters with hard-to-implement coefficients with a 4.4× speedup and 1.38× area penalty as compared to two recent adder cascade based approaches. For a set of symmetric and asymmetric filters, we compare the area-delay curves of the circuits generated by using our SOP based approach with that of the circuits generated by using a Common Sub-expression Elimination (CSE) based algorithm, which tries to minimize the number of adders utilized under a maximum adder cascade length constraint. We show that for a large range of delays, the circuits generated by using our approach have the smallest area.
Finally, we propose a new hybrid form realization for FIR filters. The hybrid form realization attempts to perform the computation using both the Direct and Transposed Direct form realization styles. We discuss conditions under which it would improve on both the Direct and Transposed Direct form realizations, in terms of circuit area and delay.
| Identifer | oai:union.ndltd.org:tamu.edu/oai:repository.tamu.edu:1969.1/149498 |
| Date | 03 October 2013 |
| Creators | Kumar, Rajeev |
| Contributors | Khatri, Sunil P., Shi, Weiping, Jiang, Anxiao |
| Source Sets | Texas A and M University |
| Language | English |
| Detected Language | English |
| Type | Thesis, text |
| Format | application/pdf |
Page generated in 0.0026 seconds