2015-07-03
197
где
.
Учтем, что,
Поэтому
Графическое представление вычислительных операций приведено на рисунке.
Стрелочками представлены множители
.
Отсчеты 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.
4.4. Алгоритм БПФ с прореживанием по частоте
Пусть имеется исходная N - точечная последовательность xn, где N = 2M. Разобьем члены этой последовательности на две группы. В первую включим первую половину членов исходной последовательности, а во вторую группу - вторую половину. Из первой группы образуем последовательность x1m, а из второй - последовательность x2m.
Индексы последовательностей xn и x1m связаны соотношением n = m, а индексы последовательностей xn и x2m - соотношением n = N/ 2 + m.
Тогда
