Устройство для умножения @ -разрядных чисел

 

УСТРОЙСТВО ДЛЯ УГ ОЖЕНИЯ . п-РАЗРЯДНЫХ ЧИСЕЛ, содержащее п -разрядный регистр множимого и п-разрядный регистр множителя, (и-2)-разрядный регистр утроенного множимого, 2л -разрядный накапливающий сумматор , первую группу из 2п -4 элементов ИЛИ, вторую группу из П/2 элементов ИЛИ, первую группу из п/2 эле ментов И, группу п/2 дешифраторов и Ih+2 коммутаторов, причем первые, вторые и третьи информационные входы коммутаторов соединены соответственно с разрядными выходами г -раз- . рядного регистра множимого и п+2 разрядного регистра утроенного множимого; , выходы

„„SU„„1111153

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

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

РЕСПУБЛИК

8 11 G. 06 F 7/52 I д;"Ф 11

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

И АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

И

1 C.k

4@в,1@,„;,- . Ф

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 3521151 /18-24 (22) 13.12.82 (46) 30.08.84. Бюл. ¹ 32 (72) Л.Г.Лопато и А.А.Шостак (71) Минский радиотехнический инсти" тут (53).681.325(088.8) (56) 1. Авторское свидетельство СССР № 482740, кл. G 06 F 7/52, 1973.

2. Авторское. свидетельство СССР № 993255, кл. G 06 F 7/52, 1981.

3. Авторское свидетельство СССР № 1022155, кл. G 06 F 7/52, 1981 (прототип). (54)(57) УСТРОЙСТВО ДЛЯ УМНОЖЕНИЯ. г1-РАЗРЯДНЫХ ЧИСЕЛ, содержащее п -разрядный регистр множимого и и-разряд ный регистр множителя,(и+21-разрядный регистр утроенного множимого, 2h -разрядный накапливающий сумматор, первую группу из 2 -4 элемен- тов ИЛИ, вторую группу из и /2 элементов ИЛИ, первую группу из п /2 элементов И, группу n/2 дешифраторов и (h +2 1коммутаторов, причем первые, вторые и третьи информационные входы коммутаторов соединены соответственно с разрядными выходами и-разрядного регистра множимого и n+2— разрядного регистра утроенного множимого, выходы (2и †.41элементов

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

l группу из и /2 элементов И, первый и второй элементы ИЛИ, элемент КЛИНЕ, причем выходы коммутаторов соединены соответственно с первыми входами элементов И столбцов матри" цы, вторые входы элементов И первой строки матрицы соединены с прямым выходом первого элемента ИЛИ второй группы, вторые входы элементов И второй и третьей строк матрицы соединены с выходами соответственно первого и вторрго элементов И блока выделения младшего значащего разряда, входы к -го элемента ИЛИ первой группы соединены с выходами (к+2 - 2 (i — 1)-х элементов И j-õ строк матрицы, выходы первого, второго элементов И первой строки матрицы и (и+11 -го и (и + 2) - r o элементов И последней строки матрицы соединены соответственно с первым, вторым,(2и — 1)-м и 2и -м разрядными входами накапливающего сумматора, первые выходы и/2 дешифраторов соединены соответственно с первыми входами элементов И первой группы, вторые выходы дешифраторов соединены соответственно с первыми входами элемен111115 З тов И второй группы, вторые входы элементов И первой и второй групп соединены соответственно с lIpRMbIM выходом первого элемента ИЛИ второй группы и выходами первого и второго элементов И блока выделения младшего значащего Разряда и с входами установки в ноль 6/2 пар разрядов б"разрядного регистра множителя, выходы элементов И первой группы соединены с входами первого элемента

ИЛИ, выходы элементов И второй группы соединены с входами второго элемента

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

Известно устройство для умножения и-разрядных чисел, содержащее и-разрядные регистры множимого и множителя, 2 и -разрядный накапливающий сумматор, матрицу иэ n ýëåìåíòîâ И, (2n -3) -разрядный блок элементов ИЛИ и два 6 -разрядных блока элементов.

И. Умножение двух чисел в этом устройстве выполняется в среднем за .и/2 тактов 1 .

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

Известно также устройство для умножения и - разрядных чисел, содержащее -разрядные регистры множимого и множителя, 2 -разрядный накаппрямые выходы второго и третьего элементов ИЛИ второй группы соедине. ны соответственно с первыми входами первого и второго элементов И блока выделения младшего значащего разряда, вторые входы первого и второго элементов И и первый вход третьего элемента И блока выделения младшего значащего; разряда соединены с инверсным выходом первого элемента ИЛИ второй группы, инверсный. выход втоI рого элемента ИЛИ второй группы соединен с третьим входом второго элемента И и вторым входом третьего элеМента И блока выделения младшего значащего: разряда, третий вход третьего:элемента И которого соединен с инверсным выходом третьего элемента ИЛИ второй группы, выход третьего элемента И блока выделения младшего значащего разряда соединен с выходом окончания умножения устройства. ливающий и п-ðàçðëäíûé комбинационный сумматоры, матрицу из элементов И, (2и -3 — разрядный блок элементов ИЛИ и A -разрядный блок элементов И. В этом устройстве умножение двух чисел также производится в среднем за и /2 тактов С21 .

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

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

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

ИЛИ второго блока и с первым и вторым входами соответствующего дешифратора блока, вход разрешения записи регистра множителя соединен с управляющим входом накапливающего сумматора и с шиной синхронизации ,устройства. Умножение двух чисел выполняется.в среднем за 3n/8 тактов 13.> .

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

Цель изобретения — сокращение аппаратурных затрат при реализации

l устройства.

Поставленная цель достигается тем, что в устройство для умножения

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

ИЛИ,вторую группу из >>/2 элементов ИЛИ, первую группу из И/2 элементов

И, группу р/2 дешифраторов и (n+2) коммутаторов, причем первые, вторые и третьи информационные входы коммутаторов соединены соответственно с разрядными выходами и -разрядного регистра множимого и (n+2) -разрядного регистра утроенного множимого, выходы (2п-4)элементов ИЛИ первой группы соединены соответственно с разрядными входами с третьего по(2и -2)-й

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

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

1О

55 вторые входы первого и второго элементов И и первь>й вход третьего элемента И блока выделения младшего значащего разряда соединены с инверсным выходом первого элемента

50 первый и второй элементы HJIH, элемен ИЛИ-НЕ, причем выходы коммутаторов соединены соответственно с первыми входами элементов И столбцов матрицы, вторые входы элементов И группы соединены с выходами (к+2 -2

- -1-х элементов И t -х строк матрицы, выходы первого, второго элементов

И первой строки матрицы и (n+I) — го и (>ъ +2)-го элементов И последней строки матрицы соединены соответственно с первым, вторым, (2n-1) -м и 2и -м разрядными входами накапливающего сумматора, первые выходы и/2 дешифраторов соединены соответственно с первыми входами элементов

И первой группы, вторые выходы дешифраторов соединены соответственно с первыми входами элементов И второй группы, вторые входы элементов И первой и второй групп соединены соответственно с прямым вь>ходом первого элемента ИЛИ второй .группы и выходами первого и второго элементов

И блока выделения младшего значащего разряда и с входами установки в ноль »/2 пар разрядов и -разрядного регистра множителя, выходы элементов

И первой группы соединены с входами. первого элемента ИЛИ, выходы элементов И второй группы соединены с входами второго элемента ИЛИ, выход первого элемента ИЛИ соединен с первым входом элемента ИЛИ-НЕ и с первыми управляющими входами коммутаторов, выход второго элемента ИЛИ соединен с вторым входом элемента

ИЛИ-НЕ и с вторыми управляющими входами коммутаторов, выход элемента ИЛИ-НЕ соединен с третьими управляющими входами коммутаторов, прямые выходы второго и третьего элементов

ИЛИ второй группы соединены соответственно с первыми входами первого и второго элементов И блока выделения младшего значащего разряда

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

45

На фнг. 1 приведена структурная 15 схема устройства для умножения fl— разрядных чисел для случая vi =6; на фиг. 2 — функциональная схема . блока выделения младшего значащего разряда; на фиг. 3 — функциональная 20 схема коммутатора. устройство содержит 6-разрядный регистр 1 множимого, 6-разрядный регистр 2 множителя, 8-разрядный регистр 3 утроенного множимого, 25 12-разрядный накапливающий сумматор

4, первую группу 5 из восьми элементов ИЛИ 6, вторую группу 7 из трех элементов ИЛИ 8„-8> группу 9 из восьми коммутаторов 10, матрицу 11 30 из 24 элементов И 12, группу 13 из трех дешифраторов !4, — 14, первую

3-разрядную группу 15 элементов И, вторую 3-разрядную группу 16 элемен- . тов И, первый элемент ИЛИ 17, второй элемент ИЛИ 18, элемент ИЛИ-HE 19, блок 20 выделения младшего значащего разряда, выход 21 индикации окон.чания операции умножения и шину 22 синхронизации, причем первые инфор- 40 мационные входы первых шести коммутаторов 10 группы 9 соединены с соответствующими разрядными выходами регистра 1 множимого, вторые информационные входы коммутаторов 10 с второго по седьмой соединены соответственно с разрядными выходами регистра 1 множимого, третьи информационные входы коммутаторов 10 с первого по восьмой группы 9 соединены соответственно с разрядными выходами регистра 3 утроенного множимого, управляющие входы коммутаторов

10 группы 9 соединены с ее шиной управления, выходы коммутаторов 10 . соединены соответственно с первой

Я группой входов матрицы 11 элементов

И 12, выходы (3-101 -го разрядов кото- рой соединены соответственно с входами элементов ИЛИ 6 группы 5, выходы 1,2,11 и 12-ro разрядов матрицы ll элементов И 12 соединены соответственно с 1,2,11 и 12-м разрядными входами накапливающего суммато" ра, 4, выходы каждой из трех пар разрядов регистра 2 множителя соединены с первым и вторым входами соответствующего элемента ИЛИ 84 -8 группы 7 и с первым и вторым входами соответствующего. дешифратора 14@-14

) первые выходы дешифраторов 14 - 14> соединены соответственно с первыми входами элементов И 15, вторые выходы дешифраторов 14» — 14Зсоедине-, ны соответственно с первыми входами элеменгов И 16 выходы элементов И

15 соединены с входами первого элемента ИЛИ 17, выходы элементов И

16 соединены с входами второго элемента ИЛИ 18, выход первого элемента

ИЛИ 17 соединен с первым входом эле-. мента ИЛИ-НЕ 19 и с первым входом шины управления группы 9 коммутаторов 10, выход второго элемента ИЛИ .

18 соединен с вторым входом элемента

ИЛИ-НЕ 19 и с вторым входом шины управления группы 9 коммутаторов 10 выход элемента ИЛИ-НЕ 19 соединен с третьим входом шины управления группы

9 коммутаторов 10, прямые выходы элементов ИЛИ 8„-8 соединены соответственно с первой группой входов блока 20 выделения младшего значащего разряда, вторая группа входов кото" рого соединена соответственно с ин-. версными выходами элементов ИЛИ 8 —

8, выходы блока 20 выделения младшего значащего разряда соединены соответственно с второй группой входов матрицы 11 элементов И 12, с входами установки в ноль трех пар разрядов регистра 2 множителя и с вторыми входами элементов И 15 и 16, выход II блока 20 выделения младше+ го значащего разряда является выходом 21 индикации окончания опера-. ции умножения, вход разрешения записи регистра 2 множителя соединен с управляющим входом накапливающего сумматора 4 и с шиной 22 синхронизации устройства.

Блок 20 выделения младщего значащего . разряда предназначен для последовательного выделения единиц из

3-разрядного двоичного кода А= а» а, а„, начиная с его млад— ших разрядов, и сформированного

1111153

Ьа прямых выходах элементов ИЛИ

8 -Q(specb и далее возрастание индексов при буквенных обозначениях принято в направлении старших разря" дов) . Блок 20 содержит(фиг. 2) три элемента И 23 — 23 и функционирует в соответствии со следующими логическими выражениями:

14 = a„, П =С1„Д,, Il>=Сi„с а, Il =0„01Ð где "< 1) П вЂ” признаки вьщеления соответственно первого, второго и третьего значащих: разрядов двоичного кода .4; ! 4П вЂ” признак окончания вьщеления значащих Разря дов кода . Этот вариант построения блока 20 выделения . младшего значащего разряда обладает исключительно..высоким быстродействием, особенно при малых значениях разрядности обрабатываемой информации. При больших же значениях из-за ограниченных возможностей логических элементов целесообразно в блоке 20 использовать принцип разбиения его на группы с последо-. вательной либо параллельной передачей между группами признаков Г1» окончания выделения значащих разрядов в группах. Это позволяет при существующей элементной базе обеспечить

s большинстве практических случаев время вьщеления значащего разряда, не превышающее величину (2-3/7) где " задержка сигнала на одном логическом элементе.

Коммутатор ь -го разряда группы

9 содержит(фиг; 3)три элемента И

244- 24 и элемент ИЛИ 25, причем первые входы элементов И 24 — 245

1 являются соответственно первым, вторым и третьим информационными входами 1,-го коммутатора(на первый информационный вход подается значение i -го разряда регистра 1 множимого Х, на второй информационный вход — значение (i-1)-ro разряда регистра 1 множимого х, т.е. 1, -ый разряд удвоенного множимого 2 Х,на третий информационный вход поступает значение ъ-го разряда регистра 3 утроенного множимого 3 х), вторые управляющие входы элементов И

24. - 245 соединены соответственно с первым 26, вторым 26 и третьим 26

5 выходами шины управления группы 9 коммутаторов 10 (первый выход 261 шины управления является выходом первого элемента ИЛИ 17, второй выход 26 шины управления — выходом

5 второго элемента ИЛИ 18, а третий выход 26 шины управления — выходом элемента ИЛИ-НЕ 19).

Таким образом, если сигнал логической единицы образуется на выходе первого элемента ИЛИ 17, то группа

9 коммутаторов 10 передает соответствующим образом на первую группу входов матрицы II элементов И 12 одинарное множимое 1, если сигнал логической единицы образуется на выходе второго элемента ИЛИ 18 — удво( енное множимое 2 X,если сигнал логической единицы формируется на выходе элемента ИЛИ-НЕ 19, то группа 9

20 коммутаторов 10 подает соответствующим образом на первую группу входов матрицы ll элементов И 12 утроенное множимое 3- х(сигнал логической единицы может образоваться только на

25 одном из выходов элементов ИЛИ 17 и 18 и элемента ИЛИ-НЕ 19, т.е. либо только на выходе первого элемента

ИЛИ 17, либо только.на выходе второго элемента ИЛИ 18, или же только на выходе элемента ИЛИ-HE 19 ).

Каждый иэ дешифраторов 14 - !4з может быть реализован с использованием двух двухвходовых элементов И, причем сигнал логической единицы формируется на его первом выходе тогда, когда значение соответствующей пары разрядов регистра 2 множителя равно единице, и на его втором выходе тог да, когда значение соответствующей

4 пары разрядов регистра 2 множителя равно двум.

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

В исходном состоянии в регистрах

45 1 и 2 хранятся без знаков 6-разрядные соответственно множимое Х и множитель у, в регистре 3 — 8- разрядное утроенное множимое 3 и (оно может быть предварительно сформировано

50 либо на сумматоре 4, либо с использованием дополнительной комбинационной схемы ), накапливающий сумматор

4 обнулен.

Детально работу устройства рас-!

51

1смотрим на примере умножения > ножимого

Хна множитель 1 =110001.С учетом этого в исходном состоянии на первом выходе дешифратора 14 формируется сигнал логической единицы, а на пря11 1 1153

10 мых выходах элементов ИЛИ 8 " 8 образуется двоичный код,.4ь =101, из которого в блоке 20 осуществляется выделение младшего значащего разряда, что приводит к образованию сиг- 5 нала признака П . По этому сигналу на выходе первого элемента ИЛИ 17 формируется сигнал логической единицы, который, поступая по шине управления группы 9 на управляющие входы его коммутаторов 10, произво дит передачу на выходы одинарного множимого 1, которое далее поступает на первую группу входов матрицы II элементов И 12 и переда- 15 ется с разрешения того же сигнала признака П через первую линейку.элементов И 12 матрицы 11 и элементы ИЛИ 6 с определенным сдвигом на соответствующие информационные входы 20 накапливающего сумматора 4.

Собственно работа устройства начинается с момента прихода первого синхроимпульса на шину 22 синхронизации устройства. С разрешения этоro 25 синхроиипульса осуществляется установка в ноль первой (самой младшей).. пары разрядов регистра 2 множителя по сигналу признака П и производится прием информации в накапливающий сумматор 4 с его информационных входов. По окончании действия первого синхроимпульса на шине 22 устрой.ства одновременно с суммированием в накапливающем сумматоре 4 первого частичного произведения в устройстве выполняются следующие действия: на всех выходах дешифраторов 14 —

14зобразуются сигналы логического нуля и одновременно с этим на прямых выходах элементов ИЛИ 81-85 формируется двоичный код А .=100, по которому в дальнейшем на третьем выходе блока 20 выделения младшего значащего; разряда формируется сиг- 4 нал признака П ; так как на всех выходах дешифраторов 14 — 14 сформированы сигналы логического нуля, то на выходах первого и второго элементов ИЛИ 17 и 18 также присутству50 ют сигналы логического нуля, а следовательно, на выходе элемента ИЛИ-HE

19 возникает сигнал логической еди-. ницы, который, поступая по шине управления группы 9 на управляющие входы его коммутаторов 10, произво55 дит передачу на выходы l"ðóïïû 9 утроенного множимого 3 g, которое далее поступает на первую группу входов матрицы ll элементов И 12; утроенное множимое 3 4 по сигналу признака П передается с определенным сдвигом через третью линейкУ элементов И

12 матрицъi ll и элементы ИЛИ 6 на соответствующие информационные входы накапливающего сумматора 4. На этом первый такт работы устройства заканчивается, Во втором такте с разрешения вто" рого синхроимпульса на шине 22 синхронизации устройства осуществля-. ется установка в ноль третьей (самой старшей1пары разрядов регистра 2 множителя по сигналу признака II> и производится прием информации в накапливающий сумматор 4 с его,информационных входов. По окончании действия второго синхроимпульса на шине

22 устройства одновременно с суммированием в накапливающем сумматоре .

4 второго частичного произведения на прямых выходах элементов ИЛИ

8 -85 формируется двоичный код@ =

=000, по которому,на выходе окончания выделения блока 20 выделения младшего значащего разряда формируется сигнал признака П . Этот сигнал поступает на выход 21 устройства, сигнализируя об окончании умножения чисел. Таким образом, умножение в .устройстве двух рассмотренных 6-разрядных чисел выполнено за два такта.

В общем же случае умножение двух

Ю -paspspHb>z чисел в предлагаемом устройстве, так же как и в известном 3 1выполняется в среднем за 3 и/8 тактов, причем длительность такта определяется либо временем сложения .(+21-разрядных чисел в накапливающем сумматоре 4, либо задержкой информации в блоках 5,7,9,15,20, в матрице 11 и на элементах 17 и 19.

Технико-экономическое преимущество предлагаемого устройства в сравнении с прототипом состоит.в значиI тельно меньших аппаратурных затратах при его реализации. Так, например, при р =32 в устройстве при его реали-. зации требуется в 1,7 раза меньше аппаратуры. Скорость же работы пред.— лагаемого устройства не ниже скорости работы прототипа.

111)!зз с

1111,153

Cfg

47

Составитель В.Виноградов

Редактор М.Петрова Техред М.Надь, Корректор О.Тигор

Заказ 6311/39 Тираж 698 Подписное

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

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

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