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

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

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

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

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

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

Основной шаг алгоритма состоит в сведении задачи для чисел к задаче для числам, где  — делитель . Пусть мы уже умеем решать задачу для чисел. Применим преобразование Фурье к наборам для . Покажем теперь, как за действий решить исходную задачу. Заметим, что . Выражения в скобках нам уже известны — это -тое число после преобразования Фурье -той группы. Таким образом, для вычисления каждого нужно действий, а для вычисления всех  — действий, что и требовалось получить.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

,

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

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

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

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

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

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