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

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

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

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

Дискретное преобразование Фурье преобразует набор чисел ${\displaystyle a_{0},\dots ,a_{n-1}}$ в набор чисел ${\displaystyle b_{0},\dots ,b_{n-1}}$ , такой, что ${\textstyle b_{i}=\sum _{j=0}^{n-1}a_{j}\varepsilon ^{ij}}$ , где ${\displaystyle \varepsilon }$ — первообразный корень из единицы , то есть ${\textstyle \varepsilon ^{n}=1}$ и ${\textstyle \varepsilon ^{k}\neq 1}$ при ${\displaystyle 0<k<n}$ . Основной шаг алгоритма состоит в сведении задачи для ${\displaystyle N}$ чисел к задаче с меньшим числом. Для ${\displaystyle N=pq,p>1,q>1}$ над полем комплексных чисел вводятся: ${\textstyle \varepsilon _{\nu }=e^{2\pi i/\nu }}$ , ${\textstyle \varepsilon _{\nu }^{\nu }=1}$ , где ${\displaystyle \nu }$ — любое число. Дискретное преобразование Фурье может быть представлено в виде ${\textstyle b_{i}=\sum _{k=0}^{p-1}\sum _{j=0}^{q-1}a_{kq+j}\varepsilon _{N}^{(kq+j)i}}$ . (Эти выражения могут быть легко получены, если исходную сумму разбить на меньшее число сумм с меньшим числом слагаемых, а после полученные суммы привести к одинаковому виду путём сдвига индексов и их последующего переобозначения).

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

${\displaystyle 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)}$ .

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

${\displaystyle b_{i}=\sum _{j=0}^{q-1}\varepsilon _{N}^{ij}\left(\sum _{k=0}^{p-1}a_{kq+j}\varepsilon _{p}^{ki}\right)}$ .

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

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

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

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

1. ${\displaystyle p\gg q\longrightarrow O(Np)}$
2. ${\displaystyle p\sim q\longrightarrow O(Nq)}$
3. ${\displaystyle p\ll q\longrightarrow O(Nq)}$

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

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

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

Общий случай

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

${\displaystyle b_{i}=\varepsilon ^{-i^{2}/2}\sum _{j=0}^{N-1}\varepsilon ^{(i+j)^{2}/2}\varepsilon ^{-j^{2}/2}a_{j}}$ .

Обозначая ${\displaystyle {\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}}$ получается:

${\displaystyle {\bar {b}}_{i}=\sum _{j=0}^{2N-2-i}{\bar {a}}_{j}c_{2N-2-i-j}}$ ,

если положить ${\displaystyle {\bar {a}}_{i}=0}$ при ${\displaystyle i\geq N}$ .

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

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

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

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

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

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

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

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

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

дискретное преобразование можно выразить как сумму двух частей: сумму чётных индексов ${\textstyle m={2n}}$ и сумму нечётных индексов ${\textstyle m={2n+1}}$ :

${\displaystyle 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}}$ .

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

${\displaystyle 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}}$

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

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

${\displaystyle 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}}$

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

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

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

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

  ${\displaystyle {\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}}}$

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

${\displaystyle {\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 для вычисления быстрого преобразования Фурье, то есть дискретное преобразование от вектора, состоящего из ${\displaystyle N}$ отсчётов, приведено к линейной композиции двух дискретных преобразований Фурье от ${\textstyle {\frac {N}{2}}}$ отсчётов, и, если для первоначальной задачи требовалось ${\textstyle N^{2}}$ операций, то для полученной композиции — ${\textstyle {\frac {N^{2}}{2}}}$ (за счёт повторного использования промежуточных результатов вычислений ${\displaystyle E_{m}}$ и ${\displaystyle O_{m}}$ ). Если ${\displaystyle N}$ является степенью двух, то это разделение можно продолжать рекурсивно до тех пор, пока не доходит до двухточечного преобразования Фурье, которое вычисляется по следующим формулам:

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

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

Ссылки

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