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

Итерационные алгоритмы БПФ с высоким частотным разрешением

Авторы

  • О. В. Осипов

Ключевые слова:

быстрое преобразование Фурье (БПФ)
вычислительный граф
высокое разрешение
сдвиг частоты
частотно-временное разрешение
проблемы цифровой обработки сигналов (ЦОС)
численный итерационный алгоритм БПФ
прямое БПФ
амплитудно-частотная характеристика
прореживание по времени

Аннотация

В работе представлены три итерационных алгоритма быстрого преобразования Фурье с прореживанием по времени, имеющие алгоритмическую сложность O (N·R·log2N), где R — частотное разрешение спектральной характеристики (отношение длины набора частот к длине N набора отсчетов исходного сигнала). Алгоритмы отличаются способами организации вычислений: некоторые используют обратную перестановку битов, другие — дополнительные массивы. Приведены подробные вычислительные графы, а также блок-схемы разработанных алгоритмов. Полученные результаты можно использовать для улучшения отечественной электроники и программного обеспечения, а также включать в учебный процесс при подготовке инженеров в области цифровой обработки сигналов.

Загрузки

Опубликован

2021-05-25

Выпуск

Том 22 (2021): Выпуск 2.

Раздел

Методы и алгоритмы вычислительной математики и их приложения

Автор

О. В. Осипов

Белгородский государственный технологический университет им. В.Г. Шухова,
кафедра программного обеспечения вычислительной техники и автоматизированных систем
ул. Костюкова, 46, 308012, Белгород
• доцент

Библиографические ссылки

  1. E. A. Al’tman, “Optimization of Computational Scheme of Fast Fourier Transformation,” Omsk. Nauch. Vestn., No. 1 (64), 149-151 (2008).
  2. L. M. Gol’denberg, B. D. Matyushkin, and M. N. Polyak, Digital Processing of Signals (Radio Svyaz, Moscow, 1990) [in Russian].
  3. L. R. Rabiner, B. Gold, and C. K. Yuen, Theory and Application of Digital Signal Processing (Prentice-Hall, Englewood Cliffs, 1975; Mir, Moscow, 1978).
  4. Fast Fourier Transform for O(Nlog N).
    https://e-maxx.ru/algo/fft_multiply . Cited May 15, 2021.
  5. O. V. Osipov, “Spectral Analysis of Discrete Signals with High Frequency Resolution,” Vychisl. Metody Programm. 20, 270-282 (2019).
  6. N. V. Ponomareva, “Fast Parametric Fourier Transform for Spectral Analysis of Signals with High Resolution in a Given Frequency Range,” DSPA: Voprosy primeneniya cifrovoj obrabotki signalov 9 (1), 28-32 (2019).
  7. V. N. Chan and V. N. Dam, “Implementation of the Spectrum Analyzer with High-Resolution on FGPA,” DSPA: Voprosy primeneniya cifrovoj obrabotki signalov 6 (4), 725-729 (2016).
  8. M. Gasior and J. L. Gonzalez, “Improving FFT Frequency Measurement Resolution by Parabolic and Gaussian Spectrum Interpolation,” AIP Conf. Proc. 732 (1), 276-285 (2004).
  9. I. A. Sidorenko and P. A. Kuskova, “On Improving the Accuracy of the Spectral Analysis of Phonemes when Using Sound Editors,” Belgorod State Univ. Sci. Bull. Ser.: Econ. Inform., No. 7, 188-193 (2015).
  10. D. D. Poleshenkov and O. O. Basov, “Pitch Frequency Separation Method Based on a Frequency Demodulation,” Belgorod State Univ. Sci. Bull. Ser.: Econ. Inform. 46 (2), 359-366 (2019).
  11. B. Gold and C. M. Rader, Digital Signal Processing (McGraw-Hill, New York, 1969; Sov. Radio, Moscow, 1973).
  12. V. I. Belov and E. I. Panimaskin, “The Fast Fourier Transform (FFT) with Decimation in Time,”
    https://docplayer.ru/25793573-Belov-v-i-panimaskin-e-i-bystroe-preobrazovanie-fure-bpf-s-prorezhivaniem-po-vremeni.html . Cited May 15, 2021.
  13. N. A. Galanina, “Synthesis of FFT Functional Modules in RNS,” Vestn. Chuvash. Gos. Univ., No. 2, 124-127 (2005).
  14. J. W. Cooley and J. W. Tukey, “An Algorithm for the Machine Calculation of Complex Fourier Series,” Math. Comput. 19 (90), 297-301 (1965).
  15. D. F. Vydrin, Yu. R. Abzalilova, and A. K. Vdovin, “Fast Fourier Transformation at Digital Signal Processing,” Teor. Prakt. Sovremen. Nauki, No. 2, 161-163 (2017).
  16. L. I. Timoshenko, “Discrete Transformation of Fourier and His Fast Algorithms,” Sovremen. Naukoemk. Tekhnol., No. 12-2, 188-193 (2014).
  17. A. I. Solonina, D. A. Ulakhovich, and L. A. Yakovlev, Algorithms and Processors for Digital Signal Processing (BHV-Petersburg, St. Petersburg, 2001) [in Russian].
  18. B. Lerner, Writing Efficient Floating-Point FFTs for ADSP-TS201 TigerSHARC® Processors.
    https://www.analog.com/media/en/technical-documentation/application-notes/EE-218.pdf . Cited May 15, 2021.
  19. V. E. Loginov and P. A. Ishin, “32-bit Floating-Point Fast Fourier Transform Optimization for Elbrus Processor,” Voprosy Radioelektron. 4 (3), 108-118 (2012).

Лицензия

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

Лицензия Creative Commons

Это произведение доступно по лицензии Creative Commons «Attribution» («Атрибуция») 4.0 Всемирная.