Skip to main content
SpringerLink
Log in

Fast Fourier Transform

  • Chapter
Orthogonal Transforms for Digital Signal Processing

Abstract

The main objective of this chapter is to develop a fast algorithm for efficient computation of the DFT. This algorithm, called the fast Fourier transform (FFT), significantly reduces the number of arithmetic operations and memory required to compute the DFT (or its inverse). Consequently, it has accelerated the application of Fourier techniques in digital signal processing in a number of diverse areas. A detailed development of the FFT is followed by some numerical examples which illustrate its applications.

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

Access this chapter

Log in via an institution
eBook
USD 16.99
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 16.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

References

  1. Cochran, W. T., et al.: What is the Fast Fourier Transform? Proc. IEEE 55 (1967) 1664–1674.

    Article  Google Scholar 

  2. Cooley, J. W., and Tukey, J. W.: An Algorithm for Machine Computation of Complex Fourier Series. Mathematics of Computation 19 (1965) 297–301.

    Article  MathSciNet  MATH  Google Scholar 

  3. Singleton, R. C.: An Algorithm for Computing the Mixed Radix Fast Fourier Transform. IEEE Trans. Audio and Electroacoustics AU-17 (1969) 99–103.

    Google Scholar 

  4. Rader, C.: Discrete Fourier Transforms when the Number of Data Samples is Prime. Proc. IEEE 56 (1968) 1107–1108.

    Article  Google Scholar 

  5. Gold, B., and Rader, C. M.: Digital Processing of Signals. New York: McGraw-Hill, 1969.

    MATH  Google Scholar 

  6. Cooley, J. W. et al.: Historical Notes on the Fast Fourier Transform. Proc. IEEE 55 (1967) 1675–1677.

    Article  Google Scholar 

  7. Ohnsorg, F. R: The Tukey-Cooley Algorithm. Honeywell Inter-office Correspondence, MR-9959, 1967, Systems and Research Center, St. Paul Minn., 55113, USA.

    Google Scholar 

  8. Bergland, G. D.: A Guided Tour of the Fast Fourier Transform. IEEE Spectrum 6, July 1969, 41–52.

    Article  Google Scholar 

  9. Kaneko, T., and Liu, B.: Accumulation of Round-off Error in Fast Fourier Transforms. Journal of ACM 17 (1970) 637–654.

    Article  MathSciNet  MATH  Google Scholar 

  10. Cooley, J. W., Lewis, P. A. W., and Welch, P. D.: The Fast Fourier Transform and its Applications. IBM Research Report RC-1743, IBM Watson Research Center, Yorkstown, N. Y.

    Google Scholar 

  11. Brigham, E. O., and Morrow, R. E.: The Fast Fourier Transform. IEEE Spectrum 4, (1967) 63–70.

    Article  Google Scholar 

  12. Campbell, M. D., Houts, R. D., and Reinhard, E. A.: A Computer Utility Incorporating the FFT Algorithm for a Signal and System Theory Course. IEEE Trans. Education E-16 (1973) 42–47.

    Article  Google Scholar 

  13. Stoekham, Jr., T. G.: High Speed Convolution and Correlation. 1966 Spring Joint Computer Conference, AFIPS Proc., 1966, 229-233.

    Google Scholar 

  14. Jagadeesan, M.: n-Dimensional Fast Fourier Transform. Proc. Thirteenth Midwest Symposium on Circuit Theory, 1970, III.2.1-III.2.8.

    Google Scholar 

  15. Brenner, N. M.: Three Fortran Programs that Perform the Cooley-Tukey Fourier Transform. MIT Lincoln Lab. Publication AD 657019, 1967.

    Google Scholar 

  16. Fisher, J. R.: Fortran Program for Fast Fourier Transform. Naval Research Laboratory Report No. 7041, Washington, D.C., 1970.

    Google Scholar 

  17. Sande, G.: Arbitrary Radix One-dimensional Fast Fourier Transform Subroutines, University of Chicago, Illinois, 1968.

    Google Scholar 

  18. Bluestein, L. I.: Several Fourier Transform Algorithms. NEREM Record, 10, 1968, 218–219, published by the Boston section of the IEEE.

    Google Scholar 

  19. Ferrie, J. R., and Nuttall, A. H.: Comparison of Four Fast Fourier Transform Algorithms. Navy Underwater Systems Center, Newport, Rhode Island 02840, NUSC Report No. 4113, 1971.

    Google Scholar 

  20. Singleton, R. C.: A Short Bibliography on the Fast Fourier Transform. IEEE Trans. Audio and Electroacoustics AU-17 (1969) 166–169.

    Article  Google Scholar 

  21. Special Issues on Fast Fourier Transform. IEEE Trans. Audio and Electroacoustics AU-15, June 1967, and AU-17, June 1969.

    Google Scholar 

  22. Ahmed, N., and Cheng, S. M.: On Matrix Partitioning and a Class of Algorithms. IEEE Trans. Education E-13 (1970) 103–105.

    Article  Google Scholar 

  23. Theilheimer, F.: A Matrix Version of the Fast Fourier Transform. IEEE Trans. Audio and Electroacoustics AU-17 (1969) 158–161.

    Article  Google Scholar 

  24. Kahaner, D. K.: Matrix Description of the Fast Fourier Transform. IEEE Trans. Audio and Electroacoustics AU-18 (1970) 442–452.

    Article  Google Scholar 

  25. White Jr., Andrew, and Gray, Paul E.: Fast Fourier Transform: A Pragmatic Approach. Dept. of Electrical Engineering, North Carolina Agricultural and Technical State University, Greensboro, North Carolina, USA. Monograph EE-M-NO. 2, April 1973.

    Google Scholar 

  26. Brigham, E. O.: The Fast Fourier Transform. Englewood Cliffs, New Jersey: Prentice-Hall, 1974.

    MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Electrical Engineering, Kansas State University, Manhattan, Kansas, USA

    Nasir Ahmed (Associate Professor)

  2. Department of Electrical Engineering, University of Texas at Arlington, Arlington, Texas, USA

    Kamisetty Ramamohan Rao (Professor)

Authors
  1. Nasir Ahmed
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Kamisetty Ramamohan Rao
    View author publications

    You can also search for this author in PubMed Google Scholar

Rights and permissions

Reprints and permissions

Copyright information

© 1975 Springer-Verlag Berlin · Heidelberg

About this chapter

Cite this chapter

Ahmed, N., Rao, K.R. (1975). Fast Fourier Transform. In: Orthogonal Transforms for Digital Signal Processing. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-45450-9_4

Download citation

  • DOI: https://doi.org/10.1007/978-3-642-45450-9_4

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-642-45452-3

  • Online ISBN: 978-3-642-45450-9

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics

Search

Navigation