Быстрое дискретное преобразование Фурье (БПФ)

Авторы: Чачба А.Н., Костоев Р.С.

Быстрое преобразование Фурье (БПФ)
Последовательный алгоритм
Последовательная сложность	[math]O(N \log N)[/math]
Объём входных данных	[math]N[/math]
Объём выходных данных	[math]N[/math]
Параллельный алгоритм
Высота ярусно-параллельной формы	[math]O(\log N)[/math]
Ширина ярусно-параллельной формы	[math]O(N)[/math]

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

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

Преобразование Фурье - взаимно однозначное отображение одной функции вещественной, называемой таргетным сигналом, с другой функцией вещественной переменной, называемой образом Фурье или спектром исходной функции по формуле:

[math] \hat{f}(\omega)=\frac{1}{\sqrt{2\pi}}\int\limits_{-\infty}^{\infty}f(x)e^{-ix\omega}\,dx [/math]

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

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

Пусть исходный сигнал имеет значения [math]x_n,\quad n = 0,\dots,N-1[/math], тогда дискретное прямое преобразование Фурье (ДПФ) имеет вид:

[math] X_k = \sum_{n=0}^{N-1}x_ne^{-\frac{2\pi i}{N}kn},\quad k = 0, \dots, N-1 [/math]

Обозначим [math] \varepsilon_{N} = e^{-\frac{2\pi i}{N}}[/math], тогда ДПФ можно перезаписать в матричной форме:

[math] \bar X = A\bar x [/math]

где матрица [math]A = \{e^{-\frac{2\pi i}{N}(i - 1)(j - 1)}\}_{i,j=1}^{N}[/math]