The FFT: an algorithm the whole family can use
Author:
- 1 January 2000
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in Computing in Science & Engineering
- Vol. 2 (1) , 60-64
Abstract
The fast Fourier transform is one of the fundamental algorithm families in digital information processing. The author discusses its past, present, and future, along with its important role in our current digital revolution. It is concluded that the FFT is both parent and child of the digital revolution, a computational technique at the nexus of the worlds of business and entertainment, national security and public communication. Although it is anyone's guess as to what lies over the next horizon in digital signal processing, the FFT will most likely be in the thick of it.Keywords
This publication has 12 references indexed in Scilit:
- On the power of quantum computation2002
- Performing out-of-core FFTs on parallel disk systemsParallel Computing, 1998
- Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum ComputerSIAM Journal on Computing, 1997
- Fast Fourier Transforms for Nonequispaced DataSIAM Journal on Scientific Computing, 1993
- The re-discovery of the fast Fourier transform algorithmMicrochimica Acta, 1987
- Gauss and the history of the fast Fourier transformArchive for History of Exact Sciences, 1985
- Arithmetic Complexity of Computations1980
- On the algebraic structure of certain partially observable finite-state Markov processesInformation and Control, 1978
- An algorithm for the machine calculation of complex Fourier seriesMathematics of Computation, 1965
- Some improvements in practical Fourier analysis and their application to x-ray scattering from liquidsJournal of the Franklin Institute, 1942