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

Содержание
Введение
В предыдущих разделах мы рассмотрели алгоритмы БПФ по основанию два с прореживанием по времени и по частоте. В данном разделе мы проанализируем их вычислительную эффективность и некоторые приемы программной реализации алгоритмов БПФ.
Для анализа приведем еще раз полные графы алгоритмов БПФ с прореживанием по времени (рисунок 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 \cdot \frac{\pi}{4})$, $W_8^2 = -j$ и $W_8^3 = \exp(-j \cdot \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}$ комплексных умножений. В результате общее количество требуемых операций комплексного умножения для алгоритмов БПФ с прореживанием по времени и по частоте равно
\begin{equation} \text{MUL}_{\text{FFT}} = \frac{N}{2} \cdot (\log_2(N) - 2). \end{equation}
(1)
Количество операций комплексного сложения (вычитания) на каждом уровне объединения равно $N$. Таким образом, общее количество операций комплексного сложения (вычитания) алгоритма БПФ с прореживанием по времени и частоте равно
\begin{equation} \text{SUM}_{\text{FFT}} = N \cdot \log_2(N). \end{equation}
(2)
Напомним, что для наивного алгоритма ДПФ требуется
\begin{equation} \text{MUL}_{\text{DFT}} = \text{SUM}_{\text{DFT}} = N^2 \end{equation}
(3)
операций комплексного умножения и сложения.
Алгоритмы БПФ с прореживанием по времени и частоте уменьшают количество требуемых операций комплексного умножения в
\begin{equation} \frac{\text{MUL}_{\text{DFT}}}{\text{MUL}_{\text{FFT}}} = \frac{N^2}{\frac{N}{2} \cdot (\log_2(N) - 2)} = \frac{2\cdot N}{\log_2(N) - 2} \end{equation}
(4)
раз, а количество требуемых операций комплексного сложения в
\begin{equation} \frac{\text{SUM}_{\text{DFT}}}{\text{SUM}_{\text{FFT}}} = \frac{N^2}{N \cdot \log_2(N)} = \frac{N}{\log_2(N)} \end{equation}
(5)
раз.
Так например для $N = 1024$ расчет БПФ требует в 256 раз меньше операций комплексного умножения, и в 102.4 раза меньше операций комплексного сложения. При этом с ростом $N$ экономия умножителей и сумматоров только растет.
Таким образом, практическое использование алгоритма БПФ с прореживанием по времени, позволяет достичь очень высокой вычислительной эффективности, по сравнению с наивным методом расчета ДПФ.
Обзор библиотек реализующих алгоритмы БПФ
Существует множество библиотек с реализацией алгоритмов БПФ, однако можно выделить две наиболее эффективные реализации: FFTW и Intel® Math Kernel Library (Intel® MKL).
Библиотека FFTW разработана Маттэо Фриго (Matteo Frigo) и Стивеном Джонсоном (Steven G. Johnson) в Массачусетском технологическом институте. Данная библиотека распространяется под лицензией GNU GPL и MIT и находит применение в таких программных продуктах как MATLAB, GNU Octave и многих других.
Библиотека Intel® Math Kernel Library (Intel® MKL) помимо алгоритмов БПФ предоставляет множество функций линейной алгебры, оптимизированных для процессоров Intel. К сожалению данная библиотека является платной.
Сравнительный анализ различных библиотек БПФ приведен в [2].
Библиотека DSPL также использует функции библиотеки FFTW для расчета дискретного преобразования Фурье. Кроме того, поддерживается многопоточность FFTW, что позволяет получить максимальную производительность на многоядерных процессорах.
Таким образом, используя DSPL вы получите «под капотом» многопоточную FFTW с максимальной производительностью БПФ.
Справку по использованию функций DSPL для быстрого преобразования Фурье вы можете получить в соответствующем разделе.
Выводы
В данном разделе мы рассмотрели свойства поворотных коэффициентов и вычислительную эффективность алгоритмов БПФ по основанию два. Было показано что алгоритм с прореживанием по частоте и алгоритм с прореживанием по времени имеют одинаково высокую эффективность, которая растет с ростом размера выборки БПФ.
Также был произведен обзор наиболее эффективных библиотек программной реализации алгоритмов БПФ.

Ваши комментарии, вопросы и пожелания вы можете оставить на форуме или в гостевой книге.
Список литературы
[1] James W. Cooley and John W. Tukey An Algorithm for the Machine Calculation of Complex Fourier Series. Mathematics of Computation, 1965 p. 297–301.

[2] Matteo Frigo and Steven G. Johnson The Design and Implementation of FFTW3. Proceedings of the IEEE, 93(2), 2005, p. 216–231

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

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

[5] А. Оппенгейм, Р. Шафер Цифровая обработка сигналов. Москва, Техносфера, 2006.

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

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

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

Oбнаружили ошибку в тексте? Выделите ее мышкой и нажмите
Описание (необязательно)
Закрыть Х