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

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

Иллюстрации

Показать все

Реферат

 

Г. Е, Пухов, А. И. Стасюк, Ф. Е. Писк к, Б.И. Белецкий и В. П. Еременко

I ,- 1 тт

Институт электродинамики АН Украинско CCPSpn. 1ИОТЕ." :"е (72) Авторы изобретеяяя (7l) Заяввтель (54)УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ СКАЛЯРНОГО

ПРОИЗВЕДЕНИЯ ДВУХ ВЕКТОРОВ

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

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

Известно устройство для вычисления суммы парных произведений, содержащее сумматор, регистры множимого и множителя, выходы которых соединены с входами квадратной матрицы и

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

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

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

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

Поставленная цель достигается тем, О что в устройство, содержащее группу элементов И, элемент ИЛИ, регистр и сумматор, введены вычитатель, сумматор-вычитатель, элемент И, сумматор по модулю два, триггер и од- 15 новибратор, причем группа элементов

И образует матрицу, каждый т-й столбец которой (i=1,2...п) состоит из и элементов И, первые входы элементов И i-ro столбца матрицы объеди- 20 нены и подключены к i ìó входу первой группы входов устройства, вторые входы j-х элементов И (j 1 ?,n) каждого столбца матрицы объединены и подключены к j --му входу второй груп-И пы входов устройства, выходы элементов И каждой f-ой строки матрицы соединены с входами i-го разряда {3=112 ...„2п-1) сумматора, выход которого подключен к первому входу { +2)-го зв разряда сумматора-вычитателя,В первые входы первого и второго разрядов которого подключены соответственно к нулевому входу устройства и к выходу переноса старшего разряда сумматора, вторые входы каждого. разряда сумматора-вычитателя и вход переноса младшего разряда подключены к выходу сумматора по модулю два, первый и второй входы которого подключены

% соответственно к знаковым входам первой и второй групп входов устрой", ства, первый выход S-го разряда (S=1,2,...,2п+1) сумматора-вычитателя соединен с первым входом S-го разряда вычитателя и информационным входом S-го разряда регистра, выход которого подключен к S-му выходу груп пы выходов устройства, второй вход S-го разряда вычитателя подключены к второму выходу S-го разряда сумматора-вычитателя, выход S- ro разряда регистра подключен к третьим входам S"õ разрядов сумматора-вычитателя и вычитателя, первый управляющий вход каж дого S-го разряда регистра подключен к выходу одновибратора, к выходу регистрации конца переходного процесса устройсTBà и к первому входу элемен8 ф та ИЛИ, выход которого подключен к нулевому входу триггера, вход обнуления устройства подключен к второму управляющему входу каждого S-ro разряда регистра и к второму входу элемента ИЛИ, выход S-го разряда вычи-." тателя подключен к 5-му входу элемента И, (5+1)-ый вход которого соединен с единичным выходом триггера, выход элемента И соединен с входом одновибратора, единичный вход триггера подключен к входу запуска устройства.

Кроме того, в устройстве каждый разряд сумматора-вычитателя содержит одноразрядный сумматор и сумматор по модулю два, выход которого подключен к первому входу одноразрядного сумматора и второму выходу разряда сумматора-вычитателя, первый выход разряда которого соединен с выходом сум-. мы одноразрядного сумматора, второй вход которого, первый и второй входы сумматора по модулю два являются соответственно третьим, вторым и первым входами разряда сумматора-вычитателя, вход и выход переноса которого соединены соответственно с входом и выходом переноса одноразрядного сумматора. Каждый разряд вычитателя содержит полусумматор, два сумматора по модулю два, элемент И и элемент ИЛИ, выход которого является выходом заема разряда вычитателя, вход заема которого соединен с первым входом полу" сумматора, выход переноса которого подключен к,первому входу элемента

ИЛИ, второй вход которого соединен с выходом элемента l), первый вход которого подключен к выходу суммы полусумматора и к первому входу первого сумматора по модулю два, второй вход которого является первым входом разряда вычитателя, второй вход разряда которого соединен с вторым входом полусумматора, выход первого сумматора по модулю два, соединен с вторым входом элемента И и с первым входом второго сумматора по модулю два, выход которого является выходом разряда вычитателя, третий вход разряда которого соединен с вторым входом второго сумматора по модулю два.

На фиг. 1 приведена схема устройства для случая, когда n=5 (и - раз5 955О88 рядность входного кода, включая зна- В 2

ыражение ковый разряд); на фиг. 2 - схема .п=4 запишем разряда сумматора-вычитателя; на фиг. 3 — схема разряда вычитателя. S

Ф в развернутом виде при

Г зз где ч

v х =

1 разрядная матри" ца, предсгавляющая зз собой иэображение компоненты Х; век" тора Х при п=3

Приняты следующие обозначения! группа 1 элементов И, сумматор 2, сумматор-вычитатель 3, вычитатель 4, регистр 5, элемент И 6, элемент

ИЛИ 7, сумматор 8 по модулю два, триггер 9, одновибратор 10, первая группа входов 11р- 11 устройства, вторая группа входов 12о - 12 устройства, группа выходов 13р- 13, элементы И !4, одноразрядные сумматоры 15, разряды 16 сумматора-вычитателя, разряды 17 вычитателя, разряды 18 регистра, полусумматор 19, одноразрядный сумматора 20, сумматоры

21-23 по модулю два, элемент ИЛИ 24, и элемент И 25.

Работу устройства рассмотрим на примере определения скалярного проГП изведения г х;у; -z,двух векторов х,у или х„Ц; - х „„= г;,1-1,2,...,m, (1)

30 предварительно представленного в разрядной форме в нижеприведенном виде разрядные векторы, представляющие собой разрядное изображение компонент y„ z; векторов х,z соответственно;

i =1,2.,m

9..

Значение .каждого разряда z, раз-. рядного вектора z â соответствии с (3) определяется как

j- 1 1-22 1- j 1 (4) х ц„ ФkÄrjÄ-Ф... х ц„ Фz, „ 2 с учетом единиц переноса из младших разрядов или (5)

Б +Ь -Z \ =<1 где ; —.булева сумма выражения „Ц;

;2 2 1 41-1 х,ц;+...+к;у;, определяется с учетом единиц переноса из младших разрядов выражения (3) . l(QHTpoflb вычислительного процесса реализуется путем вычисления в соответствии с выражением j5) зна-! 1 r31 чения z „, (обозначим его g,,) и сравнения его с заданным значением Ь (обозначим

Из> 1 1 его z „), что достигается путем модеЬи-.

1- Э рования в каждом разряде выражения (3) следующей системы логических ураво нений: 3(8)

2.„ = „0+

4 Ж 6В) j j 4

1 ®) (В) =1,2,,. т, (6)

Ь„=, Q+ z,; =1,Я„, n, S

° ° ° у где Р„ » значение заема из j-ro разряда;

Ь; значение принимающее "1", если в j-ом разряде - выражение (3) — операция выпол" иена правильно, и "0" в противном случве;

Знак произведения х;у, 1-х компонент векторов Х,Y определяется при этом в соответствии с выражением

) З ф 1., g1) Зп х. 9 зла .. (7) 955088

Момент фиксации конца переходного процесса определяется ) тогда, когда

3, конъюнкция значений (,, ) 1,2...и в выражении (6) равна единице, т.е. (8)

1=L,„ë L,, л... л1.„ ... .„, Работа ус1ройства происходит следующим образом.

На вход обнуления устройства подается импульс, благодаря чему ре- 10 гистр 5 и триггер 9 устанавливаются в нулевое состояние, После этого на входы 11 устройства, т,е. разряды

11, 11 ... 114, и входы 12, т.е, разряды 12, 12„... 124,подаются со- l$ ответственно значения разрядов соответствующих компонент векторов Х,Y и в схеме идет переходной процесс.

В это время на вход запуска устройства подается импульс, устана- щ вливающий триггер 9 в единичное состояние.

После окончания переходного процесса на выходе сумматора 8 по модулю два образуется нулевой сигнал, 2s если произведение компонент X; Y положительно, и единичный - в противном. случае, который поступает на вход, сумматора-вычитателя 3 и настраивает его на реализацию суммы или Зо вычитания соответственно. На Ьыходе одноразрядных сумматоров 15 сумматора 2 в соответствии с выражениями (3),(4),(5) образуются значения разрядов булевых сумм, которые поступают на входы разрядов 16 сумматор ра-вычитателя 3, на третьи входы которых поступают значения компонент с выходов разрядов 18 регистра

В сумматоре-вычитателе 3 в соответствии с выражениями (4),(5) образуются значения, которые поступают на первые входы разрядов 18 регистра 5 и на первые входы соответствующих разрядов 17 вычитателя

4, на вторые и третьи входы которых поступают соответственно значения и 1„ „ . При этом S поступает с второго выхода соответствующего разряда 16 сумматора-вычитателя и равно 1„, если ЗпХ, Y положительный,и

1 если знак произведения отрицательный. В каждом разряде вычитателя в соответствии с выражением (6)вычитается значение компоненты и срав нивается с заданной компонентной.

Если они равны, то н выходе разряда вычитателя образуе гся единичный сиг. нал,посту ающий на вх.-д элемента И 6.

B том случае, когда иа всех выходах разрядов 17 вычитателя 4 образуются единичные сигналы, что ха- . рактеризует правильность выполнения операции и конец переходного процесса в соответствии с выражением (8), на выходе элемента И 6 образуется единичный сигнал, которым запускается одновибратор 10. Одновибратор

10 вырабатывает импульс, которым по переднему фронту реализуется запись в регистр 5 значений Z" 3(...2„, и устанавливается триггер 9 в нулевое состояние. Кроме того., импульс поступает на выход регистрации конца переходного процессора в устройстве> характеризуя тем самым готовность устройства к реализации суммы произведения следующей пары компонент векторов. При появлении импульса на выходе регистрации конца переходного, процесса в устройстве на входы подается очередная пара компонент векторов, а на вход запуска устройства единичный сигнал установки триггера

9 в единичное состояние, после чего вычислительный процесс происходит ана. логиччо вышеописанному. -Таким образом, через m тактов на выходе регистра 5 и соответственно выходах

13 образуется в соответствии с выражениями (2),(3) значение Zm, равное скалярному произведению двух векторов. Сумма m парных произведений реализуется за m тактов, т,е. накопление произведения двух компонент за один такт, При этом, учитывая, что устройство является комбинационным с регистрацией конца переходного процесса в схеме (т.е. асинхронным, длительность одного такта является переменной и определяется величиной компонент векторов. Благодаря этому в случае равновероятного поступления всевозможных значений компонент векторов быстродействие устройства увеличивается приблизительно вдвое, так как в этом случае длительность такта изменения в общем случае от нуля до максимума.

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

Формула изобретения

1. Устройство для вычисления скалярного произведения двух векторов, содержащее группу элементов И, элеИсточники информации, принятые во внимание при экспертизе

1. Авторское свидетельство СССР и 480077, кл. G 06 F 7/50, 1973.

2. Авторское свидетельство СССР

N 561963, кл. G 06 F 7/52, 1975 (протОтип).

9 9550 мент ИЛИ, регистр и сумматор, о т— л и ч а ю щ е е с я тем, что, с целью повышения быстродействия и надежности, в него введены вычитатель, сумматор-вычитатель, элемент И, сумматор по модулю два, триггер и одновибратор, причем группа элементов

И образует матрицу, каждый i-й столбец которой (i 1,2,...,n) состоит из и элементов И, первые входы элементов И 1-ro столбца матрицы обьединены и подключены к 1-му входу пер) вой группы входов устройства, вторые входы j-x элементов И (j=1,2,,и) каждого столбца матрицы объединены и 15 подключены к 1-му входу второй группы входов устройства, выходы элементов И каждой 3-й строки матрицы соединены с входами 1-го разряда ((=1,2,...,2п-1) сумматора, выход ко- 2в торого подключен к первому входу (3+2)-го разряда сумматора-вычитателя, первые входы первого и второго разрядов которого подключены соответственно к нулевому входу уст- 25 ройства и к выходу переноса старшего разряда сумматора, вторые входы каждого разряда сумматора-вычитателя и вход переноса младшего разряда подключены к выходу сумматора по модулю 5в два, первый и второй входы которого подключены соответственно к знаковым входам первой и второй групп входов устройства, первый выход S-го разряда (5=1,2,...,2n+1) сумматора-вычитателя соединен с первым входом S-го разряда вычитателя и информационным входом S-ãî разряда регистра, выход которого подключен к 5-му выходу группы выходов устройства, второй вход

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

S-го разряда регистра и к второму входу элемента ИЛИ, выход Ь-го разря„55 да вычитателя подключен к Ь"му входу элемента И, (S+1)- и вход которо88 . 10 го соединен с единичным выходом триггера, выход элемента И соединен с входом одновибратора, единичный вход триггера подключен к входу запуска устройства.

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

3. Устройство по п.1, о т л и ч а ю щ е е с я тем, что каждый разряд вычитателя содержит полусумматор, два сумматора по модулю два, элемент И и элемент ИЛИ, выход которого является выходом заема разря да вычитателя, вход заема которого соединен с первым входом полусумматора, выход переноса которого подклю. чен к первому входу элемента ИЛИ, второй вход которого соединен с выходом элемента И, первый вход которого подключен к выходу суммы полусумматора и к первому входу первого сумматора. по модуяю два, второй вход которого является первым входом раз» ряда вычитателя, втррой вход разряда которого соединен с вторым входом полусумматора, выход. первого сумматора по модулю два соединен с вторым входом элемента И и с первым входом второго сумматора по модулю: два, выход которого является выходом разряда вычитателя, третий вход разряда которого соединен с вторым входом второго сумматора по модулю два.

955088

Фиг.g

Фиг.2

Составитель А. Жеренов

Редактор С. Тараненко Техред g. Tenep Корректор А=. Гриценко

Заказ 6439/55 Тираж 731 Подписное

ВНИИПИ Государственного комитета СССР по делам изобретений и открытий

i13035, Москва, Ж-35, Раушская наб., д. 4/5

Филиал ППП "Патент", г. Ужгород, ул. Проектная, 4