Что такое fft

Описание задачи[править]

Задача:
Необходимо научиться вычислять прямое и обратное дискретное преобразование Фурье многочлена [math]A(x)[/math] степени [math]n[/math] за время [math]O(n log n)[/math].

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

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

Алгоритм построения БПФ[править]

Итак, пусть дан вектор — значения многочлена степени в точках . Требуется восстановить коэффициенты многочлена. Эта известная задача называется интерполяцией, для этой задачи есть и общие алгоритмы решения, однако в данном случае будет получен очень простой алгоритм (простой тем, что он практически не отличается от прямого БПФ).

мы замечаем, что эти две задачи почти ничем не отличаются, поэтому коэффициенты можно находить таким же алгоритмом «разделяй и властвуй», как и прямое БПФ, только вместо везде надо использовать , а каждый элемент результата надо разделить на .

Таким образом, вычисление обратного ДПФ почти не отличается от вычисления прямого ДПФ, и его также можно выполнять за время .

Пусть имеется многочлен [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_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) = A_0(x^2) xA_1(x^2) (1)[/math]

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

Пусть [math]mathrm{DFT}(A_0) = {y_k^0}^{frac{n}{2}-1}_{k=0}[/math] и [math]mathrm{DFT}(A_1) = {y_k^1}^{frac{n}{2} — 1}_{k=0}[/math]. Найдем вектор значений [math]mathrm{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]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 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] многочлена.

[math]
begin{pmatrix}
omega_n^0 {amp}amp; omega_n^0 {amp}amp; omega_n^0 {amp}amp; ldots {amp}amp; omega_n^0\
omega_n^0 {amp}amp; omega_n^1 {amp}amp; omega_n^2 {amp}amp; ldots {amp}amp; omega_n^{n-1} \
omega_n^0 {amp}amp; omega_n^2 {amp}amp; omega_n^4 {amp}amp; ldots {amp}amp; omega_n^{2(n-1)} \
vdots{amp}amp; vdots {amp}amp; vdots {amp}amp;ddots {amp}amp; vdots\
omega_n^0 {amp}amp; omega_n^{n-1} {amp}amp; omega_n^{2(n-1)} {amp}amp;ldots {amp}amp; omega_n^{(n-1)(n-1)}
end{pmatrix}
begin{pmatrix}
a_0 \
a_1 \
a_2 \
vdots \
a_{n-1}
end{pmatrix}
=
begin{pmatrix}
y_0 \
y_1 \
y_2 \
vdots \
y_{n-1}
end{pmatrix}
[/math]

Отсюда можно найти вектор [math](a_0, a_1, ldots ,a_{n-1})[/math], умножив вектор [math](y_0, y_1, ldots ,y_{n-1})[/math] на матрицу обратную матрице Вандермонда (матрица слева).

[math]
begin{pmatrix}
a_0 \
a_1 \
a_2 \
vdots \
a_{n-1}
end{pmatrix}
=
{begin{pmatrix}
omega_n^0 {amp}amp; omega_n^0 {amp}amp; omega_n^0 {amp}amp; ldots {amp}amp; omega_n^0\
omega_n^0 {amp}amp; omega_n^1 {amp}amp; omega_n^2 {amp}amp; ldots {amp}amp; omega_n^{n-1} \
omega_n^0 {amp}amp; omega_n^2 {amp}amp; omega_n^4 {amp}amp; ldots {amp}amp; omega_n^{2(n-1)} \
vdots{amp}amp; vdots {amp}amp; vdots {amp}amp;ddots {amp}amp; vdots\
omega_n^0 {amp}amp; omega_n^{n-1} {amp}amp; omega_n^{2(n-1)} {amp}amp;ldots {amp}amp; omega_n^{(n-1)(n-1)}
end{pmatrix}}^{-1}
begin{pmatrix}
y_0 \
y_1 \
y_2 \
vdots \
y_{n-1}
end{pmatrix}
[/math]
[math]
dfrac{1}{n}
begin{pmatrix}
omega_n^0 {amp}amp; omega_n^0 {amp}amp; omega_n^0 {amp}amp; ldots {amp}amp; omega_n^0\
omega_n^0 {amp}amp; omega_n^{-1} {amp}amp; omega_n^{-2} {amp}amp; ldots {amp}amp; omega_n^{-(n-1)} \
omega_n^0 {amp}amp; omega_n^{-2} {amp}amp; omega_n^{-4} {amp}amp; ldots {amp}amp; omega_n^{-2(n-1)} \
vdots{amp}amp; vdots {amp}amp; vdots {amp}amp;ddots {amp}amp; vdots\
omega_n^0 {amp}amp; omega_n^{-(n-1)} {amp}amp; omega_n^{-2(n-1)} {amp}amp;ldots {amp}amp; omega_n^{-(n-1)(n-1)}
end{pmatrix}
[/math]
[math]a_k = dfrac{1}{n}sum limits_{j=0}^{n-1} {y_j omega_n^{-kj}} [/math]

Аналогично прямому ДПФ, по принципу разделяй и властвуй посчитаем [math]mathrm{InvDFT}[/math].

Оцените статью
Спорт и ЗОЖ