Устройство для вычисления скалярного произведения двух векторов Советский патент 1982 года по МПК G06F17/16 

1

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

Известно устройство для вычисления суммы парных произведений, содержащее сумматор, регистры множи- ,5 мого и множителя, выходы которых соединены с входами квадратной матрицы и 13 одноразрядных модулей сложения, зы,ходы суммы всех строк которой, кроле последней строки и первого столб- 20 ца, соединены с вторыми суммирующими входами одноразрядных модулей слокения старшей строки и младшего столбца , а выход переноса каждого одноразрядного модуля сложения первого столбца всех строк, кроме последней, соединены с первым суммирующим входом соответствующего одноразрядн го модуля сложения первой строки l .

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

Наиболее близким по технической сущности к изобретению является устройство, содержащее сумматор, регистры множимого и множителя, матрицу одноразрядных модулей сложения, блоки элементов И и элемент ИЛИ, причём информационные входы первого блока элемента И соединены с инверсными входами регистра множимого, а выхо-ды - с вторыми входами сумматора 2 .

Недостатком, данного устройства является достаточно низкое быстродействие, определяемое тем, что вычислительный процесс организован в виде последовательности шагов, и относительно невысокая надежность вычислений из-за того, что в устройстве не организован контроль вычислительного процесса. Цель изобретения - повышение быстродействия и надежности устройства Поставленная цель достигается тем 4to в устройство, содержащее группу элементов И, элемент ИЛИ, регистр и сумматор, введены вычитатель, сумматор-вычит.атель, элемент И, сум матор по модулю два, триггер и одновибратор, причем группа элементов И образует матрицу, каждый т-й столбец которой ( ,2.. ., состоит из п элементов И, первые входы элементов И i-ro .столбца матрицы объединены и подключены к i-му входу первой группы входов устройства., вторые входы j-х-элементов И (,,.,r каждого столбца матрицы объединены и подключены к j-му входу второй rpy пы входов устройства, выходы элементов И каждой t-ой строки матрицы сое динены с входами 1-го разряда (,2 ...2п-1) сумматора, выход которого подключен к первому входу (t+2)-ro разряда сумматора-вычитателя, первые входы первого и второго разрядов которого подключены соответственно к нулевому входу устройства и к выходу переноса старшего разряда сумматора, вторые входы каждого разряда сумматора-вычитателя и вход переноса младшего разряда подключены к выходу сумматора по модулю два, первый и второй входы которого подключены соответственно к знаковым входам первой и второй групп входов устрой-; ства, первый выход S-ro разряда ( ,2,.. .,2п+1) сумматора-вычитателя соединен с первым входом S-ro разряда вычитателя и информационным входом 5-го разряда регистра,выход которого подключен к S-му выходу груп пы выходов устройства, второй вход S-ro разряда вычитателя подключены к втором выходу S-ro разряда сумматора-вычитателя, выход S-ro разряда регистра подключен к третьим входам S-x разрядов сумматора-вычитателя и вычитателя, п(рвый управляющий вход каждого S-ro разряда регистра к выходу одновибратора, к выходу регистрации конца переходного процесса устройства и к первому входу элемента ИЛИ, выход которого подключен к нулевому входу триггера, вход обнуления устройства подключен к второму управляющему входу каждого 5-го разряда регистра и к второму входу элемента ИЛИ, выход S-ro разряда вычи-.-тателя подключен к 5-му входу элемента И, (5+1)-ый вход которого соединен с единичным выходом триггера, выход элемента И соединен с входом одновибратора, единичный вход триггера подключен к входу запуска устройства. Кроме того, в устройстве каждый разряд сумматора-вычитателя содержит одноразрядный сумматор и сумматор по модулю два, выход которого подключен к первому входу одноразрядного сумматора и второму выходу разряда сумматора-вычитателя, первый выход разряда которого соединен с выходом сумMbj одноразрядного сумматора, второй вход которого, первый и второй входы сумматора по модулю два являются соответственно третьим, вторым и первым входами разряда сумматора-вычитателя, вход и выход переноса которого соединены соответственно с входом и выходом переноса одноразрядного сумматора. Каждый разряд вымитателя содержит полусумматор, два сумматора по модулю два, элемент И и элемент ИЛИ, выход которого является выходом заема разряда вычитателя, вход заема которого соединен с первым входом полусумматора , выход переноса которого подключен к.первому входу элемента ИЛИ, второй вход которого соединен с выходом элемента И, первый вход которого подключен к выходу суммы полусумматора и к первому входу первого сумматора по модулю два, второй вход которого является первым входом разряда вычитателя, второй вход разряда которого соединен с вторым входом полусумматора, выход первого сумматора по модулю два, соединен с вторым входом элемента И. и с первым входом второго сумматора по модулю два, выход которого является выходом разряда вычитателя, третий вход разряда которого соединен с вторым входом второго сумматора по модулю два. На фиг. 1 приведена схема устройства для случая, когда (п - разрядность входного кода, включая зн ковый разряд); на фиг. 2 - схема разряда сумматора-вычитателя; на фиг. 3 - схема разряда вычита теля.. Приняты следующие обозначения: группа 1 элементов И, сумматор 2, сумматор-вычитатель 3, вычитатель k регистр 5, элемент И 6, элемент ИЛИ 7, сумматор 8 по модулю два, триггер 9 одновибратор 10, первая группа входов Ир- 1Ц устройства, вторая группа входов 12о - 124 Уст ройства, группа выходов 13о 13g, элементы И , одноразрядные сумматоры 15, разряды 16 сумматора-вычитателя, разряды 17 вычитателя, разр ды 18 регистра, полусумматор 19, од норазрядный сумматора 20, сумматоры 21-23 по модулю два, элемент ИЛИ 2 и элемент И 25. Работу устройства рассмотрим на примере определения скалярного произведения 21 ( ,двух векторов х,у или .--. 2:,,-i-1.2,.--, (1) предварительно представленного в раз РЯД14ОЙ форме в нижеприведенном виде . ..,i, (г)

разрядные векторы, представляющие собой разрядное изображение компонент y;Z векторов x,z соответственно;

V X;

разрядная матрица, представляющая собой изображение компоненты Х; вектора X при

-ir-I..-.-W,

(6)

j 1,2i.. n,

j

где P; значение заема из j-ro разряда;

значение принимающее 1,

L; если в J-OM разряде - выражение (З) операция выполнена правильно, и О в ПРОтивном случае,

Знак произведения , 1-х компонент векторов X,Y определяется при этом в соответствии с выражением , г. (7) 88 Выражение 2 в развернутом виде при запишем 1,2..m Значение каждого разряда разрядного вектора в соответствии с (3) определяется i-1 1 i-2 г JH 1 1 ly.ii.,. .i.y,младшихс учетом единиц переноса из разрядов или , (5) .;.,Z;, i 1.2,, i где S; -.булева сумма выражения t ...+ ,определяется с учетом единиц переноса из младших разрядов выражения (3). Контроль вычислительного процесса реализуется путем вычисления в соответствии с выражением С 51 зна- чения г.Добозначим его,,)м сравнения го с заданным значением {сбозначим его z,, ),.что дости -ается путем иодеАи-. ровдния в каждом разряде выражения (3) следующей системы логических урав нений: i(S) it , i i i ) j i i .R..e,,,.,R;Z.R;, Момент фиксации конца переходног процесса определяется J тогда, когд конъюнкция значений L,, ,2,..n в выражении 1б1 равна единице, т.е. л г 1 (8) ... . .. Ь. I Работа уст ройства происходит сле дующим образом. На вход обнуления устройства подается импульс, благодаря чему регистр 5 и триггер 9 устанавливаются в нулевое состояние. После этого на входы 11 устройства, т«е. разряд 11о, 11... 114, и входы 12, т.е. разряды 12 о, 12... 124,подаются со ответственно значения разрядов соответствующих компонент векторов X, и в схеме идет переходной процесс. В это время на вход запуска устройства подается импульс, устанавливающий, триггер 9 в единичное состояние. После окончания переходного процесса на выходе сумматора 8 по моду лю два образуется нулевой сигнал, если произведение компонент по ложительно, и единичный - в противном- случае, который поступает на вход .сумматора-вычитателя 3 и настр ивает его на реализацию суммы или вычитания соответственно. На выходе одноразрядных сумматоров 15 сумматора 2 в соответствии с выражениями ( 3) Л ) (5 ) образуютсязначений разрядов булевых сумм, которые поступают на входы разрядов 16 суммат ра-вымитателя 3, на третьи входы ко торых поступают значения компонент с выходов разрядов 18 регистра 5. В сумматоре-вычитателе 3 в соответствии с выражениями (4)ДЗ образуются значения, которые поступают на первые входы разрядов 18 регистра 5 и на первые входы соответствующих, разрядов 17 вычитателя 4, на вторые и третьи входы которых поступают соответственно значения S, и Z.j , При этом поступает с второго выхода соответствующего раз ряда 16 сумматора-вычитателя и равно 5;,, если ЗпХ.;У положительный и 5 , если знак -произведения отрицательный. В каждом разряде вычитател в соответствии с выражением (6.J вычитается значение компоненты и срав нивается с заданной компонентной. Если ОНП1 равны, то нз выходе разряда вычитателя образуется единичный си нал .поступающий на вх.:д элемента И 6. В том случае, когда на всех выходах разрядов 17 вычитателя k образуются единичные сигналы, что ха-. рактеризует правильность выполнения операции и.конец переходного процесса в соответствии с выражением 18), на выходе элемента И 6 образуется единичный сигнал, которым запускается одновибратрр 10. Одновибратор 10 вырабатывает импульс, которым по переднему фронту реализуется запись в регистр 5 значений Z... , и устанавливается триггер 9 в нулевое состояние. Кроме того., импульс поступает на выход регистрации конца переходного процессора в устройстве характеризуя тем самым готовность устройства к реализации суммы произведения следующей пары компонент векторов. При появлении импульса на выходе регистрации конца переходного. . процесса в устройстве на входы подается очеред1:1ая пара компонент векторов, а на вход запуска устройства единичный сигнал установки триггера 9 в единичное состояние, после чего вычислительный процесс происходит аналогиччо вышеописанному. -Таким образом, через m тактов на выходе регистра 5 и соответственно выходах 13 образуется в соответствии с выражениями (2) , (З) значение Z,, равное скалярному произведениюдвух векторов. Сумма m парных произведений реализуется за m тактов, т.е. накопление произведения двух компонент за один такт. При этом, учитывая, что устройство является комбинационным с регистрацией конца переходного процесса в схеме т.е. асинхронным), длительность одного такта является « переменной и определяется величиной компонент векторов. Благодаря этому в случае равновероятного поступления всевозможных значений компонент векторов быстродействие устройства увеличивается приблизительно вдвое так как в этом случае длительность такта изменения в общем случае от нуля до максимума. Кро,ме того, увеличивается надежность вычислений благодаря частичной проверке вычислительного процесса, которая реализуется в соответствии с выражением 6 Формула изобретения 1. Устройство для вычисления скалярного произведен ия двух векторов, содержащее группу элементов И, элемент ИЛИ, регистр и сумматор, отличающееся тем, что, с целью повышения быстродействия и надежности, в него введены вычитатель сумматор-вычитатель, элемент И, сумматор по модулю два, триггер и одновибратор, причем группа элементов И образует матрицу, каждый i-й столбец которой ( ,2,,. .,п) состоит из п элементов И, первые входы элементов И 1-го столбца матрицы объединены и подключены к -му входу первой группы входов устройства, вторые входы J-X элементов И (,2,..n каждого столбца матрицы объединены и подключены к J-му входу второй группы входов устройства, выходы элементов И каждой -й строки матрицы соединены с входами 1-го разряда ,2,,. ,,2п-1) сумматора, выход которого подключен к первому входу (t+2)-ro разряда сумматора-вычитателя, первые входы первого и второго разрядов которого подключены соответственно к нулевому входу устройства и к выходу переноса старшего разряда сумматора вторые входы каждого разряда сумматора-вычитателя и вход переноса младшего разряда подключены к выходу сумматора по модулю два, первый и второй входы которого подключены соответственно к знаковым входам первой и второй групп входов устройства, первый выход S-ro разряда ( ,2,.. .,2п+1) сумматора-вычитателя соединен с первым входом S-ro разряда вычитателя и информационным входом S-ro разряда регистра, выход которого подключен к S-му выходу гру пы выходов устройства, второй вход S-ro разряда вычитателя подключен к второму выходу S-ro разряда сумматоравычитателя, выход S-ro разряда регистра подключен к третьим входам S-x разрядов сумматора-вычитателя и вычитателя, первый управляющий вход каждого S-ro разряда регистра подключен к выходу одновибратора, к выходу регистрации конца переходного процесса устройства и к первому входу элемента ИЛИ, выход которого подключен к нулевому входу триггера, вход обнуления устройства подключен к второму управляющему входу каждого S-ro разряда регистра и к второму входу элемента ИЛИ, выход S-ro разря да вычитателя подключен к S-му входу элемента И, ()-й вход которо8 . . ,10 го соединен с единичным выходом триггера, выход элемента И соединен с входом одновибратора, единичный вход триггера подключен к входу запуска устройства. 2.Устройство поп.1,отли;ч а 10 щ е е с я тем, что каждый разряд сумматора-вычитателя содержит одноразрядный сумматор и сумматор по модулю два, выход которого подключен к первому входу одноразрядного сумматора и второму выходу разряда сумматора-вычитателя, первый выход разряда которого соединен с выходом суммы одноразрядного сумматора, второй вход которого, первый и второй входы , сумматора по модулю два являются соответственно третьим, вторым и пер,вым входами разряда сумматора-вычитателя, вход и выход переноса которого соединены соответственно с входом и выходом переноса одноразрядного сумматора. 3.Устройство по п.1,о т л и - , чающееся тем, что каждый разряд вычитателя содержит полусумматор, два сумматора по модулю два, элемент И и элемент ИЛИ, выход которого является выходом заема разряп да вычитателя, вход заема которого соединен с первым входом полусумматора, выход переноса которого подключен к первому входу элемента ИЛИ, второй вход которого соединен с выходом элемента И, первый вход которого подключен к выходу суммы полусумматора и к первому входу первого сумматора по модулю два, второй вход которого является первым входом ряда вычитателя, втррой вход разряда которого соединен с вторым входом полусумматора, выход первого сумматора по модулю два соединен с вторым входом элемента И и с первым входом второго сумматора по модулю два, выход которого является выходом разряда вычитателя, третий вход разряда которого соединен с вторым входом второго сумматора по модулю два. Источники информадии, принятые во внимание при экспертизе 1.Авторское свидетельство СССР № i 80077, кл. G Об F 7/50, 1973. 2.Авторское свидетельство СССР № 561963, кл. G 06 F 7/52, 1975 (прототип).