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

Содержание

DSPL-2.0 — свободная библиотека алгоритмов цифровой обработки сигналов

Распространяется под лицензией LGPL v3

Страница библиотеки на GitHub

Обнаружили ошибку? Выделите ее мышью и нажмите ctrl+enter
Введение

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

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

Полный граф алгоритма БПФ с прореживанием по времени для
Рисунок 1. Полный граф алгоритма БПФ с прореживанием по времени для N = 8

Полный граф алгоритма БПФ с прореживанием по частоте для
Рисунок 2. Полный граф алгоритма БПФ с прореживанием по частоте для N = 8

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

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

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

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

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

На третьем уровне имеем четыре поворотных коэффициента: W_8^0 = 1, W_8^1 = \exp(-j  \frac{\pi}{4}), W_8^2 = -j и W_8^3 = \exp(-j  \frac{3\pi}{4}).

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

Поворотные коэффициенты   а — для ; б —для
Рисунок 3. Поворотные коэффициенты
а — для N = 8; б —для N = 16

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

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

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

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

Алгоритмы с прореживанием по времени для длины N = 2^L требует L = \log_2(N) уровней разделения - объединения с использованием графа «бабочка».

При этом нижние два уровня (при расчете 2-точечного и 4-точечного ДПФ) используют только тривиальные умножения на поворотные коэффициенты W_2^0 = W_4^0 = 1 и W_4^1 = -j, которые можно не учитывать. Каждый из остальных L-2 этапов объединения требует \frac{N}{2} комплексных умножений. В результате общее количество требуемых операций комплексного умножения для алгоритмов БПФ с прореживанием по времени и по частоте равно

equation 1
(1)

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

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

equation 2
(2)
Напомним, что для наивного алгоритма ДПФ требуется
equation 3
(3)
операций комплексного умножения и сложения.

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

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

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

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

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

Существует множество библиотек с реализацией алгоритмов БПФ, однако можно выделить две наиболее эффективные реализации: 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].

Выводы

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

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

Список литературы
[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.

Последнее изменение страницы: 14.11.2020 (11:16:30)
Страница создана Latex to HTML translator ver. 5.20.11.14