Просмотр кода страницы Дискретное преобразование Фурье

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

Дискретные преобразования Фурье помогают решать дифференциальные уравнения в частных производных и выполнять такие операции, как [[Свёртка (математический анализ)|свёртки]]. Дискретные преобразования Фурье также активно используются в статистике, при анализе временных рядов. Существуют многомерные дискретные преобразования Фурье<ref>Федоренко С. В. - [http://pribor.ifmo.ru/ru/article/6336/modifikaciya_algoritma_gercelya—bleyhuta.htm Модификация алгоритма Грецеля-Блейхута] {{Wayback|url=http://pribor.ifmo.ru/ru/article/6336/modifikaciya_algoritma_gercelya%E2%80%94bleyhuta.htm|date=20220324231410}}. - Статья. - Журнал Приборостроение. - УДК 621.391</ref>.

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

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

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

:<math>X_k = \sum_{n=0}^{N-1} x_n e^{-\frac{2 \pi i}{N} k n} = \sum_{n=0}^{N-1} x_n\Big(\cos(2 \pi k n / N) - i\cdot \sin(2 \pi k n / N)\Big), \qquad k = 0, \dots, N-1.</math>

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

:<math>x_n = \frac{1}{N} \sum_{k=0}^{N-1} X_k e^{\frac{2\pi i}{N} k n} =\frac{1}{N} \sum_{k=0}^{N-1} X_k\Big(\cos(2 \pi k n / N) + i\cdot \sin(2 \pi k n / N)\Big), \qquad n = 0,\dots, N-1.</math>

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

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

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

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

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

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

* <math>\arg(X_k)</math> — фаза <math>k</math>-го синусоидального сигнала ([[аргумент комплексного числа]]);

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

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

== Вывод преобразования ==
{{нет источников в разделе|дата=2014-05-30}}
Рассмотрим некоторый периодический сигнал <math> x(t) </math> c периодом, равным T. Разложим его в [[ряд Фурье]]:
: <math> x(t) = \sum_{k=-\infty}^{+\infty} c_k e^{i\omega_k t}, \qquad \omega_k = \frac{2\pi k}{T}. </math>
Проведем дискретизацию сигнала так, чтобы на периоде было N отсчетов. Дискретный сигнал представим в виде отсчетов: <math> x_n = x(t_n)</math>, где <math> t_n = \frac nN T </math>, тогда эти отсчеты через ряд Фурье запишутся следующим образом:
: <math> 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}.</math>
Используя соотношение <math> e ^{\frac{2\pi i}{N} \left(k+mN \right)n} = e ^{\frac{2\pi i}{N} kn}</math>, получаем:
: <math> x_n = \sum_{k=0}^{N-1} X_k e ^{\frac{2\pi i}{N} kn},</math> &nbsp; &nbsp; где &nbsp; &nbsp; <math> \qquad X_k = \sum_{l=-\infty}^{+\infty} c_{k+lN}. </math>
Таким образом мы получили '''обратное дискретное преобразование Фурье'''.

Умножим теперь скалярно выражение для <math> x_n </math> на <math> e^{-\frac{2\pi i}{N} mn}</math> и получим:
: <math> \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}.</math>
Здесь использованы: а) выражение для суммы конечного числа членов (экспонент) геометрической прогрессии, и б) выражение символа Кронекера как предела отношения функций Эйлера для комплексных чисел. Отсюда следует, что:
: <math> X_k = \frac 1N \sum_{n=0}^{N-1} x_n e^{-\frac{2\pi i}{N} kn}.</math>
Эта формула описывает '''прямое дискретное преобразование Фурье'''.

В литературе принято писать множитель <math> \frac{1}{N} </math> в обратном преобразовании, и поэтому обычно пишут формулы преобразования в следующем виде:
: <math>X_n =  \sum_{m=0}^{N-1} x_m e^{-\frac{2\pi i}{N} n m}, \qquad x_m =\frac 1N \sum_{n=0}^{N-1} X_n e ^{\frac{2\pi i}{N} m n}.</math>
Иногда можно встретить симметричную форму записи преобразования
: <math>X_n = \frac 1{\sqrt N} \sum_{m=0}^{N-1} x_m e^{-\frac{2\pi i}{N} n m}, \qquad x_m =\frac 1{\sqrt N} \sum_{n=0}^{N-1} X_n e ^{\frac{2\pi i}{N} m n}.</math>

== Матричное представление ==
Дискретное преобразование Фурье является линейным преобразованием, которое переводит вектор временных отсчётов <math> \vec x </math> в вектор спектральных отсчётов той же длины. Таким образом преобразование может быть реализовано как умножение симметричной квадратной матрицы на вектор:
: <math> \vec X = \mathcal F \vec x, </math>
матрица <math> \mathcal F  </math> имеет вид:
: <math display="inline">
\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}.
</math>
Элементы матрицы задаются следующей формулой:
: <math> \mathcal F(j,k) = \omega_n^{(j-1)(k-1)} </math>, где <math>\omega_n = e^{-\frac{2\pi i}{n}}</math>.
[[Собственные числа]] матрицы — [[Корни из единицы|корни четвёртой степени из единицы]] <math>\{1, -1, i, -i\}</math>, имеющие [[Кратность корня многочлена|кратность]] <math display="inline">\lfloor \frac{n+4}{4} \rfloor </math>, <math display="inline">\lfloor \frac{n+2}{4} \rfloor </math>, <math display="inline">\lfloor \frac{n+1}{4} \rfloor </math> и <math display="inline">\lfloor \frac{n-1}{4} \rfloor </math> соответственно, где <math>\lfloor x \rfloor</math> — [[Целая часть|округлённое вниз]] число <math>x</math>.

== Применение к умножению чисел ==
Дискретное преобразование Фурье вектора <math>(a_0;a_1;\dots;a_{n-1})</math> может быть интерпретировано как [[вычисление значений многочлена]] <math>p(x)=a_0+a_1 x + \dots + a_{n-1}x^{n-1}</math> в [[Корни из единицы|корнях из единицы]] <math>x_0=1</math>, <math>x_1=\omega_n</math>, <math>x_2 = \omega_n^2</math>, …, <math>x_{n-1}=\omega_n^{n-1}</math>.

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

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

== Свойства ==
# Линейность<br /><math>{ax(n)+by(n)} \longleftrightarrow {aX(k)+bY(k)}.</math>
# Сдвиг по времени<br /><math>{x(n-m)} \longleftrightarrow X(k)e^{-\frac{2 \pi i}{N} k m}.</math>
# Периодичность<br /><math>X(k+rN)=X(k), r \in \mathbb Z.</math>
# Выполняется [[Теорема Парсеваля]].
# Обладает спектральной плотностью <br /><math>S(k)= | X(k) | ^2.</math>
# <math> x(n) \in \mathbb R, </math> <br /> <math> X(0) \in \mathbb R, </math> <br />  <math> N \mod  2 =  0 \Rightarrow X(N/2) \in \mathbb R. </math> Нулевая гармоника является суммой значений сигнала.

== См. также ==
* [[Преобразование Фурье]]
* [[Дискретное преобразование Хартли]]
* [[Дискретное преобразование Фурье над конечным полем]]
* [[Быстрое преобразование Фурье]]
* [[Дискретное комплексное преобразование]]
* [[Оконное преобразование Фурье]]

== Литература ==
* {{книга
|автор = Сергиенко А. Б.
|заглавие = Цифровая обработка сигналов
|ссылка = 
|издание = 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
|ссылка = http://www.handbookoffourieranalysis.com/Files/References.pdf
|издание = 
|место = Oxford
|издательство = [[Оксфордский университет|Oxford University]] Press
|год = 2009
|страницы = 744
|isbn = 978-0-19-533532-7
}}
*{{Cite Q|Q107157988}}

== Примечания ==
{{примечания}}

== Ссылки ==
{{cite web| url        =http://ru.dsplib.org/content/dft.html| title        =Дискретное преобразование Фурье (ДПФ)| author        =| date        =| work        =| publisher        =| accessdate        =2010-11-15| lang        =ru| archiveurl        =https://web.archive.org/web/20120101104245/http://www.dsplib.ru/content/dft/dft.html| archivedate        =2012-01-01| deadlink        =yes}}

{{cite web| url        =http://ru.dsplib.org/content/dft_prop.html| title        =Свойства дискретного преобразования Фурье (ДПФ)| author        =| date        =| work        =| publisher        =| accessdate        =2010-11-15| lang        =ru| archiveurl        =https://web.archive.org/web/20120508162219/http://www.dsplib.ru/content/propdft/propdft.html| archivedate        =2012-05-08| deadlink        =yes}}

{{DSP}}

[[Категория:Преобразование Фурье]]
[[Категория:Дискретные преобразования]]
[[Категория:Цифровая обработка сигналов]]