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

 

УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ СКАЛЯРНОГО ПРОИЗВЕДЕНИЯ ДВУХ ВЕКТОРОВ , содержащее первую матрицу элементов И, первьй сумматор, второй сумматор, вычитатель, первьй эле .мент ИЛИ и группу сумматоров по модулю два, причем первые входы элементов 1 -го столбца первой матрицы (i 1,2,3,...,п) соединены с i-м входом первой группы первого вектора устройства, вторые входы элементов И i-и строки первой матрицы соединены с i -м входом первой группы второго вектора устройства, выход i -го разряда первого сумматора соединен с первым входом i-ro разряда второго сумматора,выход i -го разряда второго сумматора соединен с первым входом 4 -го разряда вычитателя, о т - ли. чающееся тем, что, с целью повышения быстродействия, в устройство введены k матриц элементов И (k- количество KONmoHeHT векторов), матрицу элементов запрета, группу элементов И и группу элементов ИЛИ, причем перпые н.чоды элементов И i-ro столбца & -и матрицы

СОЮЗ СОВЕТСНИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК (19) ((3) (51) 4 С 06 F 15/347

Р

Д;

ОПИСАНИЕ ИЗОБРЕТЕНИЯ 1 "-К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ 1 ц М 7ССЪar

ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР

ПО ДЕЛАМ. ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ (21) 3242574/24-24 (22) 28.01. 81 (46) 15. 09. 85. Бюл. У 34 (72) Г.Е.Пухов, А.И.Стасюк, M.Н.Ку лик, В.Н.Белецкий, Ф.Е.Лисник и В.С.Мазурчук (71) Институт проблем моделирования в энергетике АН УССР (53) 681.325(088.8) (56) Авторское свидетельство СССР

В 480077, кл. С 06 F 7/52, 1973.

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

У 955088, кл. С 06 F 15/347,12.01.81. (54) (57) УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ

СКАЛЯРНОГО ПРОИЗВЕДЕНИЯ ДВУХ ВЕКТОРОВ, содержащее первую матрицу элементов И, первый сумматор, второй сумматор, вычитатель, первый эле.мент ИЛИ и группу сумматоров по модулю два, причем первые входы элеI ментов (-го столбца первой матрицы

1 () =1,2,3,..., n) соединены с 1 -м входом первой группы первого вектора устройства, вторые входы элементов И

1-й строки первой матрицы соединены с i -м входом первой группы второго вектора устройства, выход q -го разряда первого сумматора соединен с

1 первым входом i-го разряда второго сумматора, выход i -го разряда второго сумматора соединен с первым вхо4 дом q -го разряда вычитателя, о т— л и ч а ю щ е е с я тем, что, с целью повышения быстродействия, в устройство введены k матриц элементов P. (k — количество компонент векторов), матрицу элементов запрета, группу элементов И и группу элементов ИЛИ, причем первые в: оды элементов И i -го столбца В -й матрицы (6=2,3, ° ° °, k ) соединены с i -м входом (;-й группы первого вектора устройства, вторые

I входы элементов ° 1 -й строки -й матрицы соединены с 1 -м входом 3 -й группы второго вектора устройства, выходы элементов i -ro столбца ()(+i)-й матрицы соединены со входом 5 --ro элемента ИЛИ группы, выход которого подключен ко второму входу 1 --го разряда второго сумматора, входы )(-го разряда первого сумматора (4=1,2, 2))-1) соединены с выходами p-х элементов И g -х строк 1-х матриц д (p=1, и; Q =1,...,)); р+ = +1) и выходами г-х элементов запрета 5-х строк (р=1, ..., n 5 =1, ..., и -1, г+ =1), первые входы элементов H 1 ;

5-й строки (k+1)-й матрицы и управляющие входы элементов запрета 6 -й строки матрицы соединены с выходом

5-ro элемента И группы входы которого. соединены со входами с первого по (6+1)-й первой группы второго вектора устройства, второй вход g --ro элемента И i -го столбца (k+1)-й матрицы и информационный вход g --го элемента запрета 1 -го столбца матрицы соединены с выходом (6+1)-ro элемента

i --ro столбца первой матрицы, выход

i-го разряда первого сумматора подключен ко второму входу 1 -го разряда вычитателя, выход которого соединен с первым входом сумматора по модулю два группы, второй вход которого соединен с входом соответствующего разряда первой группы первого вектора устройства, выходы сумматоров по модулю два группы . йодключены ко входам первого элемен11 та ИЛИ, выход которого является вы- ",, ходом признака окончания .переходного процесса устройства, выходы переполнения первого и второго сумматоров соединены со входами второго элемента ИЛИ, выход которого является выходом. первого разряда результата устройства выходы разрядов вто79369 рого сумматора являются соответственно выходами разрядов со второго по (n+1)-й результата устройства, выходы разрядов с (n+1)-ro по (2n-1)-й первЬго .сумматора являются соответственно выходами разрядов с (й+2)-го по 211-й результата устройства. ультата, выход 21 признака окончания переходного процесса.

Работа устройства для определения скалярного произведения двух п -мерных векторов,Х и Y поясняется на примере реализации зависимости X =

-к

= K, Y; Хз, предварительно представлен25 ной в разрядной Форме ° Х

jq 17 д е Х;=(ХХ;... ), Z =(Z К ...

-) — разрядные векторы, представляющие собой разрядное изображение компонент!

3 ч ч; з г

1 1 ч входного кода, k — - количество компо- И нентов векторов).

Устройство для вычисления скалярного произведения двух векторов содержит матрицы элементов И 1-4, матрицу элементов S запрета, группу элементов ИЛИ 6, группу элементов И 7, сумматор 8, .сумматор 9, вычитатель

10, группу сумматоров 11 по модулю два, элементы ИЛИ 12 и 13, входы 14.16 групп (компонентов) первого вектора, входы 17-19 групп (компонен.тов) второго вектора, выхода 20 ре1 I I <,Х, + Тгхг

2 г 2 ° 2

Y,Х,iY,Õ, + Y Х +»2

Ъ 1 г 2 з Ъ 3 1 2 г з Ъ

11,Х, 4 YiХ,4 Ysxs + 12Х + 12Х2+ Y2) z гг гг 14 41 Зг .2Ъ

Y,х,+ У,Х, + 1x, + У, х, + Y2x i Тгхг v2 хг

4 г 3 г 2 1 4 2 з З (,Х 4 (е М (сХ, + 12Х2+ 12К2

4З Ъ4 ь

Y,Х,4 Y,Х,+ У2Х2

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

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

На чертеже приведена. схема уст1 ройстка для вычисления скалярного произведения векторов для случая, когда 11 =4 и k =3 (n — разрядность

Выражение (1) при п =4 быть записано

1 1 гТ М

3 ъ з

Ззггз2 1 1ъх ъ+ Y3xll 4 v X ъ

1 1 4 1 3 2 2 З 1 4 гx2+ 4x2 Y " з х "з Y " з

2 4 . 4 2 3 З 2 4

+ 2Х2+ ЗХЗ+ ЗХз+ 3 "з г 4 4 З З 4

+ Y2Х2+ з" з з" з г 4 4 4

Ч2Х + з з разрядная матрица, представляющая собой разрядное изображение у при п--3. и k =3 может

4 z

7

4 z z

6 z т

7,, 2

1179369 или соответственно

1 1 1 ! 32 2 13 3

2 1 2 1 2

"1X1+ У1М!+ (Х,+ YЗХЗ Ф

Ъ 21 31 31 (,Х,+ Ч,X,+,Х,+ Y,Х,4

4 4 1 4 1

"!X,+ <<Х1+ У2Хг+ >3 "3+

3

"4

z

Е к

1 ж ЭХЭ

2 2 2

1,Х, Х +!,Х +

Зг э 1 э г гэ

YX41<,X iYX +Y,X +

2 4 г 4 1 Э Э

1 1 Y2"2+Y3õзtYIХ1

+ Э r,x,+

1 3

Y,х, чх, 2 Э 2 Ъ

2 2 ЭХЗ

3 3 3

Y,Х,+ !,Хз 4

4 3 4 3

«1Х14YЗХЗ4 (3) 1

+УХ+УХ, г 4 2 4 2 4 <1Х1+ 2Х,+ <ЗХЭ

Ъ 4 3 4 Э

Yi X1+ Y2X2 4Y3X 3

4 4 4 4 4 4 !

1Х1+ <1Х14 УЗХ 3

Для реализации параллельного 15 носительно Х

I контроля вычислительного процес- шем у!, не са разрешают выражение 3 от- тим у = 1

2 3 г 1 2 2 1 1 2 1 г

М1 (т1Х1+ 2Х2 ЗХ 3 Г2Х2 3Х 3 )

3 - 3 1 3 1 3 1 2 1 2 2 2 2 1 3 1 3

Х, 2-(<<Х1+У2Х2423Х34 <1Х14 !2Х24 !2Х1+ «2Х2+ <ЗХ з)

4 5 4 ° 1 I 4 1 3 1 3 г 3 2 2 э г l 2 3 при любом старравным нулю допусг 1

7-5

3 Ъ (4) 4 4

Z-5

< 4 4

34Y2Хz+Y3>3) 7;

Операция определения скалярного произведения двух векторов, т.е.

1 1

YtXi Ф Ь

1 1

Ч,х,+ 5

3 4

Ч<Х! + ! 4 5 (1М, <4г 4г 33 33

$,Х,+ 1 Х + Y3Х 3+ 1,Х1+ < 2Х (5) В 3 2 4 2 4 .2 4

4 13ХЗ+ Y) «

<онец переходного процесса в схеме.

Устройство для вычисления с«малярного произведения векторов работает й!О следующим образом.

На каждый из входов 14;, 15;,,16

I цодаются соответственно разряды х,, 1 ч х, х компонентов х,, х, хз вектора Х, а на входы 17„, 18,;, 19! соответствующие разряды У» 92, Y 3 компонентов вектора Y. При этом значения разрядов векторов поступают на входы элементов И 1-3 матриц, в ко.торых формируются частичные произве.дения виду (2). KqoMe того, значения разРядов Х, N Х,, Х, поступают на входы соответствующих сумматоров

ii по модулю два, а на первый, второй и третий элемреты И 7 — cooTH

2 < 2

55

У1, Фз, Y .Y! .,В том случае, когда старший разряд 7! =1, то в соответствии с выражением (3) компоненты Х1, I 2 г< г, г г 1 г й X,

31 3 3 З г 33

x,. g «-«s « э 50+ Р, Р - < р

3 4 41 41 4 .4. 3 44

Х1=2 Эб, б и69 P «P 5Ð ч

S 51 5 5 5 4 5 5

X и3®Ь «6=5® P P 5P ч г! ч з, <

v<2 Х, 413 б Х1

5 4

SХ Р ОЗ (6) а реализация контроля вычислительного процесса осуществляется путем определения одновременно с вычислиГ тельным процессом (5) компонент х, °

3 4 х1, х,, х, вектора х на основании зависимостей где ® — знак, обозначающий сложение

2 по модулю два; — значение заема из (2-1)-го разряда (2=1,2,3,4,5)— и сравнение их с задайными компонен1 2 3 тами х,, х,, х,, х, вектора х<е Их равенство характеризует правильность вычисления скалярного произведения

55 вектора Z реализуется в соответствии с выражением (3;« в виде

Г

1179369

k, Х поступают на входы сумма° ° ора 9. Если Y О, 7 0 и т.д., а =1, то на выходе (S-1)-го элемента И 7 образуется единица, которая поступает на первые входы соответствуницих элементов И 4 и,управляющие входы элементов 5 запрета, благодаря чему на выходе элементов И 18 образуются значения Х, 1,, 1, g которые поступают через соответствующие элементы ИЛИ 6 на входы сумматора 9. В устройстве протекает переходной процесс, по окончанию которого на выходах элементов И 1-3 сформируются по выражению (3) частичные произведения, которые суммируются в сумматоре 8. При этом на выходах трех младших разрядов сумматора 8 по выражению (5) образуются значения трех мпадших разрядов Й

Z, скалярного произведения двух векторов Х, Y т.е. искомого вектора

1 . На выходах четырех старших раэрчдов сумматора 8 по выражениям (4) .и (5) образуются значения ь

S 1, поступающие на входы соот-. ветствующих разрядов сумматора 9 и входы соответствующих разрядов вычитателя 10. На выходах сумматора 9 по выражению 5) образуются значе-„ ния Z,2,2, искомого вектора Z поступающие на входы соответствующих разрядов вычитателя 10. На выходе элемента ИЛИ 13 образуется значение старшего разряда,й. Далее по вы10 ражению (6) на выходах вычитателя

0 образуются значения компонентов ,М,Х,,2,, вычисленных в процессе решения, которые поступают на входы соответствующих сумматоров 11 по

1 модулю два, в которых они поразрядно сравниваются с исходньии значениями 1,,1,,Х,,2,, а результат сравнения поступает на соответствующий вход элемента ИЛИ 12. Если .значения

20 Й„ полученные в результате вычисления, и заданные значения Х равны, то на выходе элемента ИЛИ 12 образу- ется сигнал, оповещающий, что вычисление (5) скалярного произведения

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

1179369

Составитель В. Березкин .Редактор И.Ковальчук Техред Т.Аанта Корректор М.Самборская

Заказ 5678/52 Тираж 710 Подписное

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

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

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