7.6. Сравнительные оценки вычислительной сложности алгоритмов БПФ с N=2^n

Приведем сравнительные характеристики рассмотренных БПФ размерности по следующим параметрам: числу нетривиальных арифметических операций: объему ОЗУ и ПЗУ; числу перестановок.

Оценки числа вещественных умножений и сложений для рассмотренных алгоритмов БПФ с приведены в табл. 7.1. В табл. 7.2 приведены

Таблица 7.2 (см. скан)

удельные оценки вдела операций перестановок данных и объема требуемой памяти. При определении оценок вычислительной эффективности принималось, что одно комплексное умножение соответствует трем вещественным умножениям и трем вещественным сложениям, одно комплексное сложение — двум вещественным сложениям, одно комплексное слово требует для хранения двух вещественных слов в ОЗУ, один комплексный коэффициент трех вещественных слов в ПЗУ.

На рис. 7.13 и 7.14 приведены оценки удельного вдела соответственно умножений и сложений для рассмотренных алгоритмов БПФ.

Рис. 7.13. Оценки удельного числа умножений для алгоритмов (кривые 1—8 определены в табл. 7.1)

Рис. 7.14. Оценки удельного числа сложений для алгоритмов