- ДПФ
-
Дискретное преобразование Фурье (в англоязычной литературе DFT, Discrete Fourier Transform) — это одно из преобразований Фурье, широко применяемых в алгоритмах цифровой обработки сигналов (его модификации применяются в сжатии звука в jpg и др.), а также в других областях, связанных с анализом частот в дискретном (к примеру, оцифрованном аналоговом) сигнале. Также дискретные преобразования Фурье помогают решать частные дифференциальные уравнения и выполнять такие операции, как свёртки. Преобразования бывают одномерные, двумерные и даже трехмерные.
Последовательность N комплексных чисел x0, …, xN−1 преобразуется в последовательность из N комплексных чисел X0, …, XN−1 с помощью дискретного преобразования Фурье по формуле:
где i — это мнимая единица. Обратное дискретное преобразование Фурье задается формулой
Поскольку напрямую вычисления дискретного преобразования требует O(N2) операций, то на практике используют более быстрый алгоритм Быстрого преобразования Фурье, которое требует O(NlogN) операций.
Содержание
Вывод преобразования
Рассмотрим некоторый периодический сигнал x(t) c периодом равным T. Разложим его в ряд Фурье:
Проведем дискретизацию сигнала так, чтобы на периоде было N отсчетов. Дискретный сигнал представим в виде отсчетов: xn = x(tn), где , тогда ряд Фурье запишется следующим образом:
Используя соотношение: , получаем:
Таким образом мы получили обратное дискретное преобразование Фурье.
Умножим теперь скалярно выражение для xn на и получим:
Откуда следует, что:
Эта формула описывает прямое дискретное преобразование Фурье.
В литературе принято писать множитель в обратном преобразовании, и поэтому обычно пишут формулы преобразования в следующем виде:
Матричное представление
Дискретное преобразование Фурье является линейным преобразованием, которое переводит вектор временных отсчетов в вектор спектральных отсчетов той же длины. Таким образом преобразование может быть реализовано как умножение квадратной матрицы на вектор:
матрица А имеет вид:
Элементы матрицы задаются следующей формулой:
Свойства
- 1) линейность
- 2) сдвиг по времени
- 3) периодичность
- 4) выполняется Теорема Парсеваля
- 5) симметрии
- X(k) = X(N − k)
Таким образом информацию несут первые N/2 гармоник.
- 6) обладает спектральной плотностью
- S(k) = | x(k) | 2
- 7)
Стоит отметить, что нулевая гармоника является суммой значений сигнала.
См. также
- Преобразование Фурье
- Дискретное преобразование Хартли
- Дискретное преобразование Фурье над конечным полем
- Быстрое преобразование Фурье
- Дискретное комплексное преобразование
- Оконное преобразование Фурье
Литература
- Сергиенко А. Б. Цифровая обработка сигналов. — 2-е. — Спб: Питер, 2006. — С. 751. — ISBN 5-469-00816-9
- М. А. Павлейно, В. М. Ромаданов Спектральные преобразования в MatLab. — СПб: 2007. — С. 160. — ISBN 978-5-98340-121-1
Wikimedia Foundation. 2010.