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

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

Алгоритм применим к любым коммутативным ассоциативным кольцам с единицей, чаще применяют к полю комплексных чисел (c $\epsilon =e^{2\pi i/n}$) и к кольцам вычетов (которым, в частности, является компьютерный целый тип).

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

Амплитуды быстрого преобразования Фурье для разного количества компонент разложения $N$. Первый случай: $N=L-10$, где $L$ — количество отсчётов сигнала; второй случай: $N=L$; третий: $N=L+10$. В первом и последних случаях спектральные характеристики оцениваются менее точно. Данный эффект связан с Шаблон:Iw.

При применении основного алгоритма дискретное преобразование Фурье может быть выполнено за $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{\epsilon }^{ij}$, где $\epsilon$ — первообразный корень из единицы, то есть ${\epsilon }^n=1$ и ${\epsilon }^k\ne 1$ при $0<k<n$. Основной шаг алгоритма состоит в сведении задачи для $N$ чисел к задаче с меньшим числом. Для $N=pq,p>1,q>1$ над полем комплексных чисел вводятся: ${\epsilon }_{\nu }=e^{2\pi i/\nu }$, ${\epsilon }_{\nu }^{\nu }=1$, где $\nu$ — любое число. Дискретное преобразование Фурье может быть представлено в виде $b_i={\sum }_{k=0}^{p-1}{\sum }_{j=0}^{q-1}{a}_{kq+j}{\epsilon }_N^{(kq+j)i}$. (Эти выражения могут быть легко получены, если исходную сумму разбить на меньшее число сумм с меньшим числом слагаемых, а после полученные суммы привести к одинаковому виду путём сдвига индексов и их последующего переобозначения).

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

$b_i=\sum _{k=0}^{p-1}\sum _{j=0}^{q-1}{a}_{kq+j}{\epsilon }_N^{(kq+j)i}=\sum _{j=0}^{q-1}{\epsilon }_N^{ij}\left(\sum _{k=0}^{p-1}{a}_{kq+j}{\epsilon }_N^{kiq}\right)$.

С учётом того, что ${\epsilon }_N^{kiq}={\epsilon }_{N/q}^{ki}$ и $N/q=p$, окончательная запись:

$b_i=\sum _{j=0}^{q-1}{\epsilon }_N^{ij}\left(\sum _{k=0}^{p-1}{a}_{kq+j}{\epsilon }_p^{ki}\right)$.

Далее вычисляется каждое $b_i$, где $i=\overline{0,p-1}$, здесь по-прежнему требуется совершить $O(N)$ действий, то есть на этом этапе производится $p\cdot O(N)=O(Np)$ операций.

Далее считается $b_{i+mp}$, где $i=\overline{0,p-1},m=\overline{1,q-1}$. При замене $i⟼i+mp$ в последней формуле, выражения, стоящие в скобках, остались неизменными, а так как они уже были посчитаны на предыдущем шаге, то на вычисление каждого из них потребуется только $O(q)$ действий. Всего $p(q-1)=N-p$ чисел. Следовательно, операций на этом шаге $(N-p)\cdot O(q)=O((N-1)q)\cong O(Nq)$. Последнее с хорошей точностью верно при любых $N$.

Алгоритм быстрого преобразования Фурье логично применять для $N\gg 1$, потому как при малом числе отсчётов он даёт небольшой выигрыш в скорости по отношению к прямому расчёту дискретного преобразования Фурье. Таким образом, для того чтобы полностью перейти к набору чисел $b_0,\dots ,b_{N-1}$, необходимо $O(Np)+O(Nq)$ действий. Следовательно, нет разницы, на какие два числа разбивать $N$ — ответ от этого сильно не будет меняться. Уменьшено же число операций может быть только дальнейшим разбиением $N$.

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

1. $p\gg q⟶O(Np)$
2. $p\sim q⟶O(Nq)$
3. $p\ll q⟶O(Nq)$

То есть число операций при любом разбиении $N$ на два числа, есть $O(Nc)$, где $c=max(p,q)$.

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

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

Общий случай

Шаблон:Основная статья Общий случай может быть сведён к предыдущему. Для $4N>2^k\ge 2N$ имеет место:

$b_i={\epsilon }^{-i^2/2}\sum _{j=0}^{N-1}{\epsilon }^{(i+j{)}^2/2}{\epsilon }^{-j^2/2}{a}_j$.

Обозначая ${\overline{a}}_i={\epsilon }^{-i^2/2}{a}_i,{\overline{b}}_i={\epsilon }^{i^2/2}{b}_i,c_i={\epsilon }^{(2N-2-i{)}^2/2}$ получается:

${\overline{b}}_i=\sum _{j=0}^{2N-2-i}{\overline{a}}_j{c}_{2N-2-i-j}$,

если положить ${\overline{a}}_i=0$ при $i\ge N$.

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

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

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

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

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

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

$\overrightarrow{X}=\hat{A}\overrightarrow{x}$,

с элементами $\hat{A}$ вида:

$a_N^{mn}=e^{-\frac{2\pi i}{N}mn}$

дискретное преобразование можно выразить как сумму двух частей: сумму чётных индексов $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^{(-2\pi i\frac{2mn}{N})}=e^{(-2\pi i\frac{mn}{N/2})}=a_{N/2}^{nm}$

$a_N^{(2n+1)m}=e^{(-2\pi i\frac{m}{N})}{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}$

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

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

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

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

  $\begin{array}{ccc}{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{array}$

В результате упрощений, обозначив дискретное преобразование Фурье чётных индексов $x_{2m}$ через $E_m$ и преобразование нечётных индексов $x_{2m+1}$ через $O_m$, для $0⩽m<\frac{N}{2}$ получается:

$\begin{array}{ccc}{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{array}$

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

$\{\begin{array}{c}{X}_0=x_0+x_1\\ X_1=x_0-x_1\end{array}$

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

См. также

• Ряд Фурье
• Преобразование Фурье
• Дискретное преобразование Фурье

Ссылки

• Шаблон:Книга