Fast Fourier transforms for constrained data

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, prime-factor,and Winograd Fourier transform algorithms and introduces the split-radix 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 split-radix FFT to Winograd's minimal multiplication FFT algorithms, it is conjectured to be optimal if both multiplications and additions are considered. A split-radix algorithms is developed for handling real or symmetric input data and an efficient program for computing the split-radix FFT for both real and complex data is developed which is faster than Bergland's highly optimized radix-8 FFT on several machines. The Hartley transform is also described, and several new algorithms such as the split-radix, prime-factor, 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 split-radix FFT algorithms. A new recursive algorithm for computing the short-time 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