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

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

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

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

[math]\displaystyle{ 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]\displaystyle{ 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]\displaystyle{ N }[/math] — количество значений сигнала, измеренных за период, а также количество компонент разложения;

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

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

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

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

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

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

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

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

[math]\displaystyle{ x(t) = \sum_{k=-\infty}^{+\infty} c_k e^{i\omega_k t}, \qquad \omega_k = \frac{2\pi k}{T}. }[/math]

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

[math]\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}. }[/math]

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

[math]\displaystyle{ x_n = \sum_{k=0}^{N-1} X_k e ^{\frac{2\pi i}{N} kn}, }[/math]     где     [math]\displaystyle{ \qquad X_k = \sum_{l=-\infty}^{+\infty} c_{k+lN}. }[/math]

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

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

[math]\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}. }[/math]

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

[math]\displaystyle{ X_k = \frac 1N \sum_{n=0}^{N-1} x_n e^{-\frac{2\pi i}{N} kn}. }[/math]

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

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

[math]\displaystyle{ 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]\displaystyle{ 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]\displaystyle{ \langle x|y\rangle=\langle X|Y\rangle }[/math], где [math]\displaystyle{ \langle x|y\rangle=\sum_{n=0}^{N-1}x_n^*\,y_n }[/math]. Здесь звёздочка обозначает комплексное сопряжение: [math]\displaystyle{ x=\operatorname{Re}x+i\operatorname{Im}x~\Rightarrow~x^*=\operatorname{Re}x-i\operatorname{Im}x }[/math].

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

Дискретное преобразование Фурье, записанное в симметричной форме является унитарным линейным преобразованием, которое переводит вектор временных отсчётов [math]\displaystyle{ \vec x }[/math] в вектор спектральных отсчётов той же <<длины>> (с тем же скалярным квадратом). Преобразование может быть реализовано как умножение симметричной квадратной матрицы на вектор-столбец (строки и столбцы нумеруются числами от 0 для [math]\displaystyle{ N-1 }[/math] в порядке возрастания):

[math]\displaystyle{ \vec X = \mathcal F \vec x, }[/math]

матрица [math]\displaystyle{ \mathcal F }[/math] имеет вид:

[math]\displaystyle{ \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]\displaystyle{ \mathcal F(j,k) = \omega_N^{(j-1)(k-1)} }[/math], где [math]\displaystyle{ \omega_N = e^{-\frac{2\pi i}{N}} }[/math].

Собственные числа матрицы — корни четвёртой степени из единицы [math]\displaystyle{ \{1, -1, i, -i\} }[/math], имеющие кратность [math]\displaystyle{ \lfloor \frac{N+4}{4} \rfloor }[/math], [math]\displaystyle{ \lfloor \frac{N+2}{4} \rfloor }[/math], [math]\displaystyle{ \lfloor \frac{N+1}{4} \rfloor }[/math] и [math]\displaystyle{ \lfloor \frac{N-1}{4} \rfloor }[/math] соответственно, где [math]\displaystyle{ \lfloor x \rfloor }[/math] — округлённое вниз число [math]\displaystyle{ x }[/math].

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

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

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

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

Свойства

1. Линейность
   [math]\displaystyle{ {ax(n)+by(n)} \longleftrightarrow {aX(k)+bY(k)}. }[/math]
2. Сдвиг по <<времени>>: если периодически продолжить [math]\displaystyle{ x(n) }[/math] на все целые [math]\displaystyle{ n }[/math] с периодом [math]\displaystyle{ N }[/math], то
   [math]\displaystyle{ {x(n-m)} \longleftrightarrow X(k)e^{-\frac{2 \pi i}{N} k m}. }[/math]
3. Периодичность
   [math]\displaystyle{ X(k+rN)=X(k), r \in \mathbb Z. }[/math]
4. Выполняется Теорема Парсеваля.
5. Обладает спектральной плотностью
   [math]\displaystyle{ S(k)= | X(k) | ^2. }[/math]
6. [math]\displaystyle{ x(n) \in \mathbb R, }[/math]
   [math]\displaystyle{ X(0) \in \mathbb R, }[/math]
   [math]\displaystyle{ 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. — Oxford: Oxford University Press, 2009. — С. 744. — ISBN 978-0-19-533532-7.
• Шаблон:Cite Q

Ссылки

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

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