Title :
Fast implementation of recursive DFTs
Author :
Zhang, Y.Z. ; Yao, Y.F.
Author_Institution :
Changcheng Inst. of Measure. & Metrol., Beijing, China
Abstract :
A fast implementation of recursive DFTs (discrete Fourier transforms) is presented. It only needs (N-1)/2 real multiplications to compute all N frequency components. A factor RT is introduced. If the ratio Tm/Ta of the multiplier and adder periods is greater than RT, this scheme is faster than the FFT (fast Fourier transform). The error and signal-to-noise ratio are studied. A parallel adder configuration that is much faster than the usual serial adder is proposed. A scheme for fast reordering of the input data that increases the reordering speed without increasing the memory size is also proposed
Keywords :
adders; fast Fourier transforms; discrete Fourier transforms; error; frequency components; input data; multiplications; parallel adder; recursive DFT; reordering speed; signal-to-noise ratio; Adders; Digital filters; Digital signal processing; Equations; Frequency domain analysis; Hardware; Metrology; Signal analysis; Signal design; Signal processing algorithms;
Conference_Titel :
Acoustics, Speech, and Signal Processing, 1989. ICASSP-89., 1989 International Conference on
Conference_Location :
Glasgow
DOI :
10.1109/ICASSP.1989.266617
