# Algorithms for Optics: Generalized version of the inverse fast Fourier transform is computationally efficient

Nov. 19, 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 imageits inverse is straightforwardly called the inverse Fourier transform. Both of these operations 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.

In the example mentioned above of the close relation between a set of data and its Fourier transform, the line-spread function, which for a given lens is the cross-sectional intensity trace of the lens’ image of an infinitely thin bright straight line on a dark background, can be Fourier-transformed to produce the 1D modulation-transfer function (MTF), which is a plot that shows the ability of the lens to image spatial frequencies from zero on up.

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 (see figure). This last point is important, as it can allow calculations to be done for near-field optical propagation that relies 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) complexity, which matches the computational complexity of the existing CZT and IFFT algorithmsin other words, it is not more computationally complex, unlike earlier attempts to generalize the ICZT algorithm.

REFERENCE

1. V. Sukhoy and A. Stoytchev, Sci. Rep.(2019); https://doi.org/10.1038/s41598-019-50234-9.

### 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.

### 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.

### Motion Scan and Data Collection Methods for Electro-Optic System Testing

April 10, 2024
Learn how different scanning patterns and approaches can be used in measuring an electro-optic sensor performance, by reading our whitepaper here!

### Case Study: Medical Tube Laser Processing

March 28, 2024
To enhance their cardiovascular stent’s precision, optimize throughput and elevate part quality, a renowned manufacturer of medical products embarked on a mission to fabricate...

### 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...