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

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

Определение

Пусть имеется последовательность чисел $$ \{f_k\}_{k=0}^{N-1}$$.
Дискретным преобразованием Фурье такой последовательности называется: \[ \{F_n\}_{n=0}^{N-1} : F_n = \sum_{k=0}^{N-1}f_kW_N^{kn} \quad,\\ W_N = e^{\frac{-2\pi i}{N}}. \]

Свойства

1. Линейность:

\[ \alpha f_k + \beta g_k \longleftrightarrow \alpha F_n + \beta G_n \]

1. Сдвиг:

\[ f_{\scriptsize(k-m)mod \, N} \longleftrightarrow F_ne^{\frac{-2\pi i}{N}nm} \]

1. Формула обращения:

\[ f_k = \frac{1}{N} \sum_{n=0}^{N-1}F_nW_N^{-kn} \]

1. Свёртка:

\[ f_k * g_k = \sum_{l=0}^{N-1}f_{\scriptsize(k-l)mod \, N}g_{\scriptsize l} \]

1. Формула Парсеваля:

\[ \sum_{k=0}^{N-1}f_k \overline g_k = \frac{1}{N}\sum_{n=0}^{N-1}F_n \overline G_n \]