Алгоритмы дискретного и быстрого преобразований Фурье

Дискретные сигналы (как и аналоговые) могут быть представлены во временной и частотной областях. В настоящее время обработка дискретных сигналов чаще всего проводится в частотной области, так как при этом значительно сокращается время и упрощается аппаратура.

Подвергнем дискретной обработке аналоговый импульсный сигнал u(t) длительностью T_и, имеющий спектральную плотность S(ω) (рис. 12.1а, б). Воспользуемся теоретическим представлением дискретизации сигнала периодической последовательностью дельта-функций

, (12.1)

где N = T_и/∆t – требуемое число отсчетов, отвечающих теореме Котельникова.

Следовательно выражение для дискретного сигнала (рис. 12.1е) с учетом пределов суммирования (от 0 до N – 1) имеет вид

(12.2)

где u_k = u(k∆t).

На основании формулы (12.2) можно сделать вывод, что спектр данного дискретного сигнала имеет периодическую структуру с периодом по оси частот ω₁ = 2π/∆t (рис. 12.1г). Мысленно продолжим дискретный сигнал периодически с интервалом T_и (рис. 12.1д) |С_n|

Рис. 12.1. Графики к выводу ДПФ:

а, б – аналоговый сигнал и его спектр; в, г – дискретный сигнал и его спектр; д – периодическая последовательность дискретного сигнала; е – ДПФ сигнала u_nT(t + T_и) = u_T(t), n = 0 ± 1, ±2,... .

По аналогии с представлением периодических непрерывных сигналов

где – комплексная амплитуда n-й гармоники. Дискретную функцию u_nT(t) можно разложить в комплексный ряд Фурье:

, (12.3)

где ω_н = 2π/T_и = 2π/(N∙∆t) – частота дискретизации сигнала.

Коэффициенты этого ряда

. (12.4)

Для определения коэффициентов проделаем следующее. Подставим формулу (12.2) в (12.4) и заменим параметр T_и = N∙∆t. Введем безразмерную переменную y = t/∆t и запишем

Используя фильтрующее свойство дельта – функции, находим

. (12.5)

Это соотношение называется дискретным преобразованием Фурье (ДПФ). Дискретное преобразование Фурье по существу представляет собой алгоритм вычисления гармонических составляющих спектра С_n по заданным дискретным отсчетам u_k аналогового сигнала u(t), что значительно сокращает время обработки. Характерный вид модулей коэффициентов С_n показан на рис. 12.1е.

Следует отметить ряд свойств ДПФ, которые вытекают из определения (12.5).

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

2. Коэффициент С₀ представляет собой среднее значение (постоянную составляющую) всех дискретных отсчетов сигнала

3. Число различных коэффициентов С_n равно числу отсчетов N за длительность сигнала T_и; при n = N коэффициент С_n = С₀.

Пример. Определить коэффициенты ДПФ дискретизированного прямоугольного импульса единичной амплитуды, заданного четырьмя отсчетами (N = 4).

Решение. Используя основную формулу (12.5), вычислим пять первых коэффициентов ДПФ: С₀ = 4/4 = 1;

При изучении теории ДПФ возникает очевидный вопрос: можно ли по известным коэффициентам ДПФ вычислить отсчетные значения u_k непрерывного сигнала? По аналогии с периодическими сигналами представим заданную периодическую последовательность отсчетов комплексным рядом Фурье, заменив t = k∆t, ω_н = 2π/(N×∆t) и, учитывая, что суммируется конечное число членов ряда, запишем

(12.6)

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

Выражение (12.5) показывает, что для определения одного коэффициента ДПФ сигнальной последовательности из N отсчетов, необходимо выполнить около N операций умножения на комплексное число и столько же сложений, а для нахождения всех коэффициентов объем вычислений составит N². В частности, при N = 2¹⁰ = 1024 надо осуществить более миллиона (1024²) умножений и сложений. Если длины обрабатываемых массивов превышают тысячу единиц, то дискретная спектральная обработка сигналов в реальном масштабе времени требует высокопроизводительных вычислительных комплексов.

Многократно сократить число операций позволяет быстрое преобразование Фурье (БПФ), обеспечивающее вычисление коэффициентов ДПФ за меньшее число операций. В основу БПФ положен принцип разбиения заданной последовательности отсчетов дискретного сигнала на несколько промежуточных последовательностей. Для этого число отсчетов N разделяется на множители (например, N = 8 = 2 × 2 × 2, N = 60 = 3 × 4 × 5). Затем определяются спектры этих промежуточных последовательностей и через них находится спектр всего сигнала.

В зависимости от состава, числа и порядка следования указанных множеств можно создать различные алгоритмы БПФ. В цифровой технике удобно обрабатывать сигнальные последовательности со значениями N, являющимся степенью числа два (4, 8, 16 и так далее). Это позволяет многократно делить входную последовательность отсчетов на подпоследовательности.

Пусть требуется вычислить ДПФ дискретного сигнала {u(k∆t)} = {u_k}, имеющего четное число отсчетов (рис. 12.2а), причем N = 2^r; r – целое число.

Рис. 12.2. Разбиение последовательности u_k на две подпоследовательности: а – входная; б – с четными номерами; в – с нечетными номерами

Представим входную последовательность в виде двух подпоследовательностей с четными и нечетными номерами и половинным числом членов в каждой (рис. 12.2б, в): u_чт = u_2k; u_нч = u_2k+1; k = 0, 1, 2,..., N/2 – 1.

Коэффициенты ДПФ для последовательностей с четными и нечетными номерами запишем отдельно:

(12.7)

Коэффициенты С_n результирующего ДПФ входной последовательности можно выразить через параметры С_nчт и С_nнч двух вновь введенных подпоследовательностей. Анализ (12.7) показывает, что в диапазоне номеров отсчетов от 0 до N/2 - 1, ДПФ входной последовательности определяется соотношением:

C_n = С_nчт + exp(-j2πn/N) ∙ С_nнч, n = 0, 12 ,..., N/2 – 1. (12.8)

Так как ДПФ четной и нечетной последовательностей являются периодическими, с периодом N/2, то С_nчт = С_(n+N/2)чт; С_nнч = С_(n+N/2)нч.

Запишем экспоненциальный множитель в формуле (12.8) при n ≥ N/2, т.е. для ДПФ С_(N/2+n)нч, в виде:

С учетом двух последних выражений находим коэффициенты ДПФ входной последовательности для отсчетов с номерами от N/2 до N - 1:

C_N/2+n = С_nчт - exp(-j2πn/N) ∙ С_nнч, n = N/2, N/2 + 1, ,..., N - 1. (12.9)

Соотношения (12.8) и (12.9) полностью определяют алгоритмы вычисления коэффициентов с помощью БПФ. Отметим, что экспоненциальные фазовые множители exp(-j2πn/N) в этих алгоритмах учитывают влияние сдвига нечетной подпоследовательности относительно четной.

Чтобы еще уменьшить число вычислений, четную и нечетную подпоследовательности также разбивают каждую на две промежуточные части. Разбиение продолжают вплоть до получения простейших двухэлементных последовательностей. Определив ДПФ данных простейших пар отсчетов, можно вычислить ДПФ четырехэлементных, восьмиэлементных и так далее подпоследовательностей. При объединении ДПФ четной и нечетной подпоследовательностей используют алгоритмы (12.8) и (12.9), подставляя в них соответствующие значения номеров N и n.

Нетрудно заметить, что вычисления по формулам (12.7) не потребуют операций умножения, в (12.7) имеются только сложение и вычитание комплексных чисел. Учитываться же должны лишь операции умножения в алгоритмах (12.8) и (12.9) для различных n при разбиениях массива отчетов на мелкие подпоследовательности. Число этих операций при первом разбиении составляло N/2. Такое же число N/2 операций требуется выполнить при каждом следующем разбиении. Таким образом, вдвое увеличивается число подпоследовательностей и вдвое сокращается наибольшее число n в формулах вычисления спектральной плотности дискретного сигнала.

Вычисление коэффициентов ДПФ последовательности из N отсчетов по алгоритмам БПФ требует примерно N∙log₂N операций умножения. Алгоритмы БПФ сокращают число операций по сравнению с алгоритмами ДПФ в N:log₂N раз. Например, при количестве отсчетов N = 2¹⁰, имеем log₂N = 10 и сокращение числа операций составляет N : log₂N ≈ 100. При очень больших массивах отсчетов входного сигнала выигрыш в скорости обработки может достигать нескольких тысяч.

Таким образом, в алгоритмах БПФ выполняются операции сложения и вычитания с умножением одного из компонентов на экспоненциальный множитель exp(-j2πn/N). Эту базовую для БПФ операцию очень удобно представлять сигнальным графом, называемым в цифровой технике «бабочкой». БПФ по рассмотренному методу называют методом прореживания отсчетов во времени.