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

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

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

Покажем, как выполнить дискретное преобразование Фурье за $O(N(p_{1}+\cdots +p_{n}))$ действий при $N=p_{1}p_{2}\cdots p_{n}$. В частности, при $N=2^{n}$ понадобится $O(N\log(N))$ действий.

Дискретное преобразование Фурье преобразует набор чисел $a_{0},\dots ,a_{n-1}$ в набор чисел $b_{0},\dots ,b_{n-1}$, такой, что $b_{i}=\sum _{j=0}^{n-1}a_{j}\varepsilon ^{ij}$, где $\varepsilon ^{n}=1$ и $\varepsilon ^{k}\neq 1$ при $0<k<n$. Алгоритм быстрого преобразования Фурье применим к любым коммутативным ассоциативным кольцам с единицей. Чаще всего этот алгоритм применяют к полю комплексных чисел (c $\varepsilon =e^{2\pi i/n}$) и к кольцам вычетов (коим, в частности, является компьютерный целый тип).

Основной шаг алгоритма состоит в сведении задачи для $N$ чисел к задаче для $p=N/q$ числам, где $q$ — делитель $N$. Пусть мы уже умеем решать задачу для $N/q$ чисел. Применим преобразование Фурье к наборам $a_{i},a_{q+i},\dots ,a_{q(p-1)+i}$ для $i=0,1,\dots ,q-1$. Покажем теперь, как за $O(Np)$ действий решить исходную задачу. Заметим, что $b_{i}=\sum _{j=0}^{q-1}\varepsilon ^{ij}(\sum _{k=0}^{p-1}a_{kq+j}\varepsilon ^{kiq})$. Выражения в скобках нам уже известны — это $i{\pmod {p}}$-тое число после преобразования Фурье $j$-той группы. Таким образом, для вычисления каждого $b_{i}$ нужно $O(q)$ действий, а для вычисления всех $b_{i}$ — $O(Nq)$ действий, что и требовалось получить.

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

Для обратного преобразования Фурье можно применять алгоритм прямого преобразования Фурье — нужно лишь использовать $\varepsilon ^{-1}$ вместо $\varepsilon$ (или применить операцию комплексного сопряжения в начале к входным данным, а затем к результату, полученному после прямого преобразования Фурье) и окончательный результат поделить на $N$.

Общий случай

Общий случай может быть сведён к предыдущему. Пусть $4N>2^{k}\geq 2N$. Заметим, что $b_{i}=\varepsilon ^{-i^{2}/2}\sum _{j=0}^{N-1}\varepsilon ^{(i+j)^{2}/2}\varepsilon ^{-j^{2}/2}a_{j}$. Обозначим ${\bar {a}}_{i}=\varepsilon ^{-i^{2}/2}a_{i},{\bar {b}}_{i}=\varepsilon ^{i^{2}/2}b_{i},c_{i}=\varepsilon ^{(2N-2-i)^{2}/2}$. Тогда ${\bar {b}}_{i}=\sum _{j=0}^{2N-2-i}{\bar {a}}_{j}c_{2N-2-i-j}$, если положить ${\bar {a}}_{i}=0$ при $i\geq N$.

Таким образом задача сведена к вычислению свёртки, но это можно сделать с помощью трёх преобразований Фурье для $2^{k}$ элементов. Выполняем прямое преобразование Фурье для $\{{\bar {a}}_{i}\}_{i=0}^{i=2^{k}-1}$ и $\{c_{i}\}_{i=0}^{i=2^{k}-1}$, перемножаем поэлементно результаты и выполняем обратное преобразование Фурье.

Вычисления всех ${\bar {a}}_{i}$ и $c_{i}$ требуют $O(N)$ действий, три преобразования Фурье требуют $O(N\log(N))$ действий, перемножение результатов преобразований Фурье требует $O(N)$ действий, вычисление всех $b_{i}$ зная значения свертки требует $O(N)$ действий. Итого для дискретного преобразования Фурье требуется $O(N\log(N))$ действий для любого $N$.

Этот алгоритм быстрого преобразования Фурье может работать над кольцом только когда известны первообразные корни из единицы степеней $2N$ и $2^{k}$.

Вывод преобразования из ДПФ

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

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

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

${\vec {X}}={\hat {A}}{\vec {x}}$

элементы матрицы ${\hat {A}}$ имеют вид: $a_{N}^{mn}=e^{-{\frac {2\pi i}{N}}mn}$.

Взяв за основание 2, ДПФ можно выразить как сумму 2 частей: сумму четных индексов $m={2n}$ и сумму нечетных индексов $m={2n+1}$:

$X_{m}=\sum _{n=0}^{N-1}x_{n}a_{N}^{mn}=\sum _{n=0}^{N/2-1}x_{2n}a_{N}^{2nm}+\sum _{n=0}^{N/2-1}x_{2n+1}a_{N}^{(2n+1)m}$

Коэффициенты $a_{N}^{2nm}$ и $a_{N}^{(2n+1)m}$ можно переписать следующим образом:

$a_{N}^{2nm}=e^{\left(-2\pi i{\frac {2mn}{N}}\right)}=e^{\left(-2\pi i{\frac {mn}{N/2}}\right)}=a_{N/2}^{nm}$

$a_{N}^{(2n+1)m}=e^{\left(-2\pi i{\frac {m}{N}}\right)}a_{N/2}^{nm}$

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

$X_{m}=\sum _{n=0}^{N/2-1}x_{2n}a_{N/2}^{nm}+e^{-{\frac {2\pi i}{N}}m}\sum _{n=0}^{N/2-1}x_{2n+1}a_{N/2}^{nm}$

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

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

$a_{N/2}^{(m+{\frac {N}{2}})n}=a_{N/2}^{nm}$,

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

${\begin{matrix}e^{{\frac {-2\pi i}{N}}(m+N/2)}&=&e^{{\frac {-2\pi im}{N}}-{\pi i}}\\&=&e^{-\pi i}e^{\frac {-2\pi im}{N}}\\&=&-e^{\frac {-2\pi im}{N}}\end{matrix}}$

В результате упрощений, обозначив ДПФ четных индексов $x_{2m}$ через $E_{k}$ (англ., even — четный) и ДПФ нечетных индексов $x_{2m+1}$ через $O_{k}$ (англ., odd — нечетный), для $0\leq m<{\frac {N}{2}}$ получаем:

${\begin{matrix}X_{m}&=&E_{m}+e^{-{\frac {2\pi i}{N}}m}O_{m}\\X_{m+{\frac {N}{2}}}&=&E_{m}-e^{-{\frac {2\pi i}{N}}m}O_{m}\end{matrix}}$

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

${\begin{cases}X_{0}=x_{0}+x_{1}\\X_{1}=x_{0}-x_{1}\end{cases}}$

При рекурсивном делении ДПФ от $N$ входных значений на сумму 2 ДПФ по $N/2$ входных значений сложность алгоритма становится равной $O(N\log(N))$.

См. также

• Бабочка (БПФ)

Ссылки

• Захаров С. И. Повышение эффективности вибродиагностики механизмов с помощью экспертных систем. М: Машиностроение//Вестник машиностроения, 2008, № 6, стр.31-32.
• БПФ по основанию 2 с прореживанием по времени  (рус.). Дата обращения: 15 ноября 2010. Архивировано 5 февраля 2012 года.
• БПФ по основанию 2 с прореживанием по частоте  (рус.). Дата обращения: 15 ноября 2010. Архивировано 5 февраля 2012 года.
• Полифазное БПФ  (рус.). Дата обращения: 15 ноября 2010. Архивировано 5 февраля 2012 года.