Устройство для вычисления суммы квадратов К @ -разрядных чисел Советский патент 1983 года по МПК G06F7/544 

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

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

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

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

задержки .

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

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

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

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

25

(где ,2,...,п-1) содержит 1 групп элементов И и сдвинут относительно

(1-1)-гно элемента И на один разряд вниз, (2J -1)-е информационные входы

( 1,2,..,К) групп элементов И 30 i-ro столбца матрицы объединены .и подключены к (1+1)-му разряду j-и входной информационной шины, к i-му разряду которой подключены 2 j-е информационные входы i-й группы эле|ментов И всех столбцов, информационные выходы групп элементов И каждой S-й (где S-1,2,..., 2п-3) строки мат рицы соединены с информационным входом (S+l)-ro разряда, сумматора, ид формационный- выход каждого 2 i-ro разряда сумматора подключен к первым информационным входам i-го полусумма тора и i-го одноразрядного вычитателя второй информационный вход i-fo одноразрядного вычитателя подключен к информационному выходу i-го полусумматора и соответствукицего 2 i-му разряду информационной выходной шины информационный выход i-го одноразрядного вычитателя соединен с первым информационным входом i-ro разряда схемы сравнения, второй вход которой подключен к второму информа ционному входу i-ro полусумматора и i-му разряду первой информационной входной шины,.информационный выход каждого (2 i-l)-ro разряда (где , 3,.,.,п-1) сумматора соединен с входом (2 1-1)-го разряда информационно выходной шины, старший разряд которой соединен с информационным выходо элемента ИЛИ, к первому и второму информационным входам которого подключены выходы.переносов соответственно сумматора и полусумматора предьвдущего разряда, выход переноса каж дого (i+1) -го полусумматора соединен с входом nepieHoca сумматора последующего разряда, а выходы (i4-l) -X разрядов каждой (j +1)-Й входной информационной шины подключены к информационному входу 2 i-го разряда сумматора, информационный выход схемы сравнения соединен с управляющим .выходом устройства. Причем каждая группа элементов И содержит К двухвходовых элемен хов И, причем первый информационный вход каждого элемента И (где j«l,2.. К) соединен с (2J -1)-ым информацион ным входом группы элементов И, второй информационный вход j -го элемен та И соединен с 2j-ым информсщионным входом группы элементов И. Кроме того, схема сравнения содержит :п сумматоров по модулю два й элемент... ИЛИ, причем первый инф6 рмациоиный вход 1-го сумматора по модулю два соединен с первым выходом i-fo разряда схемы сравнения, второй информационный вход i-ro сумматора по модулю два соединен с вторым выходом L-ro разряда схемы сравнения, информационные.выходы сумматоров по модулю два соединены с соответствующими входами элемента ИЛИ, информационный выход которог соединен с информационным выходом схеУ мы сравнения. На фиг. 1 представлена схема устройства для вычисления суммы квадратов К-п-разрядных ; чисел для случая, когда информация представлена пятью двоичными разрядами (), а количество чисел равно трем (КяЗ)/ н.а фиг. 2 - схема группы элементов И. Устройство содержит матрицу. 1, сумматор 2, схему 3 сравнения, элемент ИЛИ 4,полусумматоры Ь,одноразряд7 ные вычитатели о,К входных шинТ (где j 1, 2 ,.., к), выходную шину 8. ( где i 1, 2 ... п 1,2;.. 2 п) и управляющий выход 9 (регистрации конца переходного процесса в устройстве). Матрица 1 выполнена из групп элементов И ХО причем каждый i-й столбец (где ,2,..., п-1) содержит irpynn элементов И 10 ,и сдвинут относительно (i-l)-ro на ;о5ин разряд вниз. Сумматор 2 выполнен из (2п-1) последовательно соединенных одноразрядных сумматоров. Схема сравнения 3 выполнена из п сумматоров 11 по модулю два 12 и элемента ИЛИ 4, .. причем выход каждого i-ro сумматора, по модулю два 12 подключен к i-му входу элемента ИЛИ 4, выход. которого , соединен с выходом 9 регистрации конца переходного процесса в устройстве. Каждая группа элементов И 10 матрицы 1 содержит К двухвходовых элементов И 13, причем первый вход каждого -го элемента И 13 ( j Л.,2...,кУ является С2 -1) -ым входом группы элементов И 10 матрицы 1 и групп элементов И. Второй вход JI-го элемента И 13 группы элементов И 10 матрицы 1 из- элементов И является 2 -ым .ом группы элементов И 10. Все (2/f -10-ые входы групп . элементов И 10 каждого i-ro столбца матрицы 1 из элементов И объединены и подключены к выходу .(i+1)-го разряда -ой входной шины 7, к выходу i-ro разряда которой подключены 2j -е входы i-ой группы элементов И 10 всех столбцов матрицы 1 из элементов И. Выходы групп элементов И 10 каждой (где Sel,2,. ..,2п-3)строки м&трицы 1 из элементов И соединены совходом одноразрядного сумматора 11(S+1)-го разряда сумматора 2, выход каждого 2 i-ro разряда которого подключен к первому входу i-ro полусумматора 5 и одноразрядного вычитателя б, подключенного своим вторым входом к выходу i-ro полусумматора 5 и соответсхвуЛщему 2 i-му раэря-, ду выходной шины 8, а выходом - к первому входу сумматора по модулю два 12 i-rd разряда схемы 3 сравнения. Второй вход сумматора по модулю два 12i-ro разряда схемы 3 сравнения /подключен ко второму входу i-ro полусумматора 5 и i-м: р.аэряду первой входной шины , (Kel) . Выход одноразрядного сумматора 11 (21-1) -го разрядного сумматфа (.где 1т2,3,.., п-1) соединен со входом (21-1)-го разряда выходной шины 8,вход старшеГго разряда .которой соединен с выходом 5 РЯ элемента ИЛИ 4,к входам которого подключены выходы переносов одноразрядного сумматора 11, сумматора 2 и полусумматора .5 предыдущего разряда. Выход переноса каждого (l-t-l)-ro is1f2f...л п-1) полусумматора 5 соединен с входом Одноразрядного сумматора 11, .cyiwiMaTopa 2 .последующего разряда. .Шисоды (1ч-1}-ых разрядюв каждой (3.+1)гой входной-шины Т, то есть 7, ..., (±sl,2, . . .,п-1) .подключены к взсоду 2 1-го разряда (Сумматора 2. Выход схема 3 сргшнения подключен к выходу 9 регистрации конца переходного процесса в устройстве, а каждьЛ) одноразрядный вычит тель 6 выполнен в виде сумматора по модулю два. Работу устройства для вычисления суммы квадратов К п-раэрядных чйоел

Vi.4

ГУ

JllllL

t

Mi

} .Д.

X

iN

,L

i

Н/)и соответственно

N V

4 Я. 4 i 5 4 4. 4 A

Xa.X X ХгХа.+ ,

1

Выражение (3) положено в основу алгоритма параллельного функционирования предлагаемого устройства. . по же пр ра бо 25 ме

VtaX,

,

X

4bL

Лаг

s 344

4. г 44. ,

Xi X a.X X X

i 1

x yx A

u

Л

,

XatXi.

A

,

ъ А+Х43 а,,

ii + L

Для увеличения надеяяости вычисления в устройстве путем реализации парал65 лельного контроля вычислительного ним на примере реализации «ырая к - к варительно представленного в раэОЙ форме в виде Д ядные векторы, представляюище соразрядное изображение Xj, У ; - разрядная матрица, представляющая собой разрядное из обраикение Х1ФИ п-3. фажение (1) 6 развернутой форри и предстё1вляется в виде.

процесса (т.е. осуществления параллельной проверки-правильности.выполнения операции) и увеличения производительности путем фиксации момента конца выполнения операции суммы квадратов К п-разрядных чисел (Тае. переходного процесса в схеме) разрешаем выражение (З)ртносительно значений Х вектора X,

( ,4 Х,

Э feJ Ь 4. ay

X , ,,+ X,,X,+Xj,X5tX,V Vjf X)8-S

),-§-(,,4t, + ).§4

,(.,, C4)

§,

S,

значения соотгде

ветствующих булевых сумм в выражении (4) с учетом значений переноса из |младших разрядов в старшие. В соответствии с выражением (4) выражение (3) может быть записано I Таким образом, реализовав вырс1жение (5), получаем сумму квадратов. К п-разрядных чисел, а реализовав выраже1 е вида

г 1

i

ses

1 4 4

X, -- ©S

566

Xi-ves

(6;

489 Х,-.5©5

5 X, V©S

- знак,обозначающий сложение

где по модулю два -получаем век тор Х (обозначим его Х,, вьгаисленный), сравнивая который с зещанным вектором if , определяем правильность выполнения операции, а в момент их равенства фиксируется момент ее окончания (т.е.момент конца переходного процесса в схеме. При этом значения разрядов У,У,У.У,У и разрядов Б ,Й,S S, s определяются в процессе вычисления суммы квадратов К чи сел, а определение соответствии с (6) (т.е. контроль вычислительного процесса) реализуется параллельно с вычислителем вектора У по выражению (5) .

Работа устройства осуществляется следующим образом.

На первую, вторую и третью входные

шины 7J

7, (,2,...,п устройства, фиг. 1) подаются соответственно значения первого разрядного вектора t .

jd X.

i

второго

третьего

значения

..tсоответствующих разрядов Xj которых поступают на входы групп элементов И 10 матрицы 1 из групп элементов И.

При этом з|1ачения разрядов первого вектора 3f поступают параллельно на вторые входы сумматоров по модулю два 12 схемы 3 сравнения соответствующих ±-х разрядов и на

25 вторые входы полусумматоров 5 также соответствующих i-x разрядов. После окончания переходного процесса в устройстве на выходах каждой строки групп элементов И 10 матрицы 1

0 из элементов И образуются в соответствии с выражением (3) частичные произведения, которые суммируются соответствующим одноразрядным суммато-i ром 11 сумматора 2.После суммирования

5 на выходах второго,четвертого,шестого, восьмого и десятого разрядов сумматора 2 образуются по вьгражению (4 и 5 соответственно значения S,S sfsfs / поступающие на первые входы соответ0 ствующих разрядов полусумматоров 5 и первые входы соответствующих одноразряднызРвычитателей б. На выходах полусумматоров 5 по выражению (J образуются значения разрядов У, У, У,

5 УГ У искомого вектора У, поступающие соответственно на вторые входы одно- разрядных вычитателей 6,в которых по ;выражению (ь) реализуется вычисление соответственно разрядов Х,50), Х

ел первого вектора ,и поступают на первые входы соответствуняцих разрядов схемы 3 сравнения. В схеме 3 сравнения реализуется сравнение заданного вектора 3 с вычисленным в процессе решения вектора Х(поступающего с выходов однозарядных вычитателей 6).Если векторы равны,то сумма квадратов К п-разрядных чисел выполнена правиль но и на выходе элемента ИЛИ 4 схемы 3 сравнения и,соответственно,выходе 9 О регистрации конца переходного процес;са в устройстве вырабатывается сигнал, оповещающий,что операция выполнена правильно и переходной процессов схеме закончен,а с выходной шины 8 можно

5 считывать искомый вектор У и на входн ные шины .можно подавать следующие К чисел. Эффективность изобретения заключ ется в существенном увеличении быст родействия, определяемого временем переходного процесса в схеме, ибо устройство является параллельным (комбинационным) и вычисления суммы квадратов К п-раз рядных чисел реализуется в нем практически за один такт. Кроме того, в устройстве суcift cTBeHHO увеличивается производительность благодаря тому, что на вы ходе схемы 3 .сравнения в фабатывает ся сигнал конца переходного процесса в схеме и устройство может сразу же запускаться на следующий цикл работы. В противном случае (если бы такой сигисш не вырабатывался) устройство будет находиться в режиме ожидания, пока йе закончится такт его работы,после чего оно запу кается на следующий цикл работы, а поскольку длительность переходного процесса при подаче на вход устройства различных комбинаций К чисел. различна, то при этом достаточно мн го времени устройство простаивает. В устройстве существенно повышается также надежность вычислений благода ря тому, нем параллельно с вычислительным процессом осуществля ется контроль правильности.его выполнения. Формула изобретения 1. Устройство для вычисления сум мы квадратов К п-разрядных чисел, содержащее группу элолентов И и эле мент ИЛИ, отличающее с я /тем, что, sC целью увеличения быстрощействйя и надежности вычислений, ОНО содержит зтруппы элементов И, схему сравнения, сумматор, полусумматор и одноразрядные вычитатели, причем группы элементов И образуют матрицу, каждый i-й столбец которой (где ,2,...,п-1) содержит 1 /групп элементов И и сдвинут относительно (1-1)-го элемента И на один разряд вниз, (2 -1)-ые информацион ные входы (где el,2,...,ic) групп элементов И i-ro . столбца матрицы об динены и подключены к (i-fl) разряду j-и входной ннформгшионной шины, к.1-му разряду которой подключе ны 2 -е информационные входы i-й группы элементов И всех столбцов, и формационные выходы групп элементов И каждой S-й (где Ssl,2,.. 2п-3) строки матрицы соединены с информационным входом (S+l)-ro разряда сумматора, информационный выход каждого 2 1-го .яда сумматора .подключен к первым информационным. входам i-ro полусумматора и i-ro одноразрядного вычитателя, второй информационный вход i-ro одноразрядного вычитателя подключен к информационному выходу i-ro полусумматора и соответствующего 2 1-му разряду информационной выходной шины, информационный выход 1-го одноразрядного вычитателя соединен с первым информационным входом i-ro разряда схемы сравнения, второй вход которой подключен 1C второму информационному входу i-ro полусумматора и i-му разряду первой информационной входной шины, информационный выход каждого (2 i-1) разряда ( где ,3,...п-1) сумматора соединен с входом (2i-l)го разряда информационной выходной шины,, старший разряд которой соединен с информационным выходом элемента ИЛИ, к первому и второму информационным входам которого подключены выходы переносов соответственно сумматора и полусумматора предыдущего разряда,выход переноса каждого (i+1)го полусумматора соединен с входом пе.реноса сумматора последующего разряда, а выходы (i+l)-x разрядов каждой ( j +1)-й входной информационной шины подключены к информационному входу 2 i-ro разряда сумматора,информационный выход сравнения соединен с управляющим выходом устройства. 2.Устройство по п. 1, о т л ичающееся тем, что каждая группа элементов И содержит К двухвходовых элементов И, причем первый информационный вход каждого j -го элемента И (где j 1,2,...,К) соединен с (2J -1)-ым информационным входом . группы элементов И, второй информационный вход j-ro элемента И соединен с 2 j -ым информационным входом-группы элементов И. 3.Устройство по п. 1, отличающееся тем, что схема сравнения содержит п сумматоров по модулю два и элемент ИЛИ, причем первый рнформационньй вход 1-го сумматора по модулю два соединен с первым вы;ходом i-ro разряда схемы сравнения, второй информационный вход i-ro супинатора по модулю два соединен с вторым выходом 1-го разряда схемы сравнения, информационные выходы сумматоров по модулю два соединены с соответствующими входами элементаИЛИ, информационный выход которого соединен с выходом схемы сравнения. Источники информации, принятые во внимание при экспертизе , 1. Авторское свидетельство СССР .В 717765, кл. G Об F7/50, 1980. 2. Авторское свидетельство СССР 717759, кл. G Об F 7/38,1980 . , (прототип).