Comparison of a new multiple radix fast Fourier number theoretic transform with FFT algorithms in terms of performance and hardware cost

Abstract

The number of real multiplications and additions for all the FFT algorithms is computed for selected data lengths. The arithmetic operations and the memory required are the basis for evaluating the hardware cost for each algorithm. The accuracy of the FFT/NTT algorithm is derived, and the results are compared to previously published accuracy analyses of other FFT algorithms. The FFT/NTT algorithm provides an accurate computation of a prime length discrete Fourier transform (DFT), with the only error sources being input and trigonometric coefficient quantization. These error sources are also found in other FFT implementations. However, due to the implementation of the FFT/NTT algorithm, the effect of these noise sources on the outputs is minimum for data lengths greater than 32. In the comparison of the arithmetic operations counts, the P-length FFT/NTT required more operations than a multiple-radix FFT of length P-1. However, in some cases, the number of operations as compared to a compatible radix-2 FFT favored the FFT/NTT. A speed advantage can be realized if the FFT/NTT is implemented in a pipeline configuration.>

Related Papers

• → Five-step FFT algorithm with reduced computational complexity(2006)9 cited
• → A Grouped Fast Fourier Transform Algorithm Design For Selective Transformed Outputs(2006)4 cited
• → A COOLEY-TUKEY MODIFIED ALGORITHM IN FAST FOURIER TRANSFORM(2011)1 cited
• → A family of MD FFT algorithms of complexity intermediate between the MD Cooley-Tukey FFT and the MD prime-factor FFT(2002)
• A Kind of Improved Real-Valued Fast Fourier Transform(FFT) and implementation on DSP(2012)