Эффективность алгоритмов БПФ
DSPL-2.0 — свободная библиотека алгоритмов цифровой обработки сигналов Распространяется под лицензией LGPL v3
Страница проекта на SourceForge
|
В предыдущих разделах мы рассмотрели алгоритмы БПФ по основанию два с прореживанием по времени и по частоте. В данном разделе мы проанализируем их вычислительную эффективность и некоторые приемы программной реализации алгоритмов БПФ.
Для анализа приведем еще раз полные графы алгоритмов БПФ с прореживанием по времени (рисунок 1) и по частоте (рисунок 2).
Можно заметить, что полные графы алгоритмов БПФ по времени и по частоте являются практическим точным зеркальным отражением друг друга. В обоих алгоритмах используется двоично-инверсная перестановка. В алгоритме с прореживанием по времени она используется вначале, в алгоритме с прореживанием по частоте — в конце. В обоих алгоритмах используются одни и те же поворотные коэффициенты.
В итоге, вычислительная эффективность обоих алгоритмов эквивалентна.
Рассмотрим подробнее поворотные коэффициенты 
используемые как в алгоритме БПФ с прореживанием по времени,
так и в алгоритме БПФ с прореживанием по частоте.
На нижнем уровне разделения-объединения, при вычислении 2-точечного ДПФ,
требуется всего один поворотный коэффициент 
.
Это означает что на нижнем уровне разделения операции умножения не требуются
(умножение на единицу называется тривиальным).
На втором уровне разделения-объединения, при вычислении 4-точечного ДПФ,
имеем два поворотных коэффициента: 
и 
.
Умножения на 
также являются тривиальными, потому что реальная и мнимая части множителя
меняются местами и изменяется знак при мнимой части.
На третьем уровне имеем четыре поворотных коэффициента:
, 
, 
и 
.
Графически поворотные коэффициенты можно представить как векторы на комплексной плоскости (смотри рисунок 3a).
а — для
; б —для 
Можно заметить, что на всех уровнях объединения количество поворотных коэффициентов удваивается, причем все поворотные коэффициенты предыдущего уровня объединения присутствуют и на следующем уровне. Таким образом, для того чтобы перейти на следующий уровень необходимо между поворотными коэффициентами текущего уровня вставить поворотные коэффициенты следующего.
Графически для перехода на следующий уровень при 
необходимо дополнить
рисунок 3а как это показано на рисунке 3б.
Синие векторы показывают поворотные коэффициенты которые будут присутствовать на последнем уровне при
, которых нет при 
.
Алгоритмы с прореживанием по времени для длины 
требует
уровней разделения - объединения с использованием графа «бабочка».
При этом нижние два уровня (при расчете 2-точечного и 4-точечного ДПФ) используют только тривиальные умножения
на поворотные коэффициенты 
и , которые можно не учитывать.
Каждый из остальных 
этапов объединения требует 
комплексных умножений.
В результате общее количество требуемых операций комплексного умножения
для алгоритмов БПФ с прореживанием по времени и по частоте равно
Количество операций комплексного сложения (вычитания) на каждом уровне объединения равно 
.
Таким образом, общее количество операций комплексного сложения (вычитания) алгоритма БПФ с прореживанием по времени и частоте равно
Алгоритмы БПФ с прореживанием по времени и частоте уменьшают количество требуемых операций комплексного умножения в
Так например для 
расчет БПФ требует в 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].
В данном разделе мы рассмотрели свойства поворотных коэффициентов и вычислительную эффективность алгоритмов БПФ по основанию два. Было показано что алгоритм с прореживанием по частоте и алгоритм с прореживанием по времени имеют одинаково высокую эффективность, которая растет с ростом размера выборки БПФ.
Также был произведен обзор наиболее эффективных библиотек программной реализации алгоритмов БПФ.