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

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

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

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

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

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

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

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

Входные данные: вектор действительных чисел $a = (a_1,a_2,...,a_n)$.

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

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

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

Алгоритм:

1. Входной вектор $a = (a_1,a_2,...,a_n)$ преобразуется в матрицу $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)*n1+1} & a_{(n2-1)*n1+1} & \cdots & a_{n2*n1} \end{pmatrix}$ размера $n_1 \times n_2$, где $n=n_1*n_2$ и $n_1 \lt n_2$
2. К каждой строке полученной матрицы применяется дискретное преобразование Фурье порядка $n_1$
3. Каждый элемент полученный после применения ДПФ умножается на поворотные множители (в наиболее простом случае, когда $n$ является степенью двойки повортный множитель равен $exp (2 \pi i(m-1)(j-1)/n)$, где $m$ - номер строки, а $j$ - номер столбца)
4. Полученная после шагов 1-3 матрица $A$ транспанируется
5. К каждой строке матрицы $A^T$ применяется ДПФ порядка $n_2$

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

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

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

$V[0] = W_2^0 v[0] + W_2^0 v[1] = v[0] + W_2^0 v[1]$

$V[1] = W_2^0 v[0] + W_2^1 v[1] = v[0] + W_2^1 v[1]$

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

[[5]]

3 Литература

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