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

где

Учтем, что,

Поэтому

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

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

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

При N=2

Последовательности на входах четырех двухточечных блоков	Индексы членов исходной послед.	Индексы членов послед. после перестановки разрядов
Десятичная СС	Двоичная СС	Двоичная СС	Десятичная СС
X11₀= X1₀ = X₀
X11₁= X1₂ = X₄
X12₀ = X1₁= X₂
X12₁ = X1₃ =X₆
X21₀= X2₀ = X₁
X21₁ = X2₂ = X₅
X22₀ = X2₁ = X₃
X22₁ = X2₃ =X₇

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

Номер шага разбиения	Количество умножений на постоянный коэффициент	Количество блоков ДПФ, подлежащих дальнейшему разбиению	Вид последовательности на входах оставшихся блоков
	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.

Тогда