4.1.1. Бпф с прореживанием по времени
Рассмотрим идею БПФ с прореживанием по времени (decimation in time, DIT) на примере деления набора отсчетов пополам.
Пусть N – четное число. Выделим в формуле (4.1.1) два слагаемых, соответствующих элементам исходной последовательности с четными и нечетными номерами:
Введем обозначения y(m)=x(2m) и z(m)=x(2m+1), а также вынесем из второй суммы общий множитель e-j2πn/N:
Две суммы в (4.1.2) представляют собой ДПФ последовательностей {y(m)} (отсчеты с четными номерами) и {z(m)} (отсчеты с нечетными номерами). Каждое из этих ДПФ имеет размерность N/2. Таким образом,
Где Y(n) и Z(n) – ДПФ, соответственно, последовательностей отсчетов с четными и нечетными номерами:
Так как ДПФ размерности N/2 дает лишь N/2 спектральных коэффициентов, непосредственно использовать формулу (4.1.3) можно только при 0 ≤ n < N/2. Для остальных n (N/2 ≤ n < N) следует воспользоваться периодичностью спектра дискретного сигнала (и, соответственно, периодичностью результатов ДПФ):
С учетом этого при n ≥ N/2 формула (4.1.3) представляется в виде
(4.1.4)
Процесс вычисления 8-точечного ДПФ путем разбиения его на два 4-точечных ДПФ иллюстрируется на рис. 4.1.1. На этом рисунке использовано следующее обозначение для комплексных экспонент:
Рис. 4.1.1 Вычисление 8-точечного ДПФ с помощью двух 4-точечных ДПФ
Блоки, выполняющие на рис. 4.1.1 объединение результатов двух ДПФ, требуют дополнительных комментариев. Каждый такой блок имеет два входных и два выходных сигнала. Один из входных сигналов умножается на комплексную экспоненту , после чего суммируется со вторым входным сигналом и вычитается из него, формируя таким образом два входных сигнала. Это соответствует реализации формул (4.1.3) и (4.1.4). Данная операция получила название «бабочки» (butterfly). Расшифровка ее структуры представлена на рис. 4.1.2
Оценим количество операций, необходимое для вычисления ДПФ указанным способом. Каждое из двух ДПФ половинной размерности требует N2/4 операций.
Рис.4.1.2 Условное обозначение «бабочки» БПФ с прореживанием по времени (слева) и ее структурная схема (справа)
Кроме того, при вычислении окончательных результатов каждый спектральный коэффициент (n) умножается на экспоненциальный комплексный множитель. Это добавляет еще N/2 операции. Итого получается
что почти вдвое меньше, чем при вычислении ДПФ прямым способом.
Если N/2 тоже является четным числом (то есть если N делится на 4), можно продолжить описанную процедуру, выразив результат через четыре ДПФ размерности N/4. Это позволяет еще больше сократить число требуемых вычислительных операций.
Наибольшая степень ускорения вычислений может быть достигнута при N=2k, в этом случае деление последовательностей можно продолжать до тех пор, пока не получатся двухэлементные последовательности, ДПФ которых рассчитывается вообще без использования операций умножения (достаточно вычислить сумму и разность двух отсчетов). Число требуемых при этом пар операций «умножение-сложение» можно оценить как N log2(N). Таким образом, вычислительные затраты по сравнению с непосредственным использованием формулы (4.1.1) уменьшаются в N/log2(N) раз. При больших N это отношение становится весьма велико (например, 1024/log2(1024)=102.4, то есть при N=1024 достигается более чем стократное ускорение).