Свертка непрерывного сигнала с использованием быстрого преобразования Фурье с перекрытием для определения координат транспортного робота

S A Trefilov; D A Ponomarev

doi:10.22213/2413-1172-2024-3-4-15

Authors

S. A. Trefilov Kalashnikov ISTU
D. A. Ponomarev Izhevsk Radio Plant

DOI:

https://doi.org/10.22213/2413-1172-2024-3-4-15

Keywords:

robotics, signal processing, convolution, spectral analysis, Fft

Abstract

The paper discusses the development of a continuous discrete signal convolution algorithm using fast Fourier transform (FFT) with overlap for more accurate determination of the coordinates of a transportation robot. Two methods for determining the coordinates of a transportation robot in two-dimensional space are presented, where the convolution operation is used and where this algorithm can be applied. The algorithm is based on a method that allows the FFT to be performed on multiple computational units in parallel, such as on a TMS320F28377D digital signal processor, where three computational units are available that operate independently in parallel. The use of a FFT with overlap allows signal processing without data loss, which is critical for continuous signal processing.The study of the influence of the FFT window offset value on the frequency of obtaining the spectrum of the signal has been carried out, and as it was found that reducing the FFT window offset leads to an increase in the frequency of obtaining the spectrum of the signal, which, in turn, allows you to more accurately restore the amplitude of the original signal, that is, there is less loss of spectrum data. As results, the paper provides illustrations of the study in the form of three-dimensional graphs, where the spectra of the signal in time during the FFT with overlap, where as the initial signal is used a sinusoidal signal, which over time increases its frequency. Comparison of the results of the algorithm without overlap and with overlap at different offset values showed that the method with overlap provides significantly more accurate and frequent acquisition of spectrum data, avoiding data loss.The presented results are useful in robotics when it is required to accurately determine the coordinates of a transportation robot.

Author Biographies

S. A. Trefilov, Kalashnikov ISTU

PhD in Engineering, Associate Professor

D. A. Ponomarev, Izhevsk Radio Plant

Software Engineer, Robotics Department

References

Lukomskii S.F., Vodolazov A.M. (2020) Fast Discrete Fourier Transform on Local Fields of Zero Characteristic. P-Adic Numbers, Ultrametric Analysis, and Applications, vol. 12, no. 1, pp. 39-48. DOI: 10.1134/S2070046620010045. EDN FIFQIV.

Monroe D. (2023) Quantum Speedup for the Fast Fourier Transform? Association for Computing Machinery.Communications of the ACM, vol. 66, no. 11, pp. 8-10. DOI: 10.1145/3623641. EDN KLKNLG.

Sun Ya., Qian W. (2024) Fast algorithms for nonuniform Chirp-Fourier transform. AIMS Mathematics, vol. 9, no. 7, pp. 18968-18983. DOI: 10.3934/math. 2024923. EDN HZBXMD.

Merhi S., Zhang R., Iwen M., Christlieb A. (2019) A New Class of Fully Discrete Sparse Fourier Transforms: Faster Stable Implementations with Guarantees. Journal of Fourier Analysis and Applications, vol. 25, no. 3, pp. 751-784. DOI: 10.1007/s00041-018-9616-4. EDN KQYWCR.

Альтман Е. А. Способ уменьшения числа операций в алгоритме быстрого преобразования Фурье // Вычислительные технологии. 2018. Т. 23, № 3. С. 3-14.

Алексашкина А. А., Костромин А. Н., Нестеренко Ю. В. О быстром алгоритме вычисления преобразования Фурье // Вестник Московского университета. Серия 1: Математика. Механика. 2021. № 3. С. 36-41. EDN UIVZTB.

Aleksashkina A.A., Kostromin A.N., Nesterenko Y.V. (2021) On a Fast Algorithm for Computing the Fourier Transform. Moscow University Mathematics Bulletin, vol. 76, no. 3, pp. 123-128. DOI: 10.3103/S0027132221030025. EDN QLQQTG.

Chimmalgi S., Prins P. J., Wahls S. (2019) Fast Nonlinear Fourier Transform Algorithms Using Higher Order Exponential Integrators. IEEE Access, vol. 7, pp. 145161-145176. DOI: 10.1109/ACCESS.2019.2945480. EDN WGHNBG.

Majorkowska-Mech D., Cariow A. (2022) Some FFT Algorithms for Small-Length Real-Valued Sequences. Applied Sciences (Switzerland), vol. 12, no. 9, p. 4700. DOI: 10.3390/app12094700. EDN KJEXSG.

Кошелева Д. Д., Доронина А. В. Преобразование Фурье и быстрое преобразование Фурье // Инновации. Наука. Образование. 2021. № 38. С. 626-632.

Осипов О. В. Прямое быстрое преобразование Фурье по основанию два с высоким частотным разрешением // Цифровая обработка сигналов. 2018. № 4. С. 59-62.

Осипов О. В. Спектральный анализ дискретных сигналов с высоким частотным разрешением // Вычислительные методы и программирование. 2019. Т. 20, № 3. С. 270-282. DOI: 10.26089/NumMet.v20r324

Осипов О. В. Итерационные алгоритмы БПФ с высоким частотным разрешением // Вычислительные методы и программирование. 2021. Т. 22, № 2. С. 121-134. DOI: 10.26089/NumMet.v22r209

Kircheis M., Potts D. (2023) Fast and direct inversion methods for the multivariate nonequispaced fast Fourier transform. Frontiers in Applied Mathematics and Statistics, vol. 9. DOI: 10.3389/fams.2023.1155484. EDN UQLVPW.

Labunets V.G., Chasovskikh V.P., Starikov E.V. (2023) New many-parameter Fourier-Clifford transforms. Digital Models and Solutions, vol. 2, no. 3, pp. 5-22. DOI: 10.29141/2949-477X-2023-2-3-1. EDN MLQGCK.

Labunets V., Chasovskikh V., Starikov E. (2023) Nonlinearizad of fast Fourier transform. Digital Models and Solutions, vol. 2, no. 2, p. 1. DOI: 10.29141/2782-4934-2023-2-2-1. EDN TDVEMG.

Альтман Е. А., Захаренко Е. И., Васеева Т. В. Применение метода разложения двумерной свертки при реализации цифровых фильтров // Научный вестник Новосибирского государственного технического университета. 2017. № 4(69). С. 95-104. DOI: 10.17212/1814-1196-2017-4-95-104

Кошелев В. И., Чинь Н. Х. Алгоритм быстрого преобразования Фурье неэквидистантных последовательностей импульсов // Вестник Рязанского государственного радиотехнического университета. 2023. № 85. С. 3-13. DOI: 10.21667/1995-4565-2023-85-3-13. EDN JULSTB.

Альтман Е. А., Александров А. В. Анализ зависимости быстродействия быстрого преобразования Фурье от объема обрабатываемых данных // Вестник Ростовского государственного университета путей сообщения. 2023. № 1(89). С. 136-143. DOI: 10.46973/0201-727X_2023_1_136

Chen L. (2022) A note on the high-dimensional sparse Fourier transform in the continuous setting. Inverse Problems, vol. 38, no. 3, p. 035008. DOI: 10.1088/1361-6420/ac3c16. EDN PIMQIM.

Мартюгин С. А., Поршнев С. В. Быстрое дробное преобразование Фурье // International Journal of Open Information Technologies. 2024. Т. 12, № 1. С. 108-113. EDN BUXPXW.

Kumar G.G., Sahoo S.K., Meher P.K. (2019) 50 Years of FFT Algorithms and Applications. Circuits, Systems, and Signal Processing, vol. 38, no. 12, pp. 5665-5698. DOI: 10.1007/s00034-019-01136-8. EDN BACNKR.