Generalizing the inverse FFT off the unit circle.

摘要: This paper describes the first algorithm for computing inverse chirp z-transform (ICZT) in O(n log n) time. matches computational complexity of (CZT) that was discovered 50 years ago. Despite multiple previous attempts, an efficient ICZT remained elusive until now. Because can be viewed as a generalization fast Fourier transform (IFFT) off unit circle complex plane, it has numerous practical applications wide variety disciplines. enables exponentially growing or decaying frequency components, which cannot done with IFFT. The derived using properties structured matrices and its numerical accuracy evaluated automated tests. A modification CZT algorithm, improves stability subset parameter space, is also described evaluated.