Вычисления с замещением

Направленный граф для полного разложения восьмиточечного ДПФ в алгоритме с прореживанием по времени изображен на Рис. 1.7. На каждой ступени вычислений происходит преобразование множества из N комплексных чисел в другое множество из N комплексных чисел. Этот процесс повторяется раз, определяя в результате дискретное преобразование Фурье. Обозначим последовательность комплексных чисел, получающихся на m-ой ступени вычисления, через , где = и m=1,2,… . Можно считать входным массивом, а выходным массивом на m+1 ступени вычислений. Таким образом, для случая N=8:

; ; ;

; ; ;

Основным вычислением на графе является вычисление по схеме «бабочка» Рис. 1.8.

Рис. 1.7. Схема 8-точечного БПФ.

Рис. 1.8.

Рис. 1.9.

Уравнение, соответствующее этому графу, имеет вид:

(1.55)

Учитывая, что , получаем:

(1.56)

Следовательно, так как имеются N/2 бабочек вида (1.56) на каждую ступень и ступеней, общее требуемое число умножений . Ясно, что для вычисления элементов p и q m+1-го массива требуются комплексные числа, расположенные на местах p и q m-го массива. Поэтому реально необходим только один комплексный массив из N элементов.

Чтобы вычисления выполнялись так, как сказано выше, входные данные должны быть записаны в необычном порядке, который называется двоичной инверсией.

Если (n0,n1,n2) – двоичное представление номеров последовательности , то элемент последовательности x(n2n1n0) запоминается в массиве на месте X(n0n1n2).

; ; ;

; ; ;

; .

Объяснить этот факт можно с помощью следующей схемы:

Рис. 1.10.
Двоичная инверсия.

Рис. 1.11. Пример программы БПФ на языке C++.