Участник:Ivanov.kir.m/Быстрое дискретное преобразование Фурье

Алгоритм Кули-Тьюки одномерного преобразования Фурье для действительных чисел
Последовательный алгоритм
Последовательная сложность	[math]\displaystyle{ O (n \log n) }[/math]
Объём входных данных	[math]\displaystyle{ n }[/math] действительных чисел
Объём выходных данных	[math]\displaystyle{ \lfloor n/2 \rfloor+1 }[/math] комплексных чисел
Параллельный алгоритм
Высота ярусно-параллельной формы	[math]\displaystyle{ O (\log n) }[/math]
Ширина ярусно-параллельной формы	[math]\displaystyle{ n }[/math]

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

• Алгоритм Кули-Тьюки [1]
• Алгоритм Гуда-Томаса [2]
• Алгоритм Бруна [3]
• Алгоритм Блюштейна [4]

ЧАСТЬ. Свойства и структура алгоритмов

Общее описание алгоритма

Одним из вариантов быстрого преобразования Фурье для вектора действительных чисел с размерностью равной степени двойки является алгоритм Кули-Тьюки. Отличительной особенностью данного алгоритма является то, что он обходится без использования специфических приемов, использующихся именно для степеней четверки, восьмерки и т.п. Однако благодаря тому, что на вход данному алгоритму подается вектор чисто вещественных чисел, выходной вектор удовлетворяет эрмитовой избыточности (Hermitian redundancy) , т.е. [math]\displaystyle{ out[i] }[/math] является сопряженным с [math]\displaystyle{ out[n-i] }[/math]. Это обстоятельство позволяет достичь роста скорости и снижения затрат памяти примерно в 2 раза по сравнению с комплексным аналогом алгоритма.

Математическое описание алгоритма

Входные данные: вектор действительных чисел [math]\displaystyle{ a = (a_1,a_2,...,a_n) }[/math].

Выходные данные: вектор комплексных чисел [math]\displaystyle{ b = (b_1,b_2,...,b_{\lfloor n/2 \rfloor+1}) }[/math].

Замечание: В простейшем случае алгоритм Кули-Тьюки применяется к векторам размерности степени двойки, поэтому на практике вектора иной размерности часто дополнять до ближайшей степени двойки. Такой подход делает алгоритм Кули-Тьюки не самым эффективным алгоритмом БПФ, поскольку дополнение до степени двойки может сильно усложнить задачу.

Рекурсивное описание

Алгоритм:

1. Входной вектор [math]\displaystyle{ a = (a_1,a_2,...,a_n) }[/math] преобразуется в матрицу [math]\displaystyle{ A }[/math] размера [math]\displaystyle{ n_1 \times n_2 }[/math], где [math]\displaystyle{ n=n_1 \cdot n_2 }[/math] и [math]\displaystyle{ n_1 \lt n_2 }[/math]

[math]\displaystyle{ A = \begin{pmatrix} a_1 & a_2 & \cdots & a_{n_1} \\ a_{n_1+1} & a_{n_1} & \cdots & a_{2n_1} \\ \vdots & \vdots & \ddots & \vdots \\ a_{(n2-1)\cdot n1+1} & a_{(n2-1)\cdot n1+1} & \cdots & a_{n2\cdot n1} \end{pmatrix} }[/math]

1. К каждой строке полученной матрицы применяется быстрое дискретное преобразование Фурье (БПФ) порядка [math]\displaystyle{ n_1 }[/math]
2. Каждый элемент полученный после применения БПФ умножается на поворотные множители [math]\displaystyle{ exp (2 \pi i(m-1)(j-1)/n) }[/math], где [math]\displaystyle{ m }[/math] - номер строки, а [math]\displaystyle{ j }[/math] - номер столбца
3. Полученная после шагов 1-2 матрица [math]\displaystyle{ A }[/math] транспонируется
4. К каждой строке матрицы [math]\displaystyle{ A^T }[/math] применяется БПФ порядка [math]\displaystyle{ n_2 }[/math]

Замечание: Как правило все поворотные множители вычисляются заранее и хранятся в специальном массиве.

Вычислительное ядро алгоритма

В случае размерности входа равной степени двойки, вычислительным ядром алгоритма является, так называемая, "бабочка". В простейшем случае "бабочка" представляет из себя двухточечное преобразование. Рассмотрим этот случай:

На вход алгоритму подается двухэлементный вектор ‒ [math]\displaystyle{ v = (v[0], v[1]) }[/math]. Тогда для вычисления будут происходить по следующим формулам:

[math]\displaystyle{ V[0] = W_2^0 v[0] + W_2^0 v[1] = v[0] + W_2^0 v[1] }[/math]

[math]\displaystyle{ V[1] = W_2^0 v[0] + W_2^1 v[1] = v[0] + W_2^1 v[1] }[/math]

Данный процесс удобно изобразить с помощью следующей схемы:

Для 4-х элеметного вектора [math]\displaystyle{ v=(v[0],v[1],v[2],v[3]) }[/math], алгоритм строится похожим образом. Сначала создаются простейшие "бабочки", а потом их результаты соединяются с противоположеной "бабочкой":

[math]\displaystyle{ V[0]=v[0]+W_2^0 v[2]+W_4^0(v[1]+W_2^0 v[3]) }[/math]

[math]\displaystyle{ V[1]=v[0]-W_2^0 v[2]+W_4^1(v[1]-W_2^0 v[3]) }[/math]

[math]\displaystyle{ V[2]=v[0]+W_2^0 v[2]-W_4^0(v[1]+W_2^0 v[3]) }[/math]

[math]\displaystyle{ V[3]=v[0]-W_2^0 v[2]-W_4^1(v[1]-W_2^0 v[3]) }[/math]

Схема в таком случае будет выглядеть следующим образом:

Для случая, когда вход не является степенью двойки, "бабочки" будут "несимментричными", но в остальном вычисления будут проходить схожим образом.

Макроструктура алгоритма

Для исходного вектора [math]\displaystyle{ a = (a_1,a_2,...,a_n) }[/math] размерности [math]\displaystyle{ n = n_1 \cdot n_2 }[/math], [math]\displaystyle{ n_1 \lt n_2 }[/math] БПФ представляется как:

[math]\displaystyle{ n_2 }[/math] БПФ порядка [math]\displaystyle{ n_1 }[/math] [math]\displaystyle{ \Rightarrow }[/math] [math]\displaystyle{ n_1 \cdot n_2 }[/math] умножение комплексных чисел [math]\displaystyle{ \Rightarrow }[/math] [math]\displaystyle{ n_1 }[/math] БПФ порядка [math]\displaystyle{ n_2 }[/math]

Последовательная сложность алгоритма

Пусть [math]\displaystyle{ 4N\gt 2^k\ge2N }[/math]. Заметим, что [math]\displaystyle{ b_i=\varepsilon^{-i^2/2}\sum_{j=0}^{N-1}\varepsilon^{(i+j)^2/2}\varepsilon^{-j^2/2}a_j }[/math]. Обозначим [math]\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} }[/math]. Тогда [math]\displaystyle{ \bar{b}_i=\sum_{j=0}^{2N-2-i}\bar{a}_jc_{2N-2-i-j} }[/math], если положить [math]\displaystyle{ \bar{a}_i=0 }[/math] при [math]\displaystyle{ i\ge N }[/math].

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

Вычисления всех [math]\displaystyle{ \bar{a}_i }[/math] и [math]\displaystyle{ c_i }[/math] требуют [math]\displaystyle{ O(N) }[/math] действий, три преобразования Фурье требуют [math]\displaystyle{ O(N\log(N)) }[/math] действий, перемножение результатов преобразований Фурье требует [math]\displaystyle{ O(N) }[/math] действий, вычисление всех [math]\displaystyle{ b_i }[/math] зная значения свертки требует [math]\displaystyle{ O(N) }[/math] действий. Итого для дискретного преобразования Фурье требуется [math]\displaystyle{ O(N\log(N)) }[/math] действий для любого [math]\displaystyle{ N }[/math].

Литература

[1] Википедия [Электронный ресурс]. Тема: Быстрое преобразование Фурье – Электрон. дан. – URL Быстрое преобразование Фурье (дата обращения 17.09.2016)