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

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

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

Изобретениеотносится к вычислительной технике и может быть применено в спецпроцессорах или в комплексе с цифровой вычислительной машиной для оперативного вычисления скалярного произведения двух ч-мерных векторов, например, в системах автоматического управления быстропротекающими процессами, динамическими объектами, математические модели которых представляются в виде совокупности сумм парных произведений. Цель изобретения - повышение быстродействия. На чертеже приведена схема устройст)а для вычисления скалярного произведения векторов для случая, когда п А и k 3 (п - разрядность входного кода, k - количество компо нентов векторов). Устройство для вычисления скаляр ного произведения двух векторов содержит матрицы злементов И 1-4, мат рицу злементов 5 запрета, группу злементов ИЛИ 6, группу элементов И сумматор 8,.сумматор 9, вычитатель 10, группу сумматоров 11 по модулю два, злементы ИЛИ 12 и 13, входы 14 16 групп (компонентов) первого вектора, входы 17-19 групп (компонентов) второго вектора, выхода 20 реультата, выход 21 признака окончаия переходного процесса. Работа устройства для определения калярного произведения двух п -мерых векторов У иУ поясняется на римере регшизации зависимости Z - к. 21 Ч: XI , предварительно представлен-jVой в разрядной форме V. ГЗ 5 е Xj(XjXj...)Jp , Z (Z Z ... ) - разрядные векторы, представяющие собой разрядное изображение омпонент - .разрядная матрица, представляющая собой разрядноеизображеI ние yj при . Выражение (1) при п 4 и k 3 может ыть записано

или соотнетственно I Ч,У,+V2 VjX, IIг 1 74 2 « 1 г I г V.X, Y,K, + Y,Xj + jX3 + .+ , J i 3i 21 aiza а г i г ,X,t X, + YiX,+ YjX54. ,X,+ ,х, 4« 3 Si 31 7Э X,+ )(, + YjXj+ f,X,+ 4,XHYjXt lfjX, + Y,X,.t«г 3 4,X, +4iXi+YjXj+ X,+ , Для реализации параллельного контроля вычислительного процесса разрешают выражение 3 от( Z I 1 I I X, ,,xn а I 2 « X,-Z-(4,y,,f + YjXj) , Э1 га у г X,2-(Y,x, + YeXj+Y3X,4V,X,4YiXa + Y,yi 4 5,41 41 4i 33 за 37 ,4Y,X,4.YjXj- Y,X, Опе)ация определения скалярного произведения двух векторов, т.е. II а Y,X, t 5 ,, Y,X, + , 4442 4i ЭЗ 3 XX,+YjXj+Y,X, + Y,Xt+Y2 а реализация контроля вычислительного процесса осуществляется путем определения одновременно с вычислительным процессом (5) компонент х X,, X,, X, вектора х на основании зависимостей Vl®5 5-5®Р,р Зм4х, X.« ® J4®pJ.iM4, i 1 i |4.4 ) ЧЧ 4,) X,®6j , X, , 4 5в|55 с X,2®S ,, Р-5Р 5Х, ,р.О,где Ф - знак, обозначаюоцсй сложени по модулю два; р - значение заема из (Z-l)-ro разряда (,2,3,4,5) -и сравнениеих с заданными компонен тами X,, X,, X,, , вектора х,. Их равенство характеризует правильност вычисления скалярного произведения XX,+ t5 э f3 ,,X, I + 14 гэ зг VjXj Y, Y,X,+ YjX,. 33 5- 2 24- 2 -t iXi + YiX,,X, + , ЛЗ 41 Jt 34 it ,V,X, + 4,X, + iX,+YjX, 44 44 44 XX. + YzXx + носит льно X, при любом старшем У| , не равным нулю допусТИМ у , 1 . Л-I (4) i 13 4-YjXj + YjXj) К-5 II i аз 14 ч f ,+YiXj Y,;-fYjXj4-4,Xj Z-Z 25 вектора Z реализуется в соответствии с выражением (3) в виде 3 924 242 Xi44,X,tY,X,,Xj (5) и конец выполнения операции,т.е. koнeц переходного процесса в схеме. Устройство для вычисления скалярного произведения векторов работает следующим образом. На каждый из входов 14j, 15;, ,16 подаются соответственно разряды х, , х, ij компонентов х,, X а векто2 . ра X, а на входы 17, 18.;, 19t -; соответствующие разряды Y, , Yj, УЗ компонентов вектора Y. При этом значения разрядов векторов поступают на входы элементов И 1-3 матриц, в которых формируются частичные произведения вид (2). , значения разрядов Xj, X,, X,, X, поступают на входы соответствующих сумматоров 11 по модулю два, а на первый, второй и третий элементы И соответ- ственно значения Y, , Y, , Y, , Y, Y, Y| , f , Y, ,Y, . ,В том случае, когда старщий разряд , то в соответствии с выражением (3) компоненты Х,

X,, А, X, поступают на входы сумматора 9. Если У,0, Y, 0-и т.д., а Y,1, то на выходе (S-l)-ro элемента И 7 образуется единица, которая поступает на первые входы соответствующих элементов И 4 и,управляющие входы элементов 5 запрета, благодаря чему на выходе э.ементов И 18 образуются значения Х, X,, Х|, Х, которые поступают через соответствующие элементы ИЛИ 6 на входы сумматора 9. В устройстве протекает переходной процесс, по окончанию которого на выходах элементов И 1-3 сформируются по выражению (3) частичные произведения, которыесуммируются в сумматоре 8. При этом на выходах трех младших разрядов сумматора 8 по выражению (5) образуются значения трех младших разрядов Z , Z , скалярного произведения двух векторов X, Y, т.е. искомого вектора . На выходах четырех старших разрядов сумматора 8 по выражениям (4) .и (5) образуются значения S , S , S , S , поступающие на входы соот-. ветствующих разрядов сумматора 9 и

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

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

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

1 полученные в результате вычисления, и заданные значения }(, равны, то на выходе элемента ИЛИ 12 образуется сигнал, оповещакшщй, что вычисление (5) скалярного произведения

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

«,