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

У этого термина существуют и другие значения, см. ДПФ.

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

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

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

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

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

${\displaystyle 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.}$

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

${\displaystyle 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.}$

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

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

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

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

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

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

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

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

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

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

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

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

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

${\displaystyle 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}.}$

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

${\displaystyle x_{n}=\sum _{k=0}^{N-1}X_{k}e^{{\frac {2\pi i}{N}}kn},}$     где     ${\displaystyle \qquad X_{k}=\sum _{l=-\infty }^{+\infty }c_{k+lN}.}$

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

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

${\displaystyle \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}.}$

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

${\displaystyle X_{k}={\frac {1}{N}}\sum _{n=0}^{N-1}x_{n}e^{-{\frac {2\pi i}{N}}kn}.}$

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

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

${\displaystyle 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}.}$

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

${\displaystyle 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}.}$

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

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

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

матрица ${\displaystyle {\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}}.}$

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

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

Собственные числа матрицы — корни четвёртой степени из единицы ${\displaystyle \{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 }$ соответственно, где ${\displaystyle \lfloor x\rfloor }$ — округлённое вниз число ${\displaystyle x}$.

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

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

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

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

Свойства

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