7.Дискретное преобразование Фурье
Дискретное преобразование Фурье (в англоязычной литературе DFT, Discrete Fourier Transform) — это одно из преобразований Фурье, широко применяемых в алгоритмах цифровой обработки сигналов (его модификации применяются в сжатии звука в MP3, сжатии изображений в JPEG и др.), а также в других областях, связанных с анализом частот в дискретном (к примеру, оцифрованном аналоговом) сигнале. Дискретное преобразование Фурье требует в качестве входа дискретную функцию. Такие функции часто создаются путём дискретизации (выборки значений из непрерывных функций). Дискретные преобразования Фурье помогают решать частные дифференциальные уравнения и выполнять такие операции, как свёртки. Дискретные преобразования Фурье также активно используются в статистике, при анализе временных рядов. Существуют многомерные дискретные преобразования Фурье.
Прямое преобразование:
Обратное преобразование:
Обозначения:
—
количество
значений сигнала, измеренных за период,
а также количество компонент разложения;
—
измеренные
значения сигнала (в дискретных временных
точках с номерами 
,
которые являются входными данными для
прямого преобразования и выходными
для обратного;
—
комплексных
амплитуд синусоидальных
сигналов, слагающих исходный сигнал;
являются выходными данными для прямого
преобразования и входными для обратного;
поскольку амплитуды комплексные, то
по ним можно вычислить одновременно и
амплитуду, и фазу;
—
обычная
(вещественная) амплитуда k-го синусоидального
сигнала;
—
фаза
k-го синусоидального сигнала (аргумент
комплексного числа);
— индекс частоты. Частота k-го сигнала равна
,
где 
—
период времени, в течение которого
брались входные данные.
Из последнего видно, что преобразование раскладывает сигнал на синусоидальные составляющие (которые называются гармониками) с частотами от N колебаний за период до одного колебания за период. Поскольку частота дискретизации сама по себе равна N отсчётов за период, то высокочастотные составляющие не могут быть корректно отображены — возникает муаровый эффект. Это приводит к тому, что вторая половина из N комплексных амплитуд, фактически, является зеркальным отображением первой и не несёт дополнительной информации.
[править]Вывод преобразования
Рассмотрим
некоторый периодический сигнал 
c
периодом равным T. Разложим его в ряд
Фурье:
Проведем
дискретизацию сигнала так, чтобы на
периоде было N отсчетов. Дискретный
сигнал представим в виде отсчетов: 
,
где 
,
тогда эти отсчеты через ряд Фурье
запишутся следующим образом:
Используя
соотношение: 
,
получаем:
где
Таким образом мы получили обратное дискретное преобразование Фурье.
Умножим
теперь скалярно выражение для 
на 
и
получим:
Здесь использованы: а) выражение для суммы конечного числа членов (экспонент) геометрической прогрессии, и б) выражение символа Кронекера как предела отношения функций Эйлера для комплексных чисел. Отсюда следует, что:
Эта формула описывает прямое дискретное преобразование Фурье.
В
литературе принято писать множитель 
в
обратном преобразовании, и поэтому
обычно пишут формулы преобразования в
следующем виде:
