Эффективность алгоритмов БПФ

Content

DSPL-2.0 is free digital signal processing algorithms library

Distributed under v3 LGPL v3 license

GitHub project page.

Found a mistake? Select it with the mouse and press ctrl+enter
Введение

В предыдущих разделах мы рассмотрели алгоритмы БПФ по основанию два с прореживанием по времени и по частоте. В данном разделе мы проанализируем их вычислительную эффективность и некоторые приемы программной реализации алгоритмов БПФ.

Для анализа приведем еще раз полные графы алгоритмов БПФ с прореживанием по времени (рисунок 1) и по частоте (рисунок 2).

Полный граф алгоритма БПФ с прореживанием по времени для
Figure 1. Полный граф алгоритма БПФ с прореживанием по времени для

Полный граф алгоритма БПФ с прореживанием по частоте для
Figure 2. Полный граф алгоритма БПФ с прореживанием по частоте для

Можно заметить, что полные графы алгоритмов БПФ по времени и по частоте являются практическим точным зеркальным отражением друг друга. В обоих алгоритмах используется двоично-инверсная перестановка. В алгоритме с прореживанием по времени она используется вначале, в алгоритме с прореживанием по частоте — в конце. В обоих алгоритмах используются одни и те же поворотные коэффициенты.

В итоге, вычислительная эффективность обоих алгоритмов эквивалентна.

Поворотные коэффициенты алгоритмов БПФ

Рассмотрим подробнее поворотные коэффициенты используемые как в алгоритме БПФ с прореживанием по времени, так и в алгоритме БПФ с прореживанием по частоте. На нижнем уровне разделения-объединения, при вычислении 2-точечного ДПФ, требуется всего один поворотный коэффициент . Это означает что на нижнем уровне разделения операции умножения не требуются (умножение на единицу называется тривиальным).

На втором уровне разделения-объединения, при вычислении 4-точечного ДПФ, имеем два поворотных коэффициента: и . Умножения на также являются тривиальными, потому что реальная и мнимая части множителя меняются местами и изменяется знак при мнимой части.

На третьем уровне имеем четыре поворотных коэффициента: , , и .

Графически поворотные коэффициенты можно представить как векторы на комплексной плоскости (смотри рисунок 3a).

Поворотные коэффициенты   а — для ; б —для
Figure 3. Поворотные коэффициенты
а — для ; б —для

Можно заметить, что на всех уровнях объединения количество поворотных коэффициентов удваивается, причем все поворотные коэффициенты предыдущего уровня объединения присутствуют и на следующем уровне. Таким образом, для того чтобы перейти на следующий уровень необходимо между поворотными коэффициентами текущего уровня вставить поворотные коэффициенты следующего.

Графически для перехода на следующий уровень при необходимо дополнить рисунок 3а как это показано на рисунке 3б.

Синие векторы показывают поворотные коэффициенты которые будут присутствовать на последнем уровне при , которых нет при .

Вычислительная эффективность алгоритмов БПФ с прореживанием по времени и частоте

Алгоритмы с прореживанием по времени для длины требует уровней разделения - объединения с использованием графа «бабочка».

При этом нижние два уровня (при расчете 2-точечного и 4-точечного ДПФ) используют только тривиальные умножения на поворотные коэффициенты и , которые можно не учитывать. Каждый из остальных этапов объединения требует комплексных умножений. В результате общее количество требуемых операций комплексного умножения для алгоритмов БПФ с прореживанием по времени и по частоте равно

(1)

Количество операций комплексного сложения (вычитания) на каждом уровне объединения равно .

Таким образом, общее количество операций комплексного сложения (вычитания) алгоритма БПФ с прореживанием по времени и частоте равно

(2)

Напомним, что для наивного алгоритма ДПФ требуется

(3)
операций комплексного умножения и сложения.

Алгоритмы БПФ с прореживанием по времени и частоте уменьшают количество требуемых операций комплексного умножения в

(4)
раз, а количество требуемых операций комплексного сложения в
(5)
раз.

Так например для расчет БПФ требует в 256 раз меньше операций комплексного умножения, и в 102.4 раза меньше операций комплексного сложения. При этом с ростом экономия умножителей и сумматоров только растет.

Таким образом, практическое использование алгоритма БПФ с прореживанием по времени, позволяет достичь очень высокой вычислительной эффективности, по сравнению с наивным методом расчета ДПФ.

Обзор библиотек реализующих алгоритмы БПФ

Существует множество библиотек с реализацией алгоритмов БПФ, однако можно выделить две наиболее эффективные реализации: FFTW и Intel® Math Kernel Library (Intel® MKL).

Библиотека FFTW разработана Маттэо Фриго (Matteo Frigo) и Стивеном Джонсоном (Steven G. Johnson) в Массачусетском технологическом институте [1]. Данная библиотека распространяется под лицензией GNU GPL и MIT и находит применение в таких программных продуктах как MATLAB, GNU Octave, Python и многих других.

Библиотека Intel® Math Kernel Library (Intel® MKL) помимо алгоритмов БПФ предоставляет множество функций линейной алгебры, оптимизированных для процессоров Intel.

Сравнительный анализ различных библиотек БПФ приведен в [1].

Выводы

В данном разделе мы рассмотрели свойства поворотных коэффициентов и вычислительную эффективность алгоритмов БПФ по основанию два. Было показано что алгоритм с прореживанием по частоте и алгоритм с прореживанием по времени имеют одинаково высокую эффективность, которая растет с ростом размера выборки БПФ.

Также был произведен обзор наиболее эффективных библиотек программной реализации алгоритмов БПФ.

Reference

[1] Frigo M., Johnson S. The Design and Implementation of FFTW3 Proceedings of the IEEE. 93 (2): 216–231 doi:10.1109/JPROC.2004.840301

[2] Heideman M., Johnson D., Burrus C. Gauss and the history of the fast fourier transform. IEEE ASSP Magazine, Vol. 1, Issue 4, October 1984, p. 14-21

[3] James W. Cooley and John W. Tukey An Algorithm for the Machine Calculation of Complex Fourier Series. Mathematics of Computation, Vol. 19, no. 2, April 1965, pp. 297-301.

[4] Офман Ю.П., Карацуба А.А. Умножение многозначных чисел на автоматах. Доклады АН СССР. 1962, Т. 145, С. 293—294

[5] Ахо Альфред В., Хопкрофт Д., Ульман Джеффри Д. Структуры данных и алгоритмы. Москва, Вильямс, 2003.

[6] Блейхут Р. Быстрые алгоритмы цифровой обработки сигналов. Москва, Мир, 1989, 448 c.

[7] Нуссбаумер Г. Быстрое преобразование Фурье и алгоритмы вычисления сверток. Москва, Радио и связь, 1985.

[8] Оппенгейм А., Шаффер Р. Цифровая обработка сигналов. Москва, Техносфера, 2012. 1048 с. ISBN 978-5-94836-329-5

[9] Гольденберг Л.М., Матюшкин Б.Д., Поляк М.Н. Цифровая обработка сигналов. Москва, Радио и связь, 1985.

[10] Рабинер, Л., Гоулд, Б. Теория и применение цифровой обработки сигналов. Москва, Мир, 1978. 848 с.

[11] Сергиенко А.Б. Цифровая обработка сигналов СПб, Питер, 2002.

Page update: 24.07.2020 (14:55:34)