В частотной области

Рассмотрим теперь особенности дискретной свертки типа согласованной фильтрации в частотной области. В соответствии с теорией дискретного представления непрерывных функций, ограниченных во времени или частоте, функция u(t), представленная последовательностью отсчетов (i = 0,1, 2,..., п-1), может быть отображена в частотную область с помощью дискретного преобразования Фурье (ДПФ), которое для каждого k = 0, 1, 2, ..., п-1 имеет вид

и, наоборот, любая функция, представленная ограниченным дискретным спектром , (k= 0, 1, 2, ..., п-1), может быть восстановлена во временной области с помощью обратного ДПФ (ОДПФ) по формуле:

Заметим, что число дискретных элементов функции u(t) одинаково при ее представлении как во временнόй, так и в частотной области.

Свертка последовательностей в частотной области сводится к умножению результатов их ДПФ. Для этого необходимо предварительно осуществить два прямых преобразования Фурье – для свертываемой последовательности и последовательности отсчетов импульсной характеристики свертывающего фильтра. Если после свертки необходимо снова перейти во временную область, потребуется осуществить ОДПФ последовательности составляющих свертки.

Для комплексных функций (сигналов) алгоритм операции "ДПФ–свертка–ОДПФ":

1. ,

где h[i] – последовательность отсчетов комплексной импульсной характеристики, свертывающего фильтра.

2. ,

где u[i] – последовательность комплексных выборок входной (свертываемой) функции.

3. ,

4. .

Принципиальной особенностью рассматриваемого алгоритма является режим групповой обработки, когда анализу подвергается массив входных данных длиной Результат свертки имеет длину .

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

Необходимо также иметь в виду, что свертываемая последовательность в задачах обработки радиосигналов имеет длину L, соответствующую длине развертки РЛС, которая значительно больше длины свертывающей последовательности, равной длине n_h, импульсной характеристики СФ. Одновременная свертка таких последовательностей слишком трудоемка. Поэтому обычно входную последовательность делят на блоки, длиной l каждый, так что элемент -го блока образуется из общей последовательности по правилу:

где Е[*] – целая часть отношения в квадратных скобках.

Для каждого блока входных данных длиной l вычисляется (l+n-1)-точечное ДПФ. Для свертывающей последовательности импульсной характеристики СФ также предварительно должны быть получены и заполнены составляющие (l+n-1)-точечное ДПФ. Свертка в частотной области для каждого блока получается перемножением ДПФ свертываемой и свертывающей последовательностей в l+n-i точках. Для вычисления свертки во временной области производится ОДПФ. Длина полученной при этом последовательности Z[i] равна l+n-i, причем соседние последовательности Z[i] и Z +f[i] перекрываются в n-1 точках, так что верными будут только l значений последовательности. В дальнейшем, чтобы получить верные результаты для Z[i] во всех точках, применяется суммирование перекрывающихся частных последовательностей.

В процессе проектирования возникает задача выбора оптимального по критерию минимума времени свертки значения l при фиксированном п. При малых значениях n < 100 выполняется соотношение .

Рассмотрим теперь вопрос о трудоемкости реализации ЦСФ в частотной области. Преобразование Фурье (прямое и обратное) требует для получения l+n-1 частотных (временных) выборок (l+n-i)² операций умножения комплексных чисел и, кроме того, около (l+n-1)² операций комплексного суммирования. Полное же число операций с учетом перехода после свертки во временную область составляет 2(l+n-l)²+(l+n-1) комплексных умножений и 2(l+п-1)² комплексных сложений. При этом получаем выборку выходных данных длиной l. Для получения такой же выборки выходных данных во временной области потребуется l² операций комплексного умножения и l(l-1) операций комплексного сложения. Следовательно, свертка в частотной области более трудоемка, чем во временнόй (примерно в 8 раз, если , и применять ее в рассмотренном виде для согласованной фильтрации сигналов нецелесообразно).

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

Пусть последовательность {u[i]}, подлежащая БПФ, имеет длину М, соответствующую целой степени числа 2, т. е. М = 2^т. Эта исходная последовательность может быть разложена на две части по правилу

Последовательность содержит элементы исходной последовательности с четными номерами, а последовательность u_o[i] – с нечетными. Длина каждой последовательности М/2. Полученные в результате разложения последовательности снова разлагаются на две части до тех пор, пока будет получено М/2 двухточечных последовательностей. Число шагов разложения т = log₂M.

Суть алгоритма БПФ с прореживанием во времени состоит в том, что ДПФ последовательности длиной l>2 вычисляется путем комбинации результатов ДПФ двух последовательностей длиной l/2. В соответствии с этим в процессе реализации алгоритма БПФ М-точечной последовательности сначала производится М/2 ДПФ двухточечных последовательностей, затем полученные преобразования объединяются с целью получения М/2 четырехточечных, затем М/8 восьмиточечных и т. д. до тех пор, пока после т шагов будет получено преобразование длиной М. Вычисление преобразований производится по формулам

где ;

– ДПФ четной и нечетной последовательности.

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

Рис. 11.16. Направленный граф 8-точечного БПФ

Порядок задания входных данных на этом графе получен с помощью процедуры двоичной инверсии чисел 0, 1,..., 7. Это упрощает изображение графа и позволяет получить входную последовательность в естественном порядке (F_o, F₁ F₂, F₃ – в верхних выходных ветвях, F₄, F₅, F₆, F₇ – в нижних выходных ветвях). Как видно из рисунка, восьмиточечное БПФ осуществляется за три этапа.

На І осуществляется 4 двухточечных ДПФ, причем при вычислении учитывается, что W₂ = е^-^jx=-1. Поэтому операции умножения отсутствуют и

На II этапе две пары двухточечных БПФ объединяются в 2 четырехточечных, а на III этапе полученные 2 четырехточечных – в восьмиточечное. В общем случае число этапов т = log₂M. На каждом этапе, кроме І, производится М/2 комплексных умножений и М комплексных сложений. Поэтому для вычисления М-точечного БПФ требуется M/2log₂M комплексных умножений и Mlog₂M комплексных сложений.

Ранее было показано, что при вычислении прямого ДПФ требуется М² комплексных умножений и М(М-1) комплексных сложений. Выигрыш в реализации БПФ по сравнению с прямым ДПФ по числу операций умножения составит

Например, при М = 1024, 21 при М = 128.

Вх ЗУ

БПФ

Вых ЗУ

Рис. 11.17. Структурная схема согласованного фильтра в частотной области

Вернемся к вопросу реализации согласованной фильтрации радиосигналов в частотной области с учетом применения алгоритма БПФ. Структурная схема соответствующего вычислительного устройства представлена на рис. 11.17. Состав схемы и назначение блоков ясны из рисунка. Необходимо только отметить, что на вход процессора прямого БПФ одновременно поступают две квадратурные составляющие, которые вместе образуют комплексный сигнал, подлежащий преобразованию БПФ – комплексное умножение – ОБПФ. Поэтому входное ЗУ, выходное ЗУ и все промежуточные реόгистры должны иметь двойную длину разрядной сетки.

Для согласованной фильтрации сигналов в частотной области с применением БПФ необходимо выполнить одно прямое БПФ, одно обратное БПФ и перемножение двух М-точечных комплексных чисел. Общее число комплексных умножений

Так как при прямом вычислении во временнόй области число комплексных умножений на одну М-мерную выборку равно М₂, выигрыш в числе операций комплексного умножения при применении БПФ равен К = М/[1 + log₂M].

Скорость свертки можно значительно увеличить, применив поточную структуру алгоритма БПФ. В этом случае процессор БПФ содержит (M/2)log₂M арифметических устройств, работающих параллельно. Каждое арифметическое устройство выполняет операции преобразования на одном из этапов БПФ. При этом в пределе может быть получено сокращение времени вычислений в log₂M/2 раз. Поточная организация БПФ потребует дополнительной памяти в виде межкаскадных регистров задержки.

Отметим также, что для сокращения времени свертки, кроме БПФ, могут быть применены другие быстрые методы ортогональных преобразований, в частности, преобразования Уолша-Адамара и теоретико-числовые преобразования.