Vladimir Sukhoy and Alexander Stoytchev, left to right, with the derivation for the ICZT algorithm in structured matrix notation — the answer to a 50-year-old puzzle in signal processing. Photo By: Paul Easker
Iowa State University (ISU) researchers Alexander Stoytchev and Vladimir Sukhoy have solved the mystery of the inverse fast Fourier transform (IFFT) algorithm, which along with the FFT algorithm comprise the core of signal processing.
The fast Fourier transform (FFT), which runs on cell phones, is a signal-processing algorithm that people use more than they realize. It is, according to the title of one research paper, “an algorithm the whole family can use.”
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 – said that the FFT algorithm and its inverse (known as the IFFT) are at the heart of signal processing.
And, as such, “These are algorithms that made the digital revolution possible. They’re a part of streaming music, making a cell phone call, browsing the internet or taking a selfie”, he added.
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 inverse FFT algorithm has gone unsolved for 50 years
Until, Iowa State’s researchers Alexander Stoytchev and Vladimir Sukhoy- an Iowa State doctoral student co-majoring in electrical and computer engineering, and human computer interaction developed the inverse chirp z-transform (ICZT) algorithm to generalize the IFFT algorithm, as the FFT was generalized into the CZT.
The ICZT plots the output of the CZT back to its input, matching the computational complexity or speed of its counterpart so it can be employed with exponentially decaying or growing frequency elements.
Stoytchev said he stumbled on the idea to attempt to formulate the missing algorithm while looking for analogies to help the graduate students in his “Computational Perception” course understand the fast Fourier transform. He read a lot of the signal-processing literature and couldn’t find anything about the inverse to the related chirp z-transform.
“I got curious,” he said. “Is that because they couldn’t explain it, or is it because it doesn’t exist? It turned out it didn’t exist.”
And so he decided to try to find a fast inverse algorithm.
Sukhoy described the inverse algorithm was a harder challenge than the original forward algorithm, and “we needed better precision and more powerful computers to attack it.”
Sukhoy further explained that visualizing the algorithm within the mathematical framework of structured matrices was critical.
While applauding both the engineers James Oliver, director of Iowa State’s Student Innovation Center and former director of the university’s Virtual Reality Applications Center, said “It took courage to keep attacking the problem.
Stoytchev and Sukhoy have acknowledged Oliver in their paper,“for creating the research environment in which we could pursue this work over the past three years.”
Oliver said Stoytchev earned his support for a mathematical and computational challenge that hadn’t been solved for 50 years: “Alex has always impressed me with his passion and commitment to take on big research challenges. There is always risk in research and it takes courage to devote years of hard work to a fundamental problem. Alex is a gifted and fearless researcher.”