Abstract
In this paper we propose a fast parallel implementation of Discrete Fourier Transform (DFT) using FPGAs. Our design is based on the Arithmetic Fourier Transform (AFT) using zero-order interpolation. For a given problem of size N, AFT requires only O(N 2) additions and O(N) real multiplications with constant factors. Our design employes 2p + 1 PEs (1 ≤ p ≤ N), O(N) memory and fixed 1/O with the host. It is scalable over p (1 ≤ p ≤ N) and can solve larger problems with the same hardware by increasing the memory. All the PEs have fixed architecture. Our implementation is faster than most standard DSP designs for FFT. It also outperforms other FPGA-based implementations for FFT, in terms of speed and adaptability to larger problems.
This research was performed as part of the MAARC project (Models, Algorithms and Architectures for Reconfigurable Computing, http://maarc.usc.edu). This work is supported by DARPA Adaptive Computing Systems program under contract no. DABT63-96-C-00049 monitored by Fort Hauchuca.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
K. Bondalapati and V. K. Prasanna, “Reconfigurable Meshes: Theory and Practice”, Reconfigurable Architectures Workshop, Int. Parallel Processing Symposium (IPPS), April 1997.
K. Chapman, “Constant Coefficient Multipliers for the XC4000C”, XILINX Application Note 054, Dec. 1996.
S. Choi, Y. Chung and V. K. Prasanna, “Configurable Hardware for Symbolic Search Operations”, submitted to Int. Conf. Parallel and Distributed Systems, Dec. 1997.
Y. Chung S. Choi and V. K. Prasanna, “Parallel Object Recognition on an FPGA-based Configurable Computing Platform”, submitted to Int. Workshop on Computer Architecture for Machine Perception, Oct. 1997.
L. K. Hua, “Introduction to Number Theory”, New York: Springer-Verlag, 1982.
B. New, “Estimating the Performance of XC4000E Adders and Counters”, XILINX Application Note 018, July 1996.
H. Park and V. K. Prasanna, “Modular VLSI Architectures for Computing the Arithmetic Fourier Transform”, IEEE Trans. Signal Processing, vol. 41, no. 6, pp. 2236–2246, June 1993.
R. J. Petersen and B. L. Hutchings, “An Assessment of the Suitability of FPGA-Based Systems for use in Digital Signal Processing”, in Proc. Int. Workshop on Field-Programmable Logic and Applications, Aug. 1995.
I. S. Reed, D. W. Tufts, X. Yu, T. K. Truong, M. Shih and X. Yin, “Fourier analysis and signal processing by use of the Möbius inversion formula”, IEEE Trans. Acoust., Signal Processing, vol.38, no. 3, pp. 458–470, Mar. 1990.
I. S. Reed, M. T. Shih, T. K. Truong, E. Hendon and D. W. Tufts, “A VLSI architecture for simplified arithmetic Fourier transform algorithm”, in Proc. Int. Conf. Application Specific Array Processor, 1990.
R. Wilson, “Reprogrammable FPGA-based techniques provide prototyping aid”, Electronic Engineering Times, Mar. 11, 1996.
XILINX DSP Application notes, “The Fastest FFT in the West”, http://www.xilinx.com/apps/displit.htm
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1997 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Dandalis, A., Prasanna, V.K. (1997). Fast parallel implementation of DFT using configurable devices. In: Luk, W., Cheung, P.Y.K., Glesner, M. (eds) Field-Programmable Logic and Applications. FPL 1997. Lecture Notes in Computer Science, vol 1304. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-63465-7_236
Download citation
DOI: https://doi.org/10.1007/3-540-63465-7_236
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-63465-2
Online ISBN: 978-3-540-69557-8
eBook Packages: Springer Book Archive