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

Определение:

Быстрое преобразование Фурье (англ. Fast Fourier Transform (FFT)) — это метод, позволяющий вычислять дискретное преобразование Фурье за время [math]O(nlogn)[/math].

Алгоритм построения БПФ

Метод основывается на том, что степени одних комплексных корней единицы в степени [math]n[/math] дают другие.

Идея заключается в том, что сначала мы разделяем вектор коэффициентов на два вектора, рекурсивно вычисляем значение ДПФ для них, и объединяем их в одно ДПФ.

Пусть имеется многочлен [math]A(x)[/math] степени [math]n[/math], где [math]n \gt 1, n = 2^t[/math]. Если [math]n[/math] не является степенью двойки, добавим недостающие члены и положим коэффициенты равными нулю.

[math] A(x) = a_0 x^0 + a_1 x^1 + \ldots + a_{n-1} x^{n-1} [/math]

Разделим [math]A(x)[/math] на два многочлена, где один будет с четными, а другой с нечетными коэффициентами:

• [math] A_0(x) = a_0 x^0 + a_2 x^1 + \ldots + a_{n-2} x^{\frac{n}{2} - 1} [/math]

• [math] A_1(x) = a_1 x^0 + a_3 x^1 + \ldots + a_{n-1} x^{\frac{n}{2} - 1} [/math]

Многочлен [math]A(x)[/math] получается из [math]A_0(x)[/math] и [math]A_1(x)[/math] следующим образом:

[math]A(x) = A_0(x^2) + xA_1(x^2) \ \ \ \ \ (1)[/math]

Мы разбили исходный многочлен на два многочлена, имеющих вдвое меньшую степень. Нам необходимо по вычисленным [math]DFT(A_0)[/math] и [math]DFT(A_1)[/math] за линейное время вычислить [math]DFT(A)[/math]. Так как здесь используется идея "разделяй и властвуй", то асимптотическая оценка будет [math]O(nlogn)[/math].

Пусть [math]DFT(A_0) = \{y_k^0\}^{\frac{n}{2}-1}_{k=0}[/math] и [math]DFT(A_1) = \{y_k^1\}^{\frac{n}{2} - 1}_{k=0}[/math]. Найдем вектор значений [math]DFT(A) = \{y_k\}^{n-1}_{k=0}[/math].

• Из [math](1)[/math] получаем значения для первой половины коэффициентов:

[math]y_k = y_k^0 + \omega^k_n y_k^1, \ \ k = 0 \ldots \dfrac{n}{2} - 1 [/math]

• Для второй половины получаем:

[math]y_{k+\frac{n}{2}}= A(\omega_n^{k+\frac{n}{2}})= A_0(\omega_n^{2k+n})+ \omega_n^{k+\frac{n}{2}} A_1(\omega_n^{2k+n})= [/math] [math]A_0(\omega_n^{2k} \omega_n^{n})+ \omega_n^k \omega_n^{\frac{n}{2}} A_1(\omega_n^{2k} \omega_n^n) [/math]

Заметим, что [math] \omega_n^n = 1, \omega_n^{\frac{n}{2}} = -1[/math], тогда:

[math]y_{k+\frac{n}{2}}= A_0(\omega_n^{2k})- \omega_n^k A_1(\omega_n^{2k})= y_k^0- \omega_n^k y_k^1[/math].

Таким образом, мы получили:

[math]y_k = y_k^0 + \omega^k_n y_k^1, \ \ k = 0 \ldots \dfrac{n}{2} - 1 [/math]

[math]y_{k+\frac{n}{2}}= y_k^0- \omega_n^k y_k^1, \ \ k = 0 \ldots \dfrac{n}{2} - 1 [/math].

Алгоритм построения обратного БПФ

Пусть вектор [math]y_0, y_1, \ldots , y_{n-1}[/math] — значения многочлена [math]A[/math] степени [math]n[/math] в точках [math]n = \omega_n^k[/math]. Необходимо, по данному вектору восстановить коэффициенты [math](a_0, a_1, \ldots , a_{n-1})[/math] многочлена.