Русская Википедия:Быстрое преобразование Фурье
Быстрое преобразование Фурье (БПФ, FFT) — алгоритм ускоренного вычисления дискретного преобразования Фурье, позволяющий получить результат за время, меньшее чем <math>O(N^2)</math> (требуемого для прямого, поформульного вычисления). Иногда под быстрым преобразованием Фурье понимается один из алгоритмов, называемый алгоритмом прореживания по частоте — времени, имеющий сложность <math>O(N\log(N))</math>.
Алгоритм применим к любым коммутативным ассоциативным кольцам с единицей, чаще применяют к полю комплексных чисел (c <math>\varepsilon=e^{2\pi i/n}</math>) и к кольцам вычетов (которым, в частности, является компьютерный целый тип).
Основной алгоритм
При применении основного алгоритма дискретное преобразование Фурье может быть выполнено за <math display="inline">O(N(p_1+\cdots+p_n))</math> действий при <math display="inline">N=p_1p_2\cdots p_n</math>, в частности, при <math>N=2^n</math> понадобится <math>O(N\log(N))</math> действий.
Дискретное преобразование Фурье преобразует набор чисел <math>a_0, \dots, a_{n-1}</math> в набор чисел <math>b_0, \dots, b_{n-1}</math>, такой, что <math display="inline">b_i=\sum_{j=0}^{n-1}a_j\varepsilon^{ij}</math>, где <math>\varepsilon</math> — первообразный корень из единицы, то есть <math display="inline">\varepsilon^n=1</math> и <math display="inline">\varepsilon^k\neq 1</math> при <math>0<k<n</math>. Основной шаг алгоритма состоит в сведении задачи для <math>N</math> чисел к задаче с меньшим числом. Для <math>N=pq, p>1, q>1</math> над полем комплексных чисел вводятся: <math display="inline">\varepsilon_\nu=e^{2\pi i/\nu}</math>, <math display="inline">\varepsilon_\nu^{\nu}=1</math>, где <math>\nu</math> — любое число. Дискретное преобразование Фурье может быть представлено в виде <math display="inline">b_i=\sum_{k=0}^{p-1}\sum_{j=0}^{q-1}a_{kq+j}\varepsilon_N^{(kq+j)i} </math>. (Эти выражения могут быть легко получены, если исходную сумму разбить на меньшее число сумм с меньшим числом слагаемых, а после полученные суммы привести к одинаковому виду путём сдвига индексов и их последующего переобозначения).
Таким образом:
- <math>b_i = \sum_{k=0}^{p-1}\sum_{j=0}^{q-1}a_{kq+j}\varepsilon_N^{(kq+j)i}=\sum_{j=0}^{q-1} \varepsilon_N^{ij} \left( \sum_{k=0}^{p-1}a_{kq+j}\varepsilon_N^{kiq} \right)</math>.
С учётом того, что <math>\varepsilon_N^{kiq}=\varepsilon_{N/q}^{ki}</math> и <math>N/q=p</math>, окончательная запись:
- <math>b_i=\sum_{j=0}^{q-1} \varepsilon_N^{ij} \left( \sum_{k=0}^{p-1}a_{kq+j}\varepsilon_p^{ki} \right)</math>.
Далее вычисляется каждое <math>b_i</math>, где <math>i=\overline{0,p-1}</math>, здесь по-прежнему требуется совершить <math>O(N)</math> действий, то есть на этом этапе производится <math>p\cdot O(N)=O(Np)</math> операций.
Далее считается <math>b_{i+mp}</math>, где <math display="inline">i=\overline{0,p-1}, m=\overline{1,q-1}</math>. При замене <math display="inline">i\longmapsto i+mp</math> в последней формуле, выражения, стоящие в скобках, остались неизменными, а так как они уже были посчитаны на предыдущем шаге, то на вычисление каждого из них потребуется только <math>O(q)</math> действий. Всего <math>p(q-1)=N-p</math> чисел. Следовательно, операций на этом шаге <math display="inline">(N-p)\cdot O(q)=O((N-1)q)\cong O(Nq)</math>. Последнее с хорошей точностью верно при любых <math>N</math>.
Алгоритм быстрого преобразования Фурье логично применять для <math>N\gg1</math>, потому как при малом числе отсчётов он даёт небольшой выигрыш в скорости по отношению к прямому расчёту дискретного преобразования Фурье. Таким образом, для того чтобы полностью перейти к набору чисел <math>b_0, \dots, b_{N-1}</math>, необходимо <math display="inline">O(Np)+O(Nq)</math> действий. Следовательно, нет разницы, на какие два числа разбивать <math>N</math> — ответ от этого сильно не будет меняться. Уменьшено же число операций может быть только дальнейшим разбиением <math>N</math>.
Скорость алгоритма <math>(N=pq)</math>:
- <math>p\gg q \longrightarrow O(Np)</math>
- <math>p\sim q \longrightarrow O(Nq)</math>
- <math>p\ll q \longrightarrow O(Nq)</math>
То есть число операций при любом разбиении <math>N</math> на два числа, есть <math>O(Nc)</math>, где <math>c=max(p,q)</math>.
Обратное преобразование Фурье
Для обратного преобразования Фурье можно применять алгоритм прямого преобразования Фурье — нужно лишь использовать <math>\varepsilon^{-1}</math> вместо <math>\varepsilon</math> (или применить операцию комплексного сопряжения вначале к входным данным, а затем к результату, полученному после прямого преобразования Фурье), и окончательный результат поделить на <math>N</math>.
Общий случай
Шаблон:Основная статья Общий случай может быть сведён к предыдущему. Для <math display="inline">4N>2^k\ge2N</math> имеет место:
- <math>b_i=\varepsilon^{-i^2/2}\sum_{j=0}^{N-1}\varepsilon^{(i+j)^2/2}\varepsilon^{-j^2/2}a_j</math>.
Обозначая <math>\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}</math> получается:
- <math>\bar{b}_i=\sum_{j=0}^{2N-2-i}\bar{a}_jc_{2N-2-i-j}</math>,
если положить <math>\bar{a}_i=0</math> при <math>i\ge N</math>.
Таким образом задача сведена к вычислению свёртки, но это можно сделать с помощью трёх преобразований Фурье для <math>2^k</math> элементов: выполняется прямое преобразование Фурье для <math display="inline">\{\bar{a}_i\}_{i=0}^{i=2^k-1}</math> и <math display="inline">\{c_i\}_{i=0}^{i=2^k-1}</math>, поэлементно перемножаются результаты, и выполняется обратное преобразование Фурье.
Вычисления всех <math>\bar{a}_i</math> и <math>c_i</math> требуют <math>O(N)</math> действий, три преобразования Фурье требуют <math>O(N\log(N))</math> действий, перемножение результатов преобразований Фурье требует <math>O(N)</math> действий, вычисление всех <math>b_i</math> зная значения свёртки требует <math>O(N)</math> действий. Итого для дискретного преобразования Фурье требуется <math display="inline">O(N\log(N))</math> действий для любого <math>N</math>.
Этот алгоритм быстрого преобразования Фурье может работать над кольцом только когда известны первообразные корни из единицы степеней <math>2N</math> и <math display="inline">2^k</math>.
Вывод преобразования из дискретного
Наиболее распространённым алгоритмом быстрого преобразования Фурье является алгоритм Кули — Тьюки, при котором дискретное преобразование Фурье от <math display="inline">N=N_1 N_2</math> выражается как сумма дискретных преобразований Фурье более малых размерностей <math>N_1</math> и <math>N_2</math> рекурсивно для того, чтобы достичь сложность <math display="inline">O(N\log(N))</math>. Элементарный шаг сочленения меньших преобразований Фурье в этом алгоритме называется «бабочка». В вычислительной технике наиболее часто используется рекурсивное разложение преобразований надвое, то есть с основанием 2 (хотя может быть использовано любое основание), а количество входных отсчётов является степенью двойки. Для случаев, когда дискретное преобразование считается от количества отсчётов, являющихся простыми числами, могут быть использованы алгоритмы Блуштайна и Рейдера.
Например, для вычисления быстрого преобразования Фурье по алгоритму Кули — Тьюки с основанием 2 для вектора <math> \vec x </math>, состоящего из <math>N</math> элементов:
- <math> \vec X = \hat A \vec x </math>,
с элементами <math> \hat A </math> вида:
- <math> a_{N}^{mn} = e^ { -\frac{2\pi i}{N} mn} </math>
дискретное преобразование можно выразить как сумму двух частей: сумму чётных индексов <math display="inline">m={2n}</math> и сумму нечётных индексов <math display="inline">m={2n+1}</math>:
- <math> 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}</math>.
Коэффициенты <math> a_{N}^{2nm} </math> и <math> a_{N}^{(2n+1)m} </math> можно переписать следующим образом:
- <math> 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} </math>
- <math> a_{N}^{(2n+1)m} = e^ \left( -2\pi i \frac{m}{N} \right) a_{N/2}^{nm} </math>
В результате:
- <math> 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} </math>
Вычисление данного выражения можно упростить, используя:
- свойство периодичности ДПФ:
- <math> a_{N/2}^{(m+\frac{N}{2})n} = a_{N/2}^{nm} </math>,
- коэффициент поворота БПФ удовлетворяет следующему равенству:
- <math>
\begin{matrix} e^{\frac{-2\pi i}{N} (m + N/2)} & = & e^{\frac{-2\pi i m}{N} - {\pi i}} \\ & = & e^{-\pi i} e^{\frac{-2\pi i m}{N}} \\ & = & -e^{\frac{-2\pi i m}{N}} \end{matrix} </math> В результате упрощений, обозначив дискретное преобразование Фурье чётных индексов <math>x_{2m}</math> через <math display="inline">E_m</math> и преобразование нечётных индексов <math display="inline">x_{2m + 1}</math> через <math>O_m</math>, для <math display="inline">0 \leqslant m < \frac{N}{2}</math> получается:
- <math>
\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} </math>
Данная запись является базой алгоритма Кули — Тьюки с основанием 2 для вычисления быстрого преобразования Фурье, то есть дискретное преобразование от вектора, состоящего из <math>N</math> отсчётов, приведено к линейной композиции двух дискретных преобразований Фурье от <math display="inline">\frac N2</math> отсчётов, и, если для первоначальной задачи требовалось <math display="inline">N^2</math> операций, то для полученной композиции — <math display="inline">\frac{N^2}{2} </math> (за счёт повторного использования промежуточных результатов вычислений <math>E_m</math> и <math>O_m</math>). Если <math>N</math> является степенью двух, то это разделение можно продолжать рекурсивно до тех пор, пока не доходит до двухточечного преобразования Фурье, которое вычисляется по следующим формулам:
- <math>
\begin{cases} X_0=x_0+x_1\\ X_1=x_0-x_1 \end{cases} </math> При рекурсивном делении дискретного преобразования Фурье от <math>N</math> входных значений на сумму 2 дискретных преобразований по <math display="inline">N/2</math> входных значений сложность алгоритма становится равной <math display="inline">O(N\log(N))</math>.
Ссылки
