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

(54) УСТРОЙСТВО ДЛЯ УМНОЖЕНИЯ

Изобретение относится к области вычислительной техники и предназначено для использования в арифметических устройствах цифровых вычислительных Мсиаин. Известны последовательные умножающие устройства, содержащие последовательный двоичный сумматор 1 и 2. В таких устройствах умножение двух т-р аз рядных чисел. А а, .,.. а и В Ь, Ь,м ..гЦ выполняется за 2т циклов, причем в первом цикле вырабатывается одно элементарное произведение (а,Ь), во-втором два ( и и т.д., в 2т-м одно () . В каждом цикле вычисляется сумма всех элементарных произведений данного цикла, младший разря которой дает соответствую1ций разряд результата (окончательного произведе ния) , а старшие - переносы, учитывае мые в следующих циклах. Элементарными произведениями в каждом цикле являются произведения всевозможных пар цифр сомножителей таких, что сумма весов разрядов любой пары равна k+1 где k - номер цикла. Количество суммируемых элементарных произведений от 1-го до т-го цикла увеличивается на единицу, а от т-го до 2т-го уменьшается на единицу. Необходимость суммировать большое количество элементарных произведений (до т) является недостатком известных устройств, который обуслсшливает большую длительностьiоперации умножения и усложняет сумматор. Логические метода ускорения умножения в известных последовательных умножающих устройствах не применяют.ся. Наиболее близким поIтехнической сущности к предлагаемому является устройство для умножения, в котором для ускорения операции умножения используется древовидный многовходовый последовательный сумматор, на котором одновременно суммируются все элементарные произведения каждого цикла ЗЦ. Однако большое количество элементарных Произведений (до т) сохраняется, вследствие чего сумматор должен иметь m входов, а сложность сумматора, в свою очередь, приводит к снижению быстродействия. Цель изобретения - упрощение устройства и повышение его быстродействия. Указанная цель достигается тем, что устройство для умножения, содер жащее регистры множимого и множител и лшоговходовой одноразрядный сумма тор, содержит коммутатор, преобразо ватель прямого кода в обратный и пре оёразователи прямого кода в дополнительный, .счетчик и элементы И, ИЛИ, НЕ причем m управляющих входов (Е1 раэрядность операндов) коммутатора подключены к выходам преобразователя прямого, кода в обратный, информационные входы которого соединены с выходами регистра множителя, а управляющий вход - с выходом перепол нения счетчика (разрядность которого равна ) и с управляющим входом пер вого преобразователя прямого кода в дополнительный, -информационный вход которого подключен к выходу мноГовхо дового одноразрядного сумматора, вхо ды которого с первого по m/2-ый соединены соответственно с выходами коммутатора с-первого по ( - -1)-ый и выходом элемента ИЛИ, m информационных входов коммутатора подключены к соответствуюьшм выходам регистра Множимого, вход которого подключен ко входу множимого устройства, вхйд множителя устройства подключен ко входу регистра,множитёЛя, и ко входу счетчика, выход переполнения которого подключен к первым входам Первого и второго элементов и и через элемент НЕ - к первому входу третьего элемента Н, второй вход которого Соединен с Ш-ым выходом коммутатора, второй вход второго элемента И соединен с выходом первого разряда регистра множимого, выход {m+i)-ro разряда которого через второй преобразователь прямого кода в дополнительный подключен ко второму входу первого элемента И, третьи входы первого и второго элементов И соединены соответственно с первым и вторым управляющим входами устройства, входы элемента ИЛИ подключены к выходам элементов И. На чертеже приведена функциональная схема устройства для умножения. Устройство содержит т-разрядный регистр 1 множимого, т-разрядный регистр 2 множителя, многовходовый одноразрядный (последовательный двоичный) сумматор 3, дополнительный (п1+1)-ый разряд 4 регистра множимого элемент 5 НЕ, элементы б, 7 и 8 И, элемент 9 ИЛИ, преобразователь 10 прямого кода в обратный, преобразова тель II прямого кода в дополнительный, преобразователь 12 прямого кода в дополнительный, коммутатор 13 и счетчик 14, , Вход счётчика 14 соединен со входом регистра 2 множителя. Выход переполнения счетчика 14 подключен к управляющим входам преобразователя 10 кодов и преобразователя 11 кодов, к первым входам элементов б и 7 И, а также - через элемент 5 НЕ - к первому входу элемента 8 И. Информационные входы преобразователя 10 кодов соединены поразрядно с выходами одноименных разрядов регистра 2 множителя, а выходы - с управляющими входами коммутатора 13, информационные входы которого соединены поразрядно с выходами соответствующих разрядов регистра 1 множимого. Выход первого разряда регистра 1 множимого соединен, кроме того, со вторым входом элемент 7 И, а выход дополнительного (m-fl)-ro разряда 4 регистра множимого - через преобразователь 12 кодов - со вторым входом элемента 6 И. Первые (-1)-и информационные выходы коммутатора 13 соединены с одноименными входами многовходового одноразрядного последовательного двоичного сумматора 3, а -и информационный выход - со вторым входом элемента 8 И. Выходы элементов б, 7 и 8 И. соединены со входами элемента 9 ИЛИ, выход которого подключен к входу сумматора 3, выход которого соединен с информационным входом преобразователя 11 кодов. На третий вход элемента 7 И поступают тактовые импульсы 1-го - т-го циклов, а на третий вход элемента 8 И -(т+1)го - 2п1-го циклов. Преобразователи кодов 10, 11 и 12 могут быть выполнены по любой известной схеме, обеспечивающей при отсутствии сигнала на управляющемвходе выдачу прямого кода, а при наличии этого сигнала - обратного (дополнительного) кода двоичного числа, поступающего на информационные входы преобразователя. Коммутатор 13 имеет m управляющих входов, m информационных входов и информационных выходов и обеспечивает подключение к своим информационным выходам тех и только тех информационных входов, которым соответствуют единичные сигналы на одноименных управляющих входах. Работа устройства основана на следующих соображениях (достаточно рассмотреть случай, когда m - четное). Если количество единиц в коде множителя С меньше или равно -, то выполняется обычное умножение прямых кодов сомножителей (А . В) . Если же , -, то вместо этого множимое А умножается на условный множитель -В. Так как при этом получается условное произведение -АВ, то для получения правильного результата необходимо на выходе устройства изменить знак полученного условного произведения. Умножение, выполняется в дополнительных кодах. А Б- АхВзо„.,.1 2 Эоп1зоп--(А.,1 Практический смысл этих преобразо ваний заключается в том, что код Во (при С -j) обязательно содержит мень ше, чем - единиц. Значит, в любом случае достаточно иметь входов многовходового последовательного двоичного сумматора. Действительно, если i , то выполняется обычное умножение положительных чисел и с помощью коммутатора 13 ко входам сумматора 3 подключаются выходы р егистра 1 множимого, соответствующие единицам множителя, которых не больше,, чем -Если . 7 f ТО значит в обратном коде множителя не более, чем ( - - единиц. Поэтому для вьгчисления выражения (А« Воср) достаточно иметь ( - ) вход сумматора. Еще один вхо (а -и) необходим для суммирования этого выражения с поправками Аи , причем обе эти поправки могут подаваться на один и тот же вход сумматора, так как при последователь ном сложении их коды разделены во времени:-код поправки .Ад рдолжен подаваться непосредственно после око окончания подачи кода А, Как видно из приведенного описания, для работы устройства необходи МО, чтобы ко входам сумматора подкл чались все выхода регистра множимого, соответствующие единицаии множителя либо все выходы регистра множи мого, соответствующие нулям множите ля. Эти функции выполняет коммутато 13, управляемы соответственно прямым или обра;тным кодом множителя. Устройство работает следующим об разом. Сначала множитель В вводится в регистр 2 множителя таким образом, чтобы его младший разряд оказался в 1-м разряде регистра 2. При этом счетчик 14 подсчитывает количество единиц в коде множителя. Так как эт счетчик имеет емкость - , он выдает сигнал переполнения только в том случае, когда , Сигнал переполн ния поступает на управляющие входы преобразователей 10 и 11 кодов, а также на первые входы элементов б и 7 И и через элемент 5 - на первый вход элемента 8 И. После этой подго товки начинается собственно умножение, которое состоит из 2т циклов. При выполнении-этих циклов множител остается неподвижным в регистре 2, а множимое А последовательно продви гается (младшимиразрядами вперед) через регистр 1 множимого. Кроме то го, в 1-м -, т-м циклах тактовые импульсы подаются на третий вход элемента 7 И, а-в (in+l)-M - 2т-м циклах - на третий вход элемента, б И. Как видно из функциональной схемы при этом выполняется умножение в соответствии с выражением (1). Благодаря описанной конструкции, максимальное количество элементарных произведений, подлежащих суммированию на многовходовом последовательном двоичном сумма-горе, уменьигается-в два раза по сравнению с известными устройствами. Это обеспечивает соответствующее упрощение cyNwiaTopa, и, как следствие, - увеличение быстродействия умножающего устройства. Формула изобретения Устройство для умножения, содержащее регистры множимого и множителя и многовходовой одноразрядный сумматор, отличающеес я тем, что, с целью упрощения устройства и повыаени.я его быстродействия, устройство содержит коммутатор, преобразователь прямого кода в обратный и преобразователи прямого кода в дополнительный, счетчик и элементы И, ИЛИ, НЕ, причем m управляюир х входов (т разрядность операндов) коммутатора подключены к выходам преобразователя прямого кода в обратный, информационные входы которого соединены с выходами регистра множителя, а управляю- щий вход - с выходом переполнения счетчика (разрядность которого равна - ) и с управляющим входом первого преобразователя, прямого кода в дополнительный, информационный вход которого подключен к выходу многовходового одноразрядного сумматора, входы которого с первого по -ый соединены соответственно с выходами коммутатора с первого ПО (-1)-ый;и выходом элемента ИЛИ, m информационных входов коммутатора подключены к соответствующим выходам регистра множимого, вход которого подключен ко входу множимого устройства, вход множителя устройства подключен ко входу регистра множителя и ко входу счетчика, выход переполнения которого подключен к первым входам первого и второго элементов И и через элемент НЕ - к первому входу третьего элемента И, второй вход которого соединен с m/2-ым выходом коммутатора, второй вход второго элемента И соединен с выходом первого разряда регистра множимого, выход (га+1)-го разряда которого через второй преобразователь прямого кода в дополнительный подключен ко второму входу первого элемента И, третьи входы первого и второго элементов И соединены соответственно с первым и вторым управляющим входами устройства, входы элемента ТИЛИ подключены к выходам элементов И.

Источники информации, принятые во внимание при экспертизе

1, M.Lehman et al Serial arithmetic technigues,Proc. AFIPS FJCC, 1965, p. 715-725.

i. Авторское свидетельство СССР №409222, кл. G06 F 7/39. 1974.

3. Baker .P.W., McCrea P.G. A highspeed serial tree multiplier, Digital Processes, 1975,1, 4, pp. 343349 (прототип)..