ACM Portal
  Subscribe (Full Service)    Register (Limited Service, Free)    Login
  Search:   The ACM Digital Library   The Guide
  
ACM Home Page
Please provide us with feedback. Feedback
Algorithms: Algorithm 338: algol procedures for the fast Fourier transform
Full text PdfPdf (942 KB)
Source
Communications of the ACM archive
Volume 11 ,  Issue 11  (November 1968) table of contents
Pages: 773 - 776  
Year of Publication: 1968
ISSN:0001-0782
Author
Richard C. Singleton  Stanford Research Institute, Menlo Park, CA
Publisher
ACM  New York, NY, USA
Bibliometrics
Downloads (6 Weeks): 1,   Downloads (12 Months): 26,   Citation Count: 4
Additional Information:

abstract   references   cited by   index terms   collaborative colleagues  

Tools and Actions: Request Permissions Request Permissions    Review this Article  
DOI Bookmark: Use this link to bookmark this Article: http://doi.acm.org/10.1145/364139.364167
What is a DOI?

ABSTRACT

The following procedures are based on the Cooley-Tukey algorithm [1] for computing the finite Fourier transform of a complex data vector; the dimension of the data vector is assumed here to be a power of two. Procedure COMPLEXTRANSFORM computes either the complex Fourier transform or its inverse. Procedure REALTRANSFORM computes either the Fourier coefficients of a sequence of real data points or evaluates a Fourier series with given cosine and sine coefficients. The number of arithmetic operations for either procedure is proportional to n log2 n, where n is the number of data points.


REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

 
1
COOLEY, J. W., and TUKEY, J. W. An algorithm for the machine calculation of complex Fourier series. Math. Comput. 19, 90, (Apr. 1965), 297-301.
2
Richard C. Singleton, On computing the fast Fourier transform, Communications of the ACM, v.10 n.10, p.647-654, Oct. 1967  [doi>10.1145/363717.363771]

CITED BY  4
J. Morris, ACM Algorithm 346: F-Test Probabilities, Communications of the ACM, v.12 n.3, p.184-185, March 1969
Richard C. Singleton, Remark on algorithm 339 [C6]: an algol procedure for the fast Fourier transform with arbitrary factors, Communications of the ACM, v.12 n.3, p.187, March 1969
Richard C. Singleton, Algorithms: Algorithm 339: an algol procedure for the fast Fourier transform with arbitrary factors, Communications of the ACM, v.11 n.11, p.776-779, Nov. 68
Richard C. Singleton, Algorithm 345: an algol convolution procedure based on the fast Fourier transform [C6], Communications of the ACM, v.12 n.3, p.179-184, March 1969

INDEX TERMS

Keywords:
Fourier series, complex Fourier transform, fast Fourier transform, harmonic analysis, multivariate Fourier transform, orthogonal polynomials, orthogonal transformation, permutation, spectral analysis, virtual core memory

Collaborative Colleagues:
Richard C. Singleton: colleagues

The ACM Portal is published by the Association for Computing Machinery. Copyright © 2009 ACM, Inc.
Terms of Usage   Privacy Policy   Code of Ethics   Contact Us

Useful downloads: Adobe Acrobat    QuickTime    Windows Media Player    Real Player