Fast Fourier transforms for constrained data

Files in this item

Files Size Format View
8900281.PDF 6.804Mb application/pdf Thumbnail

Show simple item record

Item Metadata

dc.contributor.advisor Burrus, C. Sidney
dc.creator Sorensen, Henrik Vittrup 2009-06-04T00:30:37Z 2009-06-04T00:30:37Z 1988
dc.description.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, 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.
dc.format.extent 237 p.
dc.format.mimetype application/pdf
dc.language.iso eng
dc.subject Engineering, Electronics and Electrical
dc.title Fast Fourier transforms for constrained data
dc.type.genre Thesis
dc.type.material Text Electrical and Computer Engineering Engineering Rice University Doctoral Doctor of Philosophy
dc.identifier.citation Sorensen, Henrik Vittrup. (1988) "Fast Fourier transforms for constrained data." Doctoral Thesis, Rice University.

This item appears in the following Collection(s)