Алгоритм быстрого преобразования Фурье. Оценка эффективности

Алгоритм с прореживанием во времени.

. Введем обозначение . Эта величина называется фазовым, поворачивающим множителем.

Свойства фазового множителя:

1) – периодичность с периодом

2)

3)

4)

Поскольку дискретный спектр рассматривается в точках (), то если вычислять его непосредственно по формуле , потребуется раз выполнить по операций умножений и по операций сложения комплексных чисел. Так как преобразование вычисляется на ЭВМ, то общее вермя его выполнения (без учета служебных операций) равно . Возрастание вычислительной сложности ДПФ, пропорциональное квадрату длины, вызывает необходимость разработки алгоритмов БПФ.

Одна из основных идей БПФ заключается в том, что исходная -точечная последовательность разбивается на несколько более коротких последовательностей, дискретные спектры которых могут быть скомбинированы таким оразом, чтобы в итоге получилось ДПФ полной последовательности.

Разобьем длины на две подпоследовательности, в первую из которых войдут четные, а во вторую – нечетные элементы исходной последовательности:

, , .

Тогда -точечное ДПФ разбивается на два слагаемых:

при . Из свойств фазового множителя . Это позволяет в два раза сократить число используемых значений фазового множителя.

По свойствам спектров .

Окончательно, для

Полученное соотношение определяет операцию объединения «половинных» ДПФ в целое. Ее часто изображают графически.

Замечание 1. На входе должны быть в двоично-инверсионном порядке

Замечание 2. Всё преобразование выполняется на одном и том же мете без использования дополнительной памяти. ,

Замечание 3. Схема БПФ годится и для обратного ПФ – достаточно заменить множитель.