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

Как и при анализе аналоговых сигналов, дискретные сигналы можно представить во временной и частотной областях. В настоящее время обработку дискретных сигналов чаще всего проводят в частотной области, что диктуется значительными сокращениями объема цифровой аппаратуры и времени обработки.

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

(9.35)

где — требуемое число отсчетов, отвечающих теореме Котельникова.

Подставив в (9.32) пределы суммирования от 0 до , и заменив здесь и далее для упрощения и уменьшения объема формул , запишем выражение для дискретного сигнала (рис. 9.16, е)

(9.36)

На основании формулы (9.36) можно сделать вывод, что спектр данного дискретного сигнала имеет периодическую структуру с периодом по оси частот (рис. . 9.16, г). Мысленно продолжим дискретный сигнал периодически с интервалом (рис. . 9.16, д).

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

а,б - аналоговый сигнал и его спектр; в,г - дискретный сигнал и его спектр; д - периодическая последовательность дискретного сигнала; е - ДПФ сигнала

, .

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

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

(9.37)

где - частота дискретизации сигнала.

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

(9.38)

Для определения коэффициентов проделаем следующее. Подставим формулу (9.36) в (9.38) и заменим параметр . Введем безразмерную переменную и запишем

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

(9.39)

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

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

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

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

3. Число различных коэффициентов равно числу отсчетов за длительность сигнала ; при коэффициент .

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

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

;

; .

При изучении теории ДПФ возникает очевидный вопрос: можно ли по известным коэффициентам ДПФ вычислить отсчетные значения непрерывного сигнала? По аналогии с периодическими сигналами представим заданную периодическую последовательность отсчетов комплексным рядом Фурье. Заменив в (7.25) , и, учитывая, что суммируется конечное число членов ряда, запишем

(9.40)

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

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

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

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

Пусть требуется вычислить ДПФ дискретного сигнала , имеющего четное число отсчетов (рис. 9.17, а), причем ; - целое число.

Представим входную последовательность в виде двух подпоследовательностей с четными и нечетными номерами и половинным числом членов в каждой (рис. 9.17, б,в): ; ;.

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

(9.41)

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

, .

(9.42)

Так как ДПФ четной и нечетной последовательностей являются периодическими, с периодом , то ; .

Запишем экспоненциальный множитель в формуле (9.42) при , т.е. для ДПФ , в виде:

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

, .

(9.43)

Соотношения (9.42) и (9.43) полностью определяют алгоритмы вычисления коэффициентов с помощью БПФ. Отметим, что экспоненциальные фазовые множители в этих алгоритмах учитывают влияние сдвига нечетной подпоследовательности относительно четной.

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

Нетрудно заметить, что вычисления по формулам (9.41) не потребуют операций умножения, в (9.41) имеются только сложение и вычитание комплексных чисел. Учитываться же должны лишь операции умножения в алгоритмах (9.42) и (9.43) для различных при разбиениях массива отчетов на мелкие подпоследовательности. Число этих операций при первом разбиении составляло . Такое же число операций требуется выполнить при каждом следующем разбиении. Таким образом, вдвое увеличивается число подпоследовательностей и вдвое сокращается наибольшее число в формулах (7.30), (7.31).

Вычисление коэффициентов ДПФ последовательности из N отсчетов по алгоритмам БПФ требует примерно операций умножения. Алгоритмы БПФ сокращают число операций по сравнению с алгоритмами ДПФ в раз. Например, при количестве отсчетов , имеем и сокращение числа операций составляет . При очень больших массивах отсчетов входного сигнала выигрыш в скорости обработки может достигать нескольких тысяч.

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

БПФ по рассмотренному методу (его называют методом прореживания отсчетов во времени) осуществляют, как правило, в следующем порядке. Сначала для получения желательного при обработке сигнала порядка следования отсчетов ,, выполняется двоично-инверсная перестановка элементов исходной последовательности , . Для этого записывают порядковые номера элементов в двоичном коде и инвертируют порядок следования разрядов. Новый порядок следования элементов определяется номерами, полученными после инверсии разрядов.

Пример при N=4

u(l)			u(k)
0→	00→	00→	0→
1→	01→	10→	2→
2→	10→	01→	1→
3→	11→	11→	3→

Новый порядок следования элементов: . После этого поступают так. На первом этапе вычислений определяют двух точечные ДПФ "новой" последовательности , объединяя попарно элементы этой последовательности. На втором этапе из двух точечных ДПФ получают четырех точечные ДПФ, пользуясь основной базовой операцией данного метода (см. ниже). Затем четырех точечные ДПФ объединяют в восьми точечные и т.д.

Базовые операции и показывают, как два входных числа А и В объединяются для получения двух выходных чисел X и Y. Для метода прореживания во времени базовая операция изображается «бабочкой», представленной на рис. 9.18. Надпись у стрелки, идущей вверх, означает умножение на величину В.