Numerical error analysis of the ICZT algorithm for chirp contours on the unit circle

作者: Vladimir Sukhoy , Alexander Stoytchev

DOI: 10.1038/S41598-020-60878-7

关键词:

摘要: This paper shows that the inverse chirp z-transform (ICZT), which generalizes fast Fourier transform (IFFT) off unit circle in complex plane, can also be used with contours perform partial or multiple revolutions on circle. is done as a special case of ICZT, algorithmic form has same computational complexity IFFT, i.e., O(n log n). Here we evaluate ICZT algorithm for and show it numerically accurate large areas parameter space. The numerical error this depends polar angle between two adjacent contour points. More specifically, profile size n determined by elements Farey sequence order n − 1. Furthermore, generalization allows use non-orthogonal frequency components, thus lifting one main restrictions IFFT.

参考文章(28)
Dario Bini, Victor Y Pan, Dario Bini, Victor Y Pan, None, Fundamental Computations with Polynomials Polynomial and Matrix Computations. pp. 1- 80 ,(1994) , 10.1007/978-1-4612-0265-3_1
Nicholas J. Higham, Error analysis of the bjo¨rck-pereyra algorithms for solving vandermonde systems Numerische Mathematik. ,vol. 50, pp. 613- 632 ,(1987) , 10.1007/BF01408579
James Demmel, Plamen Koev, The Accurate and Efficient Solution of a Totally Positive Generalized Vandermonde Linear System SIAM Journal on Matrix Analysis and Applications. ,vol. 27, pp. 142- 152 ,(2005) , 10.1137/S0895479804440335
L. Rabiner, The chirp z-transform algorithm-a lesson in serendipity IEEE Signal Processing Magazine. ,vol. 21, pp. 118- 119 ,(2004) , 10.1109/MSP.2004.1276120
A. Dutt, V. Rokhlin, Fast Fourier Transforms for Nonequispaced Data, II Applied and Computational Harmonic Analysis. ,vol. 2, pp. 85- 100 ,(1995) , 10.1006/ACHA.1995.1007
R.M. Mersereau, A.V. Oppenheim, Digital reconstruction of multidimensional signals from their projections Proceedings of the IEEE. ,vol. 62, pp. 1319- 1338 ,(1974) , 10.1109/PROC.1974.9625
Paul N. Swarztrauber, Roland A. Sweet, William L. Briggs, Van Emden Henson, James Otto, Paper: Bluestein's FFT for arbitrary N on the hypercube parallel computing. ,vol. 17, pp. 607- 617 ,(1991) , 10.1016/S0167-8191(05)80051-1
A. Dutt, V. Rokhlin, Fast Fourier transforms for nonequispaced data SIAM Journal on Scientific Computing. ,vol. 14, pp. 1368- 1393 ,(1993) , 10.1137/0914081
Lawrence R. Rabiner, Ronald W. Schafer, Charles M. Rader, The Chirp z-Transform Algorithm and Its Application Bell System Technical Journal. ,vol. 48, pp. 1249- 1292 ,(1969) , 10.1002/J.1538-7305.1969.TB04268.X