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

Введение
Дискретное преобразование Фурье (ДПФ) — один из распространенных инструментов спектрального анализа сигналов, широко применяемый в самых разных отраслях науки и техники. При этом разработано множество быстрых алгоритмов для высокой вычислительной эффективности ДПФ.
В данном разделе будет уделено особое внимание переходу от непрерывного интеграла Фурье к дискретно-временному преобразованию Фурье (ДВПФ) и, далее, к дискретному преобразованию Фурье. Понимание данного перехода позволит лучше понять свойства ДПФ и сущность цифрового спектрального анализа в целом.
Пара непрерывного преобразования Фурье (интеграл Фурье) имеет вид:
(1)
где — спектр сигнала (в общем случае и сигнал и спектр — комплексные).
Выражения для прямого ДПФ и обратного дискретного преобразования Фурье (ОДПФ) имеют вид:
(2)
ДПФ ставит в соответствие отсчетам сигнала , , отсчетов комплексного спектра , . Здесь и далее в данном разделе переменная индексирует временные отсчеты сигнала, а переменная индексирует спектральные отсчеты ДПФ.
Как в непрерывном, так и в дискретном случаях в выражениях для обратного преобразования имеется нормировочный коэффициент. В случае интеграла Фурье это , в случае ОДПФ – .
Нормировочный коэффициент необходим для корректного масштабирования сигнала из частотной области во временную. Нормировочный коэффициент уменьшает амплитуду сигнала на выходе обратного преобразования, для того чтобы она совпадала с амплитудой исходного сигнала. Если последовательно рассчитать прямое преобразование Фурье некоторого сигнала, а после взять обратное преобразование Фурье, то результат обратного преобразования должен полностью совпадать с исходным сигналом.
Дискретизация сигнала по времени. Дискретно-временное преобразование Фурье.
Рассмотрим дискретный сигнал как результат умножения непрерывного сигнала на решетчатую функцию:
(3)
где – дельта-функция:
(4)
– интервал дискретизации. Графически процесс дискретизации можно представить, как это показано на рисунке 1.
Рисунок 1. Процесс дискретизации сигнала
Вычислим преобразование Фурье дискретного сигнала , для этого подставим выражение (3) в выражение для преобразования Фурье (1):
(5)
Поменяем местами операции суммирования и интегрирования и используем фильтрующее свойство дельта-функции:
(6)
Тогда выражение (5) с учетом (6) принимает вид:
(7)
Таким образом, мы избавились от интегрирования в бесконечных пределах, заменив его конечным суммированием комплексных экспонент.
Комплексные экспоненты в выражении (7) являются периодическими функциями с периодом:
(8)
где — частота дискретизации сигнала (Гц).
Необходимо отметить, что исключено из выражения (8), так как при комплексная экспонента равна единице. Максимальный период повторения спектра будет при , в этом случае он равен рад/c.
Таким образом, спектр дискретного сигнала , есть — периодическая функция циклической частоты , определенная как (7). Если мы введем нормировку частоты дискретизации Гц, то (7) переходит к выражению дискретно-временного преобразования Фурье (ДВПФ):
(9)
ДВПФ использует только индексы отсчетов входного сигнала при частоте дискретизации Гц. В результате ДВПФ мы получим периодическую функцию нормированной циклической частоты .
Поскольку спектр дискретного сигнала — периодическая функция, то можно рассматривать только один период повторения спектра при рад/с или при Гц.

Повторение сигнала во времени. Дискретное преобразование Фурье
Для программной реализации алгоритмов цифровой обработки требуются как дискретные отсчеты сигнала, так и дискретные отсчеты спектра. Известно что дискретным, или, как еще говорят, линейчатым спектром, обладают периодические сигналы. При этом дискретный спектр получается путем разложения в ряд Фурье периодического сигнала. Значит, чтобы получить дискретный спектр, надо сделать исходный дискретный сигнал периодическим путем повторения данного сигнала во времени бесконечное количество раз с некоторым периодом . Тогда спектр периодического сигнала будет содержать дискретные гармоники, кратные рад/c.
Графически процесс повторения сигнала во времени представлен на рисунке 2.
Рисунок 2. Повторение сигнала во времени
Черным показан исходный сигнал, красным — его повторения через некоторый период .
Повторять сигнал можно с различным периодом , однако необходимо, чтобы период повторения был больше или равен длительности сигнала , чтобы сигнал и его периодические повторения не перекрывались во времени. При этом минимальный период повторения сигнала , при котором сигнал и его повторения не накладываются друг на друга, равен
(10)
Повторение сигнала с минимальным периодом показано на рисунке 3.
Рисунок 3. Повторение сигнала с минимальным периодом
При повторении сигнала с минимальным периодом получим линейчатый спектр сигнала, состоящий из гармоник, кратных:
(11)
Таким образом, мы можем продискретизировать спектр дискретного сигнала на одном периоде повторения с шагом и получим
(12)
отсчетов спектра.
Учтем вышесказанное в выражении (7):
(13)
Если опустить в выражении (13) шаг дискретизации по времени и по частоте , то получим окончательное выражение для ДПФ:
(14)
ДПФ ставит в соответствие отсчетам дискретного сигнала , отсчетов дискретного спектра , при этом предполагается, что и сигнал и спектр являются периодическими и анализируются на одном периоде повторения.
Детально свойства ДПФ будут рассмотрены в следующих разделах.
Обратное дискретное преобразование Фурье
Аналогично (3) можно записать выражение для дискретного спектра через решетчатую функцию:
(15)
где — дискретные отсчеты спектра на одном периоде повторения рад/с.
Подставим (15) в выражение для обратного преобразования Фурье (1):
(16)
где — коэффициент пропорциональности, задача которого — обеспечить равенство по амплитуде исходного дискретного сигнала и результата ОДПФ. Коэффициент пропорциональности учитывает коэффициент обратного преобразования Фурье.
Поменяем местами операции суммирования и интегрирования и учтем фильтрующее свойство дельта-функции:
(17)
Возьмем дискретные отсчеты через интервал сек, тогда (17) можно записать:
(18)
Учтем (11) и получим:
(19)
Опустив в (19) интервалы дискретизации по частоте и по времени, получим выражение для ОДПФ, в котором остался неизвестным коэффициент пропорциональности :
(20)
Для того чтобы рассчитать коэффициент , необходимо в выражение для ОДПФ (20) подставить выражение для ДПФ (14):
(21)
Поменяем местами в (21) порядок суммирования и объединим экспоненты:
(22)
Рассмотрим подробнее сумму комплексных экспонент входящую в (22).
При имеем:
(23)
Теперь рассмотрим эту же сумму при .
Пусть , тогда:
(24)
Каждая комплексная экспонента, входящая в сумму (24), есть вектор на комплексной плоскости единичной длины, повернутый на угол:
(25)
Таких векторов будет , и они повернуты относительно друг друга на одинаковые углы .
Поскольку все векторы выходят из одной точки (из 0 комплексной плоскости) и повернуты относительно друг друга на одинаковые углы как это показано на рисунке 4 для .
Рисунок 4. Сумма комплексных экспонент
Нетрудно показать, что для всех , , , суммы комплексных экспонент (24) равны нулю.
Тогда в выражении (22) от суммы по останется только слагаемое при , и (22) можно представить в виде:
(26)
Из (26) можно заключить, что .
Таким образом, окончательное выражение для ОДПФ имеет вид:
(27)
Выводы
В данном разделе мы осуществили переход от интеграла Фурье к прямому и обратному дискретному преобразованию Фурье путем дискретизации сигнала как по времени, так и по частоте.
Было показано, что спектр дискретного сигнала — периодическая функция с периодом рад/с или Гц.
Также было введено понятие дискретно-временного преобразования Фурье как периодической функции, нормированной к частоте дискретизации циклической частоты .
ДПФ получено путем дискретизации непрерывной функции на одном периоде повторения, что эквивалентно периодическому повторению дискретного сигнала во времени с периодом сек.

Список литературы
[1] Сергиенко А.Б. Цифровая обработка сигналов Питер, 2002.

[2] Оппенгейм А., Шафер Р. Цифровая обработка сигналов Техносфера, 2006.

[3] Гольденберг Л.М., Матюшкин Б.Д., Поляк М.Н. Цифровая обработка сигналов Радио и связь, 1985.

[4] Bracewell R.N. The Fourier Transform and its Applications. McGraw Hill, Singapor, 2000.

[5] Oppenheim Alan V. and Schafer Ronald W. Discrete-Time Signal Processing Second Edition. Prentice-Hall, New Jersey, 1999.

[6] Robert J. Marks II The Joy of Fourier: Analysis, Sampling Theory, Systems, Multidimensions, Stochastic Processes, Random Variables, Signal Recovery, Pocs, Time Scales, & Applications. Baylor University, 2006.

[7] Nussbaumer Henri J. Fast Fourier Transform and Convolution Algorithms. Second Corrected and Updated Edition. Springer-Verlag, 1982.