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

---

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

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

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

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

---