Fast implementation of recursive DFTs
Y.Z. Zhang, Yi-zhou Yao · International Conference on Acoustics, Speech, and Signal Processing · 2003
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 R/sub T/ is introduced. If the ratio T/sub m//T/sub a/ of the multiplier and adder periods is greater than R/sub T/, 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.>