• DocumentCode
    1190489
  • Title

    A High-Speed Algorithm for the Computer Generation of Fourier Transforms

  • Author

    Andrews, Harry

  • Issue
    4
  • fYear
    1968
  • fDate
    4/1/1968 12:00:00 AM
  • Firstpage
    373
  • Lastpage
    375
  • Abstract
    Abstract—An efficient algorithm is presented for performing the Fourier transformation operation on a digital computer. This algorithm completes the transform calculation with Nlog2N complex additions (complex additions include complex subtractions) and ½N [log2(N)-2]+1 complex multiplications. This is a considerable savings over a brute-force method of N2complex additions and multiplications, especially when considering the use of digital machines whose MULTIPLY time is much longer than ADD time.
  • Keywords
    Index terms—Fast Fourier transform algorithm, Fourier transforms, spectral analysis.; Equations; Fourier series; Fourier transforms; NASA; Spectral analysis; Index terms—Fast Fourier transform algorithm, Fourier transforms, spectral analysis.;
  • fLanguage
    English
  • Journal_Title
    Computers, IEEE Transactions on
  • Publisher
    ieee
  • ISSN
    0018-9340
  • Type

    jour

  • DOI
    10.1109/TC.1968.229396
  • Filename
    1687348
    • Link To Document
    https://search.isc.ac/dl/search/defaultta.aspx?DTC=49&DC=1190489