[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

50 Years of FFT Algorithms and Applications

  • Published:
Circuits, Systems, and Signal Processing Aims and scope Submit manuscript

Abstract

The fast Fourier transform (FFT) algorithm was developed by Cooley and Tukey in 1965. It could reduce the computational complexity of discrete Fourier transform significantly from \(O(N^2)\) to \(O(N\log _2 {N})\). The invention of FFT is considered as a landmark development in the field of digital signal processing (DSP), since it could expedite the DSP algorithms significantly such that real-time digital signal processing could be possible. During the past 50 years, many researchers have contributed to the advancements in the FFT algorithm to make it faster and more efficient in order to match with the requirements of various applications. In this article, we present a brief overview of the key developments in FFT algorithms along with some popular applications in speech and image processing, signal analysis, and communication systems.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9
Fig. 10
Fig. 11
Fig. 12
Fig. 13
Fig. 14
Fig. 15

Similar content being viewed by others

Notes

  1. Twiddle factor multiplication by \( 1, -1,~j, \) and \( -j \) are trivial and other multiplications by \( W_{8}^{1}=0.707-j0.707, W_{16}^{1}=0.923-j0.382 \) are nontrivial.

  2. The FFT components in case of RFFT also are complex.

References

  1. O. Abari, E. Hamed, H. Hassanieh, A. Agarwal, D. Katabi, A.P. Chandrakasan, V. Stojanovic, 27.4 a 0.75-million-point fourier-transform chip for frequency-sparse signals, in 2014 IEEE International Solid-State Circuits Conference Digest of Technical Papers (ISSCC). (IEEE, 2014), pp. 458–459

  2. A. Agarwal, H. Hassanieh, O. Abari, E. Hamed, D. Katabi et al., High-throughput implementation of a million-point sparse Fourier Transform, in 2014 24th International Conference on Field Programmable Logic and Applications (FPL) (IEEE, 2014a), pp. 1–6

  3. A. Agarwal, H. Hassanieh, O. Abari, E. Hamed, D. Katabi et al., High-throughput implementation of a million-point sparse Fourier Transform, in 2014 24th International Conference on Field Programmable Logic and Applications (FPL) (IEEE, 2014b), pp. 1–6

  4. N. Ahmed, T. Natarajan, K.R. Rao, Discrete cosine transform. IEEE Trans. Comput. 100(1), 90–93 (1974)

    Article  MathSciNet  MATH  Google Scholar 

  5. M. Aminian, M. Saeedi, M.S. Zamani, M. Sedighi, Fpga-based circuit model emulation of quantum algorithms, in 2008 IEEE Computer Society Annual Symposium on VLSI. (IEEE, 2008), pp. 399–404

  6. M. Ayinala, Y. Lao, K.K. Parhi, An in-place FFT architecture for real-valued signals. IEEE Trans. Circuits Syst. II Express Briefs 60(10), 652–656 (2013)

    Article  Google Scholar 

  7. K. Babionitakis, V.A. Chouliaras, K. Manolopoulos, K. Nakos, D. Reisis, N. Vlassopoulos, Fully systolic FFT architecture for giga-sample applications. J. Signal Process. Syst. 58(3), 281–299 (2010)

    Article  Google Scholar 

  8. G. Bergland, A radix-eight fast Fourier transform subroutine for real-valued series. IEEE Trans. Audio Electroacoustics 17(2), 138–144 (1969)

    Article  Google Scholar 

  9. G.D. Bergland, Numerical analysis: a fast Fourier transform algorithm for real-valued series. Commun. ACM 11(10), 703–710 (1968)

    Article  MATH  Google Scholar 

  10. G. Bi, Y.Q. Chen, Fast DFT algorithms for length n= q* \( 2^m \). IEEE Trans. Circuits Syst. II Analog Digit. Signal Process. 45(6), 685–690 (1998)

    Article  MATH  Google Scholar 

  11. S. Bouguezel, M.O. Ahmad, M.S. Swamy, A new radix-2/8 FFT algorithm for length-q\(\times \) \( 2^m \) DFTs. IEEE Trans. Circuits Syst. I Regul. Pap. 51(9), 1723–1732 (2004)

    Article  MathSciNet  MATH  Google Scholar 

  12. R.N. Bracewell, Discrete hartley transform. JOSA 73(12), 1832–1835 (1983)

    Article  Google Scholar 

  13. O. Buneman, Inversion of the Helmholtz (or Laplace-Poisson) operator for slab geometry. J. Comput. Phys. 12(1), 124–130 (1973)

    Article  MathSciNet  Google Scholar 

  14. C. Burrus, P. Eschenbacher, An in-place, in-order prime factor FFT algorithm. IEEE Trans. Acoust. Speech Signal Process. 29(4), 806–817 (1981)

    Article  MATH  Google Scholar 

  15. Z. Chen, L. Zhang, Vector coding algorithms for multidimensional discrete Fourier transform. J. Comput. Appl. Math. 212(1), 63–74 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  16. T. Cho, H. Lee, J. Park, C. Park, A high-speed low-complexity modified radix-\(2^{5}\) FFT processor for gigabit WPAN applications, in 2011 IEEE International Symposium on Circuits and Systems (ISCAS) (2011), pp. 1259–1262. https://doi.org/10.1109/ISCAS.2011.5937799

  17. J.-R. Choi, S.-B. Park, D.-S. Han, S.-H. Park, A 2048 complex point FFT architecture for digital audio broadcasting system, in The 2000 IEEE International Symposium on Circuits and Systems, 2000. Proceedings. ISCAS 2000 Geneva, vol. 5 (IEEE, 2000), pp. 693–696

  18. W.T. Cochran, J.W. Cooley, D.L. Favin, H.D. Helms, R.A. Kaenel, W.W. Lang, G.C. Maling Jr., D.E. Nelson, C.M. Rader, P.D. Welch, What is the fast Fourier transform? Proc. IEEE 55(10), 1664–1674 (1967)

    Article  Google Scholar 

  19. J. Cooley, J. Tukey, An algorithm for the machine calculation of complex Fourier series. Math. Comput. 19(90), 297–301 (1965)

    Article  MathSciNet  MATH  Google Scholar 

  20. A. Cortés, I. Vélez, J. Sevillano, M. Turrillas, Fast Fourier Transform Processors: Implementing FFT and IFFT Cores for OFDM Communication Systems (INTECH Open Access Publisher, London, 2012)

    Google Scholar 

  21. G.C. Danielson, C. Lanczos, Some improvements in practical Fourier analysis and their application to X-ray scattering from liquids. J. Franklin Inst. 233(4), 365–380 (1942)

    Article  MathSciNet  MATH  Google Scholar 

  22. P. Duhamel, Implementation of “Split-radix” FFT algorithms for complex, real, and real-symmetric data. IEEE Trans. Acoust. Speech Signal Process. 34(2), 285–295 (1986). https://doi.org/10.1109/TASSP.1986.1164811

    Article  MathSciNet  Google Scholar 

  23. P. Duhamel, H. Hollmann, Split radix. FFT algorithm. Electron. Lett. 20(1), 14–16 (1984). https://doi.org/10.1049/el:19840012

    Article  Google Scholar 

  24. P. Duhamel, M. Vetterli, Fast Fourier transforms: a tutorial review and a state of the art. Signal Process. 19(4), 259–299 (1990)

    Article  MathSciNet  MATH  Google Scholar 

  25. V.K. Dwivedi, P. Kumar, G. Singh, A novel blind frequency offset estimation method for OFDM systems, in International Conference on Recent Advances in Microwave Theory and Applications, 2008. MICROWAVE 2008 (IEEE, 2008), pp. 668–675

  26. C.-P. Fan, M.-S. Lee, G.-A. Su, A low multiplier and multiplication costs 256-point FFT implementation with simplified radix-\(2^{4}\) SDF architecture, in IEEE Asia Pacific Conference on Circuits and Systems, 2006. APCCAS 2006 (2006), pp. 1935–1938. https://doi.org/10.1109/APCCAS.2006.342239

  27. M. Frigo, S.G. Johnson, FFTW: an adaptive software architecture for the FFT, in Proceedings of the 1998 IEEE International Conference on Acoustics, Speech and Signal Processing, 1998, vol. 3 (IEEE, 1998), pp. 1381–1384

  28. M. Garrido, K.K. Parhi, J. Grajal, A pipelined FFT architecture for real-valued signals. IEEE Trans. Circuits Syst. I Regul. Pap. 56(12), 2634–2643 (2009)

    Article  MathSciNet  Google Scholar 

  29. M. Garrido, J. Grajal, M. Sanchez, O. Gustafsson, Pipelined radix-\(2^{k}\) feedforward FFT architectures. IEEE Trans. Very Large Scale Integr. (VLSI) Syst. 21(1), 23–32 (2013). https://doi.org/10.1109/TVLSI.2011.2178275

    Article  Google Scholar 

  30. M. Garrido, S.-J. Huang, S.-G. Chen, O. Gustafsson, The serial commutator FFT. IEEE Trans. Circuits Syst. II Express Briefs 63(10), 974–978 (2016)

    Article  Google Scholar 

  31. W.M. Gentleman, G. Sande, Fast Fourier transforms: for fun and profit, in Proceedings of the November 7–10, 1966, Fall Joint Computer Conference (ACM, 1966), pp. 563–578

  32. B. Ghazi, H. Hassanieh, P. Indyk, D. Katabi, E. Price, L. Shi, Sample-optimal average-case sparse Fourier transform in two dimensions. arXiv preprint arXiv:1303.1209 (2013)

  33. J.D. Gibson, Speech compression. Information 7(2), 32 (2016)

    Article  Google Scholar 

  34. A.C. Gilbert, S. Muthukrishnan, M. Strauss, Improved time bounds for near-optimal sparse Fourier representations, in Optics and Photonics 2005 (International Society for Optics and Photonics, 2005)

  35. G. Goertzel, An algorithm for the evaluation of finite trigonometric series. Am. Math. Mon. 65, 34–35 (1958)

    Article  MathSciNet  Google Scholar 

  36. I.J. Good, The interaction algorithm and practical Fourier analysis. J. R. Stat. Soc. Ser. B (Methodol.) 20, 361–372 (1958)

    MathSciNet  MATH  Google Scholar 

  37. M.N. Haque, M.S. Uddin, M. Abdullah-Al-Wadud, Y. Chung, Fast reconstruction technique for medical images using graphics processing unit, in Signal Processing, Image Processing and Pattern Recognition (2011), pp. 300–309

  38. D. Harris, J.H. McClellan, D. Chan, H. Schuessler, Vector radix fast Fourier transform, in IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP’77, vol. 2 (IEEE, 1977), pp. 548–551

  39. H. Hassanieh, P. Indyk, D. Katabi, E. Price, Nearly optimal sparse fourier transform. CoRR, arxiv:abs/1201.2501 (2012a)

  40. H. Hassanieh, P. Indyk, D. Katabi, E. Price, Simple and practical algorithm for sparse Fourier transform, in Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms (SIAM, 2012b), pp. 1183–1194

  41. S. He, M. Torkelson, A new approach to pipeline FFT processor, in Proceedings of IPPS ’96, The 10th International Parallel Processing Symposium, 1996 (1996), pp. 766–770. https://doi.org/10.1109/IPPS.1996.508145

  42. M.T. Heideman, D.H. Johnson, C.S. Burrus, Gauss and the history of the fast Fourier transform. Arch. Hist. Exact Sci. 34(3), 265–277 (1985)

    Article  MathSciNet  MATH  Google Scholar 

  43. S.-H. Hsieh, C.-S. Lu, S.-C. Pei, Sparse fast Fourier transform by downsampling, in 2013 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP) (IEEE, 2013), pp. 5637–5641

  44. M.A. Iwen, Combinatorial sublinear-time Fourier algorithms. Found. Comput. Math. 10(3), 303–338 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  45. R.M. Jiang, An area-efficient FFT architecture for OFDM digital video broadcasting. IEEE Trans. Consum. Electron. 53(4), 1322–1326 (2007)

    Article  Google Scholar 

  46. S.G. Johnson, M. Frigo, A modified split-radix FFT with fewer arithmetic operations. IEEE Trans. Signal Process. 55(1), 111–119 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  47. O. Jung-Yeol, L. Myoung-Seob, New radix-2 to the 4th power pipeline FFT processor. IEICE Trans. Electron. 88(8), 1740–1746 (2005)

    Google Scholar 

  48. S.M. Kay, S.L. Marple, Spectrum analysisa modern perspective. Proc. IEEE 69(11), 1380–1419 (1981)

    Article  Google Scholar 

  49. M. Khalil-Hani, Y. Lee, M. Marsono, An accurate FPGA-based hardware emulation on quantum Fourier transform. Quantum 1, a1b3 (2015)

    Google Scholar 

  50. D. Kolba, T. Parks, A prime factor FFT algorithm using high-speed convolution. IEEE Trans. Acoust. Speech Signal Process. 25(4), 281–294 (1977). https://doi.org/10.1109/TASSP.1977.1162973

    Article  MATH  Google Scholar 

  51. E. Kushilevitz, Y. Mansour, Learning decision trees using the Fourier spectrum. SIAM J. Comput. 22(6), 1331–1348 (1993)

    Article  MathSciNet  MATH  Google Scholar 

  52. K. Li, W. Zheng, K. Li, A fast algorithm with less operations for length-DFTs. IEEE Trans. Signal Process. 63(3), 673–683 (2015)

    Article  MathSciNet  MATH  Google Scholar 

  53. X. Li, E. Blinka, Very Large FFT for TMS320C6678 Processors (Texas Instruments, Dallas, 2015)

    Google Scholar 

  54. Y. Liao, Phase and Frequency Estimation–High-Accuracy and Low-Complexity Techniques. Ph.D. thesis, Worcester Polytechnic Institute (2011)

  55. H.-K. Lo, T. Spiller, S. Popescu, Introduction to Quantum Computation and Information (World Scientific, Singapore, 1998)

    Book  MATH  Google Scholar 

  56. J. Markel, FFT pruning. IEEE Trans. Audio Electroacoustics 19(4), 305–311 (1971). https://doi.org/10.1109/TAU.1971.1162205

    Article  Google Scholar 

  57. S.A. Martucci, Symmetric convolution and the discrete sine and cosine transforms. IEEE Trans. Signal Process. 42(5), 1038–1051 (1994)

    Article  Google Scholar 

  58. P.K. Meher, Efficient systolic implementation of DFT using a low-complexity convolution-like formulation. IEEE Trans. Circuits Syst. II Express Briefs 53(8), 702–706 (2006)

    Article  Google Scholar 

  59. P.K. Meher, B.K. Mohanty, S.K. Patel, S. Ganguly, T. Srikanthan, Efficient vlsi architecture for decimation-in-time fast fourier transform of real-valued data. IEEE Trans. Circuits Syst. I Regul. Pap. 62(12), 2836–2845 (2015)

    Article  MathSciNet  Google Scholar 

  60. M.J. Narasimha, Modified overlap-add and overlap-save convolution algorithms for real signals. IEEE Signal Process. Lett. 13(11), 669–671 (2006)

    Article  Google Scholar 

  61. M. Narwaria, W. Lin, I.V. McLoughlin, S. Emmanuel, L.-T. Chia, Fourier transform-based scalable image quality measure. IEEE Trans. Image Process. 21(8), 3364–3377 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  62. X.S. Ni, X. Huo, Statistical interpretation of the importance of phase information in signal and image reconstruction. Stat. Probab. Lett. 77(4), 447–454 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  63. A.V. Oppenheim, J.S. Lim, The importance of phase in signals. Proc. IEEE 69(5), 529–541 (1981)

    Article  Google Scholar 

  64. A.V. Oppenheim, R.W. Schafer, J.R. Buck et al., Discrete-Time Signal Processing, vol. 2 (Prentice-Hall, Englewood Cliffs, 1989)

    MATH  Google Scholar 

  65. E. Oran Brigham, The Fast Fourier Transform and Its Applications (Prentice Hall, Englewood Cliffs, 1988)

    MATH  Google Scholar 

  66. S.-Y. Peng, K.-T. Shr, C.-M. Chen, Y.-H. Huang, Energy-efficient 128 2048/1536-point FFT processor with resource block mapping for 3GPP-LTE system, in 2010 International Conference on Green Circuits and Systems (ICGCS) (IEEE, 2010), pp. 14–17

  67. G. Popkin, Quest for qubits. Science 354(6316), 1090–1093 (2016). https://doi.org/10.1126/science.354.6316.1090

    Article  MathSciNet  MATH  Google Scholar 

  68. I. Present, Cramming more components onto integrated circuits. Read. Comput. Archit. 56 (2000)

  69. J. Princen, A. Bradley, Analysis/synthesis filter bank design based on time domain aliasing cancellation. IEEE Trans. Acoust. Speech. Signal Process. 34(5), 1153–1161 (1986)

    Article  Google Scholar 

  70. K.R. Rao, D.N. Kim, J.J. Hwang, Fast Fourier Transform-Algorithms and Applications (Springer, Berlin, 2011)

    MATH  Google Scholar 

  71. D. Rife, R. Boorstyn, Single tone parameter estimation from discrete-time observations. IEEE Trans. Inf. Theory 20(5), 591–598 (1974)

    Article  MATH  Google Scholar 

  72. R.L. Rivest, A. Shamir, L. Adleman, A method for obtaining digital signatures and public-key cryptosystems. Commun. ACM 21(2), 120–126 (1978)

    Article  MathSciNet  MATH  Google Scholar 

  73. C. Runge, Zeit. f. Math. u. Phys 48, 443–456 (1903)

    Google Scholar 

  74. A. Schönhage, V. Strassen, Schnelle multiplikation grosser zahlen. Computing 7(3–4), 281–292 (1971)

    Article  MathSciNet  MATH  Google Scholar 

  75. B.R. Sekhar, K. Prabhu, Radix-2 decimation-in-frequency algorithm for the computation of the real-valued fft. IEEE Trans. Signal Process. 47(4), 1181–1184 (1999)

    Article  MATH  Google Scholar 

  76. L. Shi et al., Imaging Applications of the Sparse FFT. Ph.D. thesis, Massachusetts Institute of Technology (2013)

  77. H. Shu, X. Bao, C. Toumoulin, L. Luo, Radix-3 algorithm for the fast computation of forward and inverse MDCT. IEEE Signal Process. Lett. 14(2), 93–96 (2007)

    Article  Google Scholar 

  78. H. Silverman, An introduction to programming the Winograd Fourier transform algorithm (WFTA). IEEE Trans. Acoust. Speech Signal Process. 25(2), 152–165 (1977)

    Article  MATH  Google Scholar 

  79. W.W. Smith, J.M. Smith, Handbook of Real-Time Fast Fourier Transforms, vol. 55 (IEEE Press, New York, 1995)

    Book  MATH  Google Scholar 

  80. H.V. Sorensen, D. Jones, M. Heideman, C. Burrus, Real-valued fast Fourier transform algorithms. IEEE Trans. Acoust. Speech Signal Process. 35(6), 849–863 (1987)

    Article  Google Scholar 

  81. D. Takahashi, An extended split-radix FFT algorithm. IEEE Signal Process. Lett. 8(5), 145–147 (2001)

    Article  Google Scholar 

  82. D. Takahashi, A radix-16 FFT algorithm suitable for multiply-add instruction based on Goedecker method, in International Conference on Multimedia and Expo, ICME’03, vol. 2 (IEEE, 2003), pp. II–845

  83. F.J. Taylor, G. Papadourakis, A. Skavantzos, A. Stouraitis, A radix-4 FFT using complex RNS arithmetic. IEEE Trans. Comput. 100(6), 573–576 (1985)

    Article  Google Scholar 

  84. C. Temperton, Implementation of a self-sorting in-place prime factor FFT algorithm. J. Comput. Phys. 58(3), 283–299 (1985)

    Article  MathSciNet  MATH  Google Scholar 

  85. M. Turrillas, A. Cortés, I. Vélez, J.F. Sevillano, A. Irizar, An FFT core for DVB-T2 receivers, in 16th IEEE International Conference on Electronics, Circuits, and Systems, 2009. ICECS 2009 (IEEE, 2009), pp. 120–123

  86. M. Turrillas, A. Cortés, I. Vélez, J.F. Sevillano, A. Irizar, An area-efficient radix-\( 2^8 \) FFT algorithm for DVB-T2 receivers. Microelectron. J. 45(10), 1311–1318 (2014)

    Article  Google Scholar 

  87. C. Van Loan, Computational Frameworks for the Fast Fourier Transform (SIAM, Philadelphia, 1992)

    Book  MATH  Google Scholar 

  88. S. Wang, V.M. Patel, A. Petropulu, An efficient high-dimensional sparse Fourier transform. arXiv preprint arXiv:1610.01050 (2016)

  89. S. Wang, V.M. Patel, A. Petropulu, The robust sparse fourier transform (RSFT) and its application in radar signal processing. IEEE Trans. Aerosp. Electron. Syst. 53(6), 2735–2755 (2017)

    Article  Google Scholar 

  90. P. Welch, The use of fast Fourier transform for the estimation of power spectra: a method based on time averaging over short, modified periodograms. IEEE Trans. Audio Electroacoustics 15(2), 70–73 (1967)

    Article  Google Scholar 

  91. L.P. Yaroslavsky, Fast transforms in image processing: compression, restoration, and resampling. Adv. Electr. Eng. (2014). https://doi.org/10.1155/2014/276241

  92. R. Yavne, An economical method for calculating the discrete Fourier transform, in Proceedings of the December 9–11, 1968, Fall Joint Computer Conference, Part I (ACM, 1968), pp. 115–125

  93. C. Yu, M.-H. Yen, Area-efficient 128-to 2048/1536-point pipeline FFT processor for LTE and mobile WiMAX systems. IEEE Trans. Very Large Scale Integr. (VLSI) Syst. 23(9), 1793–1800 (2015)

    Article  MathSciNet  Google Scholar 

  94. W. Zheng, K. Li, K. Li, A fast algorithm based on SRFFT for length DFTs. IEEE Trans. Circuits Syst. II Express Briefs 61(2), 110–114 (2014)

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Electrical Engineering, BITS - Pilani, Hyderabad Campus, Hyderabad, Telangana, India

    G. Ganesh Kumar & Subhendu K. Sahoo

  2. C V Raman College of Engineering, Bhubaneswar, India

    Pramod Kumar Meher

Authors
  1. G. Ganesh Kumar
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Subhendu K. Sahoo
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Pramod Kumar Meher
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to G. Ganesh Kumar.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Kumar, G.G., Sahoo, S.K. & Meher, P.K. 50 Years of FFT Algorithms and Applications. Circuits Syst Signal Process 38, 5665–5698 (2019). https://doi.org/10.1007/s00034-019-01136-8

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00034-019-01136-8

Keywords

Search

Navigation