17. Оценка алгоритма бпф

Быстрое преобразование Фурье (БПФ) - это алгоритм вычисления преобразования Фурье для дискретного случая. В отличие от простейшего алгоритма, который имеет сложность порядка O(N²), БПФ имеет сложность всего лишь O(Nlog₂N).

Вычислительная эффективность алгоритма БПФ с прореживанием по времени

Алгоритм с прореживанием по времени на каждом уровне требует комплексных умножений и сложений. Приколичество уровней разложения — объединения равно, таким образом общее количество операций умножения и сложения равно.

Рассмотрим во сколько раз алгоритм БПФ с прореживанием по времени эффективнее ДПФ. Для этого рассмотрим коэффициент ускорения отношение количества комплексных умножение и сложений при использовании ДПФ и БПФ, при этом учтем что:

В таблице ниже приведено требуемое количество операций для алгоритма ДПФ при различноми при использовании БПФ с прореживанием по времени.

Использование БПФ приводит к существенному уменьшению требуемого количества вычислительных операций. Так например при БПФ требует в 100 раз меньше операций чем ДПФ, а прив 341 раз! При этом очень важно, что выигрыш по производительности тем больше, чем больше размер выборки. Так например привыигрыш составитраз.

Сравнение алгоритмов БПФ по основанию 2 с прореживанием по времени и частоте

Таким образом можно сравнить алгоритм БПФ с прореживанием по частоте с алгоритмом БПФ с прореживанием по времени:

1. В обоих алгоритмах используется двоично-инверсная перестановка. В алгоритме с прореживанием по времени она используется вначале, в алгоритме с прореживанием по частоте — в конце.

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

3. В связи с вышесказанным, вычислительная эффективность обоих алгоритмов практически идентична.