AN ALGOL PROCEDURE FOR THE FAST FOURIER TRANSFORM WITH ARBITRARY FACTORS.
Abstract
The report consists of an ALGOL procedure with comments. This procedure computes the finite Fourier transform of an n-dimensional complex data vector, using a fast Fourier transform algorithm based on a method proposed by Cooley and Tukey. The dimension n is decomposed into its factors n = n sub 1 . n sub 2 . ... n sub m, and the transform is done in m steps, with n/n sub i transforms of dimension n sub i computed at the i(th) step. Except when n is a prime, the amount of computing is considerably less than for a single transform of dimension n. (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- Dec 01, 1966
- Accession Number
- AD0643997
Entities
People
- Richard C. Singleton
Organizations
- SRI International