Устройство для умножения чисел

 

СОЮЗ СОВЕТСКИХ СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК (я)5 G 06 F 7/52

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

ilO ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ГКНТ СССР

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

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4832015/24 (22) 29.05.90 (46) 23;02.92. Бюл. ¹ 7 (72) А.И.Бобровский и А.M.Ïðîõîðîâè÷ (53) 631.325(088.8) (56) Бут.Э., Бут К. Автоматические цифровые машины. Физматгиз, 1959,:с.63-66, Авторское свидетельство СССР № 754412, кл. G 06 F 7/52, 1978, (54) УСТРОЙСТВО ДЛЯ УМНОЖЕНИЯ ЧИ. СЕЛ (57) Изобретение относится к цифровой вы- . числительной технике. предназначено для умножения и-разрядных двоичных дополнительных кодов чисел и может найти применение в качестве операционного блока в

„„5U„„1714595 А1 высокопроизводительных машинах и системах. Цель изобретения — расширение функциональных возможностей устройства за счет реализации операции умножения в дополнительном коде путем введения в устройство, содержащее регистры множимого

1 и множителя 2, умножители 3, сумматор 4 элементарных произведений, регистр 8 частичных произведений, регистр 9 произведений и блок 6 микропрограммного управления, блока 7 формирования константы и сумматорэ-вычитателя 5. Произведение формируется по обобщенному алгоритму Бута.

Работа устройства организована по принципу конвейера, 1 з.п. ф-лы, 3 ил.

1714595.

Изобретение относится к цифровой вы- ментарных произведений, выход старших р числительной технике и предназначено для разрядов l-го умножителя (l = 1, 2,...,К) подумножения и-разрядных двоичных допол- ключен к первому входу соответствующих р нительных кодов чисел и может найти при- разрядов сумматора элементарных произменение в качестве операционного блока в 5 ведений, выход которого соединен с входом высокопроизводительных машинах и систе- соответствующих разрядов регистра частичных произведений, выход которого соеИзвестно устройство для умножения чи- динен с входом соответствующих разрядов сел, представленных в дополнительном ко- регистра частичных произведений, вход де, содержащее регистры операндов, 10 разрешения сдвига регистра множителя, сумматор и группу элементов И. входы разрешения выдачи умножителей, Недостатком устройства является его вход разрешения суммирования злементарниэкое быстродействие, что объясняется ных произведений, вход разрешения регибольшим числом циклов умножения (всего стра частичных произведений, входы

15 разрешения записи и разрешения сдвига — циклов, так как используется модифици- регистра" произведения соединены с соотрованный алгоритм Бута). Этот же недоста- ветствующими выходами блока управления, ток у устройства, реализующего алгоритм введены блок формирования константы, Бута (всего и циклов). сумматор-вычитатель, причем выходы младНедостатком устройства, реализующе- 20 ших р+1 разрядое регистра множителя соего умножение дополнительных кодов явля- динены с ин ормационным входом блока ется необходимость коррекции сформиро- формирования константы, выход старшего ванного кода произведения, что снижает (знакового).разряда регистра множителя собыстродействие устройства. единен с управляющим входом блока фор- .

Наиболееблизким к предлагаемому яв- 25 мирования константы, первый выход ляется устройство для умножения чисел. со- которого (р разрядов) соединен с входом держащее регистры множимого и второго сомножителя каждого умножителя, множителя, К умножителей формата р х второй выход(р разрядов) соединен с старх р + 2р (где К такое,.что К р Ъ и, и — шими рразрядамивтороговходасумматора разрядность операндов), комбинационный 30 элементарных произведений, а третий высумматор элементарных произведений (да- ход с входом режима сумматора-вычитателее употребляется сумматор элементарных ля, выход регистра частичных произведений произведений) накапливающий сумматор соединен с входом второго слагаемого сумчастичных произведений {фактически вклю- матора-вычитателя, выход которого соедичающий в себя регистр. частичных проиэее- 35 нен с входом регистра произведения, выход дений, сумматор, регистр произведения) и которого соединен с входом первого слагаблок управления. емого сумматора-вычислителя, синхронизиНедостатком устройства является рующий вход блока формирования узостьфункциональныхвозможйостей(реа- константы и вход разрешения суммировализована операция умножениядвоичныхко- 40 ния соединены с соответствующими выходов модулей чисел). Целью изобретения дами блокауправления. является расширение функциональных воз- Снабжение устройства для умножения можностей устройства путем реализации чисел блоком формирования константы, - операции умножения в дополнительных ко- сумматором-еычитателем, соединение вы45 ходов младших р+1 разрядов регистра мноПоставленная цельдостигается тем,что жителя с информационным входом блока е устройство для умножения чисел, содер- формирования константы, соединение выжащее регистры множимого и множителя, К хода старшего(знакового) разряда регистра умножителей формата р х р =2р, где К такое. множимого с управляющим входом блока ч о К р > и, n — разрядность операндов, р 3, 50 формирования константы, соединение его сумматор элементарных произведений, ре- первого выхода (р разрядов) с входом второгистр и блок управления, причем вход пер- го сомножителя каждого умножителя, втового сомножителя каждого умножителя с рого выхода {р разрядов) со старшими р выходом соответствующих р разрядов реги- разрядами второго входа сумматора элестра множимого, вход младших р разрядов 55 ментарных произведений, третьего выхода регистра частичных произведений соеди- свходомрежимасумматора-вычитателя;соненсвыходомрмлэдшихразрядовпервого единение выхода регистра частичных проумножителя,выходмладшихрразрядов)-го изведений с входом второго слагаемого умножителя (j = 2; 3, ...,К) подключен к вто- сумматора-еычитателя, соединение его вырому входу(р)-р)-х разрядов сумматора эле- хода с входом регистра произведения, сое1714595 динение выходов (n+p) старших разрядов Пусть п-раэрядноемножимоеХип-разрегистра произведения с входом первого рядный множитель Y лежат в диапазоне (О, слагаемогосумматора вычитателя, соедине- 1) и представлены в дополнительном коде, we управляющего входа блока формирова- т.е. ния константы и входа разрешения 5 X=X1,X2,Хз, Хл(Х1-знаковый разряд);.

Суммирования сумматора-вычитателя с со- У = у1, уг. уз...у (у1 — знаковый разряд). ответствующими выходами блока управления обеспечивает возможность реализации. р операции умножения в дополнительных ко- B n п 1 дах и конвейеризацию процесса умноже- 10 р р ния, причем в каждом цикле работы Ci-(-2р ур/-р+1+2р ypi-р+2+" +2ypi-1+ устройства осуществляется умножение + ypi+ ypi+1) 2 р; множимого на очередные.р разрядов мно- Zi""ХС;жителя на основе анализа очередных р+1, р Z = Z.2 Р + Zi.

> 3 разрядов множителя и не требуется пре- 15 После К-го цикла Z — есть дополнительобраэования кодов сомножителей в прямые ный код произведения Х1У, причем 26(0, 1). коды и дополнительный коррекции сформи- Докажем, что обобщенный алгоритм Бурованного кода произведения для получе- та позволяет получить дополнительный код ния . верного дополнительного кода . произведения двух сомножителей, предпроиэведения. 20 ставленных в дополнительном коде.

Кроме того, указанные отличительные Пусть Zl — содержимое накопителя попризнаки позволяют повысить быстродей- сле I-ro шага, множитель Y = y1 уг...yn уп+1, ствие устройства по сравнению с извест- имеет в исходном состоянии yn+1 = О, Zo - О. ным за счет сокращения числа циклов - Тогда пообобщенномуалгоритму Бута уМНОжЕНИя И СОВМЕщЕНИя ВО ВРЕМЕНИ ПрО- 25 Z1 = (-2р уп-p+1+ 2р Ул-р+2+ . ° . + 2уп-1+ цЕССОВ ВЫЧИСЛЕНИЯ ЧаСтИЧНЫХ И ЭЛЕМЕНтар- + yn+ ул+1) Х 2 р = (-2р Ул-p+1+ 2р Уп-p+2+ + ных произведений. + 2у -1+ уп) Х 2 р, так как уп+1 = О. (1)

Известен алгоритм Бута умножения чи- . Выражения для следующих 2домножим сел в дополнительном коде с анализом двух на соответствующую степень двойки, Полочередных (у, у1+1) разрядов множителя У. В 30 учим следующую систему равенств: исходном состоянии 2 О ул+1 О произво- — 1 Г 2 1 дИтСя A ЦИКЛОВ УМНОжЕНИя 8 )-M (j = A, A- г = — р " (- У.-(гр-1)+.-+ Ул-р+

-:1„...1) цикле вычисляется + „)X 2 р, + ул-. +1)

С) = -у! + y +1; . (2р)к-"„2 (2p)ê-3 2 + (2ð)ê-2 (2р-1 +

2=2 2 +21.

+ 2 ° Складывая систему равенств (2) и сокрагде С1 — константа, вычисляемая на основе щая подобные, получают анализа значений очередных р+1 разрядов у. . (2p) Zк = — Z1+ (-(2р)к 2 х

yi — j-й разряд множителя У, дополни- 40 тельный двоичный код которого у1 уг...

Ул Yn+1

Zi — частичнж произведение в дополни- Подставив вместо 21 значение (1) и Раэр к-г тельном коде; делив на (2, получают

Z — накопитель частичных произведе- 45 2к = f-у1+ — y2+...+

1 ний;

Х вЂ” множимое., " . + " ) Х.2

К 1 1

В известном устройстве используется (2 ) модифицированный алгоритм Бута с анали- перейдя к и = К р, получают зом трех очередных (у1 1, У1; yl+1) разрядов У, 50 Zy = (- „+ 1 У + + в котором константа С1 формируется согласно известной таблице за и циклов. а это есть истинный дополнительный код

2 2 ХУ.

Работа предлагаемого устройства осно- Нэ фиг.1. приведена структурна схема вана на обобщенном алгоритме Бута, в ко- 55 устройства для умножения чисел; на фиг.2— тором за цикл аналиэи ются +1 > 3 р . ц. а иэируются р 1, p i - относительная временная диаграмма сигнаразрядов множителя. B обобщенном алго- лов на выходах блока управления при раборитме Бута в исходном состоянии Z = 0, ул+1 =; н а ф и г,3 — блок формирования константы.

1714595

Устройство содержит регистр множимого 1 и множителя 2, К умножителей формата р х р - 2р 31...3к, сумматор 4 элементарных произведений, сумматор-вычитатель 5 частичных произведений, блок 6 управления, 5 блок 7 формирования константы, регистр 6 частичных произведений, регистр 9 проиэи ведения, причем выходы 1-й (1 = 1, ..., К-.— ) р р-разрядной группы регистра множимого 1 10 соединен с входом первого сомножителя соответствующего умножителя 3, вход второго сомножителя умножителей 3 соединен с первым выходом блока 7 (выход 13), выход старшего разряда множимого 1 соединен с 15 управляющим входом блока 7 информаци-. онный вход 12 которого соединен с выходом (р+1) младших разрядов множителя 2, второй выход блока 7 (выход 14) соединен с старшими р-разрядами второго входа сум- 20 матора 4, вход младших р разрядов регистра 8 соединен с выходом младших разрядов умножителя 31, выход младших разрядов

)-го умножителя (j - 2„.„К) подключен к второму входу (pj-р)-х разрядов сумматора 4, 25 выход старших разрядов I-ro умножителя (1 - 1,...,К) подключен к первому входу соответствующих разрядов сумматора 4, выход которого соединен с входом соответствующих разрядов регистра 8, выход последнего 30 соединен с входом второго слагаемого сумматора 5, вход режима которого соединен с третьим выходом блока 7, выход сумматора

5 соединен с входом регистра 9, выход которого соединен с входом первого слагаемого 35 сумматора 5, вход разрешения сдвига множителя 2, вход разрешения записи регистра

8, вход разрешения сдвига регистра 9 соединены с выходом 10 блока 6, выход 11 соединен с синхрониэирующим входом бло- 40 ка 7, входом разрешения выдачи умножителей 3, входом разрешения суммирования сумматора 5 и входом разрешения записи регистра 9.

Регистр множимого 1, п-разрядный, 45 предназначен для хранения множимого Х, представленного в дополнительном коде: л

Х = — х1+,>, х 2

1=,2 50

Регистр множителя 2, п+1 разряднцй, предназначен для хранения множителя У, представленного в дополнительном коде Y и

- — y>+ ; yi 2 +, причем сдвигосущеет =2. M вляется в сторону младших разрядов нэ р разрядов.

Умножители 31...3к предназначены для вычисления очередных элементарных произведений Х /С1/ i - 1,...,К, где Х; — код образованный 1-й группой р разрядов кода

Х; С1 - р — разрядный код модуля величины

С1. Умножители имеют по два информационных р-разрядных входа и 2р-разрядные информационные выходы. Умножители могут быть реализованы, например, в виде однократного матричного умножителя или в виде

ПЗУ с прошитой таблицей умножения прямых кодов положительных чисел в вторичной системе счисления.

Сумматор 4 элементарных произведений — двухвходовой, п-разрядный, предназначен для формирования, старших и разрядов частичного произведения(С1) Х, j

1, 2...К.

Регистр 9 частичных произведений предназначен для организации конвейера и. в нем хранится частичное произведение (С1)Х в дополнительном коде.

Сумматор-вычитатель 5 частичных произведений двухвходовой, n+p разрядный, предназначен для формирования суммы Z1 частичных произведений Х I С1 I, причем на вход режима поступает знак величины С1, j = 1. 2...К, Иэ блока 7 формирования константы и при значении знакаС1 - 0 проиЭЭОдится сложение, а при знаке О1. ::: -:1 вычитание..

Блок 7 формирования константы предназначен для формирования модуля кон- .„ станты (С1) в прямом коде (выход 13), поправки (выход 14) и знака С1 на основе анализа очередных р+1 разрядов множителя, Пример реализации блока 7 приведен нэ фиг.3, где 12.1, 12.2,.„.12.р, 12,р+1 — выходы младших р+1 разрядов регистра множителя. 13 — р-разрядный выход модуля константы, 14 — р-разрядный выход поправки,. 15 — р-разрядный сумматор-вычитатель, предназначенный для формирования прямого кода модуля константы.

По алгоритму

С1 =2 ур1-р+1+ 2 ур)-p+2 +„,+

+ 2ypH + ур1 + Ур1+1 °

В обозначениях фиг.3) имеют

С--2р iур+ +.2р ур+ ...+2уз+у2+у .

Для получения /С/ при yp+i = О необходимо к коду числа ур+1 ур...у2 прибавить у в младший разряд, а при ур+ " 1, то же самое и взять дополнительный код.

Кроме того, на фиг.3 показаны р-разрядный вычитатель 16, предназначенный для формирования поправки, которая образуется следующим образом: произведение Х/C/ при умножении вдополнительном коде, при отрицательном Х, т.е. Х1 = 1, имеет вид 1-/С/Х, а получаемый результат был бы (1-Х)/С/ = ICI - /С/Х, т.е. необходимапоправ ка 1-/С/, а это дополнительный код от /С1/;

1714595

Сигнал 21;

У ./С /

1-и цикл поправка / z/

Сигнал 20:

R8 1111 0000 0001 причем поправка подается на старшие р разрядов входа второго слагаемого сумматора 4. так как имеет такой вес и именно эти входы свободны от слагаемых умножителей

31„,3к, элемент И 17, группа р элементов И

18 вместе с элементом 17 предназначена для обнуления поправки при положительном Х и синхронизации ее выдачи, двухступенчатый CD-триггер 19, предназначенный для организации конвейера.

Блок 6 управления имеет два выхода.10 и 11 и формируют временную диаграмму (фиг.2). Блок управления может быть реализован, в частности, в виде блока микропрограммного управления, содержащего счетчик. адреса микрокоманды и ПЗУ микрокоманд, в котором записано 2 — + 1 р. микрокамэнд в соответствии с временной диаграммой (фиг.2).

Регистр 9 произведения, 2п-разрядный сдвиговый, причем сдвиг осуществляется в сторону младших разрядов на р разрядов.

При выполнении операции умножения устройство работает следующим образом;

В исходном состоянии в регистре 1 находится множимое Х, в регистре.2 в старших и разрядах множитель У, в младшем разряде 0 (ye+1 = О). регистры 8 и 9 об нуле н ы (фиг,1, цепи сброса, синхронизации и питания .не показаны);

Устройство работает циклически. по и принципу конвейера. Всего — циклов. В р каждом осуществляется вычисление очередкого (j-ro) и+р-рэзряднога . частичного произведения (первая ступень конвейера) и добавление к сумме частичных произведений предыдущего. (j-1) частичного произведения (вторая ступень конвейера):

8 первом (j = — ) цикле по сигналу 21 и р запиСывается знак Cj в триггер 19, на умно3 0100 ооо1

3 0011 1100

0100 00 00

14 1011 ттттттттъит жителях 31...3к формируются К элементарных произведений Х /С1/ i = 1.„.,К, которые складываются на сумматоре 4, на суммато-. ре-вычитателе складываются нули, По сигналу 20 содержимое регистра 2 множителя сдвигается на р разрядов в сторону младших разрядов, на регистр 8 записывается первое частичное произведение.

В последующих циклах па сигналу 21

"0 записывается знак С1 в триггер 19, на умножителях 31...3к формируются К элементарных произведений Х /С /! = 1,...,К, которые складываются на сумматоре 4, на сумматоре-вычитателе 5 складываются очередные

15 частичные произведения, в регистре 9 накэпливается произведение. По сигналу 20 сдвигается содержимое регистров множимого 2 и произведения 9 на р разрядов в сторону младших разрядов, на регистр 8

20:записывается сформированное на суммато ре 4 частичное произведение, и

После завершения К (К = — ) циклов не.р обходим еще один сигнал 20, по нему вхоло25 стую срабатывают умножители и блок 7 формирования константы, последнее частичное произведение сложится с содержимым регистра 9, на который пишутся старшие разряды произведения. Z. Таким

30 образом на регистре произведения оказывается (2n-1)-разрядный дополнительный код произведения, дополненный до 2п-знаковым разрядом, т.е. произведение

Z = Z1 1 Z2" Z2n-1

2А

Рассмотрим пример умножения для и -.

=8, р =4.

Пусть (XQ = 1,100 1101 (51 2 )

40 (У)д = 0.001 101 1 (+2? 2 )

Дополняя (Y) 0 справа, получают (Yg =

= 0001 10110

Анализируемая группа 10110

/Сэ/ = 0101, знак С = 1 поправка = 1011

1714595

I (71 сдвинутый на 4 разряда вправо д

0 0000 0011

Сигнал 21:

0001 1010

Х, /С,/

4 32 0001 1000

1 1

14

1111 1001 1010

2"й цикл поправка

X /С,/

Так как знак C> = 1, то на сумматоре 5 вычитают

R9 0000 0000 0000

R8 1111 0000 0001

2БГГТПТТЯТ Г, 3, R8 1111 1001 1010

R9 0000 0000 1111 1111

Сигнал 21:

R9 0000 ОООО 1113 кз 11И 100»010

ПГ| ЯТ» <,1

- 4 -фь

t.Z ) -1377 2 = "51 27 2 " X" .

23

Оценим аппаратурные затраты на до- 5 стижение поставленной цели по отношению к прототипу..

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

Vo Чумн+ VR+ VSM где VyMH — объем оборудования умножителей; VR — объем оборудования региетров 45 множителя 1, множимого 2, произведения 9 и частичного произведения 8;

Чзм — объем оборудования сумматоров элементарных и частичных произведений, Эти величины, проанализировав воз-50 можные варианты реализации, можно оценить следующим образом, приняв за единицу измерения логический элемент типа И-НЕ гр+1 55

VR =20п+ 4р;

Чзм =26n+ 10р, Тогда Vo = К 2 Р+ + 40п + 1 4р. .Объем оборудования заявляемого устройства

Чз = Чо + ЕЧЛИ - Чак + Л VR, где Чек — объем оборудования блока формирования константы 7;

Л VR — дополнительный объем оборудо-) вания регистров 2, 8

Чек = 21р+ 5, ЬVR - 20

Тогда ЛЧ 21р+ 25.

Оценим относительное увеличение объема оборудования прототипа для и. 32, р=4

= 0,01, V т.е. увеличение объема оборудования на 1 позволяет выполнить операцию умножения над числами в дополнительном коде. По. сравнению с аналогом в предлагаемом устройстве число циклов умножения уменьаеи и но на величину — — —, р 3. 3, что свиде2 р тельствует о более высоком быстродействии предлагаемого устройства.

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

1, Устройство для умножения чисел, содержащее регистры множимого и множителя, К умножителей формата р х р 2ð (где K такое, что К р > и, n — разрядность операмСигнал 20: R2 0 0000 0000

Анализируемая группа 00011

/С„/ = 0011, знак С = 0 поправка 1011

Х2 /С1/

1714595 дов, р > 3), сумматор элементарных. произведений, регистр частичных произведений, регистр произведений и блок микропрограммного управления, причем вход первого сомножителя каждого умножителя соединен.с выходом соответствующих р разрядов регистра мйожимого, вход младших р разрядов регистра частичных произведений соединен с выходом р младших разрядов первого умножителя, выход младших р разрядов)-ro умножителя O = 2, З,...,К) соединен с вторым входом (pj - р)-х разрядов сумматора элементарных произведений, выход старших р разрядов l-ro умножителя (l = 1:,;., K) соединен с первым входом соответствующих р разрядов сумматора элементарных произведений, выход которого соединен с информационным входом соответствующих разрядов регистра частичных произведений, вход разрешения сдвига регистра множителя, вход разрешения записи регистра частичных произведений и вход разрешения сдвига регистра произведений соединены .с первым выходом блока микропрограммного управления, второй выход которого соединен с входами разрешения выдачи умножителей, входом разрешения суммирования элементарных произведений и входом разрешения записи регистра про-. изведения, о т л и ч а ю щ е е с я тем,-что, с целью расширения функциональных воз. можностей устройства путем реализации операции умножения в дополнительном коде, в него введены блок формирования кон:станты и сумматор-вычитатель, причем выход младших р+1 разрядов регистра множителя соединены с информационным .(р+1)-разрядным входом блока формирования константы, выход старшего знакового разряда регистра множимого соединен с управляющим входом блока формирования, константы, первый и второй р-разрядные выходы которого соединены соответственно с входом второго сомножителя каждого умножителя и входом старших р разрядов второго слагаеМого сумматора элементарных произведений, а третий выход — с входом режима сумматора-вычитателя, выход регистра частичных произведений — с входом второго слагаемого сумматора-.вычитателя, выход которого соединен с информационным входом регистра произведения, выход которого соединен с входом первого слагаемого сумматора-вычитателя, синхровход блока формирования константы и вход разрешения суммирования сумматора-вычитателя соединены с вторым выходом блока микропрограммного управления.

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

45,блока.

1714595

Составитель А.Бобровский

Техред M.Ìîðãåíòàë Корректор В.Гирняк

Редактор М.Бланар

Производственно-издательский комбинат "Патент", г. Ужгород, ул.Гагарина, 101

Заказ 694 Тираж Подписное

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

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