Быстрое преобразование Фурье

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

Быстрое преобразование Фурье (БПФ, FFT) — алгоритм быстрого вычисления дискретного преобразования Фурье (ДПФ). То есть, алгоритм вычисления за количество действий, меньшее чем , требуемых для прямого (по формуле) вычисления ДПФ. Иногда под БПФ понимается один из быстрых алгоритмов, называемый алгоритмом прореживания по частоте/времени, имеющий сложность .

Введение[править | править вики-текст]

Дискретное преобразование Фурье преобразует набор чисел в набор чисел , такой, что , где и при . Алгоритм быстрого преобразования Фурье применим к любым коммутативным ассоциативным кольцам с единицей. Чаще всего этот алгоритм применяют к полю комплексных чисел (c ) и к кольцам вычетов (коим, в частности, является компьютерный целый тип).

Основной алгоритм[править | править вики-текст]

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

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

Дискретное преобразование Фурье может быть представлено в виде

(Эти выражения могут быть легко получено, если исходную сумму разбить на меньшее число сумм с меньшим числом слагаемых, а после, полученные суммы привести к одинаковому виду, путём сдвига индексов и их последующего переобозначения).

.

С учётом того, что и , окончательно можем записать

  1. Вычисляем каждое , где . Здесь по-прежнему требуется совершить действий. То есть на этом этапе производится операций.
  2. Далее считаем , где . Заменой в последней формуле, убеждаемся в том, что выражения стоящие в скобках остались неизменными. А так они уже были посчитаны на предыдущем шаге, то на вычисления каждого из них потребуется только действий. Всего чисел. Следовательно операций на этом шаге . Последнее с хорошей точностью верно при любых N. Но стоит также упомянуть, что алгоритм БПФ логично применять для , потому как при малом числе отсчётов он даёт небольший выигрыш в скорости по отношению к ДПФ.

Таким образом, для того чтобы полностью перейти к набору чисел , необходимо действий. Следовательно, нет разницы на какие два числа разбивать N — ответ от этого сильно не будет меняться. Уменьшено же число операций может быть только дальнейшим разбиением N.

Скорость алгоритма (N=pq):

Короче говоря, число операций при любом разбиении N на два числа, есть , где

Обратное преобразование Фурье[править | править вики-текст]

Для обратного преобразования Фурье можно применять алгоритм прямого преобразования Фурье — нужно лишь использовать вместо (или применить операцию комплексного сопряжения в начале к входным данным, а затем к результату, полученному после прямого преобразования Фурье) и окончательный результат поделить на .

Общий случай[править | править вики-текст]

Общий случай может быть сведён к предыдущему. Пусть . Заметим, что . Обозначим . Тогда , если положить при .

Таким образом задача сведена к вычислению свёртки, но это можно сделать с помощью трёх преобразований Фурье для элементов. Выполняем прямое преобразование Фурье для и , перемножаем поэлементно результаты и выполняем обратное преобразование Фурье.

Вычисления всех и требуют действий, три преобразования Фурье требуют действий, перемножение результатов преобразований Фурье требует действий, вычисление всех зная значения свертки требует действий. Итого для дискретного преобразования Фурье требуется действий для любого .

Этот алгоритм быстрого преобразования Фурье может работать над кольцом только когда известны первообразные корни из единицы степеней и .

Вывод преобразования из ДПФ[править | править вики-текст]

Наиболее распространенным алгоритмом БПФ является алгоритм Кули-Тьюки (Cooley–Tukey), при котором ДПФ от выражается как сумма ДПФ более малых размерностей и рекурсивно для того, чтобы достичь сложность . В вычислительной технике наиболее часто используется рекурсивное разложение ДПФ надвое, то есть с основанием 2, (хотя может быть использовано любое основание), а количество входных отсчетов является степенью двойки. Для случаев, когда ДПФ считается от количества отсчетов, являющихся простыми числами могут быть использованы алгоритмы Блуштайна и Рейдера.

Ниже рассмотрим наиболее простой способ вычисления БПФ по алгоритму Кули-Тьюки с основанием 2.

Дискретное преобразование Фурье для вектора , состоящего из N элементов, имеет вид:

элементы матрицы имеют вид: .

Взяв за основание 2, ДПФ можно выразить как сумму 2 частей: сумму четных индексов и сумму нечетных индексов :

Коэффициенты и можно переписать следующим образом:

В результате получаем:

Вычисление данного выражения можно упростить используя:

1. свойство периодичности ДПФ:

,

2. коэффициент поворота БПФ удовлетворяет следующему равенству:

В результате упрощений, обозначив ДПФ четных индексов через (англ., even — четный) и ДПФ нечетных индексов через (англ., odd — нечетный), для получаем:

Данная запись является базой алгоритма Кули-Тьюки с основанием 2 для вычисления БПФ. То есть ДПФ от вектора, состоящего из N отсчетов, приведено к линейной композиции двух ДПФ от отсчетов, и если для первоначальной задачи требовалось операций, то для полученной композиции — (за счет повторного использования промежуточных результатов вычислений и ). Если N является степенью двух, то это разделение можно продолжать рекурсивно до тех пор, пока не дойдем до двухточечного преобразования Фурье, которое вычисляется по следующим формулам:

При рекурсивном делении ДПФ от входных значений на сумму 2 ДПФ по входных значений сложность алгоритма становится равной .

См. также[править | править вики-текст]

Ссылки[править | править вики-текст]