Fast Fourier Transforms

By David Herres

A previous article discussed the Fourier Transform. Now we turn to a variation, the Fast Fourier Transform (FFT), which has assumed great importance since it emerged in 1965, based largely on early nineteenth-century work. To review, the Fourier Transform provides a theoretical basis for moving back and forth between time-domain and frequency-domain views of moving matter and energy. The only problem was that as originally formulated, this methodology was not accessible for most purposes because the mathematics was far too complex.

An FFT rapidly computes such transformations by factorizing the discrete Fourier transform (DFT) matrix into a product of sparse (mostly zero) factors. But there are several ways to compute FFTs. Different FFT algorithms are applicable in a wide range of mathematical operations including basic complex numeration, group theory, number theory and beyond. Using FFTs, we come up with precisely the same results as in the Fourier Transform, the only difference being that it is much faster. A modern mixed-domain oscilloscope such as the Tektronix MDO3104 can move easily from the time domain view of an electrical signal to a frequency domain graphical representation simply by a push of the button or from a remote computer, a click of the mouse.

Interestingly, distortions may be introduced while rounding off within the conventional Fourier Transform protocol. So the FFT is actually more accurate than its old-world ancestor.
Though there are numerous FFT algorithms that all involve different operating principles, the bottom line is that they all  have the ability to vastly simplify and speed up the two-way process of translating between time and frequency domains.

The principal FFT algorithm is the Cooley-Tukey protocol. This decisive breakthrough, which happened in 1965, resembled a discovery attributed to Carl Friedrich Gauss around 1805. But Gauss’ insight had never been broadly applied, so the Cooley-Tukey innovation constituted the decisive development that let oscilloscope signal analysis move forward in a meaningful way.

Wikipedia has a page devoted to the FFT which goes into the Cooley-Tukey method. To summarize the approach, it s is a divide-and-conquer algorithm that recursively divides a DFT of any size N = N1N2 into many smaller DFTs of sizes N1 and N2, along with on the order N multiplications by complex roots of unity.

The best known use of the Cooley–Tukey algorithm is to divide the transform into two pieces of size N/2 at each step. Also, because the Cooley–Tukey algorithm breaks the DFT into smaller pieces, it can be combined with any other of the many algorithms for the DFT.

FFTs are subject to ongoing efforts aimed at further simplification and acceleration. Areas for future exploration include fully functional artificial intelligence. To this end, it is possible that Fourier analysis along with the FFT implementation will provide the basis for an eventual accommodation with some of the more turbulent aspects of our destiny in our personal time and frequency domains.