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

Шаблон:Другие значения Дискретное преобразование Фурье (в англоязычной литературе DFT, Discrete Fourier Transform) — это одно из преобразований Фурье, широко применяемых в алгоритмах цифровой обработки сигналов (его модификации применяются в сжатии звука в MP3, сжатии изображений в JPEG и др.), а также в других областях, связанных с анализом частот в дискретном (к примеру, оцифрованном аналоговом) сигнале.

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

Дискретное преобразование Фурье требует в качестве входа дискретную функцию. Такие функции часто создаются путём дискретизации (выборки значений из непрерывных функций).

Формулы преобразований

Прямое преобразование:

$X_k=\sum _{n=0}^{N-1}{x}_n{e}^{-\frac{2\pi i}{N}kn}=\sum _{n=0}^{N-1}{x}_n(\cos (2\pi kn/N)-i\cdot \sin (2\pi kn/N)),k=0,\dots ,N-1.$

Обратное преобразование:

$x_n=\frac{1}{N}\sum _{k=0}^{N-1}{X}_k{e}^{\frac{2\pi i}{N}kn}=\frac{1}{N}\sum _{k=0}^{N-1}{X}_k(\cos (2\pi kn/N)+i\cdot \sin (2\pi kn/N)),n=0,\dots ,N-1.$

Вторая часть выражения следует из первой по формуле Эйлера.

Обозначения:

• $N$ — количество значений сигнала, измеренных за период, а также количество компонент разложения;

• $x_n,n=0,\dots ,N-1,$ — измеренные значения сигнала (в дискретных временных точках с номерами $n=0,\dots ,N-1$), которые являются входными данными для прямого преобразования и выходными для обратного;

• $X_k,k=0,\dots ,N-1,$ — $N$ комплексных амплитуд синусоидальных сигналов, слагающих исходный сигнал; являются выходными данными для прямого преобразования и входными для обратного; поскольку амплитуды комплексные, то по ним можно вычислить одновременно и амплитуду, и фазу;

• $\frac{|X_k|}{N}$ — обычная (вещественная) амплитуда $k$-го синусоидального сигнала;

• $\arg (X_k)$ — фаза $k$-го синусоидального сигнала (аргумент комплексного числа);

• $k$ — индекс частоты. Частота $k$-го сигнала равна $\frac{k}{T}$, где $T$ — период времени, в течение которого брались входные данные.

Из последнего видно, что преобразование раскладывает сигнал на синусоидальные составляющие (которые называются гармониками) с частотами от $1$ колебания за период до $N-1$ колебаний за период (плюс константа). Поскольку частота дискретизации сама по себе равна $N$ отсчётов за период, то высокочастотные составляющие не могут быть корректно отображены — возникает муаровый эффект. Это приводит к тому, что вторая половина из $N$ комплексных амплитуд, фактически, является зеркальным отображением первой и не несёт дополнительной информации.

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

Шаблон:Нет источников в разделе Рассмотрим некоторый периодический сигнал $x(t)$ c периодом, равным T. Разложим его в ряд Фурье:

$x(t)=\sum _{k=-\mathrm{\infty }}^{+\mathrm{\infty }}{c}_k{e}^{i{\omega }_{k}t},{\omega }_k=\frac{2\pi k}{T}.$

Проведем дискретизацию сигнала так, чтобы на периоде было N отсчетов. Дискретный сигнал представим в виде отсчетов: $x_n=x(t_n)$, где $t_n=\frac{n}{N}T$, тогда эти отсчеты через ряд Фурье запишутся следующим образом:

$x_n=\sum _{k=-\mathrm{\infty }}^{+\mathrm{\infty }}{c}_k{e}^{i{\omega }_k{t}_n}=\sum _{k=-\mathrm{\infty }}^{+\mathrm{\infty }}{c}_k{e}^{\frac{2\pi i}{N}kn}.$

Используя соотношение $e^{\frac{2\pi i}{N}(k+mN)n}=e^{\frac{2\pi i}{N}kn}$, получаем:

$x_n=\sum _{k=0}^{N-1}{X}_k{e}^{\frac{2\pi i}{N}kn},$     где     $X_k=\sum _{l=-\mathrm{\infty }}^{+\mathrm{\infty }}{c}_{k+lN}.$

Таким образом мы получили обратное дискретное преобразование Фурье.

Умножим теперь скалярно выражение для $x_n$ на $e^{-\frac{2\pi i}{N}mn}$ и получим:

$\sum _{n=0}^{N-1}{x}_n{e}^{-\frac{2\pi i}{N}mn}=\sum _{k=0}^{N-1}\sum _{n=0}^{N-1}{X}_k{e}^{\frac{2\pi i}{N}(k-m)n}=\sum _{k=0}^{N-1}{X}_k\frac{1-e^{2\pi i(k-m)}}{1-e^{\frac{2\pi i(k-m)}{N}}}=\sum _{k=0}^{N-1}{X}_{k}N{\delta }_{km}.$

Здесь использованы: а) выражение для суммы конечного числа членов (экспонент) геометрической прогрессии, и б) выражение символа Кронекера как предела отношения функций Эйлера для комплексных чисел. Отсюда следует, что:

$X_k=\frac{1}{N}\sum _{n=0}^{N-1}{x}_n{e}^{-\frac{2\pi i}{N}kn}.$

Эта формула описывает прямое дискретное преобразование Фурье.

В литературе принято писать множитель $\frac{1}{N}$ в обратном преобразовании, и поэтому обычно пишут формулы преобразования в следующем виде:

$X_n=\sum _{m=0}^{N-1}{x}_m{e}^{-\frac{2\pi i}{N}nm},x_m=\frac{1}{N}\sum _{n=0}^{N-1}{X}_n{e}^{\frac{2\pi i}{N}mn}.$

Иногда можно встретить симметричную форму записи преобразования

$X_n=\frac{1}{\sqrt{N}}\sum _{m=0}^{N-1}{x}_m{e}^{-\frac{2\pi i}{N}nm},x_m=\frac{1}{\sqrt{N}}\sum _{n=0}^{N-1}{X}_n{e}^{\frac{2\pi i}{N}mn}.$

Матричное представление

Дискретное преобразование Фурье является линейным преобразованием, которое переводит вектор временных отсчётов $\overrightarrow{x}$ в вектор спектральных отсчётов той же длины. Таким образом преобразование может быть реализовано как умножение симметричной квадратной матрицы на вектор:

$\overrightarrow{X}=ℱ\overrightarrow{x},$

матрица $ℱ$ имеет вид:

$ℱ=\frac{1}{\sqrt{n}}\left(\begin{array}{cccccc}1& 1& 1& 1& \dots & 1\\ 1& {\omega }_n& {\omega }_n^2& {\omega }_n^3& \dots & {\omega }_n^{n-1}\\ 1& {\omega }_n^2& {\omega }_n^4& {\omega }_n^6& \dots & {\omega }_n^{2(n-1)}\\ 1& {\omega }_n^3& {\omega }_n^6& {\omega }_n^9& \dots & {\omega }_n^{3(n-1)}\\ ⋮& ⋮& ⋮& ⋮& \ddots & ⋮\\ 1& {\omega }_n^{n-1}& {\omega }_n^{2(n-1)}& {\omega }_n^{3(n-1)}& \dots & {\omega }_n^{(n-1{)}^2}\end{array}\right).$

Элементы матрицы задаются следующей формулой:

$ℱ(j,k)={\omega }_n^{(j-1)(k-1)}$, где ${\omega }_n=e^{-\frac{2\pi i}{n}}$.

Собственные числа матрицы — корни четвёртой степени из единицы $\{1,-1,i,-i\}$, имеющие кратность $\lfloor \frac{n+4}{4}\rfloor$, $\lfloor \frac{n+2}{4}\rfloor$, $\lfloor \frac{n+1}{4}\rfloor$ и $\lfloor \frac{n-1}{4}\rfloor$ соответственно, где $\lfloor x\rfloor$ — округлённое вниз число $x$.

Применение к умножению чисел

Дискретное преобразование Фурье вектора $(a_0;a_1;\dots ;a_{n-1})$ может быть интерпретировано как вычисление значений многочлена $p(x)=a_0+a_{1}x+\dots +a_{n-1}{x}^{n-1}$ в корнях из единицы $x_0=1$, $x_1={\omega }_n$, $x_2={\omega }_n^2$, …, $x_{n-1}={\omega }_n^{n-1}$.

Значения многочлена $n$-й степени в $n+1$ точках однозначно определяют сам многочлен. В то же время, если $p(x)=a$ и $q(x)=b$, то $(p\cdot q)(x)=ab$, потому по значениям многочленов $p(x)$ и $q(x)$ можно также определить значения в тех же точках многочлена $p\cdot q$ и восстановить его обратным дискретным преобразованием Фурье.

Так как любое число представимо в виде многочлена от основания системы счисления $N=a_{n-1}\dots a_1{a}_0=a_0+a_1\cdot 10+\dots +a_{n-1}\cdot 10^{n-1}$, умножение двух чисел может быть в свою очередь сведено к умножению двух многочленов и нормализации результата.

Свойства

1. Линейность
   $ax(n)+by(n)⟷aX(k)+bY(k).$
2. Сдвиг по времени
   $x(n-m)⟷X(k)e^{-\frac{2\pi i}{N}km}.$
3. Периодичность
   $X(k+rN)=X(k),r\in \mathbb{Z}.$
4. Выполняется Теорема Парсеваля.
5. Обладает спектральной плотностью
   $S(k)=|X(k){|}^2.$
6. $x(n)\in ℝ,$
   $X(0)\in ℝ,$
   $Nmod2=0\Rightarrow X(N/2)\in ℝ.$ Нулевая гармоника является суммой значений сигнала.

См. также

• Преобразование Фурье
• Дискретное преобразование Хартли
• Дискретное преобразование Фурье над конечным полем
• Быстрое преобразование Фурье
• Дискретное комплексное преобразование
• Оконное преобразование Фурье

Литература

• Шаблон:Книга
• Шаблон:Книга

• Шаблон:Книга
• Шаблон:Cite Q