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

где

.

Учтем, что,

Поэтому

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

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

.

Отсчеты 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.

Тогда