{"id":88030,"date":"2025-08-22T06:03:31","date_gmt":"2025-08-22T06:03:31","guid":{"rendered":"https:\/\/www.newsbeep.com\/ca\/88030\/"},"modified":"2025-08-22T06:03:31","modified_gmt":"2025-08-22T06:03:31","slug":"fft-the-60-year-old-algorithm-underlying-todays-tech","status":"publish","type":"post","link":"https:\/\/www.newsbeep.com\/ca\/88030\/","title":{"rendered":"FFT: The 60-Year Old Algorithm Underlying Today\u2019s Tech"},"content":{"rendered":"

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

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

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

The 60-year-old ubiquitous computer code also has applications in today\u2019s cutting-edge technologies such as AI<\/a>, quantum computing<\/a>, self-driving cars<\/a>, and 5G<\/a> communication systems.<\/p>\n

The FFT was commemorated with an IEEE Milestone<\/a> during a ceremony held in May at Princeton University<\/a>.<\/p>\n

\u201cThe Cooley-Tukey algorithm significantly accelerated the calculation of DFTs,\u201d 2024 IEEE President<\/a> Tom Coughlin<\/a> said at the ceremony. \u201cPrior 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.\u201d<\/p>\n

A new mathematical tool<\/p>\n

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

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

Tukey told Garwin he was working on speeding up the computation of an existing method\u2014the Fourier transform\u2014thinking 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<\/a>.<\/p>\n

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

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

To design sensors for underground nuclear tests, however, \u201cyou would have to process all the seismic<\/a> signals, and a large part of the processing could be done by Fourier transforms,\u201d Cooley said in his oral history. But \u201cthe computing power at the time was not enough to process all of the signals you\u2019d need to do this.\u201d<\/p>\n

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

Tukey and Cooley led the team that wrote the computer code that demonstrated the FFT\u2019s power.<\/p>\n

\u201cThe demonstration of the Coley-Tukey algorithm showed that it was 100 times faster,\u201d Stone said. \u201cIt was so fast that it could keep up with the seismic data.\u201d<\/p>\n

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.<\/p>\n

\u201cBy 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.\u201d \u20142024 IEEE President Tom Coughlin<\/p>\n

In 1965 Cooley and Tukey published \u201cAn Algorithm for the Machine Calculation of Complex Fourier Series<\/a>,\u201d describing the FFT process. The seminal paper spurred development of digital signal processing<\/a> technologies.<\/p>\n

For his work, Tukey was awarded a U.S. National Medal of Science<\/a> in 1973. He also received the 1982 IEEE Medal of Honor<\/a> for \u201ccontributions to the spectral analysis of random processes and the fast Fourier transform algorithm.\u201d<\/p>\n

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

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

\u201cIn today\u2019s lingo, Garwin helped the FFT \u2018go viral\u2019 by getting Cooley and Tukey together,\u201d Stone said.<\/p>\n

\u201cGarwin and Tukey sought better information to forestall and prevent wars,\u201d added Frank Anscombe, Tukey\u2019s nephew. \u201cThe 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.\u201d<\/p>\n

A spirit of collaboration between academia and industry<\/p>\n

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<\/a> 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\u2019s dean of engineering and applied sciences. This month she started her new position as president of Stony Brook University<\/a>, in New York.<\/p>\n

\u201cTaking 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,\u201d she said. \u201cSome 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.\u201d<\/p>\n

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<\/a>, director of IEEE Region 1<\/a>.<\/p>\n

\u201cThey are a testament to human ingenuity, perseverance, and the spirit of collaboration,\u201d Prasanna said. \u201cThese 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.\u201d<\/p>\n

Another ceremony<\/a> was held on 11 June at the IBM Watson<\/a> Research Center. <\/p>\n

Milestone plaques recognizing the FFT are on display in the lobby of Princeton\u2019s School of Engineering and Applied Science<\/a> and in the main lobby at the entrance of the IBM research<\/a> center.<\/p>\n

They read:<\/p>\n

\u201cIn 1964 a computer program implementing a highly efficient Fourier analysis<\/a> 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<\/a>, audio and video compression<\/a>, signal processing, and real-time data streaming.\u201d<\/p>\n

Administered by the IEEE History Center<\/a> and supported by donors<\/a>, the Milestone program recognizes outstanding technical developments around the world. The IEEE Princeton Central Jersey Section<\/a> sponsored the nomination.<\/p>\n

From Your Site Articles<\/p>\n

Related Articles Around the Web<\/p>\n","protected":false},"excerpt":{"rendered":"CT scanning, streaming videos, and sending images over the Internet wouldn\u2019t be possible without the Fast Fourier transform.…\n","protected":false},"author":2,"featured_media":88031,"comment_status":"","ping_status":"","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[21],"tags":[49,48,285,52143,12159,52144,52145,61,52146],"class_list":{"0":"post-88030","1":"post","2":"type-post","3":"status-publish","4":"format-standard","5":"has-post-thumbnail","7":"category-computing","8":"tag-ca","9":"tag-canada","10":"tag-computing","11":"tag-fast-fourier-transform","12":"tag-ibm","13":"tag-ieee-history","14":"tag-princeton","15":"tag-technology","16":"tag-typeti"},"_links":{"self":[{"href":"https:\/\/www.newsbeep.com\/ca\/wp-json\/wp\/v2\/posts\/88030","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.newsbeep.com\/ca\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.newsbeep.com\/ca\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.newsbeep.com\/ca\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/www.newsbeep.com\/ca\/wp-json\/wp\/v2\/comments?post=88030"}],"version-history":[{"count":0,"href":"https:\/\/www.newsbeep.com\/ca\/wp-json\/wp\/v2\/posts\/88030\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.newsbeep.com\/ca\/wp-json\/wp\/v2\/media\/88031"}],"wp:attachment":[{"href":"https:\/\/www.newsbeep.com\/ca\/wp-json\/wp\/v2\/media?parent=88030"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.newsbeep.com\/ca\/wp-json\/wp\/v2\/categories?post=88030"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.newsbeep.com\/ca\/wp-json\/wp\/v2\/tags?post=88030"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}