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

Определение:

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

Так как ДПФ многолчена — это вектор его значений, значит, перемножение двух ДПФ требует только [math]O(n)[/math] операций. Осталось только вычислять ДПФ и обратное ДПФ за время [math]O(n\logn)[/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})) = \dfrac{1}{n} (a_0, a_{n-1}, \ldots , a_1) [/math]

[math]\triangleright[/math]

Применим к обеим частям обратное ДПФ и получим: [math] \mathrm{DFT}(a_0, a_1, a_{n-1}) = \mathrm{InvDFT}\left(\dfrac{1}{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} a_j e^{i\frac{2\pi k}{n} j} [/math] Теперь рассмотрим правую часть. По определению, справа у нас находится вектор коэффициентов многочлена со значениями [math]\left( \dfrac{1}{n} a_0, \dfrac{1}{n} a_{n-1}, \ldots , \dfrac{1}{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} 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} \dfrac{a_0}{n}\\ \dfrac{a_{n-1}}{n}\\ \dfrac{a_{n-2}}{n}\\ \vdots \\ \dfrac{a_1}{n} \end{pmatrix} [/math] Тогда, подставляя значения [math]z_j[/math], получаем: [math] 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} [/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} 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, [/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 = \ \ 1 \\ 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} y_0 \\ y_1 \\ y_2 \\ y_3 \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] DFT(A) = (10, 1 + 3i, 8, 1 - 3i) [/math]

См. также

• Быстрое преобразование Фурье

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

• Википедия — Дискретное преобразование Фурье
• MAXimal::algo::Быстрое преобразование Фурье за O (N log N)