БПФ с прореживанием по времени

Выделим в исходном ДПФ два слагаемых, соответствующих элементам исходной последовательности с четными и нечетными номерами:

.            (4.1)

Введем обозначения  и  и вынесем из второй суммы множитель . В этом случае можно записать:

.                               (4.2)

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

,                                            (4.3)

где  - ДПФ последовательности отсчетов с четными номерами;

 - ДПФ последовательности отсчетов с нечетными номерами.

Так как ДПФ размерностью  дает лишь  спектральных коэффициентов, то непосредственно использовать выражение (4.3) можно только при . Для остальных индексов  можно воспользоваться периодичностью спектра дискретного сигнала:

,

.

Соответственно, для аргументов  выражение (4.3) примет вид:

 

,  .                       (4.4)

 

Процесс вычисления 8-точечного ДПФ путем его разбиения на два 4-точечных ДПФ иллюстрируется рисунком 4.1.

Рисунок 4.1 – вычисление 8-точечного ДПФ с использованием двух 4-х точечных ДПФ

Объединение результатов двух ДПФ реализуется с помощью 4-х дополнительных блоков. Каждый из блоков имеет два входных и два выходных сигнала. Один из входных сигналов умножается на комплексную экспоненту , после чего суммируется со вторым сигналом и вычитается из него, формируя два выходных сигнала. Это соответствует реализации формул (4.3) и (4.4). Данная операция получила название «бабочки». Структура бабочки представлена на рисунке 4.2.

 

Рисунок 4.2 – условное обозначение «бабочки» и ее структурная схема при прореживании по времени

 

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

арифметических операций, что почти в 2 раза меньше, чем при вычислении ДПФ прямым способом.

Наибольшая степень ускорения вычислений может быть достигнута при продолжении деления последовательностей на две части до тех пор, пока не получатся двухэлементные последовательности. ДПФ двухэлементных последовательностей рассчитывается без использования операции умножения:

,

.

Алгоритм БПФ выполняется за следующее число этапов (деление на половинки):

.

Количество «бабочек» на каждом этапе одинаково и равно . Соответственно, результирующее число пар операций «умножение-сложение» равно:

.

 Например, при  достигается ускорение вычислений в 102.4 раза.

Экономия вычислительных затрат достигается за счет:

- объединения всех слагаемых, умножаемых на одинаковые множители;

- трансформации некоторых множителей в 1 или -1.