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

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

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

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

$X_k = \sum_{n=0}^{N-1} x_n e^{-\frac{2 \pi i}{N} k n} \qquad k = 0, \dots, N-1$

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

$x_n = \frac{1}{N} \sum_{k=0}^{N-1} X_k e^{\frac{2\pi i}{N} k n} \quad \quad n = 0,\dots,N-1.$

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

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

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

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

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

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

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

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

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

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

$x(t) = \sum_{k=-\infty}^{+\infty} c_k e^{i\omega_k t}, \qquad \omega_k = \frac{2\pi k}{T}$

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

$x_n = \sum_{k=-\infty}^{+\infty} c_k e^{i\omega_k t_n} = \sum_{k=-\infty}^{+\infty} c_k e^{\frac {2\pi i}{N} kn}$

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

$x_n = \sum_{k=0}^{N-1} X_k e ^{\frac{2\pi i}{N} kn},$     где     $\qquad X_k = \sum_{l=-\infty}^{+\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 1N \sum_{n=0}^{N-1} x_n e^{-\frac{2\pi i}{N} kn}$

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

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

$X_k = \sum_{n=0}^{N-1} x_n e^{-\frac{2\pi i}{N} kn}, \qquad x_n =\frac 1N \sum_{k=0}^{N-1} X_k e ^{\frac{2\pi i}{N} kn}$

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

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

$\vec X = \hat A \vec x$

матрица А имеет вид:

$\hat A = \begin{pmatrix} 1 &1 &1 &1 &\ldots &1 \\ 1 &e^{-\frac{2\pi i}{N}} &e^{-\frac{4\pi i}{N}} &e^{-\frac{6\pi i}{N}} &\ldots &e^{-\frac{2\pi i}{N}(N-1)}\\ 1 &e^{-\frac{4\pi i}{N}} &e^{-\frac{8\pi i}{N}} &e^{-\frac{12\pi i}{N}} &\ldots &e^{-\frac{2\pi i}{N}2(N-1)}\\ 1 &e^{-\frac{6\pi i}{N}} &e^{-\frac{12\pi i}{N}} &e^{-\frac{18\pi i}{N}} &\ldots &e^{-\frac{2\pi i}{N}3(N-1)}\\ \vdots &\vdots &\vdots &\vdots &\ddots &\vdots\\ 1 &e^{-\frac{2\pi i}{N}(N-1)} &e^{-\frac{2\pi i}{N}2(N-1)} &e^{-\frac{2\pi i}{N}3(N-1)} &\ldots &e^{-\frac{2\pi i}{N}(N-1)^2} \end{pmatrix}$

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

$A(m,n) = \exp \left( -2\pi i \frac{(m-1)(n-1)}{N} \right)$

Свойства

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

См. также

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

Литература

• Сергиенко А. Б. Цифровая обработка сигналов — 2-е. — Спб: Питер, 2006. — С. 751. — ISBN 5-469-00816-9.
• М. А. Павлейно, В. М. Ромаданов Спектральные преобразования в MatLab — СПб, 2007. — С. 160. — ISBN 978-5-98340-121-1.

Ссылки

Дискретное преобразование Фурье (ДПФ)  (рус.). Проверено 15 ноября 2010.

Свойства дискретного преобразования Фурье (ДПФ)  (рус.). Проверено 15 ноября 2010.