Fast Discrete Fourier Transform Computations Using the Reduced Adder Graph Technique
- PDF / 686,594 Bytes
- 8 Pages / 600.03 x 792 pts Page_size
- 40 Downloads / 160 Views
Research Article Fast Discrete Fourier Transform Computations Using the Reduced Adder Graph Technique ¨ 1 Hariharan Natarajan,1 and Andrew G. Dempster2 Uwe Meyer-Base, 1 Department
of Electrical and Computer Engineering, Florida State University, 2525 Pottsdamer Street, Tallahassee, FL 32310-6046, USA 2 School of Surveying and Spatial Information Systems, University of New South Wales, Sydney 2052, Australia Received 28 February 2006; Revised 23 November 2006; Accepted 17 December 2006 Recommended by Irene Y. H. Gu It has recently been shown that the n-dimensional reduced adder graph (RAG-n) technique is beneficial for many DSP applications such as for FIR and IIR filters, where multipliers can be grouped in multiplier blocks. This paper highlights the importance of DFT and FFT as DSP objects and also explores how the RAG-n technique can be applied to these algorithms. This RAG-n DFT will be shown to be of low complexity and possess an attractively regular VLSI data flow when implemented with the Rader DFT algorithm or the Bluestein chirp-z algorithm. ASIC synthesis data are provided and demonstrate the low complexity and high speed of the design when compared to other alternatives. Copyright © 2007 Hindawi Publishing Corporation. All rights reserved.
1.
INTRODUCTION
The discrete Fourier transform (DFT) and its fast implementation, the fast Fourier transform (FFT), have both played a central role in digital signal processing. DFT and FFT algorithms have been invented (and reinvented) in many variations. As Heideman et al. [1] have pointed out, we know that Gauss used an FFT-type algorithm we now call the CooleyTukey FFT. We will follow the terminology introduced by Burrus [2], who classified FFT algorithms according to the (multidimensional) index maps of their input and output sequences. We will therefore call all algorithms which do not use a multidimensional index map DFT algorithms, although some of them, such as the Winograd DFT algorithms, enjoy an essentially reduced computational effort. In a recent EURASIP paper by Macleod [3], the adder costs were discussed of rotators used to implement the complex multiplier in fully pipelined FFTs for 13 different methods, ranging from the direct method and 3-multiplier methods to the matrix CSE method and CORDIC-based designs. It was determined that not a single structure gave the best results for all twiddle factor values. On average the CORDICbased method gave the best results for single multiplier costs. In this paper, we restrict our design to the two most popular methods (4 × 2+ and 3 × 5+) used in FFT cores [4, 5] by FPGA vendors.
The literature provides many FFT design examples. We found implementations with programmable signal processors and ASICs [6–10]. FFTs have also been developed using FPGAs for 1D [11, 12] and 2D transforms [13, 14]. This paper deals with the implementation of two alternatives of fast DFTs via a transformation into an FIR filter. The methods are called a Rader DFT algorithm and a Bluestein chirp-z transform. We will present latency dat
Data Loading...
