Устройство для умножения чисел Советский патент 1992 года по МПК G06F7/52 

ь ел .ю ел

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

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

Недостатком устройства является его низкое быстродействие, что объясняется большим числом циклов умножения (всего

циклов, так как используется модифицированный алгоритм Бута). Этот же недостаток у устройства, реализующего алгоритм Бута (всего п циклов).

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

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

Недостатком устройства является узость функциональных возможностей (реализована операция умножения двоичных кодов модулей чисел). Целью изобретения является расширение функциональных возможностей устройства путем реализации олерации умножения в дополнительных кодах.

Поставленная цель достигается тем, что в устройство для умножения чисел, содержащее регистры множимого и множителя, К умножителей формата р х р . где К такое, что Кр п. п - разрядность операндов, р 3, сумматор элементарных произведений, регистр и блок управления, причем вход первого сомножителя каждого умножителя с выходом соответствующих р разрядов регистра множимого, вход младших р разрядов регистра частичных произведений соединен с выходом р младших разрядов первого умножителя, выход младших р разрядов j-ro умножителя О 2, 3К) подключен к второму входу (pj-p)-x разрядов сумматора элементарных произведений, выход старших р разрядов i-ro умножителя (I 1, 2,...,К) подключен к первому входу соответствующих р разрядов сумматора элементарных произведений, выход которого соединен с входом соответствующих разрядов регистра частичных произведений, выход которого соединен с входом соответствующих разрядов регистра частичных произведений, вход разрешения сдвига регистра множителя, входы разрешения выдачи умножителей, вход разрешения суммирования элементарных произведений, вход разрешения регистра частичных произведений, входы разрешения записи и разрешения сдвига регистра произведения соединены с соответствующими выходами блока управления, введены блок формирования константы, сумматор-вычитатель, причем выходы младших р+1 разрядов регистра множителя соединены с ин ормационным входом блока формирования константы, выход бтарщего (знакового) разряда регистра множителя соединен с управляющим входом блока формирования константы, первый выход которого (р разрядов) соединен с входом второго сомножителя каждого умножителя, второй выход (р разрядов) соединен с старшими р разрядами второго входа сумматора элементарных произведений, а третий выход с входом режима сумматора-вычитателя, выход регистра частичных произведений соединен с входом второго слагаемого сумМатора-вычитателй, выход которого соединен с входом регистра произведения, выход которого соединен с входом первого слагаемого сумматора-вычислителя, синхронизирующий вхОд блока формирования константы и вход разрешения суммирования соединены с соответствующими выходами блока управления.

Снабжение устройства для умножения чисел блоком формирования константы, сумматором-вычитателем, соединение выходов младших p+l разрядов регистра множителя с информационным входом блока формирования константы, соединение выхода старшего (знакового) разряда регистра множимого с управляющим входом блока формирования константы, соединение его первого выхода (р разрядов) с входом второго сомножителя каждого умножителя, второго выхода (р разрядов) со старшими р разрядами второго входа сумматора элементарных произведений, третьего выхода с входом режима сумматора-вычитателя; соединение выхода регистра частичных произведений с входом второго слагаемого сумматора-вычитателя, соединение его выхода с входом регистра произведения, соединение выходов (п-ьр) старших разрядов регистра произведения с входом первого слагаемогосуммагоравычитателя, соединение управляющего входа блока формирования константы и входа разрешения Суммирования сумматора-вычитателя с соответствующими выходами блока управления обеспечивает возможность реализйции операции умножения в дополнительных кодах и конвейеризацию процесса умножения, причем в каждом цикле работы устройства осуществляется умножение множимого наочередные р разрядов множителя на основе анализа очереднь1хр+1, р 3 разрядов множителя и не требуется преобразования кодов сомножителей в прямые коды и дополнительный коррекции сформированного кода произведения Для получения верного дополнительного кода произведения. Кроме того, указаннь1е отличительные признаки позволяют повысить быстродействие устройства по сравнению с известным за рчет сокращения числа циклов умножения и совмещения во времени процессов вычисления частичных и злементарных произведений. Известен алгоритм Бута умножения чисел в дополнительном коде с анализом двух очередных (У}, ) разрядов множителя Y. В исходном состоянии О, уп-н1 О, производится п циклов умножения. В j-M О п. п-1,...,1) цикле вычисляется Cj -у)- -yi+u Z| XCi2V . где Cj - константа, вычисляемая на основе анализа значений очередных р+1 разрядов Y;-. ; ,.; . : v-V-. .. : yj - j-й разряд множителя V, дополнительный двоичный коу которого у1 у2... УП УП-И; Zj - частичн4 е произведение в дополни тельном коде; Z - накопитель частичных произведений;Х-множимое., В известном устройстве используегся модифицированный алгоритм Бута с анализом трех очередных (yj-i,yj. yj+i) разрядов Y, в котором константа Cj формируется согласно известной таблице за - циклов. Работа предлагаемого устройства основана на обобщенном алгоритме Бута, в котором за цикл анализируются р+1, р 3 разрядов множителя. В обобщенном алгоритме Бута в исходном состоянии Z О, угн-1 0. Пусть п-разрядное множимое X и п-разрядный множитель Y лежат в диапазоне О 1 и представлены в дополнительном коде; т.е. . ; .. :-. -, . ;:.: . X Xi, Х2, Хз.,.Хп (Xi - знаковый разряд); Y yi, У2. уз...Уп {yi - знакрвый разряд). Производится К -циклов умножения. В , - -1,...,1) цикле вычисляются Cj {-2Р- ypj-pH-1 + 2Р-2 ypj.p+2 +... 2yp,-i + + ypj + ypj+l) 2Р,- . i X«D; Z-2P +: После К-ГО цикла Z - есть дополнительный код произведения XY, причем Z€tO. 1). Докажем, что обобщенный алгоритм Бута позволяет получить дополнительный код произведения двух сомножителей, представленных в дополнительном коде. Пусть Zi - содержимое накопителя после 1-го шага, множитель Y yi у2...уп уп+1, имеет в исходном состо:янии уп+1 0, Zo 0. Тогда по обобщенному алгоритму Бута Zi -2РVn-p-n + 2Р2уп-р+2 -I-... + 2уп-1 + + УП + Уп+1 X 2Р -2Р-Vn-p+1 + 2Р-2 уп-р+2+...-t+ 2уп-1 + УП X 2Р, так как уп+т 0.(1) Выражения для cлeдyющиXZдoмнoжим на соответствующую степень двойки. Получим следующую систему равенств: Z2 - Zi + (2р-1)+..+Уп-р + (2Р) ZKl + (2Р) f.jP-iyi + - + 2Р-2у2+...-ьур + ур-ц.Х.2-Р.(2) Скла,дывая систему равенств (2) и Сокращая подобные, получают (2T-fZK- 4Zi + -(2P) X 2Р У1 +...+ уп-р + yn-p+i X-2P - Подставив вместо Zi значение (1) и разелив на (2Р). получают 2к -у1 + 2У2+...+ 1 2P) ерейдя к п Кр, получают ZK - -У1 +1У2 +...+ - Уn X2Это есть истинный дополнительный код . . На фиг.1 приведена структурна схема стройства для умножения чисел; на фиг.2 тносительная временная диаграмма сигнаов на выходах блока управления при рабое устройства; на фиг.З - блок ормирования константы.

Устройство содержит регистр множимого 1 и множителя 2, К умножителей формата р X р З1...3к, сумматор 4 элементарных произведений, сумматор-вычитатель 5 частичных произведений, блок 6 управления, блок 7 формирования константы, регистр 8 частичных произведений, регистр 9 произведения, причем выходы 1-й (I 1К -)

р-разрядной группы регистра множимого 1 соединен с входом первого сомножителя соответствующего умножителя 3, вход второго сомножителя умножителей 3 соединен с первым выходом блока 7 (выход 13}. выход старшего разряда множимого 1 соединен с управляющим входом блока 7 информаци-. онный вход 12 которого соединен с выходом (р+1) младших разрядов множителя 2. второй выход блока 7 (выход 14) соединен с старшими р-разрядами второго входа сумматора 4. вход младших р разрядов регистра 8 соединен с выходом младших разрядов умножителя 3i, выход младших разрядов j-ro умножителя О 2К) подключен k второму входу (pj-p)-x разрядов сумматора 4, выход старших разрядов 1-го умножителя (1 1,..мК) подключен к первому входу соответствующих разрядов сумматора 4. выход которого соединен с входом соответствующих разрядов регистра 8. выход последнего соединен с входом второго слагаемого сумматора 5, вход режима которого соединен с третьим выходом блока 7, выход сумматора 5 соединен с входом регистра 9, выход которого соединен с входом первого слагаемого сумматйра 5, вход разрешения сдвига множителя 2, вход разрешения записи регистра 8, вход разрешения сдвига регистра 9 соединены с выходом 10 блока 6, выход 11 соединен с синхронизирующим входом блока 7, входом разрешения выдачи умножителей 3, входом разрешения суммирования сумматора 5 и входом разрешения записи регистра 9. .

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

. XI + i: XI 2--

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

п-.,

У X у| 2 причем СДВИГ осущеет1 2.

вляется в сторону младших разрядов на р разрядов.

Умножители Зь.-Зк предназначены для вычисления очередных элементарных произведений Х| /Cj/ i 1,....К, где Xi - код

образованный 1-й группой р разрядов кода X; Cj - р - разрядный код модуля величины С. Умножители имеют по два информационных р-разрядных входа и 2р-разрядные информационные выходы. Умножители могут быть реализованы, например в виде однократного матричногоумножитеяя или в виде ПЗУ с прошитой таблицей умножения прямых кодов положительных чисел в вторйч0 ной системе счисления.

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

5 -1.2...К.

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

0 Сумматор-вычитатель 5 частичных произведений двухвходовой, п+р разрядный, предназначен для формирования суммы Z} частичных произведений XI С I, причем на вход режима поступает знак величины С),

5 j 1. 2..,К, Из блока 7 формирования константы и при значении знака Cj О прОИЗлаодится сложение, а при знаке Cft- 1 вычитание.

Блок 7 формирования константы пре

0 назначен для формирования модуля константы (Cj) в прямом коде (выход 13), поправки (выход 14) и знака Cj на основе анализа очередных р+1 разрядов множителя.

5 Пример реализации блока 7 приведен на фиг.З, где 12.1, 12.2,....12.р, 12.р+1 - выходы младших р+1 разрядов регистра множителя. 13 - р-разрядный выход модуля константы, 14 - р-разрядный выход поправки, 15 - р-разрядный сумматор-вычитатепь, предназначенный для формирования прямого кода модуля константы. По алгоритму Cj -2PVpj-p i + 2P2ypj-p+2 +...+ .

5 + 2ур1-1 + ypj + ур|+1.

В обозначениях (фиг.З) имеют С -2PVp+i+ 2PV + - + 2уз + У2 + yi. Для получения /С/ при ур-ц 0 необходимо к коду числа ур-ц ур;..у2 прибавить yi в

0 младший разряд, а при ур+i 1, то же самое и взять дополнительный код.

Кроме того, на фиг.З показаны р-разрядный вычитатель 16, предназначенный для формирования поправки, которая образуется следующим образом: произведение Х/С/ при умножении в дополнительном коде, С1ри отрицательном X, т.е. Xi 1, имеет вид 1 -/С/Х, а получаемый результат был бы (1-Х)/С/ /С/ - /С/Х, т.е. необходимапоправ. ка 1-/С/. а это дополнительный код от /Cj/; причем поправка подается на старшие р разрядов входа второго слагаемого сумматора 4. так как имеет такой вес и именно эти входы свободныот слагаемых умножителей 31,..3к, элемент И 17, группа р элементов И 18 вместе с элементом 17 предназначена для обнуления поправки при положительном X и синхронизации ее выдачи, двухсту пенчатый СО-триггер 19, предназначенный для организации конвейера. Блок 6 управления имеет два выхода 10 и 11 и формируют временную диаграмму (фиг.2). Блок управления может быть реализован, в частности, в виде блока микропрограммного управления, содержащего счетчик.адреса микрокоманды и ПЗУ микрокоманд, в котором записано 2 -г 1 Микрокоманд в соответствии с временной диаграммой (фиг.2). Регистр 9 произведения. 2п-разряднь)й сдвиговый, причем сдвиг осуществляется в сторону младших разрядов на р разрядов. При выполнении операции умножения устройство работает следующим образом. В исходном состоянии в регистре 1 на ходится множимое X, в регистре 2 в старших п разрядах множитель Y, в младшем разрядеО(уп+1 0), регистры 8 и 9 обнулены (ф11г,1, цепи сброса, синхронизации и питания не пбказаны). Устройство работает циклически по принципу конвейера. Всего - циклов. В каждом осуществляется вычисление очередного (1-го) п+р-разрядного частичного произведения (первая ступень конвейера) и добавление к сумме частичных произведений предыдущего 0-1) частичного произведения (вторая ступень конвейера); В первом О -) цикле по сигналу 21 записывается знак Cj в триггер 19, наумноСигнал 21:

3,

0100

0001

Зо

ООП 1100

SM4X

0100 OOQQ 0001

J4 1011

1111

Сигнал 20:

R8 1111 0000 0001

Анализируемая группа 10110 /Cg/ 0101, знак С2 1 поправка 1011

Х,-/С,/ .-/Ср/

поправка

Y жителях З1...3к формируются К элементарных произведений Xi/Cj/ I 1К, которые складываются на сумматоре 4. на суммато-: ре-вычитателе складываются нули. По сигналу 20 содержимое регистра 2 множителя сдвигается на р разрядов в сторону младших разрядов, на регистр В записывается первое частичное произведение. В последующих циклах по сигналу 21 записывается знак Cj в триггер 19, на умножителях З1...3к формируются К элементарных произведений Xi/Cj/ 1 1К, которые складываются на сумматоре 4, на сумматоре-вычитателе 5 складываются очередные частичные произведения, в регистре 9 накапливается произведение. По сигналу 20 сдвигается содержимое регистров множимого 2 и произведения 9 на р разрядов в сторону младших разрядов, на регистр 8 записывается сформированное на сумматоре 4 частичное произведение. После завершения К (К -) циклов не. . - гобходим еще один сигнал 20, по нему вхолостую срабатывают умножители и блок 7 формирования константы, последнее часичное произведение сложится, с содержимым регистра 9, на который пишутся старшие разряды произведения. Z. Таким бразом на регистре произведения оказывается (2п-1)-разрядный до полнитель.ный од произведения, дополненный до 2п-знаовым разрядом, т.е. произведение Z 1д Z2...Z2n-j. 2п Рассмотрим пример умножения для п 8, р 4. Пусть 1.100 1101 С-512) 0.001 1011 (+2720 Дополняя О справа, получают 0001 10110.

Сигнал 21:

R9

0000 0000 1114

RS 1111 1001 1010

11,11 1010 1001 1111

R9

«-

,iit

IZjlg -1377-2 -5127-г--- XY

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

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

Vo VywH + VR VSM,

где VywH - объем оборудования умножителей;

VR - объем оборудования регистров множителя 1, множимого 2, произведения 9 и частичного произведения 8;

VSM - объем оборудования сумматоров элементарных и частичных произведений,

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

Ууми К2

VR « 20ft + 4р,VSM «20П + Юр, Тогда Vo + 40п + 14р.

Объем оборудования заявляемого устройства

Уз Vo + .UV VoK AYR.I

где V0K - объем оборудования блока форми-; рования константы 7;I

А VR-дополнителъный объем оборудо-1 вания регистров 2ч 8,

V®K 21p + 5.AVR 20 ТогдаДУ-21р + 25.

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

о,о,.г

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

Формула изобретения 1. Устройство для умножения чисел, содержащее регистры множимого и множителя, К умножителей формата р х р (где К .такое, что К-р п, п - разрядность операндов, р $-3), сумматор элементарных произведений, регистр частичных произведений, регистр произведений и блок микропрограммного управления, причем вход первого сомножителя каждого умножителя соединен С выходом соответствующих р разрядов регистра множимого, вход младших р разрядов регистра частичных произведений соединен с выходом р младших разрядов первого умножителя, выход младших р разрядов j-ro умножителя О 2, 3,...,К) соединен с вторым входом (pj - р)-х разрядов сумматора элементарных произведений, выход старших р разрядов 1-го умножителя (1 1. 2,...,К) соединен с первым входом соответствующих р разрядов сумматора элементарных произведений, выход которого соединен с информационным входом соответствующих разрядов регистра частичных произведеНИИ. вход разрешения сдвига регистра множителя, вход разрешения записи регистра Частичных произведений и вход разрешения сдвига регистра произведений соединены с первым выходом блока микроирограммного управления, второй выход которого соединен с входами разрешения выдач т умножителей, входом разрешения суммирования элементарных произведений и входом разрешения записи регистра произ.вeдeнияv0 т л и ч а ю щ ее с я тем, что, с целью расширения функциональных возможностей устройства путем реализации Iоперации умножения в дополнительном коде, в него введены блок формирования константы и сумматор-вычитатель, причем выход младших р+1 разрядов регистра мно:жителя соединены с информационным {р+1)разрядным входом блока формирования константы, выход старшего знакового разряда регистра множимого соединен с управляющим входом блока формирования константы, первый и второй р-разрядные выходы которого соединены соответственно с входом второго сомножителя каждого умножителя и входом старших р разрядов

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

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

блока.

5

7 х р

Фие.г

П. 12.2 Ш

Фиг.