About Complexity of FFT Algorithms for Length of q × 2p
Keywords:
Fast Fourier transform (FFT), Split-radix algorithm, Computational complexityAbstract
The paper presents logarithmic formula which allows to compute the exact number of necessary operations for computing the discrete Fourier transform (DFT) of an arbitrary q × 2 p - length, where q is an odd integer.
References
E. O. Brigham, The Fast Fourier Applications, Englewood Cliffs, N J, Prentice-Hall, 1988.
J. K.Ersoy, Fourier-Related Transforms. Fast Algorithms and Applications, Englewood Cliffs, N J, Prentice-Hall,1997.
J. W. Cooley and J. W.Tukey, "A n algorithm for the machine computation of the complex Fourier series," Math. Computation, pp. 297-301 ,1965.
R. Yavne, A n economical method for calculating the discrete Fourier transform," in P roc. AFIP S, vol. 33, pp. 115-125, 1 968.
M. Frigo and S. G. Johnson, " A modi¯ed split-radix FFT with fewer arithmetic operations" , Ieee Trans. Signal Processing, vol. 55, pp. 111-119, 2207.
G. Bi and Y . Q. Chen, Fast D FT algorithm for length N = q × 2 p ," IEEE Trans. Circuits and Systems II, vol. 45, no. 6, pp. 685 - 690, 1 998.
G. Bi, G. Li and X .Li, Auni¯ed expression for split-radix DFT algorithms," pp. 323 - 326, 2010.
P. Duhamel, Implementation of split-radix FFT algorithms for complex, real, and realsymmetric data" , IEEE Trans. Acoust., Speech, Signal Process., vol. 34, pp. 285 - 295, April, 1986.
H . V . Sorensen, M. T. Heideman and C. S . Burrus, " On computing the split-radix FFT," IEEE Trans. A coust., Speech, Signal Process., vol. 34,pp. 152 - 156, Feb. 1986.
S. Bouguezel, M. Omair and M. N . S. Swamy,'' A new radix-2/ 8 FFT algorithm for length-q ×2 m DFTs," IEEE Trans. Circuits and Systems I, vol. 51 , no.1 , pp. 1723- 1732, 2004.
S. Bouguezel, M. Omair and M. N . S. Swamy, '' A general class of split-radix FFT algorithms for the computation of the DFT of length-2 m," IEEE Trans. Signal Processing, vol. 55, no. 8, pp. 4127 - 4138, 2007.
Online: [Available] http://maxima.sourceforge.net
I. Selesnick and S. Burrus, Programs for Prime Length FFTs," http://cnx.org/content/m18137/1.5/.
R. Barseghyan, Complexity of the composite length FFT algorithms" , P oceedings of International Conference CSIT 2015, Yerevan, Armenia, 2015.
Downloads
Published
How to Cite
Issue
Section
License
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
