Дискретное преобразование Фурье — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (Применение ДПФ)
м (rollbackEdits.php mass rollback)
 
(не показано 29 промежуточных версий 8 участников)
Строка 1: Строка 1:
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
'''Дискретное преобразование Фурье''' (англ. ''Discrete Fourier Transform (DFT)'') {{---}} многочлена <tex>A(x)</tex> называют вектор значений этого многочлена в точках <tex>x = \omega_{n,k}</tex>:
+
'''Дискретное преобразование Фурье''' (англ. ''Discrete Fourier Transform, DFT'') многочлена <tex>A(x)</tex> называют вектор значений этого многочлена в точках <tex>x = \omega_{n,k}</tex>:
  
 
<tex>
 
<tex>
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}))
+
\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>
 
<tex>
 
<tex>
Строка 15: Строка 15:
 
{{Определение
 
{{Определение
 
|definition=
 
|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>:
+
'''Обратное дискретное преобразование Фурье''' (англ. ''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>
 
<tex>
InvDFT(y_0, y_1, \ldots , y_{n-1}) = (a_0, a_1, \ldots , a_{n-1}).
+
\mathrm{InvDFT}(y_0, y_1, \ldots , y_{n-1}) = (a_0, a_1, \ldots , a_{n-1}).
 
</tex>
 
</tex>
 
+
</center>
 
}}
 
}}
  
Строка 31: Строка 31:
 
<center>
 
<center>
 
<tex>
 
<tex>
A \times B = InvDFT(DFT(A) \times DTF(B)).
+
A \times B = \mathrm{InvDFT}(\mathrm{DFT}(A) \times \mathrm{DFT}(B)).
 
</tex>
 
</tex>
 
</center>
 
</center>
  
Так как ДПФ многолчена {{---}} это вектор его значений, значит, перемножение двух ДПФ требует только <tex>O(n)</tex> операций. Осталось только вычислять ДПФ и обратное ДПФ за время <tex>O(n)</tex>. Для этого используем [[Быстрое преобразование Фурье| быстрое преобразование Фурье]].
+
Так как ДПФ многолчена {{---}} это вектор его значений, значит, перемножение двух ДПФ требует только <tex>O(n)</tex> операций. Осталось только вычислять ДПФ и обратное ДПФ за время <tex>O(n \log n)</tex>. Для этого используем [[Быстрое преобразование Фурье| быстрое преобразование Фурье]].
 +
 
 +
 
 +
ДПФ также применяют для быстрого умножения двух длинных чисел, которые в свою очередь могут быть представлены в виде полиномов.
  
 
== ДПФ в модульной арифметике ==
 
== ДПФ в модульной арифметике ==
В основе ДПФ используются комплексные числа, являющиеся корнями <tex>n</tex>-ой степени из единицы. Для эффективного вычисления использовались свойства комплексных корней, которые образуют группу, то есть степень одного корня всегда является другим корнем. Среди них есть корень, называемый примитивным.
+
В основе ДПФ используются комплексные числа, являющиеся корнями <tex>n</tex>-ой степени из единицы. Для эффективного вычисления использовались свойства комплексных корней, которые образуют [[Группа | группу]], то есть степень одного корня всегда является другим корнем. Среди них есть корень, называемый [[Первообразные корни | примитивным]].
  
 
Однако, то же верно и в случае корней <tex>n</tex>-ой степени из единицы в модульной арифметике. Не для любого модуля <tex>p</tex> найдется <tex>n</tex> различных корней, но такие модули все же существуют. Необходимо найти примитивный корень, то есть:
 
Однако, то же верно и в случае корней <tex>n</tex>-ой степени из единицы в модульной арифметике. Не для любого модуля <tex>p</tex> найдется <tex>n</tex> различных корней, но такие модули все же существуют. Необходимо найти примитивный корень, то есть:
  
 +
<center>
 
<tex>
 
<tex>
(\omega_n)^n = 1 (mod p),
+
(\omega_n)^n = 1 \ \mod p,
 
</tex>
 
</tex>
  
 
<tex>
 
<tex>
(\omega_n)^k \ne (mod p), 1 \leqslant  k < n.
+
(\omega_n)^k \ne 1 \ \mod p, 1 \leqslant  k < n.
 
</tex>
 
</tex>
 +
</center>
  
 
Как и с комплексными корнями, остальные <tex>n-1</tex> корней <tex>n</tex>-ой степени из единицы по модулю <tex>p</tex> можно получить как степени примитивного корня <tex>\omega_n</tex>
 
Как и с комплексными корнями, остальные <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})) = n (a_0, a_{n-1}, \ldots , a_1) </tex>
 +
|proof=
 +
Применим к обеим частям обратное ДПФ и получим:
 +
 +
<center>
 +
<tex>
 +
\mathrm{DFT}(a_0, a_1, \ldots , a_{n-1}) = \mathrm{InvDFT}\left(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( n a_0, n a_{n-1}, \ldots , 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}
 +
n{a_0}\\
 +
n{a_{n-1}}\\
 +
n{a_{n-2}}\\
 +
\vdots \\
 +
n{a_1}
 +
\end{pmatrix}
 +
</tex>
 +
</center>
 +
 +
Тогда, подставляя значения <tex>z_j</tex>, получаем:
 +
 +
<center>
 +
<tex>
 +
y_k ' = a_0 e^0 + \sum\limits_{j=1}^{n-1} a_j e^{-i\frac{2\pi k}{n} (n - j)} = a_0 + \sum\limits_{j=1}^{n-1} 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-1} a_j e^{i \frac{2\pi k}{n} j} = \sum\limits_{j=0}^{n-1} 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 = \ \ 5 \\
 +
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 Википедия {{---}} Дискретное преобразование Фурье]
 
*[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)]
 
*[http://e-maxx.ru/algo/fft_multiply MAXimal::algo::Быстрое преобразование Фурье за O (N log N)]
 +
 +
[[Категория: Алгоритмы и структуры данных]]
 +
[[Категория: Алгоритмы алгебры и теории чисел]]
 +
[[Категория: Основные элементы теории чисел]]
 +
[[Категория: Основные алгоритмы теории чисел]]

Текущая версия на 19:21, 4 сентября 2022

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

[math] \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})) [/math] [math] = (A(\omega_n^0), A(\omega_n^1), \ldots , A(\omega_n^{n-1})), [/math]

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


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

[math] \mathrm{InvDFT}(y_0, y_1, \ldots , y_{n-1}) = (a_0, a_1, \ldots , a_{n-1}). [/math]


Применение ДПФ

Дискретное преобразование Фурье используют для быстрого перемножения двух полиномов [math]A[/math] и [math]B[/math].

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

[math] A \times B = \mathrm{InvDFT}(\mathrm{DFT}(A) \times \mathrm{DFT}(B)). [/math]

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


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

ДПФ в модульной арифметике

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

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

[math] (\omega_n)^n = 1 \ \mod p, [/math]

[math] (\omega_n)^k \ne 1 \ \mod p, 1 \leqslant k \lt n. [/math]

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

Следствия

Утверждение:
[math]\mathrm{DFT}(\mathrm{DFT}(a_0, a_1, \ldots , a_{n-1})) = n (a_0, a_{n-1}, \ldots , a_1) [/math]
[math]\triangleright[/math]

Применим к обеим частям обратное ДПФ и получим:

[math] \mathrm{DFT}(a_0, a_1, \ldots , a_{n-1}) = \mathrm{InvDFT}\left(n (a_0, a_{n-1}, \ldots , a_1)\right) [/math]

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

[math] y_k = \sum\limits_{j=0}^{n-1} a_j e^{i\frac{2\pi k}{n} j} [/math]

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

[math] y_k '= \dfrac{1}{n} \sum\limits_{j=0}^{n-1} z_j e^{-i\frac{2\pi k}{n} j}, [/math]

где

[math] \begin{pmatrix} z_0 \\ z_1 \\ z_2 \\ \vdots \\ z_{n-1} \end{pmatrix} = \begin{pmatrix} n{a_0}\\ n{a_{n-1}}\\ n{a_{n-2}}\\ \vdots \\ n{a_1} \end{pmatrix} [/math]

Тогда, подставляя значения [math]z_j[/math], получаем:

[math] y_k ' = a_0 e^0 + \sum\limits_{j=1}^{n-1} a_j e^{-i\frac{2\pi k}{n} (n - j)} = a_0 + \sum\limits_{j=1}^{n-1} a_j e^{-i 2\pi k} e^{i\frac{2\pi k}{n} j} [/math]

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

[math] y_k ' = a_0 + \sum\limits_{j=1}^{n-1} a_j e^{i \frac{2\pi k}{n} j} = \sum\limits_{j=0}^{n-1} a_j e^{i\frac{2\pi k}{n} j} = y_k. [/math]

[math]\triangleleft[/math]

Пример

Посчитаем [math]\mathrm{DFT}[/math] для полинома степени [math]n = 4[/math].

[math] A(x) = 5 + 2x + 4x^2 - x^3 [/math]

Тогда подставляя значения [math]k[/math] в [math]e^{2i\frac{\pi k}{4}}[/math] получаем:

[math] x_0 = \ \ 5 \\ x_1 = \ \ 2 \\ x_2 = \ \ 4 \\ x_3 = -1 [/math]

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

[math] \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} [/math]

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

[math] 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 [/math]

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

[math] \mathrm{DFT}(A) = (10, 1 + 3i, 8, 1 - 3i) [/math]

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

[math] \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} [/math]


[math] \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} [/math]


[math] 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 [/math]

См. также

Источники информации