Fast Fourier Transform – 60 years old

Fast Fourier transform (FFT), since the advent of the Cooley – Tukey algorithm, has occupied its important niche in the vast information and technical space of modern implementations. In general, assessing the importance and influence of the Cooley – Tukey algorithm on the development of various fields of science is an incredibly difficult task. The publication considers the prerequisites and historical formation of the Cooley – Tukey algorithm as a fundamental algorithm of the fast Fourier transform. The development of FFT research in the direction of developing effective algorithms for harmonic analysis, which led to significant results confirmed by numerous publications, is considered. The main directions of FFT formalization are highlighted and the multivariate nature of effective calculations is emphasized. The importance of the complementary influence of FFT on the formation of high-performance computing hardware is noted. After all, it is the development of new methods and technical capabilities for accelerating the execution of FFT that determined the architectural features of modern microprocessors as highly efficient means of implementing calculations. It is noted that the development of software has made it possible to create reliable and very fast software systems for performing Fourier transforms on various computer platforms and digital signal processors. The publication reviews the development of key aspects of FFT in the world practice of signal processing and the development of FFT tools by Lviv research institutions over the sixtieth anniversary of the Cooley – Tukey algorithm. In the OKB EIVT LPI, even before the advent of the fast Cooley – Tukey algorithm for calculating the Fourier transform, digital spectrum analyzers began to be developed. The result of the developments in 1983–1984 was the release of serial spectrum analyzers (approximately 200 samples) with parameters that exceeded the analyzers of the world-famous company “Bruel&Kjaer” (Denmark). The FFT tools developed at the Lviv Research Radio Engineering Institute and the Institute of Physics and Mechanics of the National Academy of Sciences of Ukraine have made it possible to successfully use them for radar stations, scientific space research, and others. Despite the analyses of the significance of FFTs, new theoretical results are still emerging, progress in computers and hardware is constantly renewing the main tasks of using FFTs, and new Fourier transform programs are opening up new areas for applied research.