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

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

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

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

Амплитуды быстрого преобразования Фурье для разного количества компонент разложения

N

. Первый случай:

N=L-10

, где

L

— количество отсчётов сигнала; второй случай:

N=L

; третий:

N=L+10

. В первом и последних случаях спектральные характеристики оцениваются менее точно. Данный эффект связан с явлением Гиббса^[англ.].

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

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

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)

.

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

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

.

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

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

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

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

$p\gg q\longrightarrow O(Np)$
$p\sim q\longrightarrow O(Nq)$
$p\ll q\longrightarrow O(Nq)$

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

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

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

Общий случай

Общий случай может быть сведён к предыдущему. Для ${\textstyle 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}$ элементов: выполняется прямое преобразование Фурье для ${\textstyle \{{\bar {a}}_{i}\}_{i=0}^{i=2^{k}-1}}$ и ${\textstyle \{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)$ действий. Итого для дискретного преобразования Фурье требуется ${\textstyle O(N\log(N))}$ действий для любого $N$ .

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

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

Наиболее распространённым алгоритмом быстрого преобразования Фурье является алгоритм Кули — Тьюки, при котором дискретное преобразование Фурье от ${\textstyle N=N_{1}N_{2}}$ выражается как сумма дискретных преобразований Фурье более малых размерностей $N_{1}$ и $N_{2}$ рекурсивно для того, чтобы достичь сложность ${\textstyle 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}

дискретное преобразование можно выразить как сумму двух частей: сумму чётных индексов ${\textstyle m={2n}}$ и сумму нечётных индексов ${\textstyle 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}

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

свойство периодичности ДПФ:
$a_{N/2}^{(m+{\frac {N}{2}})n}=a_{N/2}^{nm}$ ,
коэффициент поворота БПФ удовлетворяет следующему равенству:
${\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}$ через ${\textstyle E_{m}}$ и преобразование нечётных индексов ${\textstyle x_{2m+1}}$ через $O_{m}$ , для ${\textstyle 0\leqslant 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$ отсчётов, приведено к линейной композиции двух дискретных преобразований Фурье от ${\textstyle {\frac {N}{2}}}$ отсчётов, и, если для первоначальной задачи требовалось ${\textstyle N^{2}}$ операций, то для полученной композиции — ${\textstyle {\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 дискретных преобразований по ${\textstyle N/2}$ входных значений сложность алгоритма становится равной ${\textstyle O(N\log(N))}$ .

См. также

Примечания

Ссылки

Имеется викиучебник по теме «Быстрое преобразование Фурье»

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