Прямые ДПФ последовательностей x1m и x2m выражаются следующими соотношениями

где

.

 

Учтем, что,

 

Поэтому

 

Графическое представление вычислительных операций приведено на рисунке.

Стрелочками представлены множители

.

Отсчеты S₀, S₁, S₂, S₃ получаются с использованием операции сложения, поэтому около них стоит знак “ + “, отсчеты S₄, S₅, S₆, S₇ находятся после выполнения операции вычитания и около них поставлен знак “ - “.

 

 

При N=2

 

Последовательности на входах четырех двухточечных блоков	Индексы членов исходной послед.	Индексы членов послед. после перестановки разрядов
Десятичная СС	Двоичная СС	Двоичная СС	Десятичная СС
X110 = X10 = X0
X111 = X12 = X4
X120 = X11= X2
X121 = X13 =X6
X210 = X20 = X1
X211 = X22 = X5
X220 = X21 = X3
X221 = X23 =X7

 

Подсчитаем количество операций умножения, которые нужно выполнить, используя алгоритм БПФ.

 

Номер шага разбиения	Количество умножений на постоянный коэффициент	Количество блоков ДПФ, подлежащих дальнейшему разбиению	Вид последовательности на входах оставшихся блоков
	N / 2		N / 2
	2 (N / 4) = N / 2		N / 4
	4 (N / 8) = N / 2		N / 8
. . .	. . .	. . .	. . .
M -1	N / 2	2 M -1	N / 2 M -1 = 2
M	N / 2	-	-

 

На каждом шаге разбиения выполняется N / 2 умножений, количество шагов равно M = log ₂ N.

Следовательно, количество умножений равно (N / 2) log₂ N вместо N² при ДПФ.

Величина выигрыша при переходе от ДПФ к БПФ увеличивается с увеличением количества отсчетов N.

 

2.4. Алгоритм БПФ с прореживанием по частоте

 

Пусть имеется исходная N - точечная последовательность x_n, где N = 2^M. Разобьем члены этой последовательности на две группы. В первую включим первую половину членов исходной последовательности, а во вторую группу - вторую половину. Из первой группы образуем последовательность x1_m, а из второй - последовательность x2_m.

Индексы последовательностей x_n и x1_m связаны соотношением n = m, а индексы последовательностей x_n и x2_m - соотношением n = N/ 2 + m.

Тогда