Software Implementation of FFT Algorithms and Analysis of their Computational Complexity

摘要

An efficient computation of Discrete Fourier Transform (DFT) is necessary when the size of data is large and also to reduce the hardware requirements. Investigation of various algorithms which perform Fast Fourier Transformation (FFT) and also checking the numerous techniques for maximizing the FFT execution speed and reducing the complexity is the main focus. The most computational efficient algorithm is ascertained based on the comparison of the results obtained from Direct Computation of DFT, Radix-2 method using DIT-FFT (Decimation in Time Fast Fourier Transform) and DIF-FFT (Decimation in Frequency Fast Fourier Transform), Radix-3, Radix-4, algorithms and Split radix method. Results are based on the complex adders and complex multipliers each algorithm employs. Reduction in the arithmetic operations is one way to obtain a more efficient algorithm.