Многоканальный цифровой коррелятор Советский патент 1975 года по МПК G06F17/15 

(54) МНОГОКАНАЛЬНЫЙ ЦИФРОВОЙ КОРРЕЛЯТОР

1

Изобретение относится к специализированным средствам цифровой вычислительной техники, предназначенной для анализа слу-чайных процессов.

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

Однако при .увеличении быстродействия пропорционально требуется увеличение объема аппаратуры.

Цель изобретения - повышение быстродействия при относительно незначительном увеличении объема аппаратуры.

Достигается это благодаря тому, что коррелятор содержит три блока задержки, общий комбинационный сумматор и четыре группы комбинационных сумматоров, причем выходы первого и второго блоков задержки подключены соответственно к входам общего комбинационного сумматора и к первым входам блоков умножения первой и второй группы, а выход общего комбинационного сумматора соединен с первым входом блоков умножения третьей группы; выход третьего блока задержки соединен с входом шестого блока задержки, второй вход которого подключен к выходу седьмого блока задержки, а выходы - соединены соответственно с входом пятого блока задержки, с вторыми входами соответствующих блоков умножения третьей группы, с вторымр входами соответствующих комбинационных сумматоров первой группы и с первыми входами соответствующих сумматоров второй группы, вторые входы последних подключены к выходу седьмого блока задержки, а выходы - ко вторым входам блоков умножения второй группы, выходы которых соединены соответственно с первыми входами комбинационных сумматоров четвертой группы, а их вторые входы подключены к выходам блоков умножения третьей группы, а выходы - к соответствующим накаплива}ощим сумматорам первой группы; выход четвертого блока задержки соединен с входом седьмого блока задержки; выход которого подключен к вхо.чу восьмого блока задержки, соединенному выходом с входом пятого блока задержки. Выходы блока задержки подключены к вторым входам соответству ющих комбинационных сумматоров первой группы, соединенных выходами с вторыми входами соответствующих блоков умножен первой группы, подключенных к первым входам соответствующих комбинационных сумматоров третьей группы, вторые входы которых подключены к выходам соответст вующих блоков умножения третьей группы , а выходы - к входам накапливающих сумматоров второй группы. На чертея е представлена структурная схема коррелятора. В состав коррелятора входит входной блок 1, предназначенный для приема чисе рядов X и У и распределения по выход их на блоки задержки 2, 2, .. . 2. 1 о каждый из которых содержит П. сдвиговы регистров по Ш разрядов, где П, - разрядность чисел X и у , включая знак Q.I m - количество ординат корреляционной функции. Блоки задержки 2 и 2 служат для за поминания и сдвига по Q -ф чисел ;ряда X каждый. Блоки задержки 2 , 2 и 2 служат о Т о для запоминания и сдвига по Q чисел ряд У каждый. Блоки задержки 2 , 2 и 2 служат для буферного хранения по Q о чисел ряда У каждый и используются с целью согласования потока данных на вхо устройства со скоростью вычислений. Входы параллельного кода блоков задержки 2,2 2„ связаны с соответствующими выходами распределительно го блока 1. Выходы параллельного кода всех чисел блоков задержки 2 „. 2 . и 2 о 4 5 связаны с аналогичными входами блоков задержки 2 , 2 и 2 . Выход параллельо /о ного кода блока 2„ подан на вход блоков 2зИ2. Вентильные цепи для коммутации и распределения кодов, а также цепи и устройство управления на схеме не показаны Для вычитания чисел предназначены общий параллельный комбинационный сумматор 3 и группа из а комбинационных сумматоров 3.. Группа из Q комбинационных сумматоров 4 и 4 и группа из d комбинационных сумматоров 4 служат для параллельного сложения чисел. Три группы по С матричных блоков умножения 5 , S и 5 служат для попарного умножения чисел. Для накопления результатов вычислений т значений корреляционной функции предназначены накапливающие сумматоры 6. Все связи, показанные на схеме, служат для передачи параллельного кода. Выход блока задержки 2 подан на первые входы блоков умножения 5.. и на первый вход сумматора 3 , на второй вход которого подан выход блока- задержки 2„, который также соединен с первыми входами уст- . ройств умножения 5 . Сумматор 3.. предназначен для реализации операции вычитания . (здесь и далее i. fTo, ) If-f- jLi и выдачи результата по выходу на первые . входы устройств умножения -5 . Группа сумматоров 4 служит для реали- зации параллельного сложения чисел У -f.. V для чего первые входы сумматоров 4 соединены с выходами чисел блока задержки 2., а вторые входы - с выхоbдами чисел блока задержки 2. Группа сумматоров 4 предназначена для реализации операции сложения чисел V ч- Vдля чего первые входы . . сумматоров 4„ соединены с выходами чисел блока задержки 2, а вторые входыс выходами чисел блока задержки 2. Груп- пы блоков умножения 5 служит для реализации умножения ;(У (L чего на вторые входы блоков 5 поданы выходы групп сумматоров 4 . Группа блоков умножения 5„ п 1едназначена для выполнения операции X; (у, 4 /Ч+аl. чего вторые входы блоков 5 соединены с выходами сумматоров 4„. Группа блоков умножения 5 служит для реализации операции умножения (Х -X х i fr+a ° иа вторые входы устройств 5, поданы выходы -чисел блока задержки 2 Группа блоков 4 предназначена для реализации операции сложения Х.(. (i Uu) ° первы входы сумматоров соединены с выходами группы блоков умножения 5., а вторые входы - с выходами группы блоков умножения 5„. О-. Группа сумматоров 3 служит для pea лизации операции вычитания .,. (V )(l ° первые входы сумматоров 3 соединены с . выходами группы блоков 5„, а вторые с выходами группы, блоков 5 . Выходы сумматоров 4 и 3 поданы о. на входы fn накапливающих сумматоров 6 служащие для накопления кодов tTl значений корреляционной функции R , умно женных на коэффициент N-J + 1 (здесь и далее (г- jyi ) и N длина ряда чисел X Приведем алгоритм вычисления коррел циошюй функйии, реализуемый в приборе. Допустим имеются два ряда чисел , и ,,i/.,,...N|, причем К четное. Требуется определить ТТ) значений взаимной корреляционной функ ции, причем ,I ГДб У-целое чис ло. Значения R -. взаимной корреляционJ-lной функции для центрированных рядов в известных цифровых корреляторах вычисляются по формуле 1 ) для вектора значений ( N-i+l)R,/; матричной форме можно записать ,lN-l)R,...(N-iM)Rj.i,.CN-tm-i)R ,,..-Vrn 1 |x,,x,...x...xj. VA-O Y,0...0 K nx-ilmi(K-Om+2 (K.,tnfl I (K-i1ni+i (K-i)nit2 {к-1)пч- %H)n(K-,)m+3 ... У( K-l)l4 + fTl+1 )/(.,,V В частности, при К 1 получим Ы ygVy- m+i ,,X2,... n Vf Квадратная матрица В обладает свойством равенства членов по диагоналям, т. е является матрицей Ганкеля, которая симметричным разбиением по столбцам и строкам может быть представлена в виде совокупности четырех матриц, две из которых равны, следующим образом вН II 4 Обозначим вектор Д , как Д /d, А. /, d,|X. 2.1 Xal ) При этом можно записать D,B, ld,d,|.|b;. Для умножения вектора на матрицу Ганк справедлив следующий алгоритм ,,С2-Сз, C, d,, C daMlb4 t3ll, ,-i,i4ihll. Можно показать, что описанный алгоритм при ТП 10 требует меньшего количества операций, чем известный алгоритм умножения вектора на матрицу. В аппаратурной реализации алгоритма это даетвьшц. рыш в оборудовании. В частности, из приведенных вьфажейий видно, что вместо четырех матричных умножеН11й, которые обычно необходимы, требуется только три, следовательно, количество блоков умножения ; сокращается на четверть. : Таким образом, задача вычисления ТП значений корреляционной функции с;водится к вычислению t произведений векторов н матрицу В . и алгебраическому суммированию произведений. При этом процесс вычисления содержит t циклов по а тактов в каждом цикле, т. е. обработка информаци осуществляется пакетами по а слов каж дого ряда. Рассмотрим работу коррелятора. В начальный момент времени регистры блок9В задержек 2 и накапливающих сумматоров установлена в нулевое состояние. Из распределительного блока 1 в блоки задержки 2 и 2 заносится в naKeTlTl первых сло ряда ,, а в блоки задержки 2 , 2 и 2 (через блоки 2 , 2 и 2 ) заносит 3 ся пакет из - (Х. первых слов ряда ,-V : Далее начинается собственно вычисление значений взаимной корреляционной функции, для чего осуществляется сдвиг влево на Q тактов содержимого всех блоков задержки. При этом на входы сумматора 3 с выходов блоков 2 2 после- JLJL довательно поступают сдвинутые на О- так тов пары чисел ряда X , а на его выходе формируются разности этих чисел, т. е. реахшзуется операция вычитания двух векторов ( 1 о i 1 Ь результат которой поступает на входы блоков умножения 5„. На входы сумматоров 4 и 4 поступают сдвинутые на и тактов пары чисел Y и реализуются операции сложения двух мат риц Ь,-«-Ь, и Ь,,, , результаты которых поступают на входы устройств умножения 5 и 5 соответственно. На выходе группы блоков умножения 5 и 5„ формируется С (и С) результат умножения вектора el (и на сумму матриц (Ь + Ъ2)Й fb -f-ba). который далее поступает на входы группы сумматоров 4 (и З). На выходе группы блоков умножения 5 формируется С - результат умножения оо разности векторов d,,-d на матрицу Ц, который далее поступает на вторые входы группы сумматоров 4 и 3. О В сумма 1-орах 4 осуществляется сложение векторов С и С„, а в сумматорах 1v3 -3 осуществляется вычитание векторовС и С„ с выходов сумматоров 4 и 3 чаоо. стные значения корреляционной функции поступают в накапливающие сумматоры 6. Цикл работы содержит tt тактов, т. е. в два :раза меньше, чем в обычном параллельном корреляторе. Одновременно со сдвигом чисел блоках задержки 2, производится ввод новых чисел рядов Y и X через входной блок 1. При этом за а тактов цолностью обновляется содержимое чисел ряда X блоков 2. и 2, содержимое блока 2 переносится вблок 2„, новая о пачка in чисел ряда Y заносится в блоки 2 . и 2.,. По окончании цикла содержимое блоков 2 , 2 и 2... заменяется содержиt (о мым блоков 2„. 2 . и 2. о 4 Ь Далее цикл работы коррелятора повторяется. После I циклов в сумматорах 6 накапливаются m значений корреляционной функции Rj- , умноженные на коэффициент ( N - j -И ).Если m«N и N 2 , то с достаточной точностью значения корреляционной функции могут быть ВЗЯТБ1 со старщих разрядов, начиная с V накапливающих сумматоров 6. Вычисление автокорреляционной функции производится аналогично при вводе ряда X на оба входа устройства. Описанный цифро вой коррелятор целесообразно использовать как приставку к ЦВМ для повышения ее производительностиПредмет изобретения Многоканальный цифровой коррелятор, содержащий распределительный блок, подключенный к входам соответствующих блоков задержки, блоки умножения и накапливающие сумматоры, отличающийся тем, что, с целью повыщения быстродействия, коррелятор содержит дополнительно три блока задержки, общий комбинационный сумматор и четыре группы комбинационных сумматоров, причем выходы первого и второго блоков задержки подключены соответственно ко входам общего комбинационного сумматора и к первым входам блоков умножения первой и второй группы, а выход общего комбинационного сумматора соединен с первым входом блоков умножения третьей группы; выход Третьего блока задержки соединен со входом щестого блока задержки, второй вход которого подключен к выходу седьмого блока задержки, а выход соединен соответственно с входом пятого блока задержки, с вторыми входами соответствующих блоков умножения третьей группы, с вторыми входами соответствующих комбинационных сумматоров первой группы и с первыми входами соответствующих сумматоров второй группы, вторые входы которых подключены к выходу седьмого блока задержки, а выходы к вторым входам блоков умножения второй группы, выходы которых соединены соответственно с первыми

входами комбинационньа сумматоров четвертой группы, вторые входы которых подключены к выходам блрков умножения третьей группы, а выходы - к соответствующим 5 накапливающим сумматорам первой группы; выход четвертого блока задержки соединен с входом седьмого блока задержки; выход которого подключен к входу восьмого блока задержки, соединенному выходом с вхо-

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

20 группы, а выходы - к входа 1 накапливающих сумматоров второй группы.