Дискретное преобразование Фурье

2019-01-05T13:03:09Z

5.165.73.140: Исправление пределов суммирования.

{{Определение
|definition=
'''Дискретное преобразование Фурье''' (англ. ''Discrete Fourier Transform, DFT'') многочлена <tex>A(x)</tex> называют вектор значений этого многочлена в точках <tex>x = \omega_{n,k}</tex>:

<tex>
\mathrm{DFT}(a_0, a_1, \ldots , a_{n-1}) = (y_0, y_1, \ldots , y_{n-1}) = (A(\omega_{n,0}), A(\omega_{n,1}), \ldots , A(\omega_{n,n-1}))
</tex>
<tex>
= (A(\omega_n^0), A(\omega_n^1), \ldots , A(\omega_n^{n-1})),
</tex>

где <tex>\omega_{n,k} = e^{i\frac{2\pi k}{n}}</tex> {{---}} <tex> k-</tex>ый из <tex>n</tex> комплексных корней из единицы. <tex>\omega_n = \omega_{n,1} = e^{i\frac{2\pi}{n}}</tex> называется главным значением корня <tex>n</tex>-ой степени из единицы, а все остальные корни являются его степенями: <tex>\omega_{n,k} = (\omega_n)^k</tex>.
}}

{{Определение
|definition=
'''Обратное дискретное преобразование Фурье''' (англ. ''Inverse DFT'') для вектора значений многочлена <tex>A(\omega_n)</tex> <tex>(y_0, y_1, \ldots , y_{n-1})</tex> {{---}} вектор коэффициентов этого многочлена <tex>(a_0, a_1, \ldots , a_{n-1})</tex>:

<center>
<tex>
\mathrm{InvDFT}(y_0, y_1, \ldots , y_{n-1}) = (a_0, a_1, \ldots , a_{n-1}).
</tex>
</center>
}}

== Применение ДПФ ==
Дискретное преобразование Фурье используют для быстрого перемножения двух полиномов <tex>A</tex> и <tex>B</tex>.

Для того чтобы получить произведение двух многочленов за время, меньшее чем <tex>O(n^2)</tex>, необходимо сначала посчитать <tex>DFT</tex> обоих многочленов. Так как при умножении двух многочленов их значения просто перемножаются в каждой точке. Следовательно, если <tex>DFT</tex> {{---}} это вектор значений многочлена, то мы можем получить значение произведения двух многочленов, просто перемножив их ДПФ. Значит, чтобы получить коэффициенты полученного многочлена, применим обратное ДПФ.

<center>
<tex>
A \times B = \mathrm{InvDFT}(\mathrm{DFT}(A) \times \mathrm{DTF}(B)).
</tex>
</center>

Так как ДПФ многолчена {{---}} это вектор его значений, значит, перемножение двух ДПФ требует только <tex>O(n)</tex> операций. Осталось только вычислять ДПФ и обратное ДПФ за время <tex>O(n \log n)</tex>. Для этого используем [[Быстрое преобразование Фурье| быстрое преобразование Фурье]].

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

== ДПФ в модульной арифметике ==
В основе ДПФ используются комплексные числа, являющиеся корнями <tex>n</tex>-ой степени из единицы. Для эффективного вычисления использовались свойства комплексных корней, которые образуют [[Группа | группу]], то есть степень одного корня всегда является другим корнем. Среди них есть корень, называемый [[Первообразные корни | примитивным]].

Однако, то же верно и в случае корней <tex>n</tex>-ой степени из единицы в модульной арифметике. Не для любого модуля <tex>p</tex> найдется <tex>n</tex> различных корней, но такие модули все же существуют. Необходимо найти примитивный корень, то есть:

<center>
<tex>
(\omega_n)^n = 1 \ \mod p,
</tex>

<tex>
(\omega_n)^k \ne 1 \ \mod p, 1 \leqslant k < n.
</tex>
</center>

Как и с комплексными корнями, остальные <tex>n-1</tex> корней <tex>n</tex>-ой степени из единицы по модулю <tex>p</tex> можно получить как степени примитивного корня <tex>\omega_n</tex>

== Следствия ==
{{Утверждение
|statement= <tex>\mathrm{DFT}(\mathrm{DFT}(a_0, a_1, \ldots , a_{n-1})) = \dfrac{1}{n} (a_0, a_{n-1}, \ldots , a_1) </tex>
|proof=
Применим к обеим частям обратное ДПФ и получим:

<center>
<tex>
\mathrm{DFT}(a_0, a_1, a_{n-1}) = \mathrm{InvDFT}\left(\dfrac{1}{n} (a_0, a_{n-1}, \ldots , a_1)\right)
</tex>
</center>

Заметим, что слева у нас находится вектор значений многочлена с коэффициентами <tex>(a_0, a_1, \ldots , a_{n-1})</tex> и обозначим его за <tex>(y_0, y_1, \ldots , y_{n-1})</tex>. Заметим, что:

<center>
<tex>
y_k = \sum\limits_{j=0}^{n-1} a_j e^{i\frac{2\pi k}{n} j}
</tex>
</center>

Теперь рассмотрим правую часть. По определению, справа у нас находится вектор коэффициентов многочлена со значениями <tex>\left( \dfrac{1}{n} a_0, \dfrac{1}{n} a_{n-1}, \ldots , \dfrac{1}{n} a_1 \right)</tex> в точках <tex>x = \omega_n^k</tex>. Обозначим его как <tex>(y_0 ', y_1 ', \ldots , y_{n-1} ')</tex>, где:

<center>
<tex>
y_k '= \dfrac{1}{n} \sum\limits_{j=0}^{n-1} z_j e^{-i\frac{2\pi k}{n} j},
</tex>
</center>

где

<center>
<tex>
\begin{pmatrix}
z_0 \\
z_1 \\
z_2 \\
\vdots \\
z_{n-1}
\end{pmatrix}
=
\begin{pmatrix}
\dfrac{a_0}{n}\\
\dfrac{a_{n-1}}{n}\\
\dfrac{a_{n-2}}{n}\\
\vdots \\
\dfrac{a_1}{n}
\end{pmatrix}
</tex>
</center>

Тогда, подставляя значения <tex>z_j</tex>, получаем:

<center>
<tex>
y_k ' = a_0 e^0 + \sum\limits_{j=1}^{n} a_j e^{-i\frac{2\pi k}{n} (n - j)} = a_0 + \sum\limits_{j=1}^{n} a_j e^{-i 2\pi k} e^{i\frac{2\pi k}{n} j}
</tex>
</center>

А так как <tex>e^{-i 2\pi k} = \left(\dfrac{1}{e^{i 2\pi}}\right)^k = 1</tex>, получаем:

<center>
<tex>
y_k ' = a_0 + \sum\limits_{j=1}^{n} a_j e^{i \frac{2\pi k}{n} j} = \sum\limits_{j=0}^{n} a_j e^{i\frac{2\pi k}{n} j} = y_k.
</tex>
</center>
}}

== Пример ==
Посчитаем <tex>\mathrm{DFT}</tex> для полинома степени <tex>n = 4</tex>.

<center>
<tex>
A(x) = 5 + 2x + 4x^2 - x^3
</tex>
</center>

Тогда подставляя значения <tex>k</tex> в <tex>e^{2i\frac{\pi k}{4}}</tex> получаем:
<center>
<tex>
x_0 = \ \ 1 \\
x_1 = \ \ 2 \\
x_2 = \ \ 4 \\
x_3 = -1
</tex>
</center>

Построим матрицу Вандермонда:

<center>
<tex>
\begin{pmatrix}
1 & 1 & 1 & 1 \\
1 & i & -1 & -i \\
1 & -1 & 1 & -1 \\
1 & -i & 1 & i
\end{pmatrix}
\begin{pmatrix}
5 \\
2 \\
4 \\
-1
\end{pmatrix}
=
\begin{pmatrix}
10 \\
1 + 3i \\
8 \\
1 - 3i
\end{pmatrix}
</tex>
</center>

Получаем вектор значений многочлена <tex>(y_0, y_1, y_2, y_3)</tex>:

<center>
<tex>
y_0 = 1 \cdot 5 \ + \ 1 \cdot 2 \ + \ 1 \cdot 4 \ -1 \ = \ 10 \\
y_1 = 1 \cdot 5 \ + \ 2i \ - \ 4 \ + \ i \ = \ 1 \ + \ 3i \\
y_2 = 1 \cdot 5 \ - \ 2 \ + \ 4 \ + 1 \ = \ 8 \\
y_3 = 1 \cdot 5 \ - \ 2i \ - \ 4 \ - \ i = 1 \ - \ 3i
</tex>
</center>

В итоге получаем:

<center>
<tex>
\mathrm{DFT}(A) = (10, 1 + 3i, 8, 1 - 3i)
</tex>
</center>

Аналогично, получаем обратное ДПФ.

<center><tex>
\begin{pmatrix}
a_0 \\
a_1 \\
a_2 \\
a_3
\end{pmatrix}
=
{\begin{pmatrix}
1 & 1 & 1 & 1 \\
1 & i & -1 & -i \\
1 & -1 & 1 & -1 \\
1 & -i & -1 & i
\end{pmatrix}}^{-1}
\begin{pmatrix}
10 \\
1 + 3i \\
8 \\
1 - 3i
\end{pmatrix}
</tex></center>

<center><tex>
\begin{pmatrix}
a_0 \\
a_1 \\
a_2 \\
a_3
\end{pmatrix}
=
\dfrac{1}{-16i}
\begin{pmatrix}
-4i & -4i & -4i & -4i \\
-4i & -4 & 4i & 4 \\
-4i & 4i & -4i & 4i \\
-4i & 4 & 4i & -4
\end{pmatrix}
\begin{pmatrix}
10 \\
1 + 3i \\
8 \\
1 - 3i
\end{pmatrix}
</tex></center>

<center>
<tex>
a_0 = \dfrac{1}{4} (10 + 1 + 3i + 8 + 1 - 3i) = 5 \\
a_1 = \dfrac{1}{4} (10 + (1 + 3i)(-i) + (-1)8 + (1 - 3i)i) = 2 \\
a_2 = \dfrac{1}{4} (10 + (1 + 3i)(-1) + 8 + (1 - 3i)(-1)) = 4 \\
a_3 = \dfrac{1}{4} (10 + (1 + 3i)i + (-1)8 + (1 - 3i)(-i)) = -1
</tex>
</center>

== См. также ==
*[[Быстрое преобразование Фурье]]

== Источники информации ==
*[https://ru.wikipedia.org/wiki/%D0%94%D0%B8%D1%81%D0%BA%D1%80%D0%B5%D1%82%D0%BD%D0%BE%D0%B5_%D0%BF%D1%80%D0%B5%D0%BE%D0%B1%D1%80%D0%B0%D0%B7%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5_%D0%A4%D1%83%D1%80%D1%8C%D0%B5 Википедия {{---}} Дискретное преобразование Фурье]
*[http://e-maxx.ru/algo/fft_multiply MAXimal::algo::Быстрое преобразование Фурье за O (N log N)]

[[Категория: Алгоритмы и структуры данных]]
[[Категория: Алгоритмы алгебры и теории чисел]]
[[Категория: Основные элементы теории чисел]]
[[Категория: Основные алгоритмы теории чисел]]

Викиконспекты - Вклад участника [ru]

Дискретное преобразование Фурье