The Fourier transform and its inverse appear in many natural phenomena and have numerous applications. The fast Fourier transform (FFT) and the inverse FFT (or IFFT) algorithms compute the discrete versions of these transforms.
The FFT algorithm was published in 1965. After four years, scientists developed a more versatile, generalized version called the chirp z-transform (CZT). But a similar generalization of the inverse FFT algorithm has gone unsolved for 50 years.
Alexander Stoytchev – an associate professor of electrical and computer engineering at Iowa State University who’s also affiliated with the university’s Virtual Reality Applications Center, its Human-Computer Interaction graduate program and the department of computer science – says the FFT algorithm and its inverse (known as the IFFT) are at the heart of signal processing. These are algorithms that made the digital revolution possible.
Stoytchev, along with Vladimir Sukhoy – an Iowa State doctoral student co-majoring in electrical and computer engineering, and human-computer interaction – worked together to develop the long-sought algorithm, called the inverse chirp z-transform (ICZT).
ICZT is a stepwise procedure that solves a problem. It maps the output of the CZT algorithm back to its input. The two algorithms are similar to a series of two prosme – the first isolate the wavelength of white light into different colors, and the second reverses the process by combining the spectrum back into white light.
In the study, the algorithm matches the computational complexity or speed of its counterpart. It means, it can be used with exponentially decaying or growing frequency components (unlike the IFFT) and that it has been tested for numerical accuracy.
Stoytchev bumps into the idea to attempt to formulate the missing algorithm while searching for analogies in his “Computational Perception” course to understand the fast Fourier transform better.
With a curious mind, he decided to try to find a fast inverse algorithm.
Sukhoy said, “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. A key was seeing the algorithm within the mathematical framework of structured matrices.”
“Even then, there were lots of computer test runs to show everything was working – we had to convince ourselves that this could be done.”
Unlike the IFFT, which can only work with equispaced sampling points that fully cover the unit circle, the ICZT algorithm can work with contours that include only a fraction of the unit circle. It can also work with contours that wrap around and perform multiple revolutions over the circle. This enables the use of specific (non-orthogonal) frequency components, which lifts one of the main restrictions of the IFFT and could lead to better spectrum utilization.
The singularities of the ICZT of size n are related to the elements of the Farey sequence of order n-1. This is a new connection because Farey sequences often appear in number theory.
On the unit circle, the ICZT algorithm achieves high accuracy with only 64-bit floating-point numbers and does not require additional numerical precision, making it easier to implement. It reports the algorithm can pair well with the existing CZT algorithm to do back-to-back signal analysis and signal synthesis.
Stoytchev said, “This algorithm is more general than the IFFT, but maintains the same speed.”
Journal Reference:
- Generalizing the inverse FFT of the unit circle. DOI: 10.1038/s41598-019-50234-9