Изменения
Новая страница: «{{Определение |definition= '''Быстрое преобразование Фурье''' (англ. ''Fast Fourier Transform (FFT)'') {{---}} это м...»
{{Определение
|definition=
'''Быстрое преобразование Фурье''' (англ. ''Fast Fourier Transform (FFT)'') {{---}} это метод, позволяющий вычислять дискретное преобразование Фурье за время <tex>O(nlogn)</tex>.
}}
== Алгоритм построения БПФ ==
Метод основывается на том, что степени одних комплексных корней единицы в степени <tex>n</tex> дают другие.
Идея заключается в том, что сначала мы разделяем вектор коэффициентов на два вектора, рекурсивно вычисляем значение ДПФ для них, и объединяем их в одно ДПФ.
Пусть имеется многочлен <tex>A(x)</tex> степени <tex>n</tex>, где <tex>n > 1, n = 2^t</tex>. Если <tex>n</tex> не является степенью двойки, добавим недостающие члены и положим коэффициенты равными нулю.
<tex> A(x) = a_0 x^0 + a_1 x^1 + \ldots + a_{n-1} x^{n-1} </tex>
Разделим <tex>A(x)</tex> на два многочлена, где один будет с четными, а другой с нечетными коэффициентами:
* <tex> A_0(x) = a_0 x^0 + a_2 x^1 + \ldots + a_{n-2} x^{\frac{n}{2} - 1} </tex>
* <tex> A_1(x) = a_1 x^0 + a_3 x^1 + \ldots + a_{n-1} x^{\frac{n}{2} - 1} </tex>
Многочлен <tex>A(x)</tex> получается из <tex>A_0(x)</tex> и <tex>A_1(x)</tex> следующим образом:
<tex>A(x) = A_0(x^2) + xA_1(x^2) \ \ \ \ \ (1)</tex>
Мы разбили исходный многочлен на два многочлена, имеющих вдвое меньшую степень. Нам необходимо по вычисленным <tex>DFT(A_0)</tex> и <tex>DFT(A_1)</tex> за линейное время вычислить <tex>DFT(A)</tex>. Так как здесь используется идея "разделяй и властвуй", то асимптотическая оценка будет <tex>O(nlogn)</tex>.
Пусть <tex>DFT(A_0) = \{y_k^0\}^{\frac{n}{2}-1}_{k=0}</tex> и <tex>DFT(A_1) = \{y_k^1\}^{\frac{n}{2} - 1}_{k=0}</tex>. Найдем вектор значений <tex>DFT(A) = \{y_k\}^{n-1}_{k=0}</tex>.
* Из <tex>(1)</tex> получаем значения для первой половины коэффициентов:
<tex>y_k = y_k^0 + \omega^k_n y_k^1, \ \ k = 0 \ldots \dfrac{n}{2} - 1 </tex>
* Для второй половины получаем:
<tex>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})= </tex> <tex>A_0(\omega_n^{2k} \omega_n^{n})+ \omega_n^k \omega_n^{\frac{n}{2}} A_1(\omega_n^{2k} \omega_n^n) </tex>
Заметим, что <tex> \omega_n^n = 1, \omega_n^{\frac{n}{2}} = -1</tex>, тогда:
<tex>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</tex>.
Таким образом, мы получили:
<tex>y_k = y_k^0 + \omega^k_n y_k^1, \ \ k = 0 \ldots \dfrac{n}{2} - 1 </tex>
<tex>y_{k+\frac{n}{2}}= y_k^0- \omega_n^k y_k^1, \ \ k = 0 \ldots \dfrac{n}{2} - 1 </tex>.
== Алгоритм построения обратного БПФ ==
Пусть вектор <tex>y_0, y_1, \ldots , y_{n-1}</tex> {{---}} значения многочлена <tex>A</tex> степени <tex>n</tex> в точках <tex>n = \omega_n^k</tex>. Необходимо, по данному вектору восстановить коэффициенты <tex>(a_0, a_1, \ldots , a_{n-1})</tex> многочлена.
|definition=
'''Быстрое преобразование Фурье''' (англ. ''Fast Fourier Transform (FFT)'') {{---}} это метод, позволяющий вычислять дискретное преобразование Фурье за время <tex>O(nlogn)</tex>.
}}
== Алгоритм построения БПФ ==
Метод основывается на том, что степени одних комплексных корней единицы в степени <tex>n</tex> дают другие.
Идея заключается в том, что сначала мы разделяем вектор коэффициентов на два вектора, рекурсивно вычисляем значение ДПФ для них, и объединяем их в одно ДПФ.
Пусть имеется многочлен <tex>A(x)</tex> степени <tex>n</tex>, где <tex>n > 1, n = 2^t</tex>. Если <tex>n</tex> не является степенью двойки, добавим недостающие члены и положим коэффициенты равными нулю.
<tex> A(x) = a_0 x^0 + a_1 x^1 + \ldots + a_{n-1} x^{n-1} </tex>
Разделим <tex>A(x)</tex> на два многочлена, где один будет с четными, а другой с нечетными коэффициентами:
* <tex> A_0(x) = a_0 x^0 + a_2 x^1 + \ldots + a_{n-2} x^{\frac{n}{2} - 1} </tex>
* <tex> A_1(x) = a_1 x^0 + a_3 x^1 + \ldots + a_{n-1} x^{\frac{n}{2} - 1} </tex>
Многочлен <tex>A(x)</tex> получается из <tex>A_0(x)</tex> и <tex>A_1(x)</tex> следующим образом:
<tex>A(x) = A_0(x^2) + xA_1(x^2) \ \ \ \ \ (1)</tex>
Мы разбили исходный многочлен на два многочлена, имеющих вдвое меньшую степень. Нам необходимо по вычисленным <tex>DFT(A_0)</tex> и <tex>DFT(A_1)</tex> за линейное время вычислить <tex>DFT(A)</tex>. Так как здесь используется идея "разделяй и властвуй", то асимптотическая оценка будет <tex>O(nlogn)</tex>.
Пусть <tex>DFT(A_0) = \{y_k^0\}^{\frac{n}{2}-1}_{k=0}</tex> и <tex>DFT(A_1) = \{y_k^1\}^{\frac{n}{2} - 1}_{k=0}</tex>. Найдем вектор значений <tex>DFT(A) = \{y_k\}^{n-1}_{k=0}</tex>.
* Из <tex>(1)</tex> получаем значения для первой половины коэффициентов:
<tex>y_k = y_k^0 + \omega^k_n y_k^1, \ \ k = 0 \ldots \dfrac{n}{2} - 1 </tex>
* Для второй половины получаем:
<tex>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})= </tex> <tex>A_0(\omega_n^{2k} \omega_n^{n})+ \omega_n^k \omega_n^{\frac{n}{2}} A_1(\omega_n^{2k} \omega_n^n) </tex>
Заметим, что <tex> \omega_n^n = 1, \omega_n^{\frac{n}{2}} = -1</tex>, тогда:
<tex>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</tex>.
Таким образом, мы получили:
<tex>y_k = y_k^0 + \omega^k_n y_k^1, \ \ k = 0 \ldots \dfrac{n}{2} - 1 </tex>
<tex>y_{k+\frac{n}{2}}= y_k^0- \omega_n^k y_k^1, \ \ k = 0 \ldots \dfrac{n}{2} - 1 </tex>.
== Алгоритм построения обратного БПФ ==
Пусть вектор <tex>y_0, y_1, \ldots , y_{n-1}</tex> {{---}} значения многочлена <tex>A</tex> степени <tex>n</tex> в точках <tex>n = \omega_n^k</tex>. Необходимо, по данному вектору восстановить коэффициенты <tex>(a_0, a_1, \ldots , a_{n-1})</tex> многочлена.
