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

 

УСТРОЙСТВО ДЛЯ УМНОЖЕНИЯ, содержащее п-разрядный регистр множимого , п блоковвычисления разрядных значений произведения, п буферных тпti 1 2 l-ji; .; .-хт-;.-.. (., д.-4 -..- -i, i i,.i-2 Utir-fc.jt..u,L- 4-W-rTfJj. |.,,i «HVittaJ регистров первой группы и п буферных регистров второй группы причем входы буферных регистров первой группы соединены с первыми выходами старшего разряда соответствующих блоков вычисления разрядных значений произведения, первый вход 1-го блока вычисления разрядных значений произведения (I 1, 2,...,п )/соединен с выходом i-ro разряда регистра множимого, второй вход .с входом множителя устройства, третий вход - с выходом I-го буферного регистра первой группы, отличающеес я тем, что, с целью повышения быстродействия , входы буферных регистров второй группы соединены с вторыми выв § ходами старшего разряда соответству (Л ющих блоков вычисления разрядных значений произведения, четвертый вход i-ro блока вычисления разрядных значений произведения соединен с выходом i-го буферного регистра второй группы , а пятый вход - с выходом младшего разряда

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

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

РЕСПУБЛИК дд G 06F 7/52

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

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

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

ПО ДЦЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ (21 ) 3439828/18-24 (22 ) 17.05.82 (46 ) 30. 08. 83 ° Бюл, N 32 (72) Г. П. Лопато, l. Г. Лопато и А, А. Шостак (71) Минский радиотехнический институт (53) 681 ° 325(088,8) (56) 1. Авторское свидетельство СССР

769539, кл. G 06 F 7/52, 1977.

2. Авторское свидетельство СССР

O 763897, кл. G 06 F 7/52, 1978.

3. Авторское свидетельство СССР 1 7695401 кл. G 06 F 7/52, 1978.

4. Авторское свидетельство СССР

» 888109, кл, G 06 F 7/52) 1978.

5. УЙ11д H. Н, Fully ilerative

fast array for binary multiplication and addition.- "Electronics

Letters", 1969, vol, 5, " 12,р.263.

6. Dean К. I. Versatile multip1ier arrays.-"Electronics 1е1 егэ", 1968, vo l . 4. 11 16, рр ° 333-334.

7. шостак A. А. О разработке быстродействующих однородных множительных структур.- В сб . "Автоматики и вычислительная техника", Минск, 1980, вып,10, с. 132-138. (54)(57) устРойстВо для уиножкння, содержащее и-разрядный регистр множи" мого, и блоков вычисления разрядных значений произведения, и буферных

„„SU„„, 1038937 A регистров первой группы и и буферных регистров второй группы, причем входы! буферных регистров первой группы соединены с первыми выходами старшего разряда соответствующих блоков вычисления разрядных значений произведения, первый вход i-го блока вычисления разрядных значений произведения (i = 1, 2>...,n) соединен с выходом 1-ro разряда регистра множимого, второй вход.с входом множителя устройства, третий вход - с выходом i-го буферного регист. ра первой группы, о т л и ч а ю щ е ес я тем, что, с целью повышения быстродействия, входы буферных регистров второй группы соединены с вторыми вы" с2 ходами старшего разряда соответству9 ющих блоков вычисления разрядных значений произведения, четвертый вход

1-го блока вычисления разрядных значе- С ний произведения соединен с выходом

i--го буферного регистра второй rpуппы, а пятый вход — с выходом младшего разряда (1+1)-ro блока вычисления <ю разрядных значений произведения, © выход младшего разряда первого блока вычисления разрядных значений произведения подключен к выходу устройст- 1© ва, пятый вход последнего блока вычисления разрядных значений произве дения соединен с входом коррекции устройства °

1038937

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

10 и микропроцессорных систем.

Известно устройство для умножения, содержащее регистры множимого. и множителя накапливающий сумматор, n/2 одноразрядных узлов умножения (n-раз- 15 рядность множимого) и блок управле" ния, выходы которого соединены с управляющими входами регистров множимого множителя и накапливающего сумматора, первый вход i"го одноразряд" ного узла умножения (i = 1,2,...,n/2 ) соединен с выходом первого разряда регистра множителя, а второй вход — с выходом (2i-1)-го разряда регистра множимого, выходы одноразрядных узлов 25 умножения соединены с соответствующими входами накапливающего сумматора.

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

N)2 31 3.

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

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

Эти устройства также предназначены для перемножения чисел в произвольной позиционной системе счисления с основанием М>2 (2 j, (3 1.

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

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

I ° (n = 1,2, .. °,n) соединен с выходом

1 го разряда регистра множимого, второй вход - с входом множителя устройства, третий вход - с выходом i-го буферного регистра первой группы, четвертый вход - с выходом, (i+1 )-ro буферного регистра второй группы, выход первого буферного регистра второй группы подключен к выходу устройст" ва, четвертый вход последнего блока вычисления разрядных значений пооиэведения соединен с входом коррекции устройства, Известное устройство предназначено для перемножения чисел в произвольной позиционной системе счисления с осно ванием N ) 2. В частности, интересен случай использования в-ично-кодированной системы счисления с основанием и = В (когда в-ичные разряды группиK руются пс К, где К - целое число и большее единицы ), при использовании которой имеется принципиальная возможность повысить быстродействие устройства примерно в К раз по сравнению со случаем использования в-ичной системы счисления. Особый интерес представляет устройство в случае перемножения двоично-кодированных операндов в системе счисления с основанием и = 2 °

К

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

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

3 1038 использованию более высокого основания N=B в-ичнокодированной системы счисления, так как это сокращает число тактов работы устройства. Однако сокращение числа тактов за счет уве5 личения основания приводит к существенному увели чению длительности самого такта (длительность такта определяется в основном скоростью работы блоков вычисления разрядных эна- «О

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

Но тогда даже при использовании двоично-кодированной 16-ричной системы счисления. (т,е. когда 8=2, К 4 и N = 2 = )6) для реализации кажА дого блока вычисления разрядных значений произведения требуется постоянная память емкостью 2 =65536

8-разрядных двоичных слов. А это не позволяет реально обеспечить высокую скорость работы блоков вычисления разрядных значений произведения при сколь-нибудь больших значениях К, даже если снять ограничения на обьем используемого в устройстве умножения оборудования. Реализация

30 же блоков вычисления разрядных значений произведения по матричному принципу, например, в виде однородной ячеечной структуры P5 ), наряду с многими достоинствами также не обеспечивает их высокого быстродействия, так как время формирования результата на их выходах при использовании двоично-кодированной системы счисления с основанием М = 2 составляет величину (2К-1) С, где "с - задержка сигнала на одной ячейке.

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

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

937 4 вычисления разрядных значений произведения, первый вход i-ro блока вычисления разрядных значений произведения (i = 1,2,...,n ) соединен с выходом 1-го разряда регистра множимого, второй вход — с входом множителя устройства, третий вход - с выходом

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

« ão блока вычисления разрядных значений произведения соединен с выход «ом «-го буферного регистра второй

««-руппь«, а пятый вход - с выходом младшего разряда (i+1)-го блока вычисления разрядных значений произведения, выход младшего разряда первого блока вычисления разрядных значений произ" ведения подключен к выходу устройства, пятый вход последнего блока вычи" сления значений произведения соединен с входом коррекции устройства.

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

Устройство для умножения (фиг.1) содержит и-разрядный регистр 1 множимого, п блоков 2 вычисления разряд" ных значений произведения, и буферных регистров 3 первой группы и и буферных регистров 4 второй группы, вход 5 множителя устройства, вход 6 коррекции устройства и выход 7 устройства. Первый вход i-го блока вычисления разрядных значений произведения (-i (,2, ...,n) соединен с выходом 8 i-ro разряда регистра 1 множимого, второй вход - с входом 5 множителя устрой" ства, третий вход - с выходом «-го буферного регистра 3 первой группы, четвертый вяод - с выходом 1-го буферного регистра 4 второй группы и пятый вход соединен с выходом 9 младшего разряда (1+1)-ro блока 2 вычисления разрядных значений произведения. Первый

10 и второй 11 выходы i-ro блока 2 вычисления разрядных значений произве дения соединены с входами i-ых буферных регистров 3 и 4 первой и второй групп соответственно. Пятый вход и-го (самого старшего) блока 2 вы937 6

Сумма Б=a®d®e

5 1038 числения разрядных значений произведения соединен с входом 6 коррекции устройства, выход 9 младшего разряда первого (самого младшего.) блока 2 вы" числения разрядных значений проиэве"

5 дения подключен к выходу 7 устройст" ва.

Совокупность i-ro блока 2 вычис" ления разрядных значений произведения и i-ых буферных регистров 3 и 4 ið первой и второй групп соответственно может быть конструктивно выполнена в виде единого модуля 12, реализован" ного, например, как большая интегральная схема. Не составляет особого тру- 15 да включение в этот модуль, если это конечно будет признано целесообразным, 1-ых разрядов регистра 1 мно" жимого и регистра множителя (не показан) в качестве его третьего и чет- 2р вертого буферных регистров. Это обеспечивает однородность устройства умножения на уровне идентичных модулей 12. Все триггеры устройства могут быть реализованы на двух тактных синхронных D"триггерах (цели синхронизации не показаны ).

На фиг. 2 показан один из возможных вариантов реализации 1-го блока 2 вычисления разрядных значений произведения в виде однородной ячеечной структуры (здесь предполагается, что в устройстве используется в-ично-кодированная система счисления с основанием М 8,причем

К принято равным четырем ). Блок 2 содержит К2 идентичных ячеек 13,образующих итеративную сеть, подобную описанной в f7 ) и формирующую старшую в-ично"кодированную N-ичную цифру разрядного произведения в виде двух в-ично-кодированных N-ичных цифр (цифры суммы и цифры переноса), как это сделано, например, в 6 3 для случая в=2. 8 блоке 2 производится умножение в-ично-кодированной М-ичной

)( но-кодированную N-ичную цифру множителя У; = У, У У У „(возрастание индексов при буквейных обозначениях принято в направлении старших разрядов ), а также прибавление к младшей в-ично-кодированной й-ичной цифре получившегося при этом разрядного ïðîизведения двух в"ично-кодированных й-ичных цифр И, R и К старшей 55 в-ично-кодированной й-ичной цифре разрядного произведения одной в-ично-кодированной й-ичной цифры L„"+".

Цифра множимого Х поступает йа первый вход блока 2 с выхода 8 i-ro разряда регистра 1 множимого, цифра множителя У подается на второй вход блока 2 с входа 5 устройства, цифры М, R поступают на третий и четвертый входы блока 2 с выходом

i-ых буферных регистров 3 и 4 первой и второй групп соответственно, цифра I„ +"ïoäàåòcÿ на пятый вход блока 2 с выхода 9 младшего разряда (1+1)-го блока 2 вычисления разрядных значений произведения.На выходе

9 1-ro блока 2 вычисления разрядных значений произведения формирует" ся младшая в-ично-кодированная N"è÷; ная цифра разрядного произведения Р, а на выходах 10 и 1 1 образуется старшая в"ично-кодированная N-ичная цифра разрядного произведения Р в виде двух в"ично"кодированных й-ичных цифр соответственно Р", Р „(цифра

1 с" с"

Р,образована поразрядными в-ичными суммами, а цифра P i- поразрядными в"ичными переносами ).

На фиг. 3 приведена функциональная схема ячейки 13, используемой в блоке 2 вычисления разрядных значений произведения на фиг,2 для случая, когда в=2, т.е. когда в устройстве применяется двоично-кодированная система счисления с основанием и = 2".

Ячейка !3 содержит одноразрядный двоичный сумматор 14, двухвходовой элемент И 15 и функционирует в соответствии со следующими логическими:выражениями:

Перенос С = с(Л d Ч (a@+) сЦЛ е где d д

Устройство для умножения работает следующим образом, В исходном состоянии буферные регистры 3 и 4 всех модулей 12 обнулены, в регистре 1 множимого хранится без знака n"ðàçðÿäíûé в-ичный код множимого (n ° k - разрядный вичный код множимого), В каждом из и первых тактов работы устройства на его вход 5 поступает параллельно К в-ичных разрядов множителя, начиная с его младших разрядов (предполагается, что множимое и множитель имеют одинаковую разрядность ).При этом в i"ом блоке 2 вычисления разряд"ных значений произведения осуществляется умножение К в-ичных разрядов множителя, поступающих на

10389 его второй вход с входа 5 устройства, на К в-ичных разрядов множимого, поступающих на его первый ,вход с выхода 8 i-го в"-ичного разряда регистра 1 множимого, и 5 прибавление к К младшим в-ичным разрядам получившегося при этом

2К-разрядного произведения череэ третий и четвертый входы К старших в-ичных разрядов произведения 1-го блока 2, сформированMblx в предыдущем такте в двухряднрм коде и хранимых е буферных регистрах 3 и 4

i-го модуля 12, а также прибавление через пятый вход К к старшим в-ичным разрядам 2К-разрядного произведения

К младших в-ичных разрядов 2К-разрядного произведения i-го модуля 12, формируемых в данном такте на выходе 9 (i+1)-го блока 2 вычисления раз- 20 рядных значений произведения. После этого К старших в-ичных разрядов 2Кразрядного произведения, представленных в двухрядном коде, с выходов 10 и 11 i ãî блока 2 записываются в

1-ые буферные регистры 3 и 4 соответственно.

После выполнения и первых тактов работы устройства на его вход 5 поступает нулевая информация и далее 50 .осуществляется еще дополнительно и тактов, в течение которых иэ устройства выводится с соответствующим . преобразованием информация, хранимая в буферных регистрах 3 и 4 всех моду- З5 лей 12. Вывод 2п-разрядного произведения сомножителей в устройстве осуществляется через его выход 7 в параллельно-последовательном коде (по К s"è÷íûõ разрядов в каждом.:так- 4О те).8 рассмотренном случае на вход 6 коррекции устройства во всех его и дополнительных тактах подается К-раз-. рядный е-ичный код 00 ... 000 . В тех

45 случаях, когда требуется получить округленное п-разрядное произведение, необходимо в самом начале процесса умножения (например, до приема сомножителей) пбдать на вход 6 коррек50 ции устройства К-разрядный в-ичный

К которой задержкой запись результатов, сформированных на выходах бло- 55 ков 2 вычисления разрядных произведе. ний, е буферные регистры 3 и 4 модулей 12. В результате этого в буфер37 8 ном регистре 3 последнего модуля 12 будет записан код Ъ|2 0,.000 кото I

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

Очевидно, что используя определенным образом вход 6 коррекции устройства, можно одновременно осуществляТь операцию умножения и-разрядных в -ичных чисел Х и У с суммированием и-разрядного в -ичного слагаемого Z, т.е.

К в одном цикле работы устройства set. полнять сложную функцию

Q= Х Y+ 2

Для этого необходимо в течение и первых тактов рработы устройства пода-: вать на его вход 6 коррекции в каждом такте К в-ичных разрядов слагаемого Z, начиная с его младших разрядов, причем это прибавление может осуществляться либо к округленным и старшим разрядам произведения Х ° Ó, либо просто к усеченным его и стар" шим разрядам. следует особо отметить, что умножение и-разрядных чисел в предла- ° гаемом устройстве, можно выполнять за (n+1) тактов, если после выполнения и-го такта содержимое буферных регистров 3 и 4 всех модулей 12 подать для окончательного суммирования на соответствующие входы быстродействующего двухвходового сумматора (на фиг. 1 эти дополнительные цепи; передачи информации с выходов бу,ферных регистров 3 и 4 отмечены штриховыми линиями ).Это может быть целесообразным, если, например,арифметико-логическое устройство ЭВИ содержит подобный быстродействующий сумматор.

Таким образом, окончательное произ ведение в предла га емом уст рой ст ве, так же как и е f4 ), может .быть сформировано за 2п или (и+1) тактов.Од" нако длительность выполнения одного такта е предлагаемом устройстве существенно сокращена. Действительно, пусть в известном и предлагаемом устройствах применяется в-ично-кодированная в -ичная система счисления и при реализации блоков вычисления разрядных значений произведения е известном устройстве используется быстродействующая однородная ячеечная структура, подобная описанной в (7 )., а в предлагаемом устройстве - ячеечная структура, изобра10

1038937

9 женная на йиг.2 (основное отличие структур, показанных на фиг.2,3 от структур, описанных в 7 ) состоит в том, что во-первых, старшая в -ичная цифра разрядного произведения форми- 5 руется в виде двух цифр, т.е, в двухрядном коде, в то время,l.êàê, во-вторых структурах эта цифра обра" зуется в однорядном коде). Тогда в предлагаемом устройстве длительность" одного такта работы примерно равна К ., в то время, как в известном устройстве эта длительногTb составляет величину (2К-1), так как на приве" дение переносов при формировании старшей в-ично кодированной в -ичной цифры разрядного произведения в его блоках вычисления разрядных значений произведения затрачивается время (K -1)Т .(здесь через обозначена задержка информации в одной ячейке блока вычисления разрядных значений произведения ).

Предлагаемое устройство для умножения чисел при там же объеме используемого оборудования обеспечивает в (2К-1)К раза более высокое быстродействие, чем известное. Оно может быть изготовлено из множества однотипных взаимоЗаменяемых модулей, кнжцый из которых удобен для реализации в виде БИС, причем переход от уст,ройства с большим к устройствам с яа-! лым форматом обрабатываемой информации и наоборот фактически сводится к пропорциональному уменьшению либо увеличению числа используемых модулей.

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

Ф4Р f

1 038937

Р

PL(2. 5

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

Техред C Ми гунова. Корректор И. Демчик

Редактор Н.Стащишина

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

Заказ 6231/55 Тираж 706 Подписное

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

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