THE DESIGN OF DFT ALGORITHMS

[摘要] 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.

[发布机构] Rice University

[效力级别] Electrical engineering