Устройство для вычисления скалярного произведения двух векторов

Г. Е, Пухо И. Стасюк, ф. Е. Пискк, 8,Н, БелецкиВ. П. Еременко .с",с ".5.".еяЬЯ 72) Авторы изобретеяяя каС С Р В.а О ТЕ:"анститут электродинамики АН Украинс(7) Заявнтел 5 Й)УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ СКАЛЯРНОГО ПРОИЗВЕДЕНИЯ ДВУХ ВЕКТОРОВИзобретение относится к вычислительной технике и может быть применено в качестве спецпроцессора в комплексе с цифровой вычислительной машиной для оперативного вычисления5 скалярного произведения двух и-мерных векторов, например, в системах автоматического управления динамическими объектами, математические модели которых представляются в виде совокупности сумм парных произведений.Известно устройство для вычисления суммы парных произведений, содержащее сумматор, регистры множимого и множителя, выходы которых соединены с входами квадратной матрицы и 1 з одноразрядных модулей сложения, выходы суммы всех строк которой, кроче последней строки и первого столб о ца, соединены с вторыми суммирующими входами одноразрядных модулей слокения старшей строки и младшего столбца, а выход переноса каждого одноразрядного модуля сложения первого столбца всех строк, кроме последней, соединены с первый суммирующим входом соответствующего одноразряднс го модуля сложения первой строки 11,Недостатком известного устройства являются ограниченные функциональные возможности из-за того, что в устройстве реализуется сумма парных произведений только одного знака, а также низкое быстродействие и надежность вычисленийНаиболее близким по технической сущности к изобретению является устройство, содержащее сумматор, регистры множимого и множителя, матрицу одноразрядных модулей сложения, блоки элементов И и элемент ИЛИ, причем информационные входы первого блока элемента И соединены с инверсными входами регистра множимого, а выходы - с вторыми входами сумматора 2 .Недостатком, данного устройства является достаточно низкое быстро 3 95508действие, определяемое тем, что вычислительный процесс организован ввиде последовательности шагов, и относительно невысокая надежность вычислений из-за того, что в устройстве не организован контроль вычислительного процесса.Цель изобретения - .повышение быстродействия и надежности устройства.Поставленная цель достигается тем,Очто в устройство, содержащее группу элементов И, элемент ИЛИ, регистри сумматор, введены вычитатель, сумматор-вычитатель, элемент И, сумматор по модулю два, триггер и одновибратор, причем группа элементовИ образует матрицу, каждый т-й столбец которой (=1,2 п) состоит изи элементов И, первые входы элементов И -го столбца матрицы объединены и подключены к 1-му входу первой группы входов устройства, вторые входы -х элементов И (12,п)каждого столбца матрицы объединеныи подключены к )-му входу второй груп-Ипы входов устройства, выходы элементов И каждой 1-ой строки матрицы соединены с входами 1-го разряда (1=122 п) сумматора, выход которогоподключен к первому входу (1+2)-го звразряда сумматора-вычитателя,В первые входы первого и второго разрядовкоторого подключены соответственнок нулевому входу устройства и к выходу переноса старшего разряда сумматора, вторые входы каждого разрядасумматора-вычитателя и вход переносамладшего разряда подключены к выходу сумматора по модулю два, первыйи второй входы которого подключенысоответственно к знаковым входампервой и второй групп входов устрой",ства, первый выход 5-го разряда(5=1,22 п+1) сумматора-вычитателя соединен с первым входом 5-горазряда вычитателя и информационнымвходом 5-го разряда регистра, выходкоторого подключен к 5-му выходу группы выходов устройства, второй вход 5-горазряда вычитателя подключены к второму выходу 5-го разряда сумматора-вычи- о тателя, выход 5- го разряда регистраподключен к третьим входам 5"х разрядов сумматора-вычитателя и вычитателя, первый управляющий вход каж дого 5-го разряда регистра подключен к выходу одновибратора, к выходу регистрации конца переходного процесса устройства и к первому входу элемен 8 фта ИЛИ, выход которого подключен к нулевому входу триггера, вход обнуления устройства подключен к второму управляющему входу каждого 5-го разряда регистра и к второму входу элемента ИЛИ, выход 5-го разряда вычи-," тателя подключен к 5-му входу элемента И, (5+1)-ый вход которого соединен с единичным выходом триггера, выход элемента И соединен с входом одновибратора, единичный вход триггера подключен к входу запуска устройства.Кроме того, в устройстве каждый разряд сумматора-вычитателя содержит одноразрядный сумматор и сумматор по модулю два, выход которого подключен к первому входу одноразрядного сумматора и второму выходу разряда сумматора-вычитателя, первый выход разряда которого соединен с выходом сумт мы одноразрядного сумматора, второй вход которого, первый и второй вхо" ды сумматора по модулю два являются соответственно третьим, вторым и первым входами разряда сумматора-вычитателя, вход и выход переноса которого соединены соответственно с входом и выходом переноса одноразрядного сумматора.Каждый разряд вычитателя содержит полусумматор, два сумматора по модулю два, элемент И и элемент ИЛИ, выход которого является выходом заема разряда вычитателя, вход заема которого соединен с первым входом полу" сумматора, выход переноса которого подключен к,первому входу элемента ИЛИ, второй вход которого соединен с выходом элемента И, первый вход которого подключен к выходу суммы полусумматора и к первому входу первого сумматора по модулю два, второй вход которого является первым входом разряда вычитателя, второй вход разряда которого соединен с вторым входом полусумматора, выход первого сумматора по модулю два, соединен с вторым входом элемента И и с первым входом второго сумматора по модулю два, выход которого является выходом разряда вычитателя, третий вход разряда которого соединен с вторым входом второго сумматора по модулю два.На фиг. 1 приведена схема устройства для случая, когда п=5 (и - раз5 955088 рядность входного кода, включая знаВ 2ыражение ковый разряд); на Фиг. 2 - схема п=4 запишем разряда сумматора-вычитателя; нафиг. 3 - схема разряда выцитателя. 5Ф в развернутом виде при и=1,2.,е л, разствии с Знацерядного3) опре11х; ц ие каждого рчектора веляется как1-2 й л 1-1"19 ф "хЧ азрядасоответФ 2,учетом ед зрядов ил фсиниц перен младших и1.3 х=г;, -1,2 ельно предста рме в нижепри ажения кц;четом еди зрядов выленного в ра еденном виде вариой фоч слительногои вычисленияем 151 зна-г векторы, представляющиеядное изображение комповекторов х,г соответстные фз Кв 1 (в 1ь:ъ, Эь;где Р " знаце"0" в про ма е ч н разрядная матри"ца, представляющаясобой иэображениекомпоненты Х век"тора Х при п=3 е;х;у, 1- еделяетс х коя прием аж Зп Приняты следующие обозначения группа 1 элементов И, сумматор 2, сумматор-вычитатель 3, вычитатель 4 рег стр 5, элемент И 6, элемент ИЛИ 7, сумматор 8 по модулю два, триггер 9, одновибратор 10, первая группа входов 11 р устройства, вторая группа входов 12 о - 12 уст ройства, группа выходов 13 о, элементы И 14, одноразрядные сумматоры 15, разряды 16 сумматора-вычитателя, разряды 17 вычитателя, разр ды 18 регистра, полусумматор 19, од норазрядный сумматора 20, сумматоры 21-23 по модулю два, элемент ИЛИ 24 и элемент И 25. Работу устроиства рассмотрим на примере определения скалярного произведения г х;у; =л ,двух векторов х,у или где 1; - , булева сумма выр ЗО фх, ц; к 1 у;, определяется с ниц переноса из младших р ражения 3) . Нонтроль вычи процесса реализуется путе в соответствии с выражени 1 1 п 1 ЗЗ чения , (обозначим его дего с заданным значением 1 3 е 1 его к ),.что достигается и ф рования в каждом разряде выр следующей системы логичес 4 в нений: в 11=20+(если в )-омжение (3)иена правилтивном случЗнак произведениянт векторов Х,У опом в соответствииМомент фиксации конца переходного процесса определяется ) тогда, когда конъюнкция значений 1. ) 1,2 п в выражении 6) равна единице, т.е.о8)1:Ьл.,л,л. .Работа ус 1 ройства происходит следующим образом.На вход обнуления устройства подается импульс, благодаря чему ре гистр 5 и триггер 9 устанавливаются в нулевое состояние, После этого на входы 11 устройства, т,е, разряды 11, 11114, и входы 12, т.е, разряды 12, 12 124,подаются со ответственно знацения разрядов соответствующих компонент векторов Х,У и в схеме идет переходной процесс,В это время на вход запуска устройства подается импульс, устана- щ вливающий триггер 9 в единичное состояние.После окончания переходного процесса на выходе сумматора 8 по модулюдва образуется нулевой сигнал, 25 если произведение компонент Х; У положительно, и единичный - в противном случае, который поступает на вход, сумматора-выцитателя 3 и настраивает его на реализацию суммы или щ вычитания соответственно. На Ьыходе одноразрядных сумматоров 15 сумматора 2 в соответствии с выражениями 3),4),(5) образуются значения разрядов булевых сумм, которые поступают на входы разрядов 16 суммато ра-выцитателя 3, на третьи входы которых поступают знацения компонент с выходов разрядов 18 регистра 5. В сумматоре-выцитателе 3 в соответствии с выражениями (4),5) образуются значения, которые поступают на первые входы разрядов 18 регистра 5 и на первые входы соответствующих. разрядов 17 вычитателя45на вторые и третьи входы которых поступают соответственно значенияи 1 , При этом Б поступает свторого выхода соответствующего разряда 16 сумматора-выцитателя и равно 1, если ЗпХ,У положительный,и30если знак произведения отрицательный, В каждом разряде выцитателя в соответс 1 вии с выражением 6 вычитается значение компоненты и срав нивается с заданной с.мпонентнои, Если онн равны, то нз выходе разряда выцитателя образуе гся единичный сиг нал,поступающий на вхд элемента И 6. В том случае, когда иа всех выходах разрядов 17 вычитателя 4 образуются единичные сигналы, что ха- рактеризует правильность выполнения операции и конец переходного процесса в соответствии с выражением (8), на выходе элемента И 6 образуется единицный сигнал, которым запускается одновибратор 10. Одновибратор 10 вырабатывает импульс, которым по переднему фронту реализуется запись в регистр 5 значений 2" 12 , и устанавливается триггер 9 в нулевое состояние. Кроме того., импульс поступает на выход регистрации конца переходного процессора в устройстве характеризуя тем самым готовность устройства к реализации суммы произведения следующей пары компонент векторов. При появлении импульса на выходе регистрации конца переходного, процесса в устройстве на входы подается очередная пара компонент векторов, а на вход запуска устройства единичный сигнал установки триггера 9 в единичное состояние, после чего вычислительный процесс происходит ана логицчо вышеописанному. -Таким образом, через о тактов на выходе регистра 5 и соответственно выходах 13 образуется в соответствии с выра. жениями (2),(3) значение 2, равное скалярному произведению двух векторов. Сумма в парных произведений реализуется за щ тактов, т,е. накопление произведения двух компонент за один такт, При этом, учитывая, что устройство является комбинационным с регистрацией конца переходного процесса в схеме т.е. асинхронным, длительность одного такта является ю переменной и определяется величиной компонент векторов. Благодаря этому в случае равновероятного поступления всевозможных значений компонент векторов быстродействие устройства увелицивается приблизительно вдвое так как в этом случае длительность такта изменения в общем случае от нуля до максимума.Кроме того, увеличивается надежность вычислений благодаря частичной проверке вычислительного процесса, которая реализуется .в соответствии с выражением 6 .Формула изобретения1. Устройство для вычисления скалярного произведения двух векторов, содержащее группу элементов И, эле9 9550 мент ИЛИ, регистр и сумматор, о т - л и ч а ю щ е е с я тем, что, с целью повышения быстродействия и надежности, в него введены вычитатель, сумматор-вычитатель, эЛемент И, сум матор по модулю два, триггер и одновибратор, причем группа элементов И образует матрицу, каждый 1-й столбец которой (11,2,п) состоит из и элементов И, первые входы элемен- О тов И 1"го столбца матрицы обьединены и подключены к 1-му входу пер)вой группы входов устройства, вторые входы )-х элементов И (1=1,2,п) каждого столбца матрицы обьединены и 15 подключены к 1-му входу второй группы входов устройства, выходы элементов И каждой 3-й строки матрицы соединены с входами 1-го разряда (=1,2 .,2 п"1) сумматора, выход ко торого подключен к первому входу (3+2)-го разряда сумматора-вычитателя, первые входы первого и второго разрядов которого подключены соответственно к нулевому входу уст ройства и к выходу переноса старшего разряда сумматора, вторые входы каждого разряда сумматора-вычитателя и вход переноса младшего разряда подключены к выходу сумматора по модулю 50 два, первый и второй входы которого подключены соответственно к знаковым входам первой и второй групп входов устройства, первый выход 5-го разряда (5=1,22 п+1) сумматора-вычитателя соединен с первым входом 5-го разряда вычитателя и информационным входом 5-го разряда регистра, выход которого подключен к 5-му выходу группы выходов устройства, второй вход 5-го разряда вычитателя подключен к второму выходу 5-го разряда сумматоравычитателя,выход 5-го разряда регистра подключен к третьим входам 5-х разрядов сумматора-вычитателя и вычитателя, первый управляющий вход каждого 5-го разряда регистра подключен к выходу одновибратора, к выходу регистрации конца переходного процесса устройства и к первому входу элемента ИЛИ, выход которого под" ключен к нулевому входу триггера, вход обнуления устройства подключен к второму управляющему входу каждого 5-го разряда регистра и к второму входу элемента ИЛИ, выход Ь-го разря 55 да вычитателя подключен к 5"му входу элемента И, (5+1)-й вход которо 88 . 1 Ого соединен с единичным выходом триггера, выход элемента И соединен с входом одновибратора, единичный вход триггера подключен к входу запуска устройства.2. Устройство по п,1, о т л и:.ч а ю щ е е с я тем, что каждый разряд сумматора-вычитателя содержит одноразрядный сумматор и сумматор по модулю два, выход которого подключен к первому входу одноразрядного сумматора и второму выходу разряда сумматора-вычитателя, первый выход разряда которого соединен с выходом суммы одноразрядного сумматора, второй вход которого, первый и второй входы сумматора по модулю два являются соответственно третьим, вторым и пер,вым входами разряда сумматора-вычитателя, вход и выход переноса которого соединены соответственно с входом и выходом переноса одноразрядного сумматора.3, Устройство по п.1,о т л и ч а ю щ е е с я тем, что каждый раз. ряд вычитателя содержит полусумматор, два сумматора по модулю два, элемент И и элемент ИЛИ, выход которого является выходом заема разря да вычитателя, вход заема которого соединен с первым входом полусумма- тора, выход переноса которого подклю чен к первому входу элемента ИЛИ, второй вход которого соединен с выходом элемента И, первый вход кото" рого подключен к выходу суммы полу- сумматора и к первому входу первого сумматора по модулю два, второй вход которого является первым входом раз ряда вычитателя, втррой вход разряда которого соединен с вторым входом полусумматора, выход. первого сумматора по модулю два соединен с вторым входом элемента И и с первым входом второго сумматора по модулю: два, выход которого является выходом разряда вычитателя, третий вход разряда которого соединен с вторым входом второго сумматора по модулю два. Источники информации,принятые во внимание при экспертизе1. Авторское свидетельство СССРй Й 80077, кл. С 06 Г 7/50, 1973.2. Авторское свидетельство СССРН 561963 кл. 6 06 Г 7/52, 1975. 4 У илиал ППП "Патент", г, Ужгород, ул. Проектн 439/55 Тираж НИИПИ Государственног по делам изобретений 13035, Москва, Ж,1 Подписикомитета СССРоткрытийушская наб д