WikiSort.ru - Не сортированное

Дискретное преобразование Фурье (в англоязычной литературе 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}\cdot [\cos(2\pi kn/N)-i\cdot \sin(2\pi kn/N)],\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}\quad \quad (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 N}$ колебаний за период до одного колебания за период. Поскольку частота дискретизации сама по себе равна N отсчётов за период, то высокочастотные составляющие не могут быть корректно отображены — возникает муаровый эффект. Это приводит к тому, что вторая половина из ${\displaystyle N}$ комплексных амплитуд, фактически, является зеркальным отображением первой и не несёт дополнительной информации.

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

В этом разделе не хватает ссылок на источники информации. Информация должна быть проверяема, иначе она может быть поставлена под сомнение и удалена. Вы можете отредактировать эту статью, добавив ссылки на авторитетные источники. Эта отметка установлена 30 мая 2014 года.

Рассмотрим некоторый периодический сигнал ${\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}}={\hat {A}}{\vec {x}},}$

матрица ${\displaystyle {\hat {A}}}$ имеет вид:

${\displaystyle {\hat {A}}={\begin{pmatrix}1&1&1&1&\ldots &1\\1&e^{-{\frac {2\pi i}{N}}}&e^{-{\frac {4\pi i}{N}}}&e^{-{\frac {6\pi i}{N}}}&\ldots &e^{-{\frac {2\pi i}{N}}(N-1)}\\1&e^{-{\frac {4\pi i}{N}}}&e^{-{\frac {8\pi i}{N}}}&e^{-{\frac {12\pi i}{N}}}&\ldots &e^{-{\frac {2\pi i}{N}}2(N-1)}\\1&e^{-{\frac {6\pi i}{N}}}&e^{-{\frac {12\pi i}{N}}}&e^{-{\frac {18\pi i}{N}}}&\ldots &e^{-{\frac {2\pi i}{N}}3(N-1)}\\\vdots &\vdots &\vdots &\vdots &\ddots &\vdots \\1&e^{-{\frac {2\pi i}{N}}(N-1)}&e^{-{\frac {2\pi i}{N}}2(N-1)}&e^{-{\frac {2\pi i}{N}}3(N-1)}&\ldots &e^{-{\frac {2\pi i}{N}}(N-1)^{2}}\end{pmatrix}}.}$

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

${\displaystyle A(m,n)=\exp \left(-2\pi i{\frac {(m-1)(n-1)}{N}}\right).}$

Свойства

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.

Примечания

Ссылки

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

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