ИТЕРАЦИОННЫЕ АЛГОРИТМЫ БПФ С ВЫСОКИМ ЧАСТОТНЫМ РАЗРЕШЕНИЕМ (2021)
В работе представлены три итерационных алгоритма быстрого преобразования Фурье с прореживанием по времени, имеющие алгоритмическую сложность O (N·R·log2N), где R - частотное разрешение спектральной характеристики (отношение длины набора частот к длине N набора отсчетов исходного сигнала). Алгоритмы отличаются способами организации вычислений: некоторые используют обратную перестановку битов, другие - дополнительные массивы. Приведены подробные вычислительные графы, а также блок-схемы разработанных алгоритмов. Полученные результаты можно использовать для улучшения отечественной электроники и программного обеспечения, а также включать в учебный процесс при подготовке инженеров в области цифровой обработки сигналов.
Идентификаторы и классификаторы
- eLIBRARY ID
- 46169017
В зависимости от технических условий решаемых задач инженерам нередко приходится искать различные способы оптимизации алгоритмов БПФ [1]. При этом требуется учитывать архитектурные особенности современных вычислительных систем, основные из которых — способность к векторизации и распараллеливанию вычислений, а также структура кэш-памяти. Учет этих особенностей при построении алгоритмов позволяет существенно ускорить вычисления. Ранние реализации алгоритмов БПФ по основанию “два” на Бейсике и Фортране были ориентированы на однопоточное исполнение и содержали в себе три цикла [2, с. 128–131; 3, с. 405]. Это упрощало индексацию элементов в массиве комплексных чисел и не требовало лишних целочисленных операций. Такие алгоритмы, реализованные на С++ [4], вполне успешно решают свои задачи и по сей день, например при обработке звука. Но с появлением многопроцессорных систем, особенно на базе графических ускорителей (GPU), появилась возможность ускорить вычисление БПФ. Можно сократить количество циклов до двух и сделать итерации внутреннего цикла независимыми друг от друга, что позволит легко распараллелить и, следовательно, ускорить алгоритм БПФ.
Список литературы
- E. A. Al’tman, “Optimization of Computational Scheme of Fast Fourier Transformation”, Omsk. Nauch. Vestn., No. 1 (64), 149-151 (2008). EDN: JVZMON
- L. M. Gol’denberg, B. D. Matyushkin, and M. N. Polyak, Digital Processing of Signals (Radio Svyaz, Moscow, 1990) [in Russian].
- L. R. Rabiner, B. Gold, and C. K. Yuen, Theory and Application of Digital Signal Processing (Prentice-Hall, Englewood Cliffs, 1975; Mir, Moscow, 1978).
- Fast Fourier Transform for O(Nlog N). https://e-maxx.ru/algo/fft_multiply. Cited May 15, 2021.
- O. V. Osipov, “Spectral Analysis of Discrete Signals with High Frequency Resolution”, Vychisl. Metody Programm. 20, 270-282 (2019). EDN: KUAODA
- 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).
- 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).
- 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).
- 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).
-
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).
-
B. Gold and C. M. Rader, Digital Signal Processing (McGraw-Hill, New York, 1969; Sov. Radio, Moscow, 1973).
-
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.
-
N. A. Galanina, "Synthesis of FFT Functional Modules in RNS", Vestn. Chuvash. Gos. Univ., No. 2, 124-127 (2005). EDN: JWQDEF
-
J. W. Cooley and J. W. Tukey, "An Algorithm for the Machine Calculation of Complex Fourier Series", Math. Comput. 19 (90), 297-301 (1965).
-
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).
-
L. I. Timoshenko, "Discrete Transformation of Fourier and His Fast Algorithms", Sovremen. Naukoemk. Tekhnol., No. 12-2, 188-193 (2014).
-
A. I. Solonina, D. A. Ulakhovich, and L. A. Yakovlev, Algorithms and Processors for Digital Signal Processing (BHV-Petersburg, St. Petersburg, 2001) [in Russian].
-
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.
-
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).
Выпуск
Методы и алгоритмы вычислительной математики и их приложения.
Параллельные программные средства и технологии.
Другие статьи выпуска
В данной статье представлен обзор современного состояния суперкомпьютерной техники. Обзор сделан с разных точек зрения - начиная от особенностей построения современных вычислительных устройств до особенностей архитектуры больших суперкомпьютерных комплексов. В данный обзор вошли описания самых мощных суперкомпьютеров мира и России по состоянию на начало 2021 г., а также некоторых менее мощных систем, интересных с других точек зрения. Также делается акцент на тенденциях развития суперкомпьютерной отрасли и описываются наиболее известные проекты построения будущих экзафлопсных суперкомпьютеров.
Рассматривается задача построения эффективного численного алгоритма решения дробно-дифференциального обобщения неоднородного уравнения Гельмгольца с дробной степенью оператора Лапласа. Построено мультипольное разложение, основанное на факторизации фундаментального решения рассматриваемого уравнения. Предложен способ нахождения значений функций Фокса, входящих в представленное мультипольное разложение. Разработана модификация мультипольного алгоритма для решения рассматриваемого дробно-дифференциального обобщения уравнения Гельмгольца. Приведены результаты вычислительных экспериментов, демонстрирующие эффективность предложенных алгоритмов.
Рассмотрены явные симплектические разностные схемы Рунге-Кутты-Нистрема (RKN) с числом стадий от 1 до 5 для численного решения задач молекулярной динамики, описываемых системами с распадающимися гамильтонианами. Для числа стадий 2 и 3 параметры RKN-схем получены с помощью техники базисов Гребнера. Для числа стадий 4 и 5 новые схемы най дены с применением метода численной оптимизации Нелдера-Мида. В частности, для числа стадий 4 получены четыре новые схемы. Для числа стадий 5 получены три новые схемы в дополнение к четырем схемам, известным в литературе. Для каждого конкретного числа стадий найдена схема, являющаяся наилучшей с точки зрения минимума ведущего члена погрешности аппроксимации. Верификация схем осуществлена на задаче, имеющей точное решение. Показано, что симплектическая пятистадийная RKN-схема обеспечивает более точное сохранение баланса полной энергии системы частиц, чем схемы более низких порядков точности. Исследования устойчивости схем выполнены с помощью программного пакета Mathematica.
Издательство
- Издательство
- МГУ
- Регион
- Россия, Москва
- Почтовый адрес
- оссийская Федерация, 119991, Москва, Ленинские горы, д. 1
- Юр. адрес
- оссийская Федерация, 119991, Москва, Ленинские горы, д. 1
- ФИО
- Садовничий Виктор Антонович (РЕКТОР)
- E-mail адрес
- info@rector.msu.ru
- Контактный телефон
- +7 (495) 9391000
- Сайт
- https://msu.ru/