Диссертация (Двумерный корреляционный анализ пониженной вычислительной сложности для разнесенных пассивных систем), страница 4

Возьмем ближайшее целое число кратное 2, т.е. Nd=128.100δФКоличество отсчётов по задержке возьмём целое число кратное 2, Nτ=1024. Приэтом получаем, что диапазон задержек равен 102,4 мкс.21Рисунок 1.2 – Структурная схема корреляционной обработки при помощидискретной корреляцииЧислооперацийдляполученияодногоканалаДКФ:χp,q==NТ+2∙NТNd=3,36∙107 (здесь и далее число операций считается по количествукомплексных умножений и без учёта расходов на полосовую фильтрацию).Поправка по частоте осуществляется в каждом дискрете. Так как, количествоканалов равно Nτ, тогда общее число операций равно 3,4∙1010.

Формула длярасчёта количества комплексных умножений (без учёта затрат на фильтрацию):( N Т + 2 N Т N d ) Nτ . Производительность вычислителя при расчёте ДКФ в реальномвремени равна: 3,4∙1010/0,01=3,4∙1012 оп/с.Подобная структура (рисунок 1.2) обладает достаточно высоким уровнемпараллелизма, что позволяет использовать идентичные независимые вычислителидля организации параллельных каналов.Результат корреляционной обработки (рисунок 1.2) зависит не только отвременного сдвига сигналов, но и от разности их начальных фаз.

Чтобыисключить влияние неизвестной начальной фазы, необходимо использовать схемуквадратурной обработки [28]. Если время задержи сигналов неизвестно, тонеобходимо применять набор таких схем. При этом на умножители будутпоступать сигналы с различными задержками, что усложняет аппаратнуюреализацию.Недостаток этого метода заключается в большом количестве операций исоответственно жёстким требованиям, предъявляемым к вычислителю. Длясокращения количества операций переходим от дискретной корреляции ккорреляции при помощи двойного БПФ, через спектральное представление22входных сигналов [39]. Структурная схема одного канала фильтрации дляфиксированного значения частоты и диапазона задержек показана на рисунке 1.3и содержит следующие этапы обработки:- компенсация сдвига частоты при помощи “поддува”, т.е.

смещениеспектра V(M+q) (где М – частотный индекс; q=0, 1, …, ( N d − 1) ) одного изсигналов на частоту Фq;- полосовая фильтрация;- получение спектров комплексных сигналов первого и второго приёмныхканалов при помощи операции БПФ. Спектры сигналов описываются:U (M ) =( N Т + N τ ) −1∑− j 2πu ( m)emMN Т + Nτ, V ( M + q) =*( N Т + Nτ ) −1∑*− j 2πv ( m)em( M + q)N Т + Nτ,m=0m=0где m=0, 1, …, (( N Т + Nτ ) − 1) ; М=0, 1, …, (( N Т + Nτ ) − 1) ;- поэлементное перемножение спектра первого сигнала на спектрсмещённого на частоту Фq, комплексно-сопряжённого и инвариантного повремени второго сигнала;- обратное преобразование Фурье при помощи операции БПФ;- формирование элементов ДКФ.Рисунок 1.3 – Структурная схема корреляционной обработки при помощиоперации двойного БПФТаким образом, один канал позволяет получить значение диапазоназадержек при фиксированном значении частоты, т.е.

вычислить один столбец вматрице ДКФ. Для вычисления других значений необходимо повторитьоперацию,изменивнеобходимымобразомчастотуФqичастотную23характеристику полосового фильтра [125]. Аналогично проводится операцияумножения спектра U(М) на частоту Фq во втором канале.Рассчитаем количества операций для получения матрицы ДКФ.

Для этогонадо выполнить два прямых преобразования Фурье с помощью алгоритма БПФ.Для реализации этого алгоритма воспользуемся алгоритмом Кули-Тьюки пооснованию 2 (здесь и далее применяется этот алгоритм). Число комплексныхумножений для вычисления БПФ( N Т + Nτ )log 2 ( N Т + Nτ ) [29], т.е. общее число2операций 2,25∙106. Далее следует ( N Т + Nτ ) умножений и операция обратное БПФ.ЧислооперацийдляполученияодногостолбцаДКФ:2∙1,3∙105+2,25∙106+1,12∙106=3,63∙106. Если количество каналов (частот) 2Nd, тогдаобщее число операций равно 9,3∙108.Формуладлярасчётаколичествакомплексныхумножений:2 N d ⋅ ( NТ + Nτ )(1,5 log 2 ( NТ + Nτ ) + 2 ) .

Требуемая производительность вычислителя прирасчёте ДКФ в реальном времени: 9,3∙108/0,01=9,3∙1010 оп/с.2метод.Алгоритмкорреляционно-фильтровойобработкиявляетсяразвитием алгоритма корреляционной обработки. Элемент частотной фильтрации[8,34,45] представляет не что иное, как вычисление спектральной составляющейсигнала на частоте Фq.

Поэтому структурная схема (рисунок 1.2) преобразуется врисунок 1.4 и содержит следующие этапы обработки:- перемножение комплексного сигнала одного канала приёма с комплексносопряженным сигналом второго канала, задержанным на время распространения;- полосовая фильтрация разностного сигнала после преобразования длясокращения полосы частот до диапазона анализируемых частот ∆Фq << ∆f .После фильтрации может производиться прореживание выборок, уменьшающихколичество операций;- вычисление спектра и спектральный анализ сигнала [31] в анализируемойполосе;- формирование матрицы ДКФ.24Получаем отсчёты на выходе согласованного фильтра, настроенного нафиксированную задержку в заданном диапазоне частот, т.е. получаем одну строкув матрице ДКФ. Для перекрытия всего диапазона задержек, т.е. вычислениедругих строк, необходимо применить многоканальную схему.Рисунок 1.4 – Структурная схема корреляционно-фильтровой обработкиПроведем расчёт количества операций для вычисления ДКФ этим методомбез учёта расходов на полосовую фильтрацию.

После преобразования (1.1) вдискретную форму, выражение для элемента матрицы ДКФ принимает вид:χ p,q =N T −1∑um =0Формат*− j 2 πδΦqδtmm m+ pve.матрицы КФ определяется требуемым диапазоном задержкивремени и частоты. При условии, что: δФ = 1 / Tχ и δt = Tχ / N T , получаем элементматрицы ДКФ: χ p,q =N T −1∑um =0*m m+ pv− j 2πemqNT.Выражение является преобразованием Фурье от выборки, составленной изпроизведений отсчётов входных сигналов и её можно вычислить с помощьюалгоритма БПФ, если число отсчётов по частоте равно числу отсчётов по времении равно 2 в целой степени, то Nd=NT.Сформируем матрицу A с элементами из произведений отсчётов сигналов:А = а p ,m , где ap,m =umv*m+p; m=k=q=0, 1, …, ( NT − 1) ; p=0, 1, …, ( Nτ − 1) .Матрица поворачивающих множителей равна: E = ek ,q = e− j 2πkqNT.25При использовании БПФ для вычисления ДКФ по общей формуле, тополучаем больше частотных отсчётов, чем Фmax: Фq = q2Фmax,Ndгде q=0, 1, …, ( NT − 1) , которые в дальнейшем не используются (избыточныеотсчёты).Назовёмданныйпроизведения матрицспособχ = А⋅Eполным.ДКФвычисляетсяспомощьюразмерностью [Nτ×NT]∙[NT×NT]=[Nτ×NT].

Этопроизведение представляет собой: u v* 0 0* u0 v1 ........u v * 0 ( Nτ −1) χ 00 χ10= ..... χ ( N −1) 0 τu1v1*...u1v2*...............u1v(*Nτ−1) + 1......χ 01...χ11..........χ(Nτ−1)1......0⋅ 0− j 2πNT  eu( N −1) v(*N −1) 1⋅0TT− j 2πu( N −1) v(*N −1) +1  NTTT⋅ e ......... .................u( N −1) v(*N −1) + ( N −1)  τTT  − j 2π ( N T −1)⋅0NTe− j 2πe− j 2πe0⋅1NT.................− j 2πe...1⋅1NT......( N T −1)⋅1NTe1⋅( N T −1)− j 2πNT=e.................( N −1)⋅( N T −1) − j 2π TNTe− j 2π...0⋅( N T −1)NTχ 0( NT −1)χ1( N −1) T......χ ( N −1)( N −1) τT(1.3)Рассмотрим строку матрицы ДКФ. Можно заметить, что эта строка являетсярезультатом преобразования Фурье для строки матрицы произведений отсчётовсигналов с одинаковыми задержками (при фиксированном p).Матрица А содержит Nτ∙NT (1024∙131072) элементов.

Количество операцийкомплексных умножений для формирования матрицы произведений отсчётовравно: 1024∙131072≈1,3∙108 операций. Для каждой строки матрицы выполняетсяБПФ. Каждое БПФ это131072⋅ 17 ≈ 1,1 ⋅ 10 6 операций. Всего 1024 строк.2Количество операций при вычислении БПФ: 1024∙1,1∙106=1,1∙109. Общееколичество операций комплексного умножения: 1,3∙108+1,1∙109 ≈1,28∙109.Формула для получения количества комплексных умножений принимаетвид:Nτ N Т (1 + 0,5 log 2 N Т ) . Требуемая производительность вычислителя прирасчёте ДКФ в реальном времени: 1,28∙109/0,01=1,28∙1011 оп/с.26Оценим затраты, когда сокращён диапазон частот: Фq = q2Фmax,Ndгде q=0, 1, …, ( N d − 1) . В этом случае получение ДКФ χp,q выполняется черезпреобразование Фурье: χ p,q =N T −1∑um =0*m m+ pv− j 2πemqNT,(1.4)где q = 0, 1, …, ( N d − 1) ; m = 0, 1, …, ( NT − 1) ; p = 0, 1, …, ( Nτ − 1) .В соответствие с формулой (1.4) получаем произведение матриц [Nτ×NT]∙∙[NT×Nd]=[Nτ×Nd].

Это произведение представляет собой: u v* 0 0* u0 v1 ........u v * 0 ( Nτ −1) χ10= ..... χ ( N −1) 0 τχ 00u1v1*...u1v2*...............u1v(*Nτ−1) +1......0⋅0− j 2πNT  eu( N −1) v(*N −1) 1⋅0TT− j 2πu( N −1) v(*N −1) +1  NTTT⋅ e ......... .................u( N −1) v(*N −1) + ( N −1)  ( N −1)⋅0 TTτ− j 2π TNTeχ 01...χ 0( Nχ11...χ1( N....χ(Nτ−1)1− j 2πe− j 2πe0⋅1NT.................− j 2πe...1⋅1NT......( N T −1)⋅1NTe1⋅( N d −1)− j 2πNT=e.................( N −1)⋅( N d −1) − j 2π TNTe− j 2π...0⋅( N d −1)NTd −1)............... χ ( N −1)( N −1) τdd −1)Количество комплексных умножений в матрице произведений отсчётовравно 1,3∙108 операций. Количество умножений для вычисления одного элементаДКФ через произведение матриц равно 131072.

Число элементов ДКФ получаем:Nτ N d = 1024 ⋅ 128 = 1,3 ⋅ 105 операций.Общее число операций: 1,3∙108+131072∙1,3∙105≈1,7∙1010. Формула длярасчёта количества комплексных умножений принимает вид: Nτ N Т (1 + N d ) .Требуемая производительность вычислителя при расчёте ДКФ в реальномвремени: 1,7∙1010/0,01=1,7∙1012 оп/с.Следующий этап сокращения количества операций - это применениепрореживания по времени. Прореженная матрица А представляет собой:ai , j = ulm vlm + p = a p ,lm , где l − целое число больше 1.27В этом случае матрица А имеет вид: u v* 0 0* u0 v1 ........u v * 0 ( Nτ −1)u1⋅l v1*⋅l + 0...u1⋅l v1*⋅l +1..................u1⋅l v1*⋅l + ( N −1)...τ..........u( N −1) v(*N −1) + ( N −1) ТТτv*−1) ( N −1) + 0Тu( N −1) v(*N −1) +1ТТu( NТПри этом число элементов отсчётов по времени равно: N T / l , скоростьобработки P при этом увеличивается в l раз: P1 = P0l .Приl =128получаем,чтоNТ=Nτ.ДКФможнопредставить,какпроизведения матриц χ = А ⋅ E размерностью [Nτ×Nτ]∙[Nτ×Nd]=[Nτ×Nd].После подстановки получаем общее число операций ≈1,4∙108.

Формула длярасчёта количества комплексных умножений: Nτ2 (1 + N d ) . При этот способеуменьшается отношение С/Ш на выходе коррелятора и теряется частьинформации об КФ, следовательно, искажается форма ДКФ.Для сокращения количества операций можно применить алгоритм БПФ,тогда Nd=Nτ.