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

Дискретное преобразование Фурье (в англоязычной литературе 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}{\Big (}\cos(2\pi kn/N)-i\cdot \sin(2\pi kn/N){\Big )},\qquad 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}{\Big (}\cos(2\pi kn/N)+i\cdot \sin(2\pi kn/N){\Big )},\qquad 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$ — период времени, в течение которого брались входные данные.

Из последнего видно, что преобразование раскладывает сигнал на синусоидальные составляющие (которые называются гармониками) с частотами от $1$ колебания за период до $N-1$ колебаний за период (плюс константа). Поскольку частота дискретизации сама по себе равна $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 {n}{N}}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 {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},\qquad 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},\qquad x_{m}={\frac {1}{\sqrt {N}}}\sum _{n=0}^{N-1}X_{n}e^{{\frac {2\pi i}{N}}mn}.$

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

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

${\vec {X}}={\mathcal {F}}{\vec {x}},$

матрица ${\mathcal {F}}$ имеет вид:

${\textstyle {\mathcal {F}}={\frac {1}{\sqrt {n}}}{\begin{pmatrix}1&1&1&1&\ldots &1\\1&\omega _{n}&\omega _{n}^{2}&\omega _{n}^{3}&\ldots &\omega _{n}^{n-1}\\1&\omega _{n}^{2}&\omega _{n}^{4}&\omega _{n}^{6}&\ldots &\omega _{n}^{2(n-1)}\\1&\omega _{n}^{3}&\omega _{n}^{6}&\omega _{n}^{9}&\ldots &\omega _{n}^{3(n-1)}\\\vdots &\vdots &\vdots &\vdots &\ddots &\vdots \\1&\omega _{n}^{n-1}&\omega _{n}^{2(n-1)}&\omega _{n}^{3(n-1)}&\ldots &\omega _{n}^{(n-1)^{2}}\end{pmatrix}}.}$

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

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

Собственные числа матрицы — корни четвёртой степени из единицы $\{1,-1,i,-i\}$, имеющие кратность ${\textstyle \lfloor {\frac {n+4}{4}}\rfloor }$, ${\textstyle \lfloor {\frac {n+2}{4}}\rfloor }$, ${\textstyle \lfloor {\frac {n+1}{4}}\rfloor }$ и ${\textstyle \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)}\longleftrightarrow {aX(k)+bY(k)}.$
2. Сдвиг по времени
   ${x(n-m)}\longleftrightarrow 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 \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.

• Robert J. Marks II. Handbook of Fourier Analysis & Its Applications. — Oxford: Oxford University Press, 2009. — С. 744. — ISBN 978-0-19-533532-7.
• Mehta M. L. Eigenvalues and eigenvectors of the finite Fourier transform (англ.) // Journal of Mathematical Physics — AIP, 1986. — Vol. 28, Iss. 4. — P. 781—785. — ISSN 0022-2488; 1089-7658; 1527-2427 — doi:10.1063/1.527619

Ссылки

Дискретное преобразование Фурье (ДПФ)  (рус.). Дата обращения: 15 ноября 2010. Архивировано из оригинала 1 января 2012 года.

Свойства дискретного преобразования Фурье (ДПФ)  (рус.). Дата обращения: 15 ноября 2010. Архивировано из оригинала 8 мая 2012 года.