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.

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).1

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.



1. Vladimir Sukhoy and Alexander Stoytchev, Scientific Reports (2019);

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.

Sponsored Recommendations

Request a free Micro 3D Printed sample part

April 11, 2024
The best way to understand the part quality we can achieve is by seeing it first-hand. Request a free 3D printed high-precision sample part.

How to Tune Servo Systems: The Basics

April 10, 2024
Learn how to tune a servo system using frequency-based tools to meet system specifications by watching our webinar!

How Precision Motion Systems are Shaping the Future of Semiconductor Manufacturing

March 28, 2024
This article highlights the pivotal role precision motion systems play in supporting the latest semiconductor manufacturing trends.

Melles Griot® XPLAN™ CCG Lens Series

March 19, 2024
IDEX Health & Science sets a new standard with our Melles Griot® XPLAN™ CCG Lens Series fluorescence microscope imaging systems. Access superior-quality optics with off-the-shelf...

Voice your opinion!

To join the conversation, and become an exclusive member of Laser Focus World, create an account today!