Так как , то

 

.

 

Здесь выражения в фигурных скобках представляют прямые ДПФ от последовательностей x₁[n] и x₂[n], половинной длины

 

(24)

 

Из формулы (1.164) следует, что N – точечное ДПФ X[k] может быть вычислено через два N/2 – точечных ДПФ и . Следует иметь в виду, что отсчеты ДПФ для последовательностей x₁[n] и x₂[n] повторяются с периодом N/2, поэтому

(25)

Учитывая, что из (1.164), получаем выражение для определения второй части последовательности спектральных коэффициентов X[k]:

 

(26)

 

Формулы (1.164), (1.166) представляют базовую операцию БПФ (так называемую «бабочку»). Схематическое изображение (1.164), (1.166) показано на рис.1.21. Здесь кружок в центре обозначает операцию сложения/вычитания. Стрелка обозначает операцию умножения на W_N^k. Жирные точки обозначают регистры, содержащие входные и выходные массивы для отдельных этапов БПФ.

На рис.1.22 показана схема вычисления 8 – точечного БПФ с использованием двух 4 – точечных преобразований.

Рис. 1.21 Основная операция БПФ –«бабочка»

Рис.1.22 Вычисление 8-точечного БПФ

 

В свою очередь 4 – точечные преобразования могут быть вычислены через 2 – точечные. Двухточечные БПФ могут быть вычислены по формулам:

(27)

. (28)

 

На рис.1.23 показан результирующий граф 8 – точечного БПФ.

Описанный алгоритм БПФ называется алгоритмом с прореживанием по времени, поскольку требуется перестановка входных значений x[n] (см. рис.1.23). Алгоритмы, при реализации которых требуется перестановка отсчетов X[k], называются алгоритмами с прореживанием по частоте.

Для каждой базовой операции БПФ необходимо выполнять только одно умножение X₂[k] на множитель W_N^k, поскольку произведение X₂[k]×W_N^k можно после вычисления запомнить. Входные и выходные значения базовых операций можно хранить в одних и тех же ячейках памяти. На одну базовую опера-

цию требуется одна дополнительная ячейка для хранения произведения X₂[k]×W_N^k. Поэтому для хранения входной x[n] и выходной последовательности X[k], а также промежуточных результатов можно использовать один и тот же массив ячеек памяти. Алгоритм БПФ, использующий ука

занные возможности, называют алгоритмом с замещением.

Рис.1.23 Результирующий граф 8-точечного БПФ