Рассмотрим теперь особенности дискретной свертки типа согласованной фильтрации в частотной области. В соответствии с теорией дискретного представления непрерывных функций, ограниченных во времени или частоте, функция , представленная последовательностью отсчетов (і = 0, 1, 2, … , п – 1), может быть отображена в частотную область с помощью дискретного преобразования Фурье (ДПФ), которое для каждого k = 0, 1, 2, ... , п – 1 имеет вид:
,
где , и наоборот, любая функция, представленная ограниченным дискретным спектром , может быть восстановлена во временной области с помощью обратного ДПФ (ОДПФ) по формуле:
.
Заметим, что число дискретных элементов функции одинаково при ее представлении как во временнόй, так и в частотной областях.
Свертка последовательностей в частотной области сводится к умножению результатов их ДПФ. Для этого необходимо предварительно осуществить два прямых преобразования Фурье – для свертываемой последовательности о последовательности отсчетов импульсной характеристики свертывающего фильтра. если после свертки необходимо снова перейти во временную область, потребуется осуществить ОДПФ последовательности составляющих свертки.
Для комплексных функций (сигналов) алгоритм операции ДПФ – свертка – ОДПФ.
1. ,
где – последовательность отсчетов комплексной импульсной характеристики свертывающего фильтра
2.
где – последовательность комплексных выборок входной (свертываемой) функции.
3. .
4. .
Принципиальной особенностью рассматриваемого алгоритма является режим групповой обработки, когда анализу подвергается массив входных данных длинной . Результат свертки имеет длину .
При решении задачи согласованной фильтрации радиосигналов импульсная характеристика СФ неизменна (по крайней мере для зондирующих сигналов одного типа). поэтому ее ДПФ производится заранее и записывается в ЗУ соответствующего вычислителя. В процессе свертки же необходимо осуществить одно прямое и одно обратное ДПФ.
Необходимо также иметь в виду, что свертываемая последовательность в задачах обработки радиосигналов имеет длину , соответствующую длиннее развертки РЛС, которая значительно больше длинны свертывающей последовательности, равной длине , импульсной характеристики СФ. одновременная свертка таких последовательностей слишком трудоемкая. Поэтому входную последовательность делят на блоки длинной каждый так, что элемент – го блока образуется из общей последовательности по правилу:
,
где – целая часть отношения в квадратных скобках.
Для каждого блока входных данных длинною вычисляется – точечное ДПФ для свертывающей последовательности импульсной характеристики СФ также предварительно должны быть получены запомнены соответствующие точечные ДПФ. Свертка в частотной области для каждого блока получается перемножением ДПФ свертываемой и свертывающей последовательностей точках. Для вычисления свертки во временной области производится ОДПФ. длинна полученной при этом последовательности и перекрываются в точках, так, что верными будут только значений последовательности. В дальнейшем, чтобы получить верные результаты для во всех точках, применяется суммирование перекрывающихся частотных последовательностей.
В процессе перекрывания возникает задача выбора оптимального по критерия минимума времени свертки значения при фиксированном . При малых значениях выполняется соотношение .
Рассмотрим теперь вопрос о трудоемкости реализации ЦСФ в частотной области. Преобразование Фурье (прямое и обратное) требует для получения частотных (временных) выборок операций умножения комплексных чисел и, кроме того, около операций комплексного суммирования. Полное же число операций с учетом перехода после свертки во временную область составит комплексных умножений комплексных сложений. при этом получаем выборку выходных данных длинной . Для получения такой же выборки выходных данных во временной области потребуется операций комплексного умножения и операций комплексного сложения. Следовательно, свертка в частотной области более трудоемкая, чем во временной (примерно в 8 раз, если ), и применять ее в рассмотренном виде для согласованной фильтрации нецелесообразно.
Существенно уменьшить число операций при свертке в частотной области можно, применив специальные алгоритмы ДПФ, получившие название алгоритмов быстрого преобразования Фурье (БПФ).
Пусть последовательность , подлежащая БПФ, имеет длину М, соответствующую целой степени числа 2, т. е. . Эта исходная последовательность может быть разложена на две части по правилу:
Последовательность содержит элементы исходной последовательности с четными номерами, а последовательность – с нечетными. длинна каждой последовательности . Полученные в результате разложения последовательности снова разлагаются на две части до тех пор, пока будет получено двухточечных последовательностей. Число шагов разложения .
Суть алгоритма ДПФ с прореживанием во времени состоит в том, что ДПФ последовательности вычисляется путем комбинации результатов ДПФ М – точечной последовательности сначала производится ДПФ двухточечных последовательностей, затем полученные преобразования объединяются в целях получения четырехточечных, затем восьмиточечных и т. д. до тех пор, пока после т шагов будет получено преобразование длинной М. Вычисление преобразований производится по формулам:
,
где – ДПФ четной и нечетной последовательностей.
Для графического представления алгоритма БПФ используются направленные графы, в которых применяются следующие обозначения: точка (кружочек) означает операцию слоения – вычитания, причем сумма появляется в верхней выходной ветви, а разность – в нижней выходной ветви, стрелка на ветви – операция умножения на константу, записанную над стрелкой (при отсутствии стрелки константа равна 1). направленный граф для восьмиточечного БПФ с прореживанием во времени по основанию 2 представлен на рис. 4.17.
Порядок задания входных данных на этом графе получен с помощью процедуры двоичной инверсии чисел 0, 1, …, 7. Это упрощает изображение графа и позволяет получить входную последовательность в естественном порядке (F0, , F1, F2, , F3, - в верхних выходных ветвях, F4, , F5, F6, , F7, – в нижних выходных ветвях). Как видно из рисунка, восьмиточечный БПФ осуществляется а три этапа.
На І – осуществляется 4 двухточечных ДПФ, причем при вычислении учитывается, что :
На ІІ этапе две пары двухточечных БПФ объединяются в два четырехточечных, на ІІІ этапе два четырехточечных – в восьмиточечное. В общем случае число этапов . На каждом этапе, кроме первого, производится М/2 комплексных умножений и М комплексных сложений. Поэтому для вычисления М – точечного БПФ требуется комплексных умножений и комплексных слоений.
Ранее было показано, что при вычислении прямого ДПФ требуется комплексных умножений и комплексных сложений. Выигрыш в реализации БПФ по сравнению с ДПФ по числу операций составит:
.
Например, при М = 1024, при М = 128.
Вернемся к вопросу реализации согласованной фильтрации радиосигналов в частотной области с учетом применения алгоритма БПФ. Структурная схема соответствующего вычислительного устройства представлена на рис. 4,18. состав схемы и назначение блоков ясны и рисунка. Необходимо только отметить, что на вход процессора прямого БПФ одновременно поступают две квадратурные составляющие, которые вместе образуют комплексный сигнал, подлежащий преобразованию БПФ – комплексное умножение ОБПФ. Поэтому входное ЗУ, выходное ЗУ и все промежуточные регистры должны иметь двойную длину разрядной сетки.
Для согласованной фильтрации сигналов в частотной области с применением БПФ необходимо выполнить одно прямое БПФ и перемножение двух М – точечных комплексных чисел. Общее число комплексных умножений
.
Так как при прямом вычислении во временнόй области число комплексных умножений на одну М – мерную выборку равно М2, выигрыш в числе операций комплексного умножения при применении БПФ равен .
Скорость свертки моно значительно увеличить, применив поточную структуру алгоритма БПФ. В этом случае процессор БПФ содержит арифметических устройств, работающих параллельно. Каждое арифметическое устройство выполняет операции преобразования на одном из этапов БПФ. При этом в пределе может быть получено сокращение времени вычисления в раз. Поточная организация БПФ потребует дополнительной памяти в виде межкаскадных регистров задержки.
Отметим также, что для сокращения времени свертки, кроме БПФ, могут быть применены другие быстрые методы ортогональных преобразований, в частности, преобразования Уолша–Адамара и теоретико-числовые преобразования.