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

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

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

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

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

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

3 Литература

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