Hello! In our last lesson, we concluded our journey through the z-domain by examining the impulse invariance method, a technique that directly connects the analog s-plane to the digital z-plane. We saw how an analog pole at maps to a digital pole at , elegantly preserving system stability. This provided our first concrete method for designing a digital filter based on an analog prototype.
As previewed, we are now shifting our focus from the time and complex-frequency domains to the analysis of discrete-time signals directly in the frequency domain. The theoretical tool for this is the Discrete-Time Fourier Transform (DTFT), but its output is a continuous function of frequency, making it impossible to compute on a digital computer. We need a practical, computable equivalent: the Discrete Fourier Transform (DFT).
However, a direct computation of the DFT was, for a long time, prohibitively slow. The algorithm that unlocked its potential is the Fast Fourier Transform (FFT). This lesson is dedicated to the fascinating story behind this algorithm. Your appreciation for historical context will be well-served here, as the FFT's history is not a simple, linear progression but a compelling narrative of discovery, loss, and rediscovery, driven by some of the great scientific challenges of the last two centuries.
Our learning outcome for today is to trace the historical development of the Fast Fourier Transform (FFT) from Gauss to the Cooley-Tukey algorithm.
1. The Problem: A Transform in Search of Speed
Before the FFT, the DFT was a powerful theoretical tool with limited practical use. The reason was its computational complexity. To understand the context for the FFT's "re-discovery" in the 1960s, we first need to appreciate the problem it solved. The story is surprisingly tied to the geopolitics of the Cold War.
The Most Important Algorithm Of All Time
To understand the urgency behind the search for a faster transform, let's watch a segment from a Veritasium video. It masterfully sets the scene, explaining the high-stakes problem that drove researchers in the 1960s.
Please watch from 6:03 to 7:28. This section explains how scientists needed to use Fourier analysis on seismic signals to distinguish underground nuclear tests from natural earthquakes—a crucial capability for verifying a potential nuclear test ban treaty.
The challenge of distinguishing a bomb from an earthquake required analyzing the frequency content of a seismic signal. This meant computing a Fourier transform. For a discrete signal with samples, this is the DFT.
The direct calculation of the DFT requires on the order of complex multiplications and additions. We will explore the DFT formula in detail in the next lesson, but for now, the key takeaway is its complexity.
The Most Important Algorithm Of All Time
Let's continue with the Veritasium video to see why this N-squared complexity was such a bottleneck.
Now watch from 11:02 to 14:55. The video gives a conceptual overview of the DFT and powerfully illustrates the intractability of an N-squared algorithm for the large datasets required for seismic analysis in the 1960s.
As the video highlights, a transform of even a moderately large signal—say, a million samples—would have taken years on the computers of the day. This computational barrier rendered the DFT impractical for real-world, time-sensitive applications like nuclear test monitoring, creating a powerful incentive to find a better way.
Test your understanding!
Suppose a computer in 1963 can perform 10,000 complex multiplications per second. You are given a seismic signal with samples.
- Approximately how many multiplications are needed for a direct DFT, which has a complexity of ? How long would this take?
- The FFT has a complexity of approximately . How many multiplications would it require, and how long would that take?
Show answer
-
Direct DFT:
- Number of multiplications .
- Time seconds, or about 28 minutes.
-
FFT:
- Number of multiplications .
- Time seconds.
The speedup is dramatic ( times faster), and this ratio only grows as increases. This illustrates why the FFT was revolutionary.
2. The 1965 "Re-discovery": Cooley and Tukey
The breakthrough came in 1965 with a paper by James W. Cooley of IBM and John W. Tukey of Princeton University. They didn't invent a new transform; they published an exceptionally efficient algorithm to compute the existing DFT. The core of their method was a "divide and conquer" strategy that recursively breaks down a large transform into smaller, more manageable ones.
The story of how they came to collaborate is a piece of scientific history in itself, involving a presidential advisory committee, a somewhat boring meeting, and a brilliant insight. James Cooley himself recounted the events.
The Re-Discovery of the Fast Fourier Transform Algorithm
In this article, James Cooley gives his first-person account of how the modern FFT came to be. It's a fascinating look at the confluence of academic insight, industrial research, and government priorities.
Please read the section titled 'Richard Garwin's Role in the FFF' (pages 35-36). This short section describes how John Tukey's factorization idea was brought to Cooley by Richard Garwin, and the initial motivation (a cover story about Helium-3 crystals) versus the real motivation (seismic and acoustic monitoring).
Tukey's crucial insight was that if the number of data points is a composite number, say , the DFT can be re-expressed as a combination of smaller DFTs of size and . By applying this decomposition recursively, the computational complexity drops from to .
The publication of their 1965 paper, "An Algorithm for the Machine Calculation of Complex Fourier Series," is widely regarded as the starting point of the modern digital signal processing revolution.
3. Uncovering the Past: The Path Back to Gauss
The excitement around the Cooley-Tukey paper was immense, but it soon became clear that they were not the first to have this idea. The history of the FFT is a perfect example of how important ideas can be discovered, forgotten, and independently re-discovered when the time—and technology—is right.
Cooley himself began to learn of this history shortly after his paper was published.
The Re-Discovery of the Fast Fourier Transform Algorithm
Let's return to Cooley's article. He describes how he learned about the algorithm's precursors after his own publication.
Read the section titled 'The History of the FFT' (pages 41-43). Notice how Cooley traces the lineage back through L.H. Thomas (1948), Danielson and Lanczos (1942), and finally gets a reference to the work of Carl Friedrich Gauss.
As Cooley recounts, researchers like Danielson and Lanczos had developed a similar "doubling" algorithm in 1942 for use in X-ray crystallography. However, in the era of manual desk calculators, they saw it primarily as a way to do a 16-point transform from two 8-point transforms, not as a recursive process to be automated for arbitrarily large . The lack of high-speed computers meant its full potential wasn't appreciated.
The most astonishing discovery, however, was that the algorithm's true origin lay over a century earlier, with the legendary mathematician Carl Friedrich Gauss.
How the FFT Works | Part 1: The History Of The FFT
This short video provides a quick summary of Gauss's original work.
Please watch the first 2 minutes and 24 seconds. It explains how Gauss, while trying to determine the orbits of asteroids like Ceres, developed a divide-and-conquer method for trigonometric interpolation that was, in essence, an FFT.
Gauss's work in 1805 on the orbits of the asteroids Pallas and Juno led him to the problem of trigonometric interpolation. To solve it efficiently, he developed an algorithm that is mathematically equivalent to the Cooley-Tukey FFT. For a deep dive into this, we can turn to a detailed historical analysis.
Gauss and the history of the fast Fourier transform
This academic paper by Heideman, Johnson, and Burrus is the definitive investigation into Gauss's contribution. It provides the mathematical evidence connecting his work to the modern FFT.
This is a dense paper, so let's focus on the key parts. Read the section 'Gauss' Algorithm for Computing the DFT' (pages 269-271). You don't need to follow every detail of the Latin translation, but focus on the modern interpretation presented in Equation (4) and the authors' conclusion that it is 'exactly the FFT algorithm derived by COOLEY & TUKEY'. Then, read the 'Discussion' section (page 271) to understand the compelling reasons why Gauss's groundbreaking work remained obscure for over 150 years (published posthumously, in Latin, with unfamiliar notation).
The investigation is conclusive: Gauss had developed a fully general FFT algorithm in 1805, predating even Fourier's own work on harmonic series. However, he used it as a tool for a specific problem and never published it widely. It was written in Latin in his notebooks and only appeared in his collected works after his death, where it went largely unnoticed by the scientific community until the 1960s.
Conclusion
Today we've journeyed through more than 150 years of scientific history to uncover the origins of one of signal processing's most vital algorithms. We saw that while the FFT-fueled DSP revolution began in 1965, the seed of the idea was planted long before.
Key Takeaways:
- The FFT is a "re-discovered" algorithm. Its history is marked by independent discoveries separated by decades.
- The core concept is a "divide and conquer" strategy that reduces the DFT's computational complexity from an impractical to a highly efficient .
- The development and popularization of the algorithm have been driven by the pressing scientific needs of the day:
- Carl Friedrich Gauss (1805): Discovered it to aid in calculating asteroid orbits. His work was lost for 150 years.
- Danielson & Lanczos (1942): Used a similar method for X-ray crystallography, but its full potential was unappreciated in the pre-computer era.
- Cooley & Tukey (1965): Re-discovered and popularized the algorithm, motivated by Cold War needs like nuclear test monitoring, which finally provided the context for its power to be recognized.
Preview of the Next Lesson:
Now that we understand the history and importance of having an efficient algorithm, we are ready to formally define the Discrete Fourier Transform (DFT). In the next lesson, we will derive the DFT by sampling the DTFT spectrum. We will see precisely how the continuous spectrum of the DTFT becomes the discrete set of frequency samples that the DFT calculates, setting the stage for a deeper analysis of its properties and, eventually, a mathematical derivation of the FFT algorithm itself.