2022, issue 2, p. 52-57
Received 12.09.2022; Revised 25.09.2022; Accepted 29.09.2022
Published 30.09.2022; First Online 05.10.2022
Previous | FULL TEXT (in Ukrainian) | Next
Algorithm for Calculating Primary Spectral Density Estimates Using FFT and Analysis of its Accuracy
Olena Kolomys * , Liliya Luts *
V.M. Glushkov Institute of Cybernetics of the NAS of Ukraine, Kyiv
Introduction. Fast algorithms for solving problems of spectral and correlation analysis of random processes began to appear mainly after 1965, when the algorithm of fast Fourier transform (FFT) entered computational practice. With its appearance, a number of computational algorithms for the accelerated solution of some problems of digital signal processing were developed, speed-efficient algorithms for calculating such estimates of probabilistic characteristics of control objects as estimates of convolutions, correlation functions, spectral densities of stationary and some types of non-stationary random processes were built.
The purpose of the article is to study a speed-efficient algorithm for calculating the primary estimate of the spectral density of stationary ergodic random processes with zero mean. Most often, the direct Fourier transform method using the FFT algorithm, is used to calculate it. The article continues the research and substantiation of this method in the direction of obtaining better estimates of rounding errors.
Results. The research and substantiation of the method in the direction of obtaining more qualitative estimates of rounding errors, taking into account the errors of the input information specification, has been continued. The main characteristics of the given algorithm for calculating the primary estimate of the spectral density are accuracy and computational complexity.
The main attention is paid to obtaining error estimates accompanying the process of calculating the primary estimate of the spectral density. The estimates of the rounding error and ineradicable error of the given algorithm for calculating the primary estimate of the spectral density, which appear during the implementation of the algorithm for the classical rounding rule for calculation in floating-point mode with τ digits in the mantissa of the number, taking into account the input error, are obtained.
Conclusions. The obtained results make it possible to diagnose the quality of the solution to the problem of calculating the primary estimate of the spectral density of stationary ergodic random processes with a zero mean value by the described method and to choose the parameters of the algorithm that will ensure the required accuracy of the approximate solution of the problem.
Keywords: primary estimation of spectral density, fast Fourier transform, discrete Fourier transform, rounding error, input error.
Cite as: Kolomys O., Luts L. Algorithm for Calculating Primary Spectral Density Estimates Using FFT and Analysis of its Accuracy. Cybernetics and Computer Technologies. 2022. 2. P. 52–57. (in Ukrainian) https://doi.org/10.34229/2707-451X.22.2.5
1. Stockham T.G. High speed convolution and correlation. AFIPS Proceedings of the April 26-28, 1966. P. 229–233. https://doi.org/10.1145/1464182.1464209
2. Zadiraka V.K. Theory of Computation of the Fourier Transform. Kyiv: Nauk. dumka, 1983. 216 p. (in Russian)
3. Sergienko I.V., Zadiraka V.K., Lytvyn O.M. Elements of the General Theory of Optimal Algorithms and Related Issues. Kyiv: Nauk. dumka, 2012. 400 p. (in Ukrainian)
4. Julius S. Bendat, Allan G. Piersol. Measurement and Analysis of Random Data. M.: Mir, 1974. – 463 p. (in Russian)
5. James W. Cooley and John W. Tukey An Algorithm for the Machine Calculation of Complex Fourier Series. Math. Comput., 1965, Apr. P. 257–301. https://www.ams.org/journals/mcom/1965-19-090/S0025-5718-1965-0178586-1/S0025-5718-1965-0178586-1.pdf
6. Ivanov V.V., Babich M.D., Berezovskii A.I., Besarab P.N., etc. Characteristics of Problems, Algorithms, and Computers in Software Systems of Computational Mathematics. V.M. Glushkov Inst. Cybern., NAS USSR, Kyiv, 1984 54 p. (in Russian)
7. Wilkinson J.H. The Algebraic Eigenvalue Problem. Oxford: Clarendon Press, 1965. 662 p. https://ru.djvu.online/file/X75oFFC5CY5w9
ISSN 2707-451X (Online)
ISSN 2707-4501 (Print)
Previous | FULL TEXT (in Ukrainian) | Next