THE FAST FOURIER TRANSFORM.
Abstract
Good has proposed a fast algorithm for computing the complex Fourier transform x sub j = sum from k = o to N-1 of alpha sub k exp (i2 ps jk/N) for j = 0,1,... N-1, and Cooley and Tukey have restated the algorithm and reported major time savings in using it to compute large transforms on a digital computer. With N an integer power of two, computing time for this algorithm is proportional to N log2 N, a major improvement over other methods with computing time proportional to N(2). In this paper, the fast Fourier transform algorithm is discussed, and ALGOL procedures given for the basic method plus some of its variations. ALGOL procedures organized for efficient computing on a system with a virtual memory feature are given; these procedures reduce the need for moving portions of data arrays to and from high speed memory. A method for solving very large problems by use of auxiliary memory is also proposed. Methods of using the fast Fourier transform algorithm on real data are restated, and a way of reducing computing in this case is shown. A plan of scaling for computing the fast transform with fixed-point arithmetic is outlined; this method has been used on a small computer without floating-point hardware. (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- Dec 01, 1966
- Accession Number
- AD0643998
Entities
People
- Richard C. Singleton
Organizations
- SRI International