Рис. 4.1 (см. скан) Структура модуля ДПФ
Таким образом, матрица ДПФ F разбиваются на две
-точечных циклических свертки
, отсюда минимальное число умножений для
Таблица 4.2 (см. скан)
алгоритма (4.20) равно
Число вещественных умножений
так как весовые коэффициенты в
и
являются действительными числами. Число вещественных сложений равно
где
— число сложений, требуемых для вычисления
точечных ЦС.
В табл. 4.2 приведены оценки числа арифметических операций для алгоритма (4.20) (оценки а взяты из [3]).
Как следует из табл. 4.1 и 4.2, вычислительная эффективность алгоритмов (4.13) и (4.20) примерно одинакова. Для размерностей 13 и 17 алгоритм (4.20) является более экономичным. Кроме того, алгоритм (4.20) перспективнее в случае применения распределенной арифметики с использованием
так как в этом случае требуется векторный вход размерностью
вместо полной размерности
.