THE FAST FOURIER TRANSFORM.
STANFORD RESEARCH INST MENLO PARK CALIF
Pagination or Media Count:
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 jkN 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 N2. 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
- Theoretical Mathematics