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

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

Математическое определение

Пусть задана последовательность комплексных чисел \( x_0, x_1, \ldots, x_{N-1} \), представляющая собой \( N \) отсчётов сигнала во временной области. Дискретное преобразование Фурье преобразует эту последовательность в другую последовательность комплексных чисел \( X_0, X_1, \ldots, X_{N-1} \), описывающую спектр сигнала в частотной области. Прямое ДПФ определяется формулой:

\[ X_k = \sum_{n=0}^{N-1} x_n \cdot e^{-i \frac{2\pi}{N} k n}, \quad k = 0, 1, \ldots, N-1 \]

где:

• \( X_k \) — \( k \)-й спектральный коэффициент (комплексное число), соответствующий частоте \( f_k = k \cdot \frac{f_s}{N} \), где \( f_s \) — частота дискретизации исходного сигнала.
• \( x_n \) — \( n \)-й отсчёт сигнала во временной области.
• \( N \) — количество отсчётов (размер преобразования).
• \( i \) — мнимая единица (\( i^2 = -1 \)).
• \( e^{-i \frac{2\pi}{N} k n} \) — комплексная экспонента, представляющая собой синусоидальную волну определённой частоты и фазы.

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

Обратное дискретное преобразование Фурье (ОДПФ, IDFT) позволяет восстановить исходный сигнал по его спектру. Формула ОДПФ:

\[ x_n = \frac{1}{N} \sum_{k=0}^{N-1} X_k \cdot e^{i \frac{2\pi}{N} k n}, \quad n = 0, 1, \ldots, N-1 \]

Отличие от прямого преобразования заключается в знаке показателя экспоненты и нормирующем множителе \( \frac{1}{N} \). Существование и единственность ОДПФ гарантирует, что преобразование является обратимым и не приводит к потере информации.

Свойства дискретного преобразования Фурье

ДПФ обладает рядом свойств, которые широко используются при анализе и обработке сигналов.

Линейность

ДПФ от суммы двух последовательностей равно сумме их ДПФ. Если \( x_n = a \cdot u_n + b \cdot v_n \), то \( X_k = a \cdot U_k + b \cdot V_k \), где \( a \) и \( b \) — произвольные константы.

Сдвиг (теорема о запаздывании)

Сдвиг сигнала во времени на \( m \) отсчётов приводит к умножению его спектра на фазовый множитель: если \( y_n = x_{n-m} \), то \( Y_k = X_k \cdot e^{-i \frac{2\pi}{N} k m} \). Амплитуда спектра при этом не меняется, изменяется только фаза.

Симметрия (для вещественных сигналов)

Если исходная последовательность \( x_n \) состоит из вещественных чисел (что характерно для большинства реальных сигналов), то её ДПФ обладает эрмитовой симметрией: \( X_{N-k} = \overline{X_k} \), где черта сверху означает комплексное сопряжение. Это означает, что вторая половина спектральных коэффициентов является зеркальным отражением первой и не несёт новой информации. Поэтому на практике часто отображают только первую половину спектра (от 0 до \( N/2 \)).

Свёртка и корреляция

Одно из важнейших свойств ДПФ — преобразование циклической свёртки двух последовательностей в поточечное умножение их спектров: \( \text{ДПФ}\{x_n * y_n\} = X_k \cdot Y_k \). Это свойство лежит в основе быстрых алгоритмов вычисления свёртки, используемых, например, в цифровых фильтрах.

Быстрое преобразование Фурье

Прямое вычисление ДПФ по формуле требует порядка \( N^2 \) операций (умножений и сложений), что делает его непрактичным для больших \( N \). Быстрое преобразование Фурье (БПФ, FFT) — это набор алгоритмов, позволяющих вычислить ДПФ за \( O(N \log N) \) операций.

Наиболее известным алгоритмом БПФ является алгоритм Кули — Тьюки (1965 год). Он основан на принципе «разделяй и властвуй»: ДПФ размера \( N \) разбивается на два ДПФ размера \( N/2 \) (по чётным и нечётным отсчётам), что рекурсивно повторяется. Это возможно, если \( N \) является степенью двойки. Благодаря БПФ, ДПФ стало практически применимым в реальном времени и в вычислительных системах с ограниченными ресурсами.

Применение

ДПФ и БПФ находят применение в огромном числе областей науки и техники.

Спектральный анализ

Основное применение — определение частотного состава сигнала. Анализируя модуль ДПФ (\( |X_k| \)), можно выявить доминирующие частоты, шумы, гармоники. Используется в:

• Акустике: анализ звука, настройка музыкальных инструментов, распознавание речи.
• Радиотехнике: анализ радиосигналов, поиск помех.
• Медицине: анализ электроэнцефалограмм (ЭЭГ) и электрокардиограмм (ЭКГ).

Сжатие данных

В алгоритмах сжатия с потерями (например, JPEG, MP3) используется модификация ДПФ — дискретное косинусное преобразование (ДКП). Оно позволяет сконцентрировать энергию сигнала в небольшом числе низкочастотных коэффициентов, а высокочастотные составляющие, менее заметные для человеческого восприятия, отбрасываются или квантуются с меньшей точностью.

Цифровая фильтрация

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

Обработка изображений

Двумерное ДПФ применяется для анализа текстур, выделения границ, удаления шума, а также в задачах компьютерного зрения и распознавания образов.

Телекоммуникации

В системах OFDM (ортогональное частотное разделение каналов), используемых в Wi-Fi, 4G/5G, цифровом телевидении, ДПФ и ОДПФ являются ключевыми операциями для модуляции и демодуляции сигнала.

Ограничения и особенности

Несмотря на широкое применение, ДПФ имеет ряд ограничений, которые необходимо учитывать.

• Эффект утечки спектра: Если частота сигнала не совпадает точно с одной из частотных «бин» (дискретных частот, на которых вычисляется ДПФ), энергия сигнала «размазывается» по соседним частотам. Для уменьшения этого эффекта используются весовые функции (окна), такие как окно Ханна, Хэмминга или Блэкмана.
• Разрешающая способность по частоте: Она равна \( \Delta f = f_s / N \). Чем больше \( N \) (длиннее анализируемый отрезок сигнала), тем выше разрешение, но тем больше вычислительных затрат.
• Требование к стационарности: ДПФ даёт усреднённую спектральную характеристику за всё время наблюдения. Для анализа сигналов с быстро меняющимся спектром (например, речь) применяется кратковременное преобразование Фурье (STFT), где ДПФ вычисляется на коротких перекрывающихся окнах.

Источники

1. Оппенгейм А., Шафер Р. «Цифровая обработка сигналов». — М.: Техносфера, 2006.
2. Лайонс Р. «Цифровая обработка сигналов». — М.: Бином-Пресс, 2006.
3. Гольденберг Л. М., Матюшкин Б. Д., Поляк М. Н. «Цифровая обработка сигналов: Справочник». — М.: Радио и связь, 1985.
4. Cooley J. W., Tukey J. W. «An algorithm for the machine calculation of complex Fourier series». — Mathematics of Computation, 1965.