Efficient Computer Implementations of Fast Fourier Transforms

摘要

A comprehensive comparison of the most efficient Discrete Fourier Transform (DFT) techniques is presented. The DFT algorithms selected are the fixed radix Fast Fourier Transform (FFT), mixed radix FET, the Winograd Fourier Transform Algorithm (WFTA), and the Prime Factor Algorithm (PFA). Comparison of the algorithms is based on the number of real multiplications, additions, and memory arrays required as a function of sequence length N. This paper reviews the literature, selects the most efficient DFT FORTRAN programs available, develops the number of real multiplications and additions as a function of N, and compares the algorithms using tables and plots of real multiplications, additions, and memory arrays. Comparison shows that the WFTA and PFA require the least real multiplications and additions, but the fixed radix and mixed radix FFTs require the least memory. The mixed radix FFT is much more flexible than WFTA or PFA since N can be any length sequence. The WFTA and PFA are closely studied and tradeoffs between the two are discussed. Based on the results of the paper, an algorithm is presented to select the most efficient DFT for an N length sequence given the multiply speed, add speed, and memory size of the computer.