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

摘要

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.