Главная       Скачать       Коммерческая поддержка       FAQ       Forum       О нас       Английская версия

Быстрое преобразование Фурье

Дискретное преобразование Фурье трансформирует последовательность комплексных (либо вещественных) чисел x в последовательность комплексных чисел X. Прямое и обратное преобразования Фурье определяются, как:

Приведенные выше формулы имеют сложность O(N 2), однако широко известен способ снизить сложность дискретного преобразования Фурье до O(N·log(N)). Быстрое преобразование Фурье широко используется как само по себе, так и для ускорения вычисления других преобразований - быстрого вычисления свертки и кросс-корреляции.

Реализация быстрого преобразования Фурье в ALGLIB

Пакет ALGLIB поддерживает быстрые преобразования Фурье комплексных последовательностей любой длины. В случае, если длина преобразования N является составным числом, используется алгоритм Cooley-Tukey, сводящий исходное преобразование Фурье к более коротким преобразованиям, соответствующим простым множителям N. Преобразования короткой длины (N ≤ 5) вычисляются с использованием специальных формул для коротких преобразований; более длинные преобразования, соответствующие простому N или крупным простым множителям составного N, вычисляются с использование алгоритма Блюштейна (Bluestein). В результате алгоритм имеет быстродействие O(N·log(N)) для любого N - простого или составного. Вместе с тем, некоторые преобразования вычисляются быстрее других. Если длина преобразования - простое число или составное число с крупными простыми множителями, то такое преобразование может потребовать в 4-6 раз больше времени, чем если бы длина была близким составным числом с малыми простыми множителями.

Вещественное быстрое преобразование Фурье в ALGLIB

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

Таким образом, если длина преобразования - четное число, то вещественное преобразование будет примерно в два раза быстрее комплексного. Если же длина преобразования - нечетное число, то скорость вещественного преобразования не будет отличаться от скорости комплексного преобразования той же длины.

Manual entries

C++ fft subpackage   
C# fft subpackage   

This article is intended for personal use only.

Скачать ALGLIB

C#

Исходный код на C#

Downloads page

 

C++

Исходный код на C++

Downloads page

 

C++, арифметика высокой точности

Исходный код на C++, использующий библиотеки MPFR/GMP.

Исходный код GMP доступен на сайте gmplib.org. Исходный код MPFR доступен на сайте www.mpfr.org.

Downloads page

 

FreePascal

Исходный код на Free Pascal.

Downloads page

 

Delphi

Исходный код на Delphi.

Downloads page

 

VB.NET

Исходный код на VB.NET.

Downloads page

 

VBA

Исходный код на VBA.

Downloads page

 

Python

Исходный код на Python (CPython и IronPython).

Downloads page

 

 

ALGLIB® - numerical analysis library, 1999-2017.
ALGLIB is registered trademark of the ALGLIB Project.