6.6.7. Быстрое преобразование Фурье.
Для реализации цифровой фильтрации в частотной области дискретизированные колебания подвергаются дискретному преобразованию Фурье (ДПФ), результат умножается на дискретную амплитудно-частотную характеристику ЦФ (рис.6.41), после чего формируется выходной сигнал в виде
6.41. Дискретное преобразование Фурье (ДПФ)
обратного дискретного преобразования Фурье (ОДПФ). Переход в частотную область целесообразен в связи с возможностью сокращения времени обработки и объема аппаратуры за счет применения разновидности ДПФ - быстрого преобразования Фурье (БПФ).
Для вычисления ДПФ последовательности из N чисел при каком-либо n (одна частотная выборка) индекс k принимает N значений. Так как эта операция повторяется N раз, то всего получится N2 операций умножения на комплексное число и столько же операций сложения. Именно по этой причине ЭВМ долгое время не применялись для спектрального анализа сигналов.
Существенный сдвиг произошел благодаря использованию быстрого преобразования Фурье, основанного на прореживании по времени или по частоте (рис. 6.42). Рассмотрим вариант прореживания временных выборок многократным членением на подпоследовательности. Заданная последовательность чисел xk (k= 0, 1, ..., N - 1) разбивается на две подпоследовательности; нечетную (н) х2k+1 и четную (ч) х2к.
Рис. 6.42. Быстрое преобразование Фурье: разделение на две подпоследовательности
Для получения двух выборок ДПФ нужно сделать одно умножение на комплексное число и два суммирования. Так как для каждой из подпоследовательностей требуется (N/2)2 умножений на комплексное число и еще N/2 + N/2 = N умножений на комплексное число n, то всего требуется N2/2 умножений, т. е. вдвое меньше, чем при использовании ДПФ.
При последующем разбиении каждой последовательности можно получить дальнейшее сокращение объема вычислений. Этот процесс продолжается до тех пор, пока не будут получены N последовательностей, содержащих только одно число. Для этого необходимо, чтобы N = 2m, где m - целое число. Вначале имеем N = 2м последовательностей по одному числу. После 1-го этапа получим 2m-1 = N/2 последовательностей по 2 числа и т. д. В конце образуется одна последовательность из N членов, представляющая ДПФ исходной функции. Вся процедура содержит m = 1оg2 N этапов. При больших N выигрыш оказывается значительней. Например, при N = 210 = 1024, когда log2 N = 10, число операций умножения снижается в 200 раз.
При цифровой фильтрации в частотной области, полученные в результате БПФ дискреты спектра входного сигнала Sn умножаются на дискреты частотной характеристики фильтра Kп. которые найдены заранее и занесены в табличную память. Затем производится ОДПФ с использованием алгоритма БПФ, т. е. обратное быстрое преобразование Фурье (ОБПФ).
Алгоритмы БПФ находят применение в импульсно-доплеровских РЛС для многоканального спектрального анализа по доплеровским частотам, для формирования угловых каналов в РЛС с ФАР, для цифрового сжатия в РЛС с широкополосными зондирующими сигналами и др.