Researchers develop a more versatile, generalized version of the inverse fast Fourier transform

Oct. 11, 2019

The fast Fourier transform (FFT) and IFFT are key to many photonics-related algorithms; now, they are more useful than ever.

John Wallace

Vladimir Sukhoy (left) and Alexander Stoytchev (right), with the derivation for the ICZT algorithm in structured matrix notation -- the answer to a 50-year-old puzzle in signal processing.

The Fourier Transform is a mathematical operation that allows one to determine, for example, the spatial-frequency components of an image; it's inverse is straightforwardly called the inverse Fourier transform. Both of these are fundamental to optics and photonics. The fast Fourier transform (FFT), an algorithm that implements the Fourier transform in practical form, and its inverse algorithm, the IFFT, are used in myriad applications, from image compression to fiber-optic encoding, wavefront sensing, optical spectrum analysis, interferogram analysis, vibration control, spectroscopy, and many more.

The FFT algorithm was published in 1965; four years later, researchers developed a more versatile, generalized version called the chirp z-transform (CZT), but a similar generalization of the IFFT algorithm has gone unsolved for 50 years. Now, Alexander Stoytchev and Vladimir Sukhoy, two researchers at Iowa State University (Ames, IA), have come up with the long-sought algorithm, called the inverse chirp z-transform (ICZT).¹

Like all algorithms, the ICZT is a step-by-step process that solves a problem. In this case, it maps the output of the CZT algorithm back to its input. The algorithm matches the computational complexity or speed of its counterpart, has been tested for numerical accuracy, and, unlike the IFFT, can be used with exponentially decaying or growing frequency components (this last point is important, as it allows calculations to be done for near-field optics that rely on evanescent electromagnetic waves).

Sukhoy says that the inverse algorithm is a harder problem than the original, forward algorithm and so “we needed better precision and more powerful computers to attack it.” He also says a key was seeing the algorithm within the mathematical framework of structured matrices. The accuracy of the ICZT algorithm was determined via automated testing.

The newly developed ICZT algorithm has so-called O(n log n) compexity, which matches the computational complexity of the existing CZT and IFFT algorithms -- in other words, it is not more computationally complex, unlike earlier attempts to generalize the ICZT algorithm.

Source: https://www.news.iastate.edu/news/2019/10/10/signalprocessing

REFERENCE

1. Vladimir Sukhoy and Alexander Stoytchev, Scientific Reports (2019); https://doi.org/10.1038/s41598-019-50234-9

Got optics- and photonics-related news to share with us? Contact John Wallace, Senior Editor, Laser Focus World

About the Author

John Wallace | Senior Technical Editor (1998-2022)

John Wallace was with Laser Focus World for nearly 25 years, retiring in late June 2022. He obtained a bachelor's degree in mechanical engineering and physics at Rutgers University and a master's in optical engineering at the University of Rochester. Before becoming an editor, John worked as an engineer at RCA, Exxon, Eastman Kodak, and GCA Corporation.