Abstract:

This thesis develops several new algorithms for computing the discrete Fourier transform (DFT). The work describes algorithms for which a set of constraints on the input or the output allow the DFT to be computed more efficiently than the standard fast Fourier transform (FFT) algorithms. The thesis reviews the Cooley Tukey, primefactor,and Winograd Fourier transform algorithms and introduces the splitradix FFT, which is a very powerful algorithm, since it requires the lowest number of total operations of any known algorithm for length that are powers of two. Comparing the splitradix FFT to Winograd's minimal multiplication FFT algorithms, it is conjectured to be optimal if both multiplications and additions are considered.
A splitradix algorithms is developed for handling real or symmetric input data and an efficient program for computing the splitradix FFT for both real and complex data is developed which is faster than Bergland's highly optimized radix8 FFT on several machines. The Hartley transform is also described, and several new algorithms such as the splitradix, primefactor, Winograd Hartley transform are developed.
Putting restrictions on either the number of inputs or outputs, a new algorithm, transform decomposition (TD), that reduces the number of operations over pruning is developed. The TD algorithm is also much more flexible than pruning, since it does not restrict the number of inputs/outputs and does not require the inputs/outputs to be sequential and it allows a reduction in the number of operations when the input or output is either real or symmetric. The TD algorithm is based on the splitradix FFT algorithms.
A new recursive algorithm for computing the shorttime Fourier transform (STFFT) is also developed, which is based on the TD algorithm. It is found to be more efficient than successive application of an efficient FFT for lags up to about a fourth of the transform length. The algorithm works with windows that can be efficiently applied in the frequency domain and the error accumulation is shown to be within tolerable ranges for most applications. 