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

При применении основного алгоритма дискретное преобразование Фурье может быть выполнено за ${\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.