где
.
Учтем, что,
Поэтому
Графическое представление вычислительных операций приведено на рисунке.
Стрелочками представлены множители
.
Отсчеты S0, S1, S2, S3 получаются с использованием операции сложения, поэтому около них стоит знак “ + “, отсчеты S4, S5, S6, S7 находятся после выполнения операции вычитания и около них поставлен знак “ - “.
При 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 2 N.
Следовательно, количество умножений равно (N / 2) log2 N вместо N2 при ДПФ.
Величина выигрыша при переходе от ДПФ к БПФ увеличивается с увеличением количества отсчетов N.
2.4. Алгоритм БПФ с прореживанием по частоте
Пусть имеется исходная N - точечная последовательность xn, где N = 2M. Разобьем члены этой последовательности на две группы. В первую включим первую половину членов исходной последовательности, а во вторую группу - вторую половину. Из первой группы образуем последовательность x1m, а из второй - последовательность x2m.
Индексы последовательностей xn и x1m связаны соотношением n = m, а индексы последовательностей xn и x2m - соотношением n = N/ 2 + m.
Тогда
