Русская Википедия:Дискретное преобразование Фурье
Шаблон:Другие значения Дискретное преобразование Фурье (в англоязычной литературе DFT, Discrete Fourier Transform) — это одно из преобразований Фурье, широко применяемых в алгоритмах цифровой обработки сигналов (его модификации применяются в сжатии звука в MP3, сжатии изображений в JPEG и др.), а также в других областях, связанных с анализом частот в дискретном (к примеру, оцифрованном аналоговом) сигнале. Дискретное преобразование Фурье требует в качестве входа дискретную функцию. Такие функции часто создаются путём дискретизации (выборки значений из непрерывных функций). Дискретные преобразования Фурье помогают решать дифференциальные уравнения в частных производных и выполнять такие операции, как свёртки. Дискретные преобразования Фурье также активно используются в статистике, при анализе временных рядов. Существуют многомерные дискретные преобразования Фурье[1].
Формулы преобразований
Прямое преобразование:
- <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> комплексных амплитуд, фактически, является зеркальным отображением первой и не несёт дополнительной информации.
Вывод преобразования
Шаблон:Нет источников в разделе Рассмотрим некоторый периодический сигнал <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> где <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>, умножение двух чисел может быть в свою очередь сведено к умножению двух многочленов и нормализации результата.
Свойства
- Линейность
<math>{ax(n)+by(n)} \longleftrightarrow {aX(k)+bY(k)}.</math> - Сдвиг по времени
<math>{x(n-m)} \longleftrightarrow X(k)e^{-\frac{2 \pi i}{N} k m}.</math> - Периодичность
<math>X(k+rN)=X(k), r \in \mathbb Z.</math> - Выполняется Теорема Парсеваля.
- Обладает спектральной плотностью
<math>S(k)= | X(k) | ^2.</math> - <math> x(n) \in \mathbb R, </math>
<math> X(0) \in \mathbb R, </math>
<math> N \mod 2 = 0 \Rightarrow X(N/2) \in \mathbb R. </math> Нулевая гармоника является суммой значений сигнала.
См. также
- Преобразование Фурье
- Дискретное преобразование Хартли
- Дискретное преобразование Фурье над конечным полем
- Быстрое преобразование Фурье
- Дискретное комплексное преобразование
- Оконное преобразование Фурье
Литература
Примечания
Ссылки
- ↑ Федоренко С. В. - Модификация алгоритма Грецеля-Блейхута Шаблон:Wayback. - Статья. - Журнал Приборостроение. - УДК 621.391
