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

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

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

Основной алгоритм

[править | править код]
Амплитуды быстрого преобразования Фурье для разного количества компонент разложения . Первый случай: , где  — количество отсчётов сигнала; второй случай: ; третий: . В первом и последних случаях спектральные характеристики оцениваются менее точно. Данный эффект связан с явлением Гиббса[англ.].

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

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

Таким образом:

.

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

.

Далее вычисляется каждое , где , здесь по-прежнему требуется совершить действий, то есть на этом этапе производится операций.

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

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

Скорость алгоритма :

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

Обратное преобразование Фурье

[править | править код]

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

Общий случай

[править | править код]

Общий случай может быть сведён к предыдущему. Для имеет место:

.

Обозначая получается:

,

если положить при .

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

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

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

Вывод преобразования из дискретного

[править | править код]

Наиболее распространённым алгоритмом быстрого преобразования Фурье является алгоритм Кули — Тьюки, при котором дискретное преобразование Фурье от выражается как сумма дискретных преобразований Фурье более малых размерностей и рекурсивно для того, чтобы достичь сложность . Элементарный шаг сочленения меньших преобразований Фурье в этом алгоритме называется «бабочка». В вычислительной технике наиболее часто используется рекурсивное разложение преобразований надвое, то есть с основанием 2 (хотя может быть использовано любое основание), а количество входных отсчётов является степенью двойки. Для случаев, когда дискретное преобразование считается от количества отсчётов, являющихся простыми числами, могут быть использованы алгоритмы Блуштайна и Рейдера.

Например, для вычисления быстрого преобразования Фурье по алгоритму Кули — Тьюки с основанием 2 для вектора , состоящего из элементов:

,

с элементами вида:

дискретное преобразование можно выразить как сумму двух частей: сумму чётных индексов и сумму нечётных индексов :

.

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

В результате:

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

  • свойство периодичности ДПФ:
    ,
  • коэффициент поворота БПФ удовлетворяет следующему равенству:

В результате упрощений, обозначив дискретное преобразование Фурье чётных индексов через и преобразование нечётных индексов через , для получается:

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

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

Примечания

[править | править код]
  • Нуссбаумер Г. Быстрое преобразование Фурье и алгоритмы вычисления свёрток. — М.: Радио и связь, 1985.