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

Материал из sawiki
Перейти к навигации Перейти к поиску
Строка 12: Строка 12:
 
== Свойства ==
 
== Свойства ==
 
# Линейность: <br /> \(\alpha \, f_k + \beta  g_k \longleftrightarrow \alpha F_n + \beta G_n\)
 
# Линейность: <br /> \(\alpha \, f_k + \beta  g_k \longleftrightarrow \alpha F_n + \beta G_n\)
# Сдвиг: <br /> \(f_{\scriptsize(k-m)mod \, N} \longleftrightarrow F_ne^{\scriptsize\frac{-2\pi i}{N}nm}\)
+
# Сдвиг: <br /> \(f_{(k-m)mod \, N} \longleftrightarrow F_ne^{\scriptsize\frac{-2\pi i}{N}nm}\)
 +
# Симметрия: <br /> \(f_k \longleftrightarrow F_n \\
 +
f_{(k-m)mod \, N} \longleftrightarrow F_n e^{\frac{-2\pi inm}{N}} \)
 
# Формула обращения: <br /> \(f_k = \frac{1}{N} \sum\limits_{n=0}^{N-1}F_nW_N^{-kn}\)
 
# Формула обращения: <br /> \(f_k = \frac{1}{N} \sum\limits_{n=0}^{N-1}F_nW_N^{-kn}\)
 
# Свёртка: <br /> \(f_k * g_k = \sum\limits_{l=0}^{N-1}f_{(k-l)\scriptsize mod \, N}g_{\scriptsize l}\)
 
# Свёртка: <br /> \(f_k * g_k = \sum\limits_{l=0}^{N-1}f_{(k-l)\scriptsize mod \, N}g_{\scriptsize l}\)
 
# Формула Парсеваля: <br /> \(\sum\limits_{k=0}^{N-1}f_k \overline g_k = \frac{1}{N}\sum\limits_{n=0}^{N-1}F_n \overline G_n\)
 
# Формула Парсеваля: <br /> \(\sum\limits_{k=0}^{N-1}f_k \overline g_k = \frac{1}{N}\sum\limits_{n=0}^{N-1}F_n \overline G_n\)
 +
# Симметрия:
  
 
== Многомерный случай ==
 
== Многомерный случай ==

Версия 17:12, 20 ноября 2020

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

Определение

Пусть имеется последовательность чисел $$ \{\,f_k\,\}_{k=0}^{N-1}$$.
Дискретным преобразованием Фурье такой последовательности называется: \[ \{F_n\}_{n=0}^{N-1} : F_n = \sum\limits_{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\)
  2. Сдвиг:
    \(f_{(k-m)mod \, N} \longleftrightarrow F_ne^{\scriptsize\frac{-2\pi i}{N}nm}\)
  3. Симметрия:
    \(f_k \longleftrightarrow F_n \\ f_{(k-m)mod \, N} \longleftrightarrow F_n e^{\frac{-2\pi inm}{N}} \)
  4. Формула обращения:
    \(f_k = \frac{1}{N} \sum\limits_{n=0}^{N-1}F_nW_N^{-kn}\)
  5. Свёртка:
    \(f_k * g_k = \sum\limits_{l=0}^{N-1}f_{(k-l)\scriptsize mod \, N}g_{\scriptsize l}\)
  6. Формула Парсеваля:
    \(\sum\limits_{k=0}^{N-1}f_k \overline g_k = \frac{1}{N}\sum\limits_{n=0}^{N-1}F_n \overline G_n\)
  7. Симметрия:

Многомерный случай

  • Прямое преобразование:
    \(F_{n_1,...,n_m} = \sum\limits_{k_1=0}^{\small N_1 - 1}...\sum\limits_{k_m=0}^{\small N_m - 1}f_{k_1,...,k_m}W_{\small N_1}^{k_1 n_1}\cdot ... \cdot W_{\small N_m}^{k_m n_m} \, \\ W_{\small N_i} = e^{\frac{-2\pi i}{N_i}}, \quad {\small i = 1,...,m} \) ,
  • Обратное преобразование:
    \(f_{k_1,...,k_m} = \frac{1}{N_1...N_m}\sum\limits_{n_1=0}^{\small N_1 - 1}...\sum\limits_{n_m=0}^{\small N_m - 1}F_{n_1,...,n_m}W_{\small N_1}^{-k_1 n_1}\cdot ... \cdot W_{\small N_m}^{-k_m n_m} \, \\ W_{\small N_i} = e^{\frac{-2\pi i}{N_i}}, \quad {\small i = 1,...,m} \) ,

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

Быстрое преобразование Фурье (БПФ, FFT) — алгоритм ускоренного вычисления дискретного преобразования Фурье, позволяющий получить результат за время, меньшее чем $$O(N^2)$$ (требуемого для прямого, поформульного вычисления). Иногда под быстрым преобразованием Фурье понимается один из алгоритмов, называемый алгоритмом прореживания по частоте — времени, имеющий сложность $$(N\log N)$$.

Вывод преобразования

Пусть N $$-$$ чётное.
\( F_n = \sum\limits_{k=0}^{N-1}f_ke^{\frac{-2 \pi ink}{N}} = \{W_N = e^{\frac{-2 \pi i}{N}}\} = \sum\limits_{k=0}^{N-1}f_kW_{\scriptsize N}^{nk} = \sum\limits_{k=0}^{\frac{N}{2}-1}\left(f_{2k}W_{\scriptsize N}^{2nk} + f_{2k+1}W_{\scriptsize N}^{n(2k+1)}\right) = \\ = \sum\limits_{k=0}^{\frac{N}{2}-1}\left(f_{2k}W_{\scriptsize N/2}^{nk} + f_{2k+1}W_{\scriptsize N}^{n}W_{\scriptsize N/2}^{nk}\right) = \left(\sum\limits_{k=0}^{\frac{N}{2}-1}f_{2k}W_{\scriptsize N/2}^{nk}\right) + W_{\scriptsize N}^{n}\left(\sum\limits_{k=0}^{\frac{N}{2}-1}f_{2k+1}W_{\scriptsize N/2}^{nk}\right)\)
Количество сложений: \(\: N(N-1) = N^2 - N\)
Количество умножений: \(\: \frac{N}{2}\cdot \frac{N}{2} + N + \frac{N}{2}\cdot \frac{N}{2}= \frac{N^2}{2} + N\)
Оценка сложности: \(\: o \, (N\log N)\)