Comparison of Arithmetic Requirements for the PFA (Prime Factor Algorithm), WFTA (Winograd Fourier Transform Algorithm), SWIFT, MFFT (Mixed Radix Fast Fourier Transform), FFT (Fast Fourier Transform) and DFT (Discrete Fourier Transform) Algorithms.

摘要

This discrete Fourier transform (DFT) is a powerful reversible mapping transform for discrete data sequences with mathematical properties analogous to those of the Fourier transform. The DFT can be used for spectral analysis of time series, fast correlation of sequences, fast convolution of sequences for the purpose of digital filtering, and for radar digital beamforming. The ever increasing importance of the DFT algorithm has led to the development of several more efficient algorithms requiring far less arithmetic computations than the DFT. This report examines the multidimensional DFT decomposition theory central to many of these algorithms and gives a brief introduction to the radix-2 fast Fourier transform (FFT), radix-4 FFT, mixed radix fast Fourier transform (MFFT), prime factor algorithm (PFA), Winograd Fourier transform (WFTA), and SWIFT algorithms. In addition, the arithmetic complexity of these algorithms is compared for various one and two-dimensional transform sizes. Included in the comparison are the number of real additions, real multiplications, total real operations, total equivalent real multiplications, and integrated circuit chips required for each algorithm. (Author)