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

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

Преобразование Фурье (Fouriertransform) — это разложение функций на синусоиды (далее косинусные функции мы тоже называем синусоидами, т.к. они отличаются от «настоящих» синусоид только фазой). Существует несколько видов преобразования Фурье.

• 1. Непериодический непрерывный сигнал можно разложить в интеграл Фурье.
• 2. Периодический непрерывный сигнал можно разложить в бесконечный ряд Фурье.
• 3. Непериодический дискретный сигнал можно разложить в интеграл Фурье.
• 4. Периодический дискретный сигнал можно разложить в конечный ряд Фурье.

Компьютер способен работать только с ограниченным объемом данных, следовательно, реально он способен вычислять только последний вид преобразования Фурье. Рассмотрим его подробнее.

ДПФ вещественного сигнала Пусть дискретный сигнал x[n] имеет период N точек. В этом случае его можно представить в виде конечного ряда (т.е. линейной комбинации) дискретных синусоид:

Эквивалентная запись (каждый косинус раскладываем на синус и косинус, но теперь без фазы):

Базисные синусоиды имеют кратные частоты. Первый член ряда (k=0) — это константа, называемая постоянной составляющей (DC offset) сигнала. Самая первая синусоида (k=1) имеет такую частоту, что ее период совпадает с перио-дом самого исходного сигнала. Самая высокочастотная составляющая (k=N/2) имеет такую частоту, что ее период равен двум отсчетам. Коэффициенты и называются спектром сигнала (spectrum). Они показывают амплитуды синусоид, из которых состоит сигнал. Шаг по частоте между двумя соседними синусоидами из разложения Фурье называется частотным разрешением спектра.

На рис. 1 показаны синусоиды, по которым происходит разложение дискретного сигнала из 8 точек. Каждая из синусоид состоит из 8 точек, то есть является обычным дискретным сигналом. Непрерывные синусоиды показаны на рисунке для наглядности.

Как мы увидим далее, для каждого сигнала можно однозначно определить коэффициенты и .

Зная эти коэффициенты, можно однозначно восстановить исходный сигнал, вычислив сумму ряда Фурье в каждой точке. Разложение сигнала на синусоиды (т.е. получение коэффициентов) называется прямым преобразованием Фурье. Обратный процесс — синтез сигнала по синусоидам — называется обратным преобразованием Фурье (inverseFouriertransform).

Алгоритм обратного преобразования Фурье очевиден (он содержится в формуле ряда Фурье; для проведения синтеза нужно просто подставить в нее коэффициенты). Рассмотрим алгоритм прямого преобразования Фурье, т. е. нахождения коэффициентов и .

Система функций:

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

Итак, коэффициенты и вычисляются как скалярные произведения (в непрерывном случае — интегралы от произведения функций, в дискретном случае — суммы от произведения дискретных сигналов):

Возникает вопрос: почему в исходном сигнале N чисел, а описывается он с помощью N+2 коэффициентов? Вопрос разрешается следующим образом: коэффициенты и всегда равны нулю (т.к. соответствующие им «базисные» сигналы тождественно равны нулю в дискретных точках), и их можно отбросить при вычислении обратного и прямого преобразований Фурье.

Итак, мы выяснили, что спектральное представление сигнала полностью эквивалентно самому сигналу. Между ними можно перемещаться, используя прямое и обратное преобразования Фурье. Алгоритм вычисления этих преобразований содержится в приведенных формулах.