БПФ

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

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


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

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

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

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

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

.

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

.

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

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

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

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

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

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

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

Общий случай[ | ]

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

.

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

,

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

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

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

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

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

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

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

,

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

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

.

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

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

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

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

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

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

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

Ссылки[ | ]

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