An interesting algorithm known as the fast Fourier transform (or FFT) is present in a variety of devices, including smartphones.
FFT is a signal-processing algorithm that can be used for a wide variety of purposes, and a new study argues that FFT and the reverse, which is known as IFFT are the foundation of signal processing. They are deemed to be the algorithms that made the digital revolution a reality, are essential for tasks like streaming music, performing a call, shooting a photo and much more.
The first version of the FFT algorithm was released in 1965. An improved version, known as the chirp-z transform (or CZT), was published after for years, but there was no equivalent for the IFFT until now.
Two researchers with a background in electrical and computer engineering worked hard on the new algorithm, which is called inverse chirp z-transformation (or ICZT). To achieve this milestone the researchers unraveled CZT back to the input. According to one of the researchers the two algorithms are like two prisms, with one being able to separate white light into different colors while the other combines these colors back into white light.
A paper published by the researchers mentions that the algorithm is on par with the computational complexity and speed of its equivalent, and it can be used along with exponentially decaying or growing frequency components without problems.
As expected, the reverse algorithm is considerably more complicated in comparison to the original, and superior tools were needed to track it down. Lots of attempts took place before the new algorithm could be pinned down without conflicts. The result of the venture has been appreciated by researchers from all over the world as they solved a dilemma that remained a challenge for 50 years.
More data about the discovery and the methods that were used can be found in the paper, which was published in a scientific journal.