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

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

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

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

$X_k=\underset{n=0}{\overset{N-<!--\; -\; -->1}{\sum <!--\; \sum \; -->}}{x}_n{e}^{-<!--\; -\; -->\frac{2\mathrm{\pi <!--\; \pi \; -->}i}{N}kn}=\underset{n=0}{\overset{N-<!--\; -\; -->1}{\sum <!--\; \sum \; -->}}{x}_n(\cos <!--\; \; -->(2\mathrm{\pi <!--\; \pi \; -->}kn/N)-<!--\; -\; -->i\cdot <!--\; \cdot \; -->\sin <!--\; \; -->(2\mathrm{\pi <!--\; \pi \; -->}kn/N)),k=0,\dots <!--\; \dots \; -->,N-<!--\; -\; -->1.$$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}\underset{k=0}{\overset{N-<!--\; -\; -->1}{\sum <!--\; \sum \; -->}}{X}_k{e}^{\frac{2\mathrm{\pi <!--\; \pi \; -->}i}{N}kn}=\frac{1}{N}\underset{k=0}{\overset{N-<!--\; -\; -->1}{\sum <!--\; \sum \; -->}}{X}_k(\cos <!--\; \; -->(2\mathrm{\pi <!--\; \pi \; -->}kn/N)+i\cdot <!--\; \cdot \; -->\sin <!--\; \; -->(2\mathrm{\pi <!--\; \pi \; -->}kn/N)),n=0,\dots <!--\; \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$$N$  — количество значений сигнала, измеренных за период, а также количество компонент разложения;

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

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

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

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

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

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

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

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

$x(t)=\underset{k=-<!--\; -\; -->\mathrm{\infty <!--\; \infty \; -->}}{\overset{+\mathrm{\infty <!--\; \infty \; -->}}{\sum <!--\; \sum \; -->}}{c}_k{e}^{i{\mathrm{\omega <!--\; \omega \; -->}}_{k}t},{\mathrm{\omega <!--\; \omega \; -->}}_k=\frac{2\mathrm{\pi <!--\; \pi \; -->}k}{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)$$x_n = x(t_n)$ , где $t_n=\frac{n}{N}T$$t_n = \frac nN T$ , тогда эти отсчеты через ряд Фурье запишутся следующим образом:

$x_n=\underset{k=-<!--\; -\; -->\mathrm{\infty <!--\; \infty \; -->}}{\overset{+\mathrm{\infty <!--\; \infty \; -->}}{\sum <!--\; \sum \; -->}}{c}_k{e}^{i{\mathrm{\omega <!--\; \omega \; -->}}_k{t}_n}=\underset{k=-<!--\; -\; -->\mathrm{\infty <!--\; \infty \; -->}}{\overset{+\mathrm{\infty <!--\; \infty \; -->}}{\sum <!--\; \sum \; -->}}{c}_k{e}^{\frac{2\mathrm{\pi <!--\; \pi \; -->}i}{N}kn}.$$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\mathrm{\pi <!--\; \pi \; -->}i}{N}\left(k+mN\right)n}=e^{\frac{2\mathrm{\pi <!--\; \pi \; -->}i}{N}kn}$$e ^{\frac{2\pi i}{N} \left(k+mN \right)n} = e ^{\frac{2\pi i}{N} kn}$ , получаем:

$x_n=\underset{k=0}{\overset{N-<!--\; -\; -->1}{\sum <!--\; \sum \; -->}}{X}_k{e}^{\frac{2\mathrm{\pi <!--\; \pi \; -->}i}{N}kn},$$x_n = \sum_{k=0}^{N-1} X_k e ^{\frac{2\pi i}{N} kn},$      где     $X_k=\underset{l=-<!--\; -\; -->\mathrm{\infty <!--\; \infty \; -->}}{\overset{+\mathrm{\infty <!--\; \infty \; -->}}{\sum <!--\; \sum \; -->}}{c}_{k+lN}.$$\qquad X_{k}=\sum _{l=-\infty }^{+\infty }c_{k+lN}.$ 

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

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

$\underset{n=0}{\overset{N-<!--\; -\; -->1}{\sum <!--\; \sum \; -->}}{x}_n{e}^{-<!--\; -\; -->\frac{2\mathrm{\pi <!--\; \pi \; -->}i}{N}mn}=\underset{k=0}{\overset{N-<!--\; -\; -->1}{\sum <!--\; \sum \; -->}}\underset{n=0}{\overset{N-<!--\; -\; -->1}{\sum <!--\; \sum \; -->}}{X}_k{e}^{\frac{2\mathrm{\pi <!--\; \pi \; -->}i}{N}(k-<!--\; -\; -->m)n}=\underset{k=0}{\overset{N-<!--\; -\; -->1}{\sum <!--\; \sum \; -->}}{X}_k\frac{1-<!--\; -\; -->e^{2\mathrm{\pi <!--\; \pi \; -->}i(k-<!--\; -\; -->m)}}{1-<!--\; -\; -->e^{\frac{2\mathrm{\pi <!--\; \pi \; -->}i(k-<!--\; -\; -->m)}{N}}}=\underset{k=0}{\overset{N-<!--\; -\; -->1}{\sum <!--\; \sum \; -->}}{X}_{k}N{\mathrm{\delta <!--\; \delta \; -->}}_{km}.$$\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}\underset{n=0}{\overset{N-<!--\; -\; -->1}{\sum <!--\; \sum \; -->}}{x}_n{e}^{-<!--\; -\; -->\frac{2\mathrm{\pi <!--\; \pi \; -->}i}{N}kn}.$$X_{k}={\frac {1}{N}}\sum _{n=0}^{N-1}x_{n}e^{-{\frac {2\pi i}{N}}kn}.$ 

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

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

$X_n=\underset{m=0}{\overset{N-<!--\; -\; -->1}{\sum <!--\; \sum \; -->}}{x}_m{e}^{-<!--\; -\; -->\frac{2\mathrm{\pi <!--\; \pi \; -->}i}{N}nm},x_m=\frac{1}{N}\underset{n=0}{\overset{N-<!--\; -\; -->1}{\sum <!--\; \sum \; -->}}{X}_n{e}^{\frac{2\mathrm{\pi <!--\; \pi \; -->}i}{N}mn}.$$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}}\underset{m=0}{\overset{N-<!--\; -\; -->1}{\sum <!--\; \sum \; -->}}{x}_m{e}^{-<!--\; -\; -->\frac{2\mathrm{\pi <!--\; \pi \; -->}i}{N}nm},x_m=\frac{1}{\sqrt{N}}\underset{n=0}{\overset{N-<!--\; -\; -->1}{\sum <!--\; \sum \; -->}}{X}_n{e}^{\frac{2\mathrm{\pi <!--\; \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}.$ 

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

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

$\stackrel{\to <!--\; \to \; -->}{X}=\mathcal{F}\stackrel{\to <!--\; \to \; -->}{x},$${\vec {X}}={\mathcal {F}}{\vec {x}},$ 

матрица $\mathcal{F}$${\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)={\mathrm{\omega <!--\; \omega \; -->}}_n^{(j-<!--\; -\; -->1)(k-<!--\; -\; -->1)}$${\mathcal {F}}(j,k)=\omega _{n}^{(j-1)(k-1)}$ , где ${\mathrm{\omega <!--\; \omega \; -->}}_n=e^{-<!--\; -\; -->\frac{2\mathrm{\pi <!--\; \pi \; -->}i}{n}}$$\omega _{n}=e^{-{\frac {2\pi i}{n}}}$ .

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

Применение к умножению чиселПравить

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

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

Так как любое число представимо в виде многочлена от основания системы счисления $N=a_{n-<!--\; -\; -->1}\dots <!--\; \dots \; -->a_1{a}_0=a_0+a_1\cdot <!--\; \cdot \; -->10+\cdots <!--\; \cdots \; -->+a_{n-<!--\; -\; -->1}\cdot <!--\; \cdot \; -->{10}^{n-<!--\; -\; -->1}$$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).$${ax(n)+by(n)}\longleftrightarrow {aX(k)+bY(k)}.$ 
2. Сдвиг по времени
   $x(n-<!--\; -\; -->m)⟷<!--\; ⟷\; -->X(k)e^{-<!--\; -\; -->\frac{2\mathrm{\pi <!--\; \pi \; -->}i}{N}km}.$${x(n-m)}\longleftrightarrow X(k)e^{-{\frac {2\pi i}{N}}km}.$ 
3. Периодичность
   $X(k+rN)=X(k),r\in <!--\; \in \; -->\mathbb{Z}.$$X(k+rN)=X(k),r\in \mathbb {Z} .$ 
4. Выполняется Теорема Парсеваля.
5. Обладает спектральной плотностью
   $S(k)=|X(k){|}^2.$$S(k)=|X(k)|^{2}.$ 
6. $x(n)\in <!--\; \in \; -->\mathbb{R},$$x(n)\in \mathbb {R} ,$ 
   $X(0)\in <!--\; \in \; -->\mathbb{R},$$X(0)\in \mathbb {R} ,$ 
   $N\mathrm{mod}2=0\Rightarrow <!--\; \Rightarrow \; -->X(N/2)\in <!--\; \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 (англ.) // J. Math. Phys. — 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 года.