Fast Fourier Transform

Photo : Virginia Konchan Michael Spleit is a PhD Candidate at Polytechnique School of Montréal in Applied Mathematics

Photo : Virginia Konchan

Michael Spleit is a PhD Candidate at Polytechnique School of Montréal in Applied Mathematics

by Michael Spleit
 

The Fast Fourier Transform (FFT) is an algorithm for computing the Discrete Fourier Transform (DFT), or its inverse. The FFT is one of the most important algorithms in existence for signal processing and data analysis, and yet its innovation is not in what it actually accomplishes, but in its recognition of symmetrical properties of the DFT that can be exploited to speed it up.

Image reuse with modification.

Image reuse with modification.

So the FFT is a “fast” version of the DFT – but what’s a DFT? A DFT takes a signal (a good example is a sound wave) and breaks it down into its frequency components. For example, in standard audio recording software on your computer, you see the signal represented with time on the x-axis, and amplitude on the y-axis. By calculating the DFT of that signal, you get the break-down of the intensity of each of a series of frequency bins. In the example below, the signal is mostly composed of one frequency, with a second less-intense higher-frequency component.  

Fig 1: Dicola, T. (2016). What is the Fourier transform?. [Blog] adafruit.com. Available at: https://learn.adafruit.com/fft-fun-with-fourier-transforms/background [Accessed 1 Feb. 2016].

Fig 1: Dicola, T. (2016). What is the Fourier transform?. [Blog] adafruit.com. Available at: https://learn.adafruit.com/fft-fun-with-fourier-transforms/background [Accessed 1 Feb. 2016].

The DFT is super useful for signal processing because often it is much easier to manipulate a signal in the frequency domain than in the time domain. Sticking with the idea of audio recording, imagine you have recorded yourself singing a song, but in the background of the recording you can hear your fridge humming at a low frequency. You want to clean up your recording and get rid of that hum, but doing so in the time-domain would be near impossible. You may realize that what you want here is to apply a high-pass filter: you want to specify a cut-off frequency and supress sound below that cut-off. Using a DFT to convert the recording to the frequency domain, the information in the lowest frequency bins can be discarded and then the signal inverted back to the time domain. 

Among other applications, DFTs can be used for data compression by discarding the less noticeable frequencies, for audio processing by detecting specific frequencies and altering or removing them, radar by detecting how a shift in frequency of a reflected signal relates to distance traveled and the speed of an object. 

The problem with the DFT, however, is that it is very slow to actually calculate. In contrast, the FFT was revolutionary when Cooley and Tukey published their paper in 1965: it made a whole new world of digital processing possible by increasing the power of Fourier methods by several orders of magnitude. 

In 1963, Cooley was working at IBM when he was approached by Richard Garwin, a researcher at Columbia University. Garwin was interested in doing remote seismic monitoring of nuclear explosions. At that time, the Russians would not agree to inspections within their borders, so it was difficult to enforce a nuclear test ban treaty that was desired. In trying to address this problem, he spoke with John Tukey during a meeting of a committee of which they were both members and Tukey had shown him a way of reducing the number of calculations needed for a Fourier transform. Garwin brought this fundamental insight to Cooley and asked him to flesh it out further. Cooley was able to further exploit symmetries in the problem to reduce the number of needed calculations, and implemented it in a computer program that could run efficiently. 

As it was later discovered, the basic algorithm proposed by Cooley had already been discovered in 1866 by the famous German mathematician Gauss. Historians found a host of others who wrote of FFT methods between Gauss and the Cooley-Tukey publication, but for those ~150 years, its importance was not recognized. This story of the FFT teaches us to not just investigate new and novel approaches, but to occasionally look over old papers with tricks and clever ideas that were used when computing was not as ubiquitous and powerful as it is today. Re-imagining these ideas with the new technologies of today can unlock new possibilities.


References

C.F. Gauss, Nachlafl: Theoria interpolationis methodo nova traetata (Carl Friedrich Gauss, Werke, Band 3), K6nigliche Gesellschaft der Wissenschafte.n, G6ttingen, 1866, pp. 265—303

Dicola, T. (2016). What is the Fourier transform?. [Blog] adafruit.com. Available at: https://learn.adafruit.com/fft-fun-with-fourier-transforms/background [Accessed 1 Feb. 2016].

Wooley, J. The Re-Discovery of the Fast Fourier Transform Algorithm, Mikrochim. Acta [Wien] 1987, III, 33-45.