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

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

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

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

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

Одним из вариантов быстрого преобразования Фурье для вектора действительных чисел с размерностью равной степени двойки является алгоритм Кули-Тьюки. Отличительной особенностью данного алгоритма является то, что он обходится без использования специфических приемов, использующихся именно для степеней четверки, восьмерки и т.п. Однако благодаря тому, что на вход данному алгоритму подается вектор чисто вещественных чисел, выходной вектор удовлетворяет эрмитовой избыточности (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. Входной вектор a = (a_1,a_2,...,a_n) дополняется элементами до ближайшей степени двойки Вектор записывается по строкам по 2 элемента в каждой. После этого над каждой строкой выполняется преобразование Фурье порядка 2, получившиеся элементы умножаются на поворотные множители [math]\displaystyle{ exp (2 \pi i(m-1)(j-1)/n) }[/math] ([math]\displaystyle{ m }[/math] - номер строки, [math]\displaystyle{ j }[/math] - номер столбца), после чего выполняется БПФ порядка [math]\displaystyle{ n/2 }[/math] над каждым из столбцов. Поскольку для 1-го столбца поворотные множители равны 1, то реально умножение на них не выполняется, а умножения на поворотные множители элементов второго столбца соединяются с преобразованием Фурье порядка 2. Эта комбинация, называемая "бабочкой" в среде специалистов по БПФ, и является основной операцией в простом алгоритме Кули-Тьюки. "Бабочка" состоит из вычисления суммы двух комплексных чисел, а также из вычисления их разности с последующим умножением на комплексное число. Всего на каждом шаге выполняется [math]\displaystyle{ n/2 }[/math] "бабочек", а шагов - [math]\displaystyle{ l-1 }[/math]. Последний, [math]\displaystyle{ l }[/math]-й шаг вычисляет только суммы и разности.

Литература

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