Алгоритм БПФ по основанию два с прореживанием по частоте

Введение
В предыдущем разделе был подробно рассмотрен алгоритм БПФ с прореживанием по времени.
Рассмотрим еще один способ разделения и объединения, который носит название прореживание по частоте.
Алгоритм БПФ с прореживанием по частоте
Пусть имеется отсчетов входного сигнала , , при этом представляет собой целую степень двойки .
В алгоритме БПФ с прореживанием по времени производилось разделение исходного сигнала в соответствии с двоично-инверсной перестановкой. Таким образом, мы получили первую и вторую половины дискретного преобразования Фурье (ДПФ).
В алгоритме с прореживанием по частоте исходный сигнал , , делится пополам, т.е. и , .
Тогда ДПФ сигнала может быть записано в виде:
(1)
Рассмотрим выражение (1) для спектральных отсчетов , , с четными индексами:
(2)
Учтем в выражении (2), что , а также , тогда получим:
(3)
Таким образом, спектральные отсчеты , , с четными индексами есть точечное ДПФ сигнала .
Аналогично рассмотрим выражение (1) для спектральных отсчетов , , с нечетными индексами:
(4)
Учтем в выражении (4), что , а также, что . Тогда выражение (4) можно представить в виде:
(5)
Спектральные отсчеты , , с нечетными индексами есть точечное ДПФ сигнала .
Таким образом, процедура разделения заключается в расчете сигналов половинной длительности и , . После чего можно заменить точечное ДПФ двумя точечными ДПФ сигналов и .
Граф «бабочка» алгоритма БПФ с прореживанием по частоте
Процедура расчета сигналов половинной длительности
(6)
может быть представлена в виде графа «бабочка», как это показано на рисунке 1.
Рисунок 1. Граф «бабочка» алгоритма БПФ с прореживанием по частоте
Отличие графа «бабочка» алгоритма с прореживанием по частоте от аналогичного графа для алгоритма с прореживанием по времени заключается в том, что умножение на поворотный коэффициент производится после вычитания ветвей. В графе «бабочка» алгоритма с прореживанием по времени умножение на поворотный коэффициент производилось до вычитания ветвей.
Полный граф алгоритма БПФ с прореживанием по частоте
Мы заменили расчет точечного ДПФ двумя точечными. В результате граф алгоритма БПФ с прореживанием по частоте для приведен на рисунке 2.
Рисунок 2. Граф алгоритма БПФ с прореживанием по частоте для
При этом каждое из точечных ДПФ также может быть рассчитано с использованием алгоритма с прореживанием по частоте. В результате получим полный граф алгоритма БПФ с прореживанием по частоте, как это показано на рисунке 3.
Рисунок 3. Полный граф алгоритма БПФ с прореживанием по частоте для
На первом этапе получаем и , в соответствии с (6):
(7)
Для расчета 4-точечных ДПФ сигналов и , , снова используем алгоритм с прореживанием по частоте. Тогда получим сигналы:
(8)
После расчета двухточечных ДПФ на последнем уровне разбиения получаем переставленные спектральные отсчеты:
(9)
которые мы должны подвергнуть двоично-инверсной перестановке аналогично тому, как производится эта процедура в алгоритме с прореживанием по времени.
Выводы
В данном разделе мы рассмотрели алгоритм БПФ по основанию два с прореживанием по частоте. В следующем разделе мы рассмотрим вычислительную эффективность алгоритмов БПФ по основанию два и некоторые вопросы программной реализации алгоритмов БПФ.
Список литературы
[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] Блейхут Р. Быстрые алгоритмы цифровой обработки сигналов. Москва, Мир, 1989.

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

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

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

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

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