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

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

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

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

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

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

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

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

, .

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

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

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

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

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

.

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

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

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

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

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

.

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

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

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

;

; .

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Рис. 9.18. Операция «бабочка», используемая

при реализации алгоритма БПФ

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

Пример 9.3. Построим граф вычисления БДНФ с прореживанием во времени для N=4 (рис. 9.19).

Рис. 9.19. Граф для вычисления БПФ при N=4

Учитывая, что, , получаем согласно приведенному графу

На рис. 9.20 показан граф вычисления БДПФ с прореживанием во времени для N=8.

Рис. 9.20. Граф для вычисления БПФ при N=8