The 60-Year Old Algorithm Underlying Today’s Tech

CT scanning, streaming videos, and sending images over the Internet wouldn't be possible without the Fast Fourier transform. Commonly known as FFT, the computer algorithm designed by researchers at Princeton University and IBM is found in just about every electronic device, according to an entry in the Engineering and Technology History Wiki.

Demonstrated for the first time in 1964 by IEEE Fellows John Tukey and James W. Cooley, the algorithm breaks down a signal-a series of values over time-and converts it into frequencies. FFT was 100 times faster than the existing discrete Fourier transform. The DFT also requires more memory than the FFT because it saves intermediate results while processing.

The FFT has become an important tool for manipulating and analyzing signals in many areas including audio processing, telecommunications, digital broadcasting, and image analysis. It helps filter, compress, eliminate noise from, and otherwise modify signals.

The 60-year-old ubiquitous computer code also has applications in today's cutting-edge technologies such as AI, quantum computing, self-driving cars, and 5G communication systems.

The FFT was commemorated with an IEEE Milestone during a ceremony held in May at Princeton University.

The Cooley-Tukey algorithm significantly accelerated the calculation of DFTs," 2024 IEEE President Tom Coughlin said at the ceremony. Prior methods required significantly more computations, making FFT a revolutionary breakthrough. By leveraging algebraic properties and periodicities, the FFT reduced the number of the operations, making it particularly and practically feasible for everyday tasks, replacing the less efficient analog methods."

A new mathematical tool

In 1963 Tukey, a professor of mathematics and statistics at Princeton, participated in a meeting of U.S. President John F. Kennedy's Science Advisory Committee to discuss ways to detect underground nuclear tests, according to the ETHW entry.

Also attending that meeting was Richard Garwin, a physicist and engineer at IBM who played a key role in designing the first hydrogen bomb. He died in May. Read about his fascinating life in this month's In Memoriam.

Tukey told Garwin he was working on speeding up the computation of an existing method-the Fourier transform-thinking it might help with the detection. His algorithm mathematically converted a signal from its original domain, such as time or space, to a frequency domain.

Garwin recognized its potential and asked IBM to select a mathematical analyst to collaborate with Tukey. That person was Cooley, a research staff member working on numerical analysis and computation projects.

If the Fourier transform could be made faster, Garwin said, seismometers could be planted in the ground in countries surrounding the Soviet Union to detect nuclear explosions from atomic bomb tests, because the Soviets wouldn't allow on-site tests, according to Cooley's oral history in the Engineering and Technology History Wiki. A seismometer measures ground vibrations, which are converted into electrical signals and recorded as seismograms.

To design sensors for underground nuclear tests, however, you would have to process all the seismic signals, and a large part of the processing could be done by Fourier transforms," Cooley said in his oral history. But the computing power at the time was not enough to process all of the signals you'd need to do this."

The FFT could calculate a seismic sensor's frequency and produce images, IEEE Life Fellow Harold S. Stone said at the Milestone event. He is an image processing researcher and Fellow emeritus at the NEC Laboratories America, in Princeton, and a former IBM researcher.

Tukey and Cooley led the team that wrote the computer code that demonstrated the FFT's power.

The demonstration of the Coley-Tukey algorithm showed that it was 100 times faster," Stone said. It was so fast that it could keep up with the seismic data."

Sensors using the algorithm were planted, and they detected nuclear explosions within a 15-kilometer radius from where they were detonated, according to the ETHW entry.

By leveraging algebraic properties and periodicities, the FFT reduced the number of the operations, making it particularly and practically feasible for everyday tasks, replacing the less efficient analog methods." -2024 IEEE President Tom Coughlin

In 1965 Cooley and Tukey published An Algorithm for the Machine Calculation of Complex Fourier Series," describing the FFT process. The seminal paper spurred development of digital signal processing technologies.

For his work, Tukey was awarded a U.S. National Medal of Science in 1973. He also received the 1982 IEEE Medal of Honor for contributions to the spectral analysis of random processes and the fast Fourier transform algorithm."

Cooley, who received the 2002 IEEE Kilby Signal Processing Medal for pioneering the FFT, was a leading figure in the field of digital signal processing. Through his involvement with the IEEE Digital Signal Processing Committee (today known as the IEEE Signal Processing Society), he helped establish terminology and suggested research directions.

Although not one of the inventors, Garwin is credited with recognizing that the algorithm had wider applications, especially in scientific and engineering fields.

In today's lingo, Garwin helped the FFT go viral' by getting Cooley and Tukey together," Stone said.

Garwin and Tukey sought better information to forestall and prevent wars," added Frank Anscombe, Tukey's nephew. The Cooley-Tukey FFT swiftly advanced this cause by giving a practical, simplifying solution for wavy data. Thanks to the FFT, a technological rubicon began to be crossed: analog-to-digital machines."

A spirit of collaboration between academia and industry

Like so many innovations, the FFT came out of a collaboration between industry and academia, and it should be recognized for that, IEEE Fellow Andrea Goldsmith said at the ceremony. She explained that she regularly works with FFT in her research projects. At the time of the event, she was Princeton's dean of engineering and applied sciences. This month she started her new position as president of Stony Brook University, in New York.

Taking the ideas we have from basic research in our university labs, talking to people in industry, and understanding how the research problems we work on can benefit industry either tomorrow or in five years or 20 years from now, is incredibly important," she said. Some people think of engineering as boring and dry and something that only nerds do, but there is such beauty and creativity in a lot of the innovations that we have developed, and I think the FFT is a perfect example of that."

The FFT joins more than 270 other IEEE Milestones. They are more than a marker of achievement, said IEEE Life Senior Member Bala S. Prasanna, director of IEEE Region 1.

They are a testament to human ingenuity, perseverance, and the spirit of collaboration," Prasanna said. These Milestones were more than just breakthroughs; they became catalysts for innovation, enabling progress in ways once thought impossible. Each one ensures that the story behind these innovations is preserved, not just as history but as inspiration for future generations."

Another ceremony was held on 11 June at the IBM Watson Research Center.

Milestone plaques recognizing the FFT are on display in the lobby of Princeton's School of Engineering and Applied Science and in the main lobby at the entrance of the IBM research center.

They read:

In 1964 a computer program implementing a highly efficient Fourier analysis algorithm was demonstrated at IBM Research. Jointly developed by Princeton University and IBM collaborators, the Cooley-Tukey technique calculated discrete Fourier transforms orders of magnitude faster than had been previously demonstrated. Known as the Fast Fourier Transform (FFT), its speed impacted numerous applications including computerized tomography, audio and video compression, signal processing, and real-time data streaming."

Administered by the IEEE History Center and supported by donors, the Milestone program recognizes outstanding technical developments around the world. The IEEE Princeton Central Jersey Section sponsored the nomination.