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

7.6. Эффективность алгоритма БПФ

При непосредственном вычислении ДПФ, рассмотренном ранее и иллюстрируемом фиг. 7.9, для вычисления каждого из значений требуется комплексных умножений. Поскольку умножение — самая медленная из всех операций, выполняемых на ЦВМ, то время, необходимое для вычисления ДПФ таким способом, будет почти точно пропорционально

С другой стороны, исследуя направленный граф на фиг. 7.12 г находим, что БПФ требует комплексных умножений. Действительно, конечный или любой промежуточный массив получается из предыдущего с помощью взвешиваний, каждое из которых включает одно комплексное умножение. Всего таких циклов взвешивания причем

Для больших значений N БПФ значительно сокращает время вычислений. Например, если оказывается приблизительно в 100 раз быстрее обычного ДПФ.

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