Главная > Разное > Методы синтеза быстрых алгоритмов свертки и спектрального анализа сигналов
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

5.3. Сравнение вычислительных характеристик алгоритма простых множителей и гнездового алгоритма

В табл. 5.2 приведены оценки удельного числа арифметических операций и объема памяти (ПЗУ и ОЗУ) для АПМ и ГА. В таблице рассмотрены размерности, близкие к

Из приведенных оценок следует, что для арифметических операций и объема памяти соотношения АПМ/ГА составляют

Таким образом, АПМ по многим показателям эффективнее, чем Кроме того, как было показано выше, АПМ имеет более простую структуру вычислений, так как состоит из независимых блоков

В общем виде поиск оптимального алгоритма необходимо проводить с использованием целевой функции вида

где соответственно число умножений, сложений, объем памяти, число перестановок; — весовые коэффициенты вычислительной сложности данных операций при конкретной реализации. При такой постановке задачи возможен при использовании гибридных алгоритмов, использующих смешанную факторизацию: гнездовую и построчно-столбцовую.

В общем виде такая задача к настоящему времени не решена. Примеры построения таких алгоритмов для некоторых частных случаев приведены в работах [14, 15]. В [16] разработан подход к построению квазиоптимальных алгоритмов БПФ данного класса путем покоординатной оптимизации функционала (5.15).

<< Предыдущий параграф Следующий параграф >>
Оглавление