Дискретное преобразование Фурье (в англоязычной литературе DFT, Discrete Fourier Transform) — это одно из преобразований Фурье, широко применяемых в алгоритмах цифровой обработки сигналов (его модификации применяются в сжатии звука в MP3, сжатии изображений в JPEG и др.), а также в других областях, связанных с анализом частот в дискретном (к примеру, оцифрованном аналоговом) сигнале.
Дискретные преобразования Фурье помогают решать дифференциальные уравнения в частных производных и выполнять такие операции, как свёртки. Дискретные преобразования Фурье также активно используются в статистике, при анализе временных рядов. Существуют многомерные дискретные преобразования ФурьеФедоренко С. В. - Модификация алгоритма Грецеля-Блейхута . - Статья. - Журнал Приборостроение. - УДК 621.391.
Дискретное преобразование Фурье требует в качестве входа дискретную функцию. Такие функции часто создаются путём дискретизации (выборки значений из непрерывных функций).
Формулы преобразований
Прямое преобразование:
Обратное преобразование:
Вторая часть выражения следует из первой по формуле Эйлера.
Обозначения:
— количество значений сигнала, измеренных за период, а также количество компонент разложения;
— измеренные значения сигнала (в дискретных временных точках с номерами ), которые являются входными данными для прямого преобразования и выходными для обратного;
— комплексных амплитуд синусоидальных сигналов, слагающих исходный сигнал; являются выходными данными для прямого преобразования и входными для обратного; поскольку амплитуды комплексные, то по ним можно вычислить одновременно и амплитуду, и фазу;
— обычная (вещественная) амплитуда -го синусоидального сигнала;
— фаза -го синусоидального сигнала (аргумент комплексного числа);
— индекс частоты. Частота -го сигнала равна , где — период времени, в течение которого брались входные данные.
Из последнего видно, что преобразование раскладывает сигнал на синусоидальные составляющие (которые называются гармониками) с частотами от колебания за период до колебаний за период (плюс константа). Поскольку частота дискретизации сама по себе равна отсчётов за период, то высокочастотные составляющие не могут быть корректно отображены — возникает муаровый эффект. Это приводит к тому, что вторая половина из комплексных амплитуд, фактически, является зеркальным отображением первой и не несёт дополнительной информации.
Вывод преобразования
Рассмотрим некоторый периодический сигнал c периодом, равным T. Разложим его в ряд Фурье:
Проведем дискретизацию сигнала так, чтобы на периоде было N отсчетов. Дискретный сигнал представим в виде отсчетов: , где , тогда эти отсчеты через ряд Фурье запишутся следующим образом:
Используя соотношение , получаем: где Таким образом мы получили обратное дискретное преобразование Фурье.
Умножим теперь скалярно выражение для на и получим:
Здесь использованы: а) выражение для суммы конечного числа членов (экспонент) геометрической прогрессии, и б) выражение символа Кронекера как предела отношения функций Эйлера для комплексных чисел. Отсюда следует, что:
Эта формула описывает прямое дискретное преобразование Фурье.
В литературе принято писать множитель в обратном преобразовании, и поэтому обычно пишут формулы преобразования в следующем виде:
Иногда можно встретить симметричную форму записи преобразования
Матричное представление Дискретное преобразование Фурье является линейным преобразованием, которое переводит вектор временных отсчётов в вектор спектральных отсчётов той же длины. Таким образом преобразование может быть реализовано как умножение симметричной квадратной матрицы на вектор:
матрица имеет вид:
Элементы матрицы задаются следующей формулой: , где . Собственные числа матрицы — корни четвёртой степени из единицы , имеющие кратность , , и соответственно, где — округлённое вниз число .
Применение к умножению чисел Дискретное преобразование Фурье вектора может быть интерпретировано как вычисление значений многочлена в корнях из единицы , , , …, .
Значения многочлена -й степени в точках однозначно определяют сам многочлен. В то же время, если и , то , потому по значениям многочленов и можно также определить значения в тех же точках многочлена и восстановить его обратным дискретным преобразованием Фурье.
Так как любое число представимо в виде многочлена от основания системы счисления , умножение двух чисел может быть в свою очередь сведено к умножению двух многочленов и нормализации результата.
Свойства Линейность Сдвиг по времени Периодичность Выполняется Теорема Парсеваля. Обладает спектральной плотностью Нулевая гармоника является суммой значений сигнала.
Теорема смещения Умножение на линейную фазу при некотором целом m соответствует циклическому сдвигу выходного сигнала : заменяется на , где индекс интерпретируется по модулю N (то есть, периодически). Аналогично, циклический сдвиг входного сигнала соответствует умножению выходного сигнала на . Математически, если представляет вектор x то
еслиif то и
См. также Преобразование Фурье Дискретное преобразование Хартли Дискретное преобразование Фурье над конечным полем Быстрое преобразование Фурье Дискретное комплексное преобразование Оконное преобразование Фурье
Литература
Примечания
Ссылки
Категория:Преобразование Фурье Категория:Дискретные преобразования Категория:Цифровая обработка сигналов