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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

Основной алгоритм[править | править вики-текст]

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

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

Основной шаг алгоритма состоит в сведении задачи для N чисел к задаче для p=N/q числам, где q — делитель N. Пусть мы уже умеем решать задачу для N/q чисел. Применим преобразование Фурье к наборам a_i,a_{q+i}, \dots, a_{q(p-1)+i} для i=0,1,\dots,q-1. Покажем теперь, как за O(Np) действий решить исходную задачу. Заметим, что b_i=\sum_{j=0}^{q-1} \varepsilon^{ij} (\sum_{k=0}^{p-1}a_{kq+j}\varepsilon^{kiq}). Выражения в скобках нам уже известны — это i\pmod p-тое число после преобразования Фурье j-той группы. Таким образом, для вычисления каждого b_i нужно O(q) действий, а для вычисления всех b_i — O(Nq) действий, что и требовалось получить.

Обратное преобразование Фурье[править | править вики-текст]

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

Общий случай[править | править вики-текст]

Общий случай может быть сведён к предыдущему. Пусть 4N>2^k\ge2N. Заметим, что 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}_jc_{2N-2-i-j}, если положить \bar{a}_i=0 при i\ge N.

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

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

Вывод преобразования из ДПФ[править | править вики-текст]

Наиболее распространенным алгоритмом БПФ является алгоритм Кули-Тьюки (Cooley–Tukey), при котором ДПФ от N=N_1 N_2 выражается как сумма ДПФ более малых размерностей N_1 и N_2 рекурсивно для того, чтобы достичь сложность 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} .

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

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

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

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

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


\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}

В результате упрощений, обозначив ДПФ четных индексов x_{2m} через E_k (англ., even - четный) и ДПФ нечетных индексов x_{2m + 1} через O_k (англ., odd - нечетный), для 0 \leq 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 отсчетов, приведено к линейной композиции двух ДПФ от \frac N2 отсчетов, и если для первоначальной задачи требовалось N^2 операций, то для полученной композиции — \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 ДПФ по N/2 входных значений сложность алгоритма становится равной O(N\log(N)).

Пример программы[править | править вики-текст]

Ниже приведен пример расчета комплексного БПФ, написанный на С:

Ниже приведен пример вычисления модуля спектра действительного массива чисел на основе реализации быстрого преобразования Фурье, написанный на C++ :

Пример реализации на Delphi :

Пример реализации на C#

Графическое представление работы вышеприведенного алгоритма.

Ссылки[править | править вики-текст]

  • Преобразование Фурье — Суть метода, теоремы, физические эффекты при преобразовании реальных сигналов, примеры оптимизированных программ на C++.
  • Реализация преобразования Фурье на Delphi — Проект приложения Delphi с исходными кодами, реализующего преобразование сигнала, представленного в виде квадратурных составляющих I и Q.
  • Захаров С.И. Повышение эффективности вибродиагностики механизмов с помощью экспертных систем. М: Машиностроение//Вестник машиностроения, 2008, №6, стр.31-32.
  • FFTW — свободно распространяемая библиотека, написанная на С, поддерживает разложение n-мерного сигнала, представленного как вещественными, так и комплексными числами.  (англ.)