DOI: https://doi.org/10.26089/NumMet.v25r321

An algorithm for approximating a discrete signal with a small number of harmonics with decreasing amplitudes

Authors

  • Oleg V. Osipov

Keywords:

trigonometric polynomial
sequential harmonic subtraction method
fast Fourier transform (FFT)
high resolution
trigonometric approximation
least squares method
digital signal processing (DSP)
the amplitude spectrum of the signal
data analysis
spectrum spreading

Abstract

An algorithm for approximating an arbitrary discrete signal by a trigonometric polynomial with decreasing harmonics in amplitude is proposed. It has an algorithmic complexity of O(NR(L + log2 N)), where L is the length of the polynomial, N is the length of the set of samples of the original signal, and NR is the length of the frequency basis of the fast Fourier transform (FFT) algorithm. The flowcharts of the developed algorithms, the source texts of Python programs, and the results of numerical experiments are presented. The developed algorithms can be applied to improve domestic technologies in the field of electronics and software, as well as included in the curricula of engineering specialties.

Downloads

Published

2024-08-07

Issue

Vol. 25 (2024): Issue 3.

Section

Methods and algorithms of computational mathematics and their applications

Author Biography

Oleg V. Osipov

V.G. Shukhov Belgorod State Technological University
• Assistant Professor

References

  1. A. B. Sergienko, Digital Signal Processing (Piter, St. Petersburg, 2002) [in Russian].
  2. D. D. Kosheleva and A. V. Doronina, “Fourier Transform and Fast Fourier Transform,” Innovatsii. Nauka. Obrazovanie. No. 38, 626-632 (2021).
  3. S. A. Bakhurin, “Time-Domain Decimation FFT Algorithm,”
    https://ru.dsplib.org/content/fft_dec_in_time/fft_dec_in_time.html . Cited July 19, 2024.
  4. S. P. Sikorskiy and E. V. Ivanchukov, “Digital Signal Processing and Fourier Transform in the Case of Spectral Spreading,” Zh. Nauchnykh i Prikladnykh Issledovaniy. 1 (11), 67-69 (2016).
  5. N. M. Popov and A. N. Serov, “Comparative Analysis of Methods for Reducing the ’Spectral Spreading’ Effect,” Avtomatizatsiya Izmereniya v Mashinostroyenii, No. 3, 48-53 (2019).
  6. E. V. Dmitriev, “Harmonic Discrete Spectra and Approximation of Short Processes, Signals, and Functions,” Aviakosmicheskoe Priborostroenie, No. 3, 23-31 (2006).
  7. E. V. Dmitriev, “Detection and Discrimination of Signals in Additive Mixture by Calculation and Analysis of Natural Spectrum,” Fizika Volnovykh Protsessov i Radiotekhnicheskie Sistemy. 11 (2), 61-66 (2008).
    https://elibrary.ru/item.asp?id=12931786 . Cited July 19, 2024.
  8. V. G. Getmanov, “On Reducing the Solution Time of the Discrete Trigonometric Approximation Problem,” Avtometriya, No. 6, 108-110 (1988).
  9. V. G. Getmanov, R. A. Dabagyan, and R. V. Sidorov, “Studying Geomagnetic Pulsation Characteristics with the Local Approximation Method,” Geomagnetism i Aeronomiya, 56 (2), 209-216 (2016) [Geomagn. Aeron. 56 (2), 195-202 (2016)].
    doi 10.1134/S0016793216020055
  10. V. K. Abalakin, E. P. Aksyonov, E. A. Grebenikov, et al., Handbook of Celestial Mechanics and Astrodynamics (Nauka, Moscow, 1976) [in Russian].
  11. S. L. Marple, Digital Spectral Analysis with Applications (Prentice-Hall, Englewood Cliffs, 1987; Mir, Moscow, 1990).
  12. O. N. Granichin and D. V. Pavlenko, “Data Randomization and L_1-Optimization,” Komp’yuternye Instrumenty v Obrazovanii, No. 1, 4-13 (2010).
  13. B. A. Knyazev and V. M. Chernen’kiy, “Convolutional Sparse Coding for Static and Dynamic Images Analysis,” Nauka i Obrazovanie, No. 11, 664-695 (2014).
    doi 10.7463/1114.0730860
  14. O. V. Osipov, “Iterative FFT-Algorithms with High Frequency Resolution,” Numerical Methods and Programming (Vychislitel’nye Metody i Programmirovanie). 22 (2), 123-137 (2021).
    doi 10.26089/NumMet.v22r209
  15. A. A. Burtsev, “Optimization of Fast Fourier Transform Operation in OpenCL Environment,” Trudy Inst. Sistemnykh Issledovaniy RAN. 12 (1-2), 11-27 (2022).
    doi 10.25682/NIISI.2022.1-2.0002
  16. V. G. Getmanov, Digital Processing of Signals (NIYAU MEPhI, Moscow, 2010).
  17. S. V. Porshnev and D. V. Kusaikin, “On Accuracy of Trigonometric Interpolation,” Digital Signal Processing (Tsifrovaya Obrabotka Signalov), No. 1, 43-51 (2019).
    https://elibrary.ru/item.asp?id=41269684 . Cited July 19, 2024.
  18. S. I. Ziatdinov and N. V. Girin, “Analysis of Errors in Trigonometric Interpolation,” Izv. Vyssh. Uchebn. Zaved., Priborostroen. 51 (5), 42-45 (2008).
  19. V. M. Efimov and A. L. Reznik, “Sampling Functions in Periodical Signal Reconstruction. The Variance of a Trigonometric Interpolation Error,” Avtometriya 41 (4), 3-14 (2005). [Optoelectron., Instrum. Data Process. 41 (4), 3-13 (2005)].
    https://sibran.ru/en/journals/issue.php?ID=120300 . Cited July 20, 2024.
  20. O. V. Osipov, “Spectral Analysis of Discrete Signals with High Frequency Resolution,” Numerical Methods and Programming (Vychislitel’nye Metody i Programmirovanie). 20 (3), 270-282 (2019).
    doi 10.26089/NumMet.v20r324
  21. T. V. Vaseeva and E. A. Altman, “Algorithm for Finding the Optimum Unbias Estimate of the Amplitude Harmonics Based on the Method of Correlation Functions,” Vestn. Rostov Gos. Univ. Putey Soobshchen., No. 1, 168-176 (2022).
    doi 10.46973/0201-727X_2022_1_168
  22. S. N. Chizhma and R. I. Gazizov, “Method of Spectral Analysis of Signals in Power Supply Systems,” Omskiy Nauch. Vestn., No. 1, 198-201 (2013).

License

Copyright (c) 2024 О. В. Осипов

Creative Commons License

This work is licensed under a Creative Commons Attribution 4.0 International License.