Так как , то

.

Здесь выражения в фигурных скобках представляют прямые ДПФ от последовательностей 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-точечного БПФ

Важной особенностью рассматриваемых алгоритмов БПФ является необходимость перестановки входных или выходных значений. Элементы входной последовательности для алгоритма с прореживанием по времени должны быть расположены в памяти в бит–инверсном порядке. Бит–инверсный порядок задается путем «зеркального» отображения двоичных разрядов входной последовательности (табл.1.3).

Бит-инверсный порядок Таблица 1.3.

N	Двоичный номер	бит инверсия	бит-инверсный номер

На всех этапах выполнения БПФ используются коэффициенты W_N^k, k =0,1,…N-1. Обычно указанные значения вычисляют до выполнения БПФ и хранят в таблице, к которой можно обращаться в процессе счета.

Количество этапов в процессе вычисления БПФ равно log2N, количество “бабочек” на каждом этапе - N/2. Так как в процессе БПФ используются комплексные числа, то каждая «бабочка» БПФ сопровождается четырьмя операциями умножения и четырьмя операциями сложения. Поэтому количество парных операций умножение-сложение равно 2N log2N. При больших N применение алгоритма БПФ существенно сокращает количество операций по сравнению с ДПФ.