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

Материал из Викиконспекты
Перейти к: навигация, поиск
(ДПФ в модульной арифметике)
м (rollbackEdits.php mass rollback)
 
(не показаны 23 промежуточные версии 8 участников)
Строка 4: Строка 4:
  
 
<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>
Строка 31: Строка 31:
 
<center>
 
<center>
 
<tex>
 
<tex>
A \times B = \mathrm{InvDFT}(\mathrm{DFT}(A) \times \mathrm{DTF}(B)).
+
A \times B = \mathrm{InvDFT}(\mathrm{DFT}(A) \times \mathrm{DFT}(B)).
 
</tex>
 
</tex>
 
</center>
 
</center>
  
Так как ДПФ многолчена {{---}} это вектор его значений, значит, перемножение двух ДПФ требует только <tex>O(n)</tex> операций. Осталось только вычислять ДПФ и обратное ДПФ за время <tex>O(nlogn)</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> различных корней, но такие модули все же существуют. Необходимо найти примитивный корень, то есть:
Строка 56: Строка 59:
 
== Следствия ==
 
== Следствия ==
 
{{Утверждение
 
{{Утверждение
|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>
+
|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=
 
|proof=
 
Применим к обеим частям обратное ДПФ и получим:
 
Применим к обеим частям обратное ДПФ и получим:
Строка 62: Строка 65:
 
<center>
 
<center>
 
<tex>
 
<tex>
\mathrm{DFT}(a_0, a_1, a_{n-1}) = \mathrm{InvDFT}(\dfrac{1}{n} (a_0, a_{n-1}, \ldots , a_1))
+
\mathrm{DFT}(a_0, a_1, \ldots , a_{n-1}) = \mathrm{InvDFT}\left(n (a_0, a_{n-1}, \ldots , a_1)\right)
 
</tex>
 
</tex>
 
</center>
 
</center>
Строка 70: Строка 73:
 
<center>
 
<center>
 
<tex>
 
<tex>
y_k = \sum\limits_{j=0}^{n} a_j e^{i\frac{2\pi k}{n} j}
+
y_k = \sum\limits_{j=0}^{n-1} a_j e^{i\frac{2\pi k}{n} j}
 
</tex>
 
</tex>
 
</center>
 
</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>, где:
+
Теперь рассмотрим правую часть. По определению, справа у нас находится вектор коэффициентов многочлена со значениями <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>
 
<center>
 
<tex>
 
<tex>
y_k '= \dfrac{1}{n} \sum\limits_{j=0}^{n} z_j e^{-i\frac{2\pi k}{n} j},
+
y_k '= \dfrac{1}{n} \sum\limits_{j=0}^{n-1} z_j e^{-i\frac{2\pi k}{n} j},
 
</tex>
 
</tex>
 
</center>
 
</center>
Строка 95: Строка 98:
 
=
 
=
 
\begin{pmatrix}
 
\begin{pmatrix}
\dfrac{a_0}{n}\\
+
n{a_0}\\
\dfrac{a_{n-1}}{n}\\
+
n{a_{n-1}}\\
\dfrac{a_{n-2}}{n}\\
+
n{a_{n-2}}\\
 
\vdots \\
 
\vdots \\
\dfrac{a_1}{n}
+
n{a_1}
 
\end{pmatrix}
 
\end{pmatrix}
 
</tex>
 
</tex>
Строка 108: Строка 111:
 
<center>
 
<center>
 
<tex>
 
<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}
+
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>
 
</tex>
 
</center>
 
</center>
Строка 116: Строка 119:
 
<center>
 
<center>
 
<tex>
 
<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,
+
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>
 
</tex>
 
</center>
 
</center>
что и требовалось доказать.
 
 
}}
 
}}
  
Строка 134: Строка 136:
 
<center>
 
<center>
 
<tex>
 
<tex>
x_0 = \ \ 1 \\
+
x_0 = \ \ 5 \\
 
x_1 = \ \ 2 \\
 
x_1 = \ \ 2 \\
 
x_2 = \ \ 4 \\
 
x_2 = \ \ 4 \\
Строка 149: Строка 151:
 
1 & i & -1 & -i \\
 
1 & i & -1 & -i \\
 
1 & -1 & 1 & -1 \\
 
1 & -1 & 1 & -1 \\
1 & -i & 1 & i
+
1 & -i & -1 & i
 
\end{pmatrix}
 
\end{pmatrix}
 
\begin{pmatrix}
 
\begin{pmatrix}
Строка 159: Строка 161:
 
=
 
=
 
\begin{pmatrix}
 
\begin{pmatrix}
y_0 \\
+
10 \\
y_1 \\
+
1 + 3i \\
y_2 \\
+
8 \\
y_3
+
1 - 3i
 
\end{pmatrix}
 
\end{pmatrix}
 
</tex>
 
</tex>
Строка 182: Строка 184:
 
<center>
 
<center>
 
<tex>
 
<tex>
DFT(A) = (10, 1 + 3i, 8, 1 - 3i)
+
\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>
 
</tex>
 
</center>
 
</center>
Строка 193: Строка 253:
 
*[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]

См. также

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