A Generalization of the Fast Fourier Transform
- 1 February 1970
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers
- Vol. C-19 (2), 105-116
- https://doi.org/10.1109/t-c.1970.222875
Abstract
A procedure for factoring of the N×N matrix representing the discrete Fourier transform is presented which does not produce shuffled data. Exactly one factor is produced for each factor of N, resulting in a fast Fourier transform valid for any N. The factoring algorithm enables the fast Fourier transform to be implemented in general with four nested loops, and with three loops if N is a power of two. No special logical organization, such as binary indexing, is required to unshuffle data. Included are two sample programs, one which writes the equations of the matrix factors employing the four key loops, and one which implements the algorithm in a fast Fourier transform for N a power of two. The algorithm is shown to be most efficient for Na power of two.Keywords
This publication has 8 references indexed in Scilit:
- Algorithm 338: algol procedures for the fast Fourier transformCommunications of the ACM, 1968
- Use of a Digital Convolution Device to Perform Recursive Filtering and the Cooley-Tukey AlgorithmIEEE Transactions on Computers, 1968
- An Adaptation of the Fast Fourier Transform for Parallel ProcessingJournal of the ACM, 1968
- The fast Fourier transformIEEE Spectrum, 1967
- Historical notes on the fast Fourier transformProceedings of the IEEE, 1967
- What is the fast Fourier transform?Proceedings of the IEEE, 1967
- Fast Fourier TransformsPublished by Association for Computing Machinery (ACM) ,1966
- An algorithm for the machine calculation of complex Fourier seriesMathematics of Computation, 1965