deposit_your_work

THE DESIGN OF DFT ALGORITHMS

Files in this item

Files Size Format View
8216326.PDF 3.145Mb application/pdf Thumbnail

Show full item record

Item Metadata

Title: THE DESIGN OF DFT ALGORITHMS
Author: JOHNSON, HOWARD WAYNE
Degree: Doctor of Philosophy thesis
Abstract: A broad class of efficient discrete Fourier transform algorithms is developed by partitioning short DFT algorithms into factors. The factored short DFT's are combined into longer DFT's using multidimensional index maps. By exploiting a property which allows some of the factors to commute, a large set of possible DFT algorithms is generated which contains both the prime factor algorithm (PFA) and the Winograd Fourier Transform Algorithm (WFTA) as special cases. The problem of finding an algorithm from this class which is optimal with respect to the specific add, multiply, and data transfer characteristics of a particular implementation is posed, and a highly effective dynamic programming algorithm is presented as a solution. Finally, it is demonstrated that the output reordering inherent in a PFA can be accomplished with zero data transfers by modifying the coefficients used in its constituent modules. Such a modification does not alter the signal flow topology of the module algorithms. A concrete procedure is derived to calculate the modified coefficients.
Citation: JOHNSON, HOWARD WAYNE. (1982) "THE DESIGN OF DFT ALGORITHMS." Doctoral Thesis, Rice University. http://hdl.handle.net/1911/15688.
URI: http://hdl.handle.net/1911/15688
Date: 1982

This item appears in the following Collection(s)