The fast Fourier transform (FFT) is an important digital signal processing algorithm used by a wide range of radio communication devices including your mobile phone. Although the transform and its inverse function has been routinely been used for many years now there has always been one function missing from the signal processing toolbox. Now after a 50 year gap researchers have finally produced an algorithm to perform the inverse Chirp-Z transformation (ICZT).

After three years work Alexander Stoytchev and his doctoral student Vladimir Sukhoy from the Department of Electrical and Information Technology at Iowa State University made the breakthrough. It was thought that Carl Friedrich Gauss was the first to describe the FFT way back in 1805 while Cooley and Tukey came up with an efficient variant of the FFT algorithm for use with complex vectors in 1965 which is still in use today. An inverse function, the IFFT, was also developed to convert the results of the FFT process and achieve the original values. Four years after the FFT, a more versatile, generalized version called Chirp-Z Transformation (CZT) was developed. But a similar generalization of the inverse FFT algorithm, the ICZT, was never solved.

Stoytchev and Sukhoy have spent the last few years working on the development of the much anticipated inverse Chirp-Z transformation (ICZT). Again, the ICZT returns its input with the results of the CZT. In principle, the two algorithms are said to function much like two prisms where white light passing through the first prism is split into all the wavelengths of the visible spectrum while the second prism reverses the process.
 
Three different types of frequency components: (a) exponentially decaying, (b) fixed size, and (c) exponentially increasing. FFT and IFFT use only frequency components of fixed size. Picture: A. Stoytchev and V. Sukhoy, Scientific Reports.

Stoytchev and Sukhoy describe their new algorithm in the journal Scientific Reports. Their contribution shows that the algorithm corresponds to the complexity or speed of its counterpart, and that it can be used with exponentially varying frequency components (unlike IFFT) and has been rigorously tested to prove its numerical accuracy.

Originally Stoytchev was not even aware of the missing function, he was looking for information to help explain fast Fourier transforms to his students but could not find anything about the inverse to the related chirp z-transform. When he realised such an algorithm didn’t exist he set about trying to find a solution.
The inverse algorithm was harder to crack than its forward algorithm counterpart; they needed more powerful computers so that the calculations achieved a better level of precision. The main key to the solution was to see the algorithm within a mathematical framework of structured matrices.

Source: Iowa State University