Show simple item record

dc.creatorJOHNSON, HOWARD WAYNE
dc.date.accessioned 2007-05-09T19:29:52Z
dc.date.available 2007-05-09T19:29:52Z
dc.date.issued 1982
dc.identifier.urihttp://hdl.handle.net/1911/15688
dc.description.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.
dc.format.mimetype application/pdf
dc.language.iso eng
dc.subjectElectronics
Electrical engineering
dc.title THE DESIGN OF DFT ALGORITHMS
dc.type.genre Thesis
dc.type.material Text
thesis.degree.department Electrical and Computer Engineering
thesis.degree.discipline Engineering
thesis.degree.grantor Rice University
thesis.degree.level Doctoral
thesis.degree.name Doctor of Philosophy
dc.identifier.citation JOHNSON, HOWARD WAYNE. "THE DESIGN OF DFT ALGORITHMS." (1982) PhD diss., Rice University. http://hdl.handle.net/1911/15688.


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record