Дискретное преобразование Фурье представляет собой частный случай преобразования Фурье, предложенного французским математиком и физиком Жан-Батистом Жозефом Фурье в 1807 году. Сегодня его модификации широко используются в теории обработки сигналов, сжатии звука, изображений и множестве других областей.
Быстрое преобразование Фурье (БПФ) - метод, основанный на использовании свойств комплексных корней из единицы и позволяющий вычислять Д П Ф Nза время меньшее чем О ( N 2 ) . В данной работе будет предложена эффективная параллельная реализация алгоритма быстрого преобразования Фурье, которая будет выполняться параллельно на р процессорах (р
Были реализованы следующие алгоритмы БПФ: Radix-2 DIT NR, Radix-2 DIT RN, Radix-2 DIT NN, Radix-2 DIF NR, Radix-2 DIF RN, Radix-2 DIF NN, Radix-4 DIT NR, Radix-4 DIT RN, Radix-4 DIT NN, Radix-4 DIF NR, Radix-4 DIF RN, Radix-4 DIF NN. Также были получены итеративная реализация алгоритма БПФ для составного N , и рекурсивная реализация Split-Radix DIT алгоритма. Были получены параллельные реализации следующих алгоритмов БПФ: Radix- 2 DIT NR, Radix-2 DIF NR, Radix-4 DIT NR, Radix-4 DIF NR. Также была получена параллельная реализация алгоритма БПФ для составного N. Реализации Radix-2 и Radix-4 алгоритмов потребовали использования объектов синхронизации. Кроме того, были получены реализации Radix-2 и Radix-4 DIT RN алгоритмов, не требующие использования объектов синхронизации.
Были сделаны следующие выводы: наиболее эффективным является использование параллельных DIT алгоритмов не требующих использования объектов синхронизации. Также подтвердилось, что в случае, когда дополнение вектора незначащими нулями недопустимо, выгодно использовать алгоритм для составного N.
