It was around two centuries ago, when eminent mathematician Joseph Fourier demonstrated that some functions could be represented as an infinite sum of harmonics. Named the Fourier series in his honour, this technique was employed thereafter on other mathematical functions as well. Over the decades, these functions have been discretized, and methods such as FFTs (Fast Fourier Transforms) have been developed, and used to quickly find their Fourier transforms.
Naturally, the question that pops to mind is this – what are Fourier transforms, and how do they concern us?
Fourier Transforms – what are they?
In layman terms, it is simply a way of representing a given signal in the form of sinusoidal waves – the kind of waves scientists and engineers encounter on an almost daily basis.
At first, it might not appear to be very useful. After all, Fourier transforms merely convert signals from the time domain into components in the frequency domain. Is there any point in performing any more computations on a given signal, that is already defined in the time domain?
However, given that all real-world signals are prone to noise, it becomes essential to find a simple representation of such signals. As it turns out, Fourier transformations help accomplish that.
This GIF explains the concept more clearly, showing how a complex signal may be analyzed on the basis of its frequencies, thanks to the Fourier transform:
This signal is still a relatively simple one. Once signals become more complex, calculating their Fourier transforms becomes a tedious process. To simplify these calculations, DFTs (Discrete Fourier Transforms) are used in place of regular Fourier transforms – more specifically, N-point DFTs.
DFTs and FFTs
Here is the formula for an N-point DFT:
Despite the merits this method had to offer, DFTs were still found to be computationally intensive. Hence, to reduce the calculation time, James Cooley and John Tukey proposed a new technique in their research paper titled “An Algorithm for the Machine Calculation of Complex Fourier Series”, in 1965.
Although the main motive behind the Cooley-Tukey algorithm was to locate nuclear explosions in the Soviet Union through sensors planted in surrounding countries, it soon began to be used in all electronic devices in general. In fact, it is the most commonly used method to calculate FFTs even today.
The Butterfly Structure
The Cooley-Tukey algorithm makes use of a ‘butterfly structure’, in which the ‘butterfly’ is the basic computational element of the FFT, that converts two complex points into two other complex points. Here is what it looks like:
This structure helps visualize the working of the FFT. It explains the reduction in number of computations, right from the N2 multiplications and N(N-1) additions in an N-point DFT, to (N/2)log2N multiplications and Nlog2N additions in an N-point radix-2 FFT.
Because of their ability to convert complex information into data of a much smaller size, along with being reversible (through Inverse Fast Fourier Transforms, or IFFTs), FFTs are widely used by modern-day devices process large amounts of data, especially in audio(mp3), video (mp4), and image(JPEG) files. Moreover, they are used in almost all communication protocols in use today, such as Ethernet, Wi-Fi, 4G, Bluetooth etcetera, because of their ability to convert analog information into digital data, and vice versa.
Hence, we cannot deny the importance of FFTs in our daily lives. With more appliances and electronic devices turning into ‘smart’ devices, we can only expect the implementation of FFTs to become more commonplace. In fact, you would not have read this article, had it not been for the Cooley-Tukey algorithm scrambling and unscrambling the information bits comprising this blog post!
- The Fourier Transform; a website:
- An Algorithm for the Machine Calculation of Complex Fourier Series; the original paper by James W. Cooley and John W. Tukey:
- Computing FFT Twiddle Factors; an article:
- Cooley-Tukey FFT algorithm; an article:
- How the FFT Works; an article:
- Fourier analysis and applications to sound processing; a PDF with MATLAB examples:
- FFT; an old article:
- Amateur-radio Applications of Fast Fourier Transform; an old PDF: