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

сл

с

Изобретение относится к вычислительной технике и,может быть использовано в арифметических устройствах ЭВМ. Целью изобретения является повышение быстродействия устройства. Новым в устройстве, содержащем регистр множимого, сдвиговый регистр множителя, три группы элементов И и накапливающий сумматор, является введение блока формирования пар двоичных разрядов утроенного значения множителя, дополнительного нулевого разряда в регистре множителя, п/2 дешифраторов состояний пар двоичных разрядов множимого, что позволило реализовать умножение в прямых кодах на два разряда множителя одновременно и исключить три знаковых разряда накапливающего сумматора. Это приводит к сокращению времени распространения переносов. 3 ил.

Изобретение относится к вычислитель ной технике и может быть использовано в арифметических устройствах ЭВМ. ,

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

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

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

11 в анализируемой паре разрядов множителя производится вычитание множимого и выработка переноса в следующую пару разрядов, i.e. комбинация 11 преобразуется в комбинацию 101 {2.

По технической сущности наиболее близким к предложенному является устройство, которое содержит n-разрядный регистр множимого, (п+3)-разрядный сдвиговый накапливающий сумматор, п- разрядный сдвиговый регистр множителя, три группы вентилей, блок расшифровки состояний пар двоичных разрядов множителя и управления умножением, выходы двоичных разрядов регистра множимого соединены со входами вентилей, выходы вентилей, относящихся к 1-му разряду, под ключейы ко входам 1-го разряда накапливающего сумматора, выходы двух младших

XI

СО

ю VI

00

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

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

Целью изобретения является повышение быстродействие устройства

Поставленная цель достигается тем, что в устрЬйство умножения двоичных чисел, содержащее n-разрядный регистр множимого (n-разрядность сомножителей), сдвиговый регистр множителя, три группы по п элементов И и n-разрядный /трехвходовой накапливающий сумматор, причем выходы i-x элементов И первой, второй и третьей групп соединены соответственно о первым, вторым и третьим входами i-ro разряда п- разр&дного трехвходового накапливающего сумматора (I 1,2, .., п), дополнительно введены блок формирования пар двоичных разрядов утроенного значения множителя и п/2 дешифраторов состояний пар двоичных разрядов множимого, а сдвиговый регистр множителя имеет разрядность с нулевого по n-й разряды, причем выход нулевого разряда сдвигового регистра множителя соединен с первыми входами нечетных элементов И второй группы и первым входом блока формирования пар двоичных разрядов утроенного значения множителя, второй вход которого сое- динен с первыми входами четных элементов И второй группы и нечетных элементов И первой группы и выходом первого разряда сдвигового регистра множителя, выход второго разряда которого соединен с первыми входами четных элементов И первой группы и третьим входом блока формирования пар двоичных разрядов утроенного значения множителя, первый и второй выходы которого соединены с первыми входами соответственно нечетных и четных элементов И третьей группы, выходы j-ro и (jM)-ro разрядов n-рэзряднсго регистра множимого соединены соответственно с первым и вторым входами m-ro дешифратора состояний пар двоичных разрядов множимого 0 1- 3, §п-1, m 1, 2 п/2),

первый, второй и третий выходы которого соединены соответственно со вторыми входами j-ro и k-ro элементов И первой, второй и третьей групп (к 2, 4, 6,..,, п).

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

0 уменьшению быстродействия устройства,

На фиг. 1 приведена структурная схема устройства; на фиг. 2 - пример конкретной реализации блока формирования пар двоичных разрядов утроенного значения множи5 теля; на фиг. 3 - пример умножения.

Устройство (фиг. 1) содержит п-разряд- ный регистр 1 множимого, сдвиговый регистр 2 множителя, имеющий разряды с нулевого по п, первую группу 3 элементов И,

0 включающую в себя нечетные 4 и четные 5 элементы И, вторую группу 6 элементов И, включающую в себя нечетные 7 и четные 8 элементы И, третью группу 9 элементов И, включающую в себя нечетные 10 и четные

5 11 олемеиты 1/1, n-разрядный трехвходовой накапливающий сумматор 12, блок 13 фор- мирования пар двоичных разрядов утроенного значения множителя, дешифраторы 14 состояний пар двоичных разрядов множи0 мого, выход 15 нулевого разряда сдвигового регистра множителя соединен с первыми входами нечетных элементов И 7 второй группы 6 элементов И и первым входом 25 блока 13 формирования пар двоичных рэз5 рядов утроенного значения множителя, второй вход 26 которого соединен с первыми входами четных элементов И 8 второй группы б элементов И и нечетных элементов И 4 первой группы 3 элементов

0 И м выходом 16 первого разряда сдвигового регистра множителя, выход 17 второго разряда которого соединен с первыми входами четных элементов И 5 первой группы 3 элементов И и третьим входом 27 блока 13

5 формирования пар двоичных разрядов утроенного значения множителя, первый 18 и второй 19 выходы которого соединены с первыми входами соответственно нечетных 10 и четных 11 элементов И третьей группы

0 9 элементов И, выход 20 j-ro и выход 21 (j+1)-ro разрядов n-разрядного регистра множимого соединены соответственно с первым и вторым входами m-ro дешифратора 14 состояний пар двоичных разрядов

5 множимого 0 1. 3. 5n-1. m 1, 2. 3

п/2), первый 22, второй 23 и третий 24 выходы которого соединены соответственно со вторыми входами J-ro и k-ro элементов И первой 3, второй 6 и третьей 9 групп элементов И ( 2, 4, 6, ., п)

На фиг. 2 представлен пример конкретной реализации блока 13 формирования пар двоичных разрядов утроенного значения множителя. Блок содержит три инвертора 48-50, триггер 28, первую логическую схему 29, включающую в себя четыре элемента И 30-33 и элемент ИЛИ 34, вторую логическую схему 35, включающую в себя пять элементов И 36-40 и элемент ИЛИ 41, и третью логическую схему 42, состоящую из четырех элементов И 43-46 и элемента ИЛИ 47.

Первый вход 25 блока 13 соединен со входом инвертора 48 и первыми входами элементов И 30, 33. 38, 39, 43, 46, второй вход 26 соединен со входом инвертора 49, первыми входами элементов И 37, 44, 45 и вторыми входами элементов И 30,32,40,43, третий вход 27 подключен ко входу инвертора 50, вторым входам элементов И 37,38, 44, 46 и третьему входу элемента И 36, выход инвертора 48 соединен с первыми входами элементов И 31, 32, 36, 40, выход инвертора 49 подключен ко вторым входам элементов И 31.33. 36, 39, выход инвертора 50 соединен с третьими входами элементов И 39,40. прямой выход триггера 28 подключен ко второму входу элемента И 45, третьим входам элементов И 30, 31, 37, 46 и четвертому входу элемента И 39, инверсный выход триггера соединен с третьими входами элементов И 32, 33, 38 и четвертым входом элемента И 40, выходу элементов И 30-33 подключены ко входам элемента ИЛИ 34, выход которого соединен с первым выходом 18 блока 13, выходы элементов И 36-40 подключены ко входам элемента ИЛИ 41. выход которого соединен со вторым выходом 19 блока 13, выходы элементов И 43-46 подключены ко входам элемента ИЛИ 47. выход которого соединен со входом установки в единицу триггера 28

Устройство для умножения двоичных чисел работает следующим образом. Множимое размещается в регистре 1 (фиг. 1), множитель - в регистре 2. В первом такте умножения на выходах первого 16 и второго 17 разрядов регистра 2 формируются логические сигналы первого и второго двоичных разрядов множителя, которые поступают на входы злементов И 4, 5, 8. а также на второй 26 и третий 27 входы блока 13, На выходе 15 нулевого разряда регистра 2 в первом такте присутствует сигнал логического нуля, который подается на входы элементов И 7 и на первый вход 25 блока 13. Блок 13 формирует на своих выходах 18 и 19 первые два разряда кода утроенного значения множителя.

Логические сигналы пары двоичных разрядов множимого, поступающие на входы 20 и 21 дешифратора 14, формируют сигнал логической единицы на выходе 22 дешифратора, если на входах 21 и 20 присутствует сочетание сигналов 01, или 5 формирует сигнал единицы на выходе 23, есяи на входах 21 и 20 присутствует сочетание сигналов 10, или на выходе 24, если присутствует комбинация 11. В случае комбинации 00 не будет состояния логической 10 единицы ни на одном из выходов дешифратора. В зависимости от того, на каком из выходов m-го дешифратора будет присутствовать логическая единица, на входы т-й пары разрядов накапливающего сумматора 15 12 будут передаваться либо пара разрядов кода множителя через элементы И 4,5, либо пара разрядов кода удвоенного значения множителя через элементы И -7, 8, либо пара разрядов кода утроенного значения 0 множителя через элементы И 10, 11 п/2 пар разрядов, одновременно передаваемых через элементы И на входы накапливающего сумматора, сбставляют п-разрядное частичное произведение. Сформирован- 5 ное частичное произведение суммируется с содержимым накапливающего сумматора, которое на первом такте равно нулю После окончания распространения в накапливающем сумматоре переносов, произво- 0 дится сдвиг содержимого накапливающего сумматора и содержимого регистра множителя на два разряда в сторону младших разрядов.

Второй и последующие такты отличают- 5 ся от первого такта тем, что на выходах 16 и 17 появляются логические сигналы последующих пар разрядов кеда множителя, на выходах 18 и 19 блока 13 формируются последующие пары разрядов кода утроен- 0. ного значения множителя, а на входах накапливающего суШТатЪра образуются второе и последующие частичные произведения

Так как код удвоенного или утроенного 5 значения множителя может мметь дополнительную старшую (т/2 + 1)-ю пару разрядов, то количество тактов умножения равно п/2+ 1

Блок 13 (фиг, 2) формирования пар дво- 0 ичных разрядов утроенного значения множителя представляет собой параллельный двухразрядный двоичный сумматор Он формирует очередную пару двоичных разрядов кода утроенного значения множителя 5 путем суммирования очередных пар двоичных разрядов кода множителя и кода удвоенного значения множителя Удвоение значения множителя осуществляется сдвигом кода множителя на один разряд в сторону старших разрядов (влево), следовательно, блок 13 образует сумму пары 0+1V го, j-ro разрядов кода множителя и пары -го, (-1)-го разрядов удвоенного кода множителя. Таким образом, на блок 13 должны подаваться 0+1)-й, j-й и СН)-й разряды кода множителя. Сигналы этих разрядов снимаются с выходов 17,16 и 15 регистра множителя 2.

Младший разряд пары двоичных разрядов кода утроенного значения множителя формируется логической схемой 29, которая представляет собой трехвходовой одноразрядный двоичный сумматор без схемы переноса в следующий разряд. Схема переноса4 перенесена в логическую схему 35, которая формирует старший разряд. Логическая схема 35 представляет собой одноразрядный двоичный сумматор с внесенной в нее схемой предыдущего переноса, при этом сумматор не содержит схему переноса в следующий разряд. Логическая схема 42 формирует перенос из старшего разряда, который запоминается на триггере 28 и учитывается при обработке следующей пары двоичных разрядов множителя.

На фиг. 3 приведен пример умножения двух восьмиразрядных чисел в процессе формирования первого (фиг. 3, а), второго (3, б), третьего (3, в), четвертого (3, г) и пятого (3, д) частичных произведений, показано размещение кодов самого множителя, удвоенного и утроенного значения множителя, кода множимого, кодов в накапливающем сумматоре перед прибавлением к нему очередного частичного произведения и очередные частичные произведения, состоящие из 4-х пар двоичных разрядов. Младшая пара двоичных разрядов множимого содержит сочетание 01, которое возбуждает логическую единицу на выходе 22 первого дешифратора, вторая пара содержит сочетание 11, логическая единица формируется на выходе 24 второго дешифратора, третья пара - комбинацию 00 - на выходах третьего дешифратора формируются логические нули, четвертая пара разрядов множимого содержит сочетание 10, на выходе 23 четвертого дешифратора появляется логическая единица. Поэтому младшая пара двоичных разрядов первого частичного произведения (фиг. 2а) будет состоять из пары младших разрядов кода множителя, поступивших с выходов 16 и 17 через элементы И 4 и 5, вторая пара двоичных разрядов частичного произведения будет состоять из пары двоичных разрядов кода утроенного значения множителя, поступивших с выходов 8 и 19 блока 13 через элементы И 10 и 11, третья пара двоичных разрядов будет состоять из нулей, четвертая

пара - из пары разрядов кода удвоенного значения множителя, поступивших с выходов 15 и 16 регистра множителя через элементы И 7 и 8. Таким же образом образуются остальные частичные произведения после очередных сдвигов множителя в регистре множителя.

Общее время умножения в заявляемом устройстве Т3у « t3y(n/2+1), где t3y - время,

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

сдвиг. Если задержка сигналов на одном элементе И или на одном элементе ИЛИ равна т, то время формирования частичного произведения включает в себя время распространения сигналов в блоке 13 (2 г) (с

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

процессе суммирования время суммирования определяется временем распространения сквозного переноса через п разрядов накапливающего сумматора. Так как в сумматоре сигнал задерживается на

одном элементе И и- на одном элементе ИЛИ в каждом разряде, то общая задержка при распространении переноса составит 2п т. Затраты времени на сдвиг займут 3 т, так как триггеры могут быть представлены в

виде двух последовательно соединенных элементов И-НЕ с задержкой на каждом по т, плюс задержка г на элементе И, передающем сигналы с одного триггера на другой. В сумме время, затрачиваемое в заявляемом устройстве на один такт, равно t3y 3 т + 2п т + 3 т 2п т + 6 г. а время, затрачиваемое на п/2+1 тактов составляет Тзу (2пг+6г)(п/2 + 1) n2 r+5nr+6t. Так как формирование произведения в последнем такте умножения заканчивается прибавлением частичного произведения и в дальнейшем сдвиг готового произведения производить не нужно, время последнего сдвига (3 т) исключается из Т3у . Таким

образом, время выполнения операции умножения в заявляемом устройстве Т3у п2 Г+бпг 4-Зт.

В устройстве-прототипе время, затрачиваемое на формирование частичного пройзведения такое же, как и в заявляемом устройстве, так как вместо блока 13 в устройстве-прототипе имеется блок выработки сигналов управления группами вентилей, содержащий четыре логических схемы ИИЛИ и триггер переноса, и задерживающий сигналы на 2 г. Затраты времени на сдвиг останутся теми же, что и в заявляемом устройстве (3). Время распространения сквозного переноса в накапливающем сумматоре в устройстве-прототипе больше по сравнению с временем в трех старших знаковых разрядах сумматора без учета последнего переноса, который отбрасывается, т.е. на 5 т. Количество тактов умножения остается тем же. Длительность такта умножения в устройстве-прототипе равна tyn 3 т + +2п т +5 т +3г 2пт+11г, а время выполнения (п/2+1) тактов - ТугГ - n T+. +7,5п т + 11 г. В последнем такте сдвиг готового произведения не производится. Таким образом, время выполнения операции умножения в устройстве-прототипе ТУп ггг+7,5пг +8 т.

Сравнительные данные по затратам времени на умножение в зависимости от величины n для заявляемого устройства и устройства-прототипа приведены в таблице.

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

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

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

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

первой группы и выходом первого разряда сдвигового регистра множителя, выход второго разряда которого соединен с первыми входами четных элементов И первой группы и третьим входом блока формирования пар двоичных разрядов утроенного значения множителя, первый и второй выходы которого соединены с первыми входами соответственно нечетных и четных элементов И третьей группы, выходы j-ro и (j+1)-ro разрядов n-разрядного регистра множимого соединены соответственно с первым и вторым

входами пт-го дешифратора состояний пар двоичных разрядов множимого Q 1, 3. 5.

..., n-1, m 1. 2п/2) первый, второй и

третий выходы которого соединены соответственно с вторыми входами J-ro и k-ro

элементов И первой, второй и третьей групп (k - 2, 4, 6n).

Фиг. i.

Фиг. 2.

Множитель

Регистр множители

Накапливающий суннамор с JipedudtjmUH tocmutHUM Произведением

Hoboe частичное hp6utt tfanue / на fax одах групп злемгнтой И

3 t 1 1 о AI

О

Дешисрреторы - Pe.vue.mp множимою

0t t 1 о 1

0160 f{

«

г.

Выходы 18,1$ Ьлоы 13

&шоды&.16 регистра 2

Вшоды f6,t7 petucntpo 2

6111

0100

в

ripou$t c)eHue