2015-02-04
542
где
.
Учтем, что,
Поэтому
Графическое представление вычислительных операций приведено на рисунке.
Стрелочками представлены множители
.
Отсчеты S0, S1, S2, S3 получаются с использованием операции сложения, поэтому около них стоит знак “ + “, отсчеты S4, S5, S6, S7 находятся после выполнения операции вычитания и около них поставлен знак “ - “.
Подсчитаем количество операций умножения, которые нужно выполнить, используя алгоритм БПФ.
| Номер шага разбиения | Количество умножений на постоянный коэффициент | Количество блоков ДПФ, подлежащих дальнейшему разбиению | Вид последовательности на входах оставшихся блоков |
| 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.
|
|
|
