WikiSort.ru - Не сортированное

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

Введение

Дискретное преобразование Фурье преобразует набор чисел ${\displaystyle a_{0},\dots ,a_{n-1}}$ в набор чисел ${\displaystyle b_{0},\dots ,b_{n-1}}$ , такой, что ${\displaystyle b_{i}=\sum _{j=0}^{n-1}a_{j}\varepsilon ^{ij}}$ , где ${\displaystyle \varepsilon ^{n}=1}$ и ${\displaystyle \varepsilon ^{k}\neq 1}$ при ${\displaystyle 0<k<n}$ . Алгоритм быстрого преобразования Фурье применим к любым коммутативным ассоциативным кольцам с единицей. Чаще всего этот алгоритм применяют к полю комплексных чисел (c ${\displaystyle \varepsilon =e^{2\pi i/n}}$ ) и к кольцам вычетов (коим, в частности, является компьютерный целый тип).

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

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

Основной шаг алгоритма состоит в сведении задачи для ${\displaystyle N}$ чисел к задаче с меньшим числом. Пусть ${\displaystyle N=pq}$ , ${\displaystyle p>1,q>1}$ . Действуем над полем комплексных чисел: ${\displaystyle \varepsilon _{\nu }=e^{2\pi i/\nu }}$ , ${\displaystyle \varepsilon _{\nu }^{\nu }=1}$ , где ${\displaystyle \nu }$ - любое число.

Дискретное преобразование Фурье может быть представлено в виде ${\displaystyle 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}(\sum _{k=0}^{p-1}a_{kq+j}\varepsilon _{N}^{kiq})}$ .

С учётом того, что ${\displaystyle \varepsilon _{N}^{kiq}=\varepsilon _{N/q}^{ki}}$ и ${\displaystyle N/q=p}$ , окончательно можем записать ${\displaystyle b_{i}=\sum _{j=0}^{q-1}\varepsilon _{N}^{ij}(\sum _{k=0}^{p-1}a_{kq+j}\varepsilon _{p}^{ki})}$

1. Вычисляем каждое ${\displaystyle b_{i}}$ , где ${\displaystyle i={\overline {0,p-1}}}$ . Здесь по-прежнему требуется совершить ${\displaystyle O(N)}$ действий. То есть на этом этапе производится ${\displaystyle p\cdot O(N)=O(Np)}$ операций.
2. Далее считаем ${\displaystyle b_{i+mp}}$ , где ${\displaystyle i={\overline {0,p-1}},m={\overline {1,q-1}}}$ . Заменив ${\displaystyle i\longmapsto i+mp}$ в последней формуле, убеждаемся в том, что выражения, стоящие в скобках, остались неизменными. А так как они уже были посчитаны на предыдущем шаге, то на вычисление каждого из них потребуется только ${\displaystyle O(q)}$ действий. Всего ${\displaystyle p(q-1)=N-p}$ чисел. Следовательно, операций на этом шаге ${\displaystyle (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}}$ , необходимо ${\displaystyle O(Np)+O(Nq)}$ действий. Следовательно, нет разницы, на какие два числа разбивать ${\displaystyle N}$ — ответ от этого сильно не будет меняться. Уменьшено же число операций может быть только дальнейшим разбиением ${\displaystyle N}$ .

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

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

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

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

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

Общий случай

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

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

Вывод преобразования из ДПФ

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

Ниже рассмотрим наиболее простой способ вычисления БПФ по алгоритму Кули-Тьюки с основанием 2.

Дискретное преобразование Фурье для вектора ${\displaystyle {\vec {x}}}$ , состоящего из N элементов, имеет вид:

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

элементы матрицы ${\displaystyle {\hat {A}}}$ имеют вид: ${\displaystyle a_{N}^{mn}=e^{-{\frac {2\pi i}{N}}mn}}$ .

Взяв за основание 2, ДПФ можно выразить как сумму 2 частей: сумму четных индексов ${\displaystyle m={2n}}$ и сумму нечетных индексов ${\displaystyle 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}}$

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

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

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

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

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

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

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

См. также

• Бабочка (БПФ)

Ссылки

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

• Захаров С. И. Повышение эффективности вибродиагностики механизмов с помощью экспертных систем. М: Машиностроение//Вестник машиностроения, 2008, № 6, стр.31-32.
• БПФ по основанию 2 с прореживанием по времени (рус.). Проверено 15 ноября 2010. Архивировано 5 февраля 2012 года.
• БПФ по основанию 2 с прореживанием по частоте (рус.). Проверено 15 ноября 2010. Архивировано 5 февраля 2012 года.
• Полифазное БПФ (рус.). Проверено 15 ноября 2010. Архивировано 5 февраля 2012 года.