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

СОЮЗ СОВЕТСКИХСОЦИАЛИСТИЧЕСКИХРЕСПУБЛИК 389 0 06 Е 7/52 ПИ ИЗО ЕН ТОРСНОМУ СВ ЕЛЬСТ 18" 24(53) 681.325 (56) 1. Авто769539, кл Бюл, М 32пато, И. Г. Лкрадиотехническ опато нс 96 НЯ,множдныхых ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР ПО ДЦЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТ(088,8 )рское свидетельство ССС 06 Р 7/52, 1977.2. Авторское свидетельство СССР М 763897, кл. С 06 Р 7/52, 1978.3. Авторское свидетельство СССР 11 769540, кл. С 06 Р 7/52, 1978.Авторское свидетельство СССР И 888109, кл. С 06 Р 7/52 1978.5. Уц 11 д Н. Н, Гц 11 у 11 егат.1 че 1 аэ 1 аггау Уог Ь 1 пагу ац 1 г 1 р 11 сай 1 оп апд адд 1 й 1 оп. - Е 1 есйгоп 1 сэ 1.есегэ, 1969, чо 1, 5, 1 ф 12,р.2636. Оеап К. . чегэат 11 е па 1 й 1 р 11 ег аггауэ,-"Е 1 ес 1 гоп 1 сэ 1.е 11 е гэ 1 8, чо 1. 4. У 16, рр. 333-334.7. шостак А, А, О разработке стродеиствующих однородных множительных структур.- В сб . "Автомаи вычислительная техника" Минск1980, вып,10, с. 132-138.(5")(57) УСТРОЙСТВО ДЛЯ УИНОЖЕНсодержащее и-разрядный регистрмого, и блоков вычисления раэрязначений произведения, и буферн регистров первой группы и и буферных регистров второй группы, причем входы буферных регистров первой группы соединены с первыми выходами старшего разряда соответствующих блоков вычисления разрядных значений произведения, первый вход 1-го блока вычисления разрядных значений произведения (1 = 1, 2,п ) соединен с выходом 1-го разряда регистра множимого, второй вход,- с входом множителя устройства, третий вход - с выходом 1-го буферного регистра первой группы, о т л и ч а ю щ е ес я тем, что, с целью повышения быстродействия, входы буферных регистров второй группы соединены с вторыми вы" с ходами старшего разряда соответствуе ющих блоков вычисления разрядных значений произведения, четвертый вход 1-го блока вычисления разрядных значе Се ний произведения соединен с выходом 1-го буферного регистра второй грУппь а пятый вход - с выходом младшего разряда (1+1)-го блока вычисления разрядных значений произведениявыход младшего разряда первого блока вычисления разрядных значений произведения подключен к выходу устройст ва, пятый вход последнего блока вы- фф числения разрядных значений произве- ф 3 дения соединен с входом коррекции устройстваИзобретение относится к вычислительной технике и может быть использовано .при разработке быстродействующих устройств для умножения чиселпредставленных в любой позиционной 5системе счисления, Особенно эффективно его применение при использованиибольших интегральных схем, в частности, при разработке высокопроизводи"тельных наращиваемых микропроцессоров10и микропроцессорных систем.Известно устройство для умножения,содержащее регистры множимого. и множителя накапливающий сумматор, и/2одноразрядных узлов умножения (и-разрядность множимого) и блок управле"ния, выходы которого соединены с управляющими входами регистров множимого, множителя и накапливающего сум"матора, первый вход "го одноразряд"ного узла умножения (1 = 12п/2 )соединен с выходом первого разрядарегистра множителя, а второй вход - свыходом (21-1)-го разряда регистрамножимого, выходы одноразрядных узлов 25умножения соединены с соответствующими входами накапливающего сумматора,Данное устройство может быть ис"польэовано для умножения чисел,пред- З 0ставленных в произвольной позиционной системе счисления с основаниемй)2 13.Основным недостатком известногоустройства является низкое быстродействие, вызванное в первую очередьдвухша говым .принципом обработки од"ной цифры множителя. Кроме этого дляустройства характерна низкая эффективность при реализации его на больших 40интегральных схемах (устройство кроме однотипных одноразрядных узлов умножения содержит регистры множимогои множителя с цепями сдвига, накапливающий сумматор с распространением 45переноса и с цепью сдвига, а такженесколько сложный блок управления ).Известны устройства для умножения, содержащие регистры множимого имножителя, накапливающий сумматор и 50и операционных модулей.Эти устройства также предназначены для перемножения чисел в произвольной позиционной системе счисленияс основанием М 2 21,1.3 1.Основными недостатками устройствявляются относительно низкое быстродействие и невысокая эффективность при реализации их на больших интегральных схемах.Наиболее близким к предлагаемомуявляется устройство дгя умножения,содержащее и-разрядный регистр множи,мого, и блоков вычисления разрядных значений произведения, и буферных регистров первой группы и и буферных регистров второй группы,при"чем входы буферных регистров первойи второй групп соединены соответственно с выходами ствршего и младшегоразряда соответствующих блоков вычисления разрядных значений произведения, первый вход 1"го блока выцисле"ния разрядных значений произведения1(и = 1,2,п) соединен с выходом1-го разряда регистра множимого, второй вход - с входом множителя устройства, третий вход - с выходом 1-гобуферного регистра первой группы, четвертый вход - с выходом, (1+1 )-го буферного регистра второй группы, выходпервого буферного регистра второйгруппы подключен к выходу устройст"ва четвертый вход последнего блокавычисления разрядных значений пооиэведения соединен с входом коррекции устройства,Известное устройство предназначенодля перемножения чисел в произвольнойпозиционной системе счисления с основанием й ) 2. В частности, интересенслучай использования в-ицно-кодированной системы счисления с основаниемй = В (когда в"ичные разряды группи круются пс К, гдеК - целое число ибольшее единицы), при использованиикоторой имеется принципиальная возможность повысить быстродействие устройства примерно в К раз по сравнению сослучаем использования в-ичной системысчисления. Особый интерес представляет устройство в случае перемнениядвоично-кодированных операндов в системе счисления с основанием й = 2КВ этом случае каждый разряд.как множимого, так и множителя представляет собой набор из К двоичных цифр,а перемножение двух и-разрядных 2 -ичных чисел эквивалентно перемножениюдвух и К-разрядных двоичных чисел,разряды которых сгруппированы по К 1 1.Недостатком известного. устройстваявляется его ограниченное быстродействие. Это связано с тем, что с цельюувеличения скорости умножения чиселв устройстве необходимо стремиться к937 4 3 1038 использованию более высокого основания И=В в-ичнокодированной системы счисления, так как это сокращает число тактов работы устройства. Однако сокращение числа тактов за счет уве 5 личения основания приводит к существенному увеличению длительности самого такта (длительность такта определяется в основном скоростью работы блоков вычисления разрядных эна- О чений произведения). Действительно, пусть блоки вычисления разрядных значений произведения в известном устройстве реализованы в виде пос" тоянного запоминающего устройства. Но тогда даже при использовании двоично-кодированной 16-ричной системы счисления.(т,е. когда В=2, К=4 и й = 2 = 16) для реализации каж 4дого блока вычисления разрядных значений произведения требуется постоянная память емкостью 26=65536 8-разрядных двоичных слов. А это не позволяет реально обеспечить высокую скорость работы блоков вычисления разрядных знацений произведения при сколь-нибудь больших значениях К, даже если снять ограничения на обьем используемого в устройстве умножения оборудования. Реализация30 же блоков вычисления разрядных значений произведения по матричному принципу, например, в виде однородной яцеечной структуры 5 , наряду с многими достоинствами также не обеспечивает их высокого быстродействия, так как время формирования результата на их выходах при использовании двоицно-кодированной системы счисления с основанием М = 2 составляет величину (2 К) С , где ь - задержка сигнала на одной ячейке.Цель изобретения - повышение быстродействия устройства за счет использования в нем блоков вычисления разрядных значений произведения,в которых старшая цифра разрядного произведения формируется в виде двух цифр (цифры суммы и цифры переноса ).Поставленная цель достигается тем, что в устройстве для умножения, содержащем и"разрядный регистр множимого, и блоков вычисления разрядных значений произведения, и буферных регистров первой группы и и буферныхрегистров второй группы, причем вхо ды буферных регистров первой группы соединены с первыми выХодами старше" го разряда соответствующих блоков вычисления разрядных знацений произведения, первый вход -го блока вычисления разрядных значений произведения ( = 1,2и ) соединен с выходом 1-го разряда регистра множимого, второй вход - с входом множителя устройства, третий вход - с выходом -го буферного регистрв первой группы, причем входы буферных регистров вто" рой группы соединены с вторыми выходами старшего разряда соответствующих блоков вычисления разрядных значений произведения, четвертый вход -го блока вычисления разрядных значений произведения соединен с выхо- ом -го буферного регистра второй группы, а пятый вход - с выходом младшего разряда (+1)-го блока вычисления разрядных значений произведения, выход младшего разряда первого блока вычисления разрядных значений произ" ведения подключен к выходу устройства, пятый вход последнего блока выци" сления значений произведения соединен с входом коррекции устройства.На фиг, 1 представлена структурная схема предлагаемого устройства для умножения; на фиг. 2 блок вычисления разрядных значений произведения в виде ячеечной структуры; нафиг.3- функциональная схема ячейки, которая может быть использована в однородной структуре на фиг;2.Устройство для умножения (фиг.1) содержит и-разрядный регистр 1 множимого, и блоков 2 вычисления разряд" ных значений произведения, и буферных регистров 3 первой группы и и буферных регистров 4 второй группы, вход 5 множителя устройства, вход 6 коррекции устройства и выход 7 устройства. Первый вход -го блока выцисления разрядных значений произведения :,= 1,2, ,и ) соединен с выходом 8 -го разряда регистра 1 множимого, второй вход - с входом 5 множителя устрой" ства, третий вход - с выходом -го буферного регистра 3 первой группы, четвертый вяод - с выходом 1-го буферного регистра 4 второй группы и пятый вход соединен с выходом 9 младшего разряда (1+1)-го блока 2 вычисления разрядных значений произведения. Первый 10 и второй 11 выходы -го блока 2 вычисления разрядных значений произве дения соединены с входами 1-ых буферных регистров 3 и 4 первой и второй групп соответственно. Пятый вход п-го (самого старшего) блока 2 вы937 б Сумма 5 =сс 3 Е 5 1038числения разрядных значений произведения соединен с входом 6 коррекцииустройства, выход 9 младшего разрядапервого (самого младшего.) блока 2 вы" числения разрядных значений проиэве"5дения подключен к выходу 7 устройст"ва.Совокупность 1-го блока 2 вычис" ления разрядных значений произведения и 1-ых буферных регистров 3 и 4 10первой и второй групп соответственно может быть конструктивно выполнена в виде единого модуля 12, реализован" ного, например, как большая интегральная схема. Не составляет особого тру да включение в этот модуль, если это конечно будет признано целесообразным, 1-ых разрядов регистра 1 мно" жимого и регистра множителя (не показан) в качестве его третьего и чет вертого буферных регистров. Это обеспечивает однородность устройства умножения на уровне идентичных модулей 12. Все триггеры устройства могут быть реализованы на двухтактных синхронных О"триггерах (цели синхронизации не показаны ).На Фиг, 2 показан один из возможных вариантов реализации 1-го блока 2 вычисления разрядных значений произведения в виде однородной ячеечной структуры (здесь предполагается, что в устройстве используется в-ично-кодированная система счисления с основанием М6 ,причем К принято равным четырем ). Блок 2 содержит К идентичных ячеек 13,обра" эующих итеративную сеть, подобную описанной в 7 1 и формирующую старшую в-ично"кодированную М-ичную цифру разрядного произведения в виде двух в-ично-кодированных М-ичных цифр (цЙФры суммы и цифры переноса ), как это сделано, например, в 6 3 для случая в=2. 8 блоке 2 производится умножение в-ично"кодированной М-ицнойифры множимого)(11 Х 1 на в иц но-кодированную М-ичную цифру множителя У;= У,УУ 1 У(возрастание индексов при буквейных обозначениях принято в направлении старших разрядов), а также прибавление к младшей в-ицно-кодированной М-ичной цифре получившегося при этом разрядного произведения двух в"ично-кодированных М"ичных цифр М, к и К старшей 55 в-ицно-кодированной М-ичной цифре разрядного произведения одной в-ично-кодированной М"ицной цифры 1 "+". Цифра множимого М поступает йа первый вход блока 2 с выхода 8 1-го разряда регистра 1 множимого, цифра множителя У подается на второй вход блока 2 с входа 5 устройства, цифры М, й поступают на третий и четвертый входы блока 2 с выходом 1-ых буферных регистров 3 и 4 первой и второй групп соответственно, цифра 1.+"подается на пятый вход блока 2 с выхода 9 младшего разряда (1+1)-го блока 2 вычисления разряд" ных значений произведения,На выходе 9 1-го блока 2 вычисления разрядных значений произведения формирует" ся младшая в-ицно-кодированная М"ич; ная цифра разрядного произведения Р, а на выходах 10 и 11 образуется старшая в"ицно-кодированная М-ичная цифра разрядного произведения Р в виде двух в"ично"кодированных М-ицных цифр соответственно Р", Р(цифрасф с" Р ,образована поразрядными в-ичными суммами, а цифра Ри- поразрядными в"ицными переносами ).На фиг. 3 приведена Функциональная схема ячейки 13, используемой в блоке 2 вычисления разрядных эначе" ний произведения на Фиг,2 для случая, когда в=2, т.е. когда в устройстве применяется двоично-кодированная система счисления с основанием М = 2". Ячейка 3 содержит одноразрядный двоичный сумматор 14, двухвходовой элемент И 15 и Функционирует в соответствии со следующими логическими:выражениями: Перенос С = с( Л д Ч (аД+ д)Л е где дд ГУстройство для умножения работает следующим образом.В исходном состоянии буферные регистры 3 и 4 всех модулей 12 обнулены, в регистре 1 множимогр хранится без знака и"разрядный в-ичный код множимого (и к - разрядный в- ичный код множимого), В каждом из и первых тактов работы устройства на его вход 5 поступает параллельно К в-ичных разрядов множителя, начиная с его младших разрядов (предполагается, что множимое и множитель имеют одинаковую разрядность ).При этом в 1"ом блоке 2 вычисления разряд"- ных значений произведения осуществляется умножение К в-ичных разрядов множителя, поступающих на10389 его второй вход с входа 5 устройства, на К е-ицных разрядов множимого, поступающих на его первый,вход с выхода 8 1"го в"-ичногоразряда регистра 1 множимого, и 5прибавление к К младшим в-ичнымразрядам получившегося при этом2 К-разрядного произведения череэтретий и четвертый входы К старшихв-ицных разрядое произведения 1-гоблока 2, сформированных в предыдущем такте в двухряднрм коде и хранимых в буферных регистрах 3 и 41-го модуля 12, а также прибавлениецерез пятый вход К к старшим в"ичнымразрядам 2 К-разрядного произведенияК младших в-ицных разрядов 2 К-разрядного произведения 1-го модуля 12,формируемых в данном такте на выходе 9 (1+1)"го блока 2 вычисления разрядных значений произведения, Послеэтого К старших в"ицных разрядов 2 Кразрядного произведения, представленных в двухрядном коде, с выходов 1 Ои 11 1-го блока 2 записываются в 251-ые буферные регистры 3 и 4 соответственно,После выполнения и первых тактовработы устройства на его вход 5 поступает нулевая информация и далее ЗО.осуществляется еще дополнительнои тактов, в течение которых иэ устройства выводится с соответствующимпреобразованием информация, хранимаяв буферных регистрах 3 и 4 всех моду- З 5лей 12. Вывод 2 и-разрядного произведения сомножителей в устройствеосуществляется через его выход 7 в параллельно"последовательном коде(по К в"ичных разрядов в каждом:такте),8 рассмотренном случае на вход бкоррекции устройства во всех его идополнительных тактах подается К-раз-,рядный е-ичный код 00000 . В техК 45случаях, когда требуется получитьокругленное и-разрядное произведение,необходимо в самом начале процессаумножения (например, до приема сомножителей) пбдать на вход б коррек 50ции устройства К-разрядный в-ичныйКкоторой задержкой запись результатов сформированных на выходах блоков 2 еыцисления разрядных произведений, в буферные регистры 3 и 4 модулей 12. В результате этого в буфер 37 8ном регистре 3 последнего модуля 12 будет записан код Ь/2 О,. 000 котоК рый и позволит в процессе умножения осуществить округление результата без дополнительных временных затрат. Очевидно, что используя определенным образом вход 6 коррекции устройства, можно одновременно осуществлять операцию умножения и-разрядных в -ичных чисел Х и У с суммированием и-разрядного в -ичного слагаемого 2, т.е.Кв одном цИкле работы устройства вщ полнять сложную функцию Я= Х 1 + ЕДля этого необходимо в течение ипервых тактов работы устройства пода-вать на его вход б коррекции в каждом такте К в-ичных разрядов слагаемого Е, начиная с его младших разрядов, причем это прибавление можетосуществляться либо к округленным истаршим разрядам произведения ХюУ,либо просто к усеченным его и стар"шим разрядам,следует особо отметить, что ум"ножение п-разрядных чисел в предлагаемом устройстве, можно выполнять за(и+1) тактов, если после выполненияи-го такта содержимое буферных регистров 3 и 4 всех модулей 12 податьдля окончательного суммирования насоответствующие входы быстродействующего двухвходового сумматора(на фиг. 1 эти дополнительные цепикпередачи информации с выходов бу,ферных регистров 3 и 4 отмечены штриховыми линиями ),Это может быть целесообразным, если, например,арифметико-логическое устройство ЭВИ содержит подобный быстродействующий сумматор., Таким образом,окончательное произ ведение в предла га емом уст рой ст ве, так же как и е 4, может .быть сформировано за 2 п или (и+1) тактов.Од" нако длительность выполнения одного такта е предлагаемом устройстве существенно сокращена. Действительно, пусть в известном и предлагаемом устройствах применяетоя в-ицно-кодированная в -ичная система счисления и ири реализации блоков вычисления разрядных значений произведения е известном устройстве используется быстродействующая однородная ячеечная структура, подобная описан" ной в 1 7 1, а в предлагаемом устрой" стае " ячеечная структура, изобра"10 1038937 9женная на Фиг.2 (основное отличиеструктур, показанных на фиг.2,3 отструктур, описанных в7 1 состоит втом, что во-первых, старшая в -ичнаяцифра разрядного произведения формируется в виде двух цифр, т.е. вдвухрядном коде, в то время, как,во-вторых структурах эта цифра обра"зуется в однорядном коде). Тогда впредлагаемом устройстве длительность"одного такта работы примерно равна К.,в то время, как в известном устройстве эта длительногть составляетвеличину (2 К) ь, так как на приве"дение переносов при формированиистаршей в-ичнокодированной в-ичнойцифры разрядного произведения в егоблоках вычисления разрядных значенийпроизведения затрачивается время(К)Т .(здесь черезобозначеназадержка информации в одной ячейкеблока вычисления разрядных значенийпроизведения ),Предлагаемое устроиство для умножения чисел при там же объеме исполь" зуемого оборудования обеспечивает в (2 К)К раза более высокое быстродействие, чем известное. Оно может быть изготовлено из множества однотипных взаимозаменяемых модулей, кнжцый из которых удобен для реализации в виде БИС, причем переход от уст,ройства с большим к устройствам с яалым форматом обрабатываемой информации и наоборот фактически сводится к пропорциональному уменьшению либо увеличению числа используемых модулей.Если соответствующие разряды регистров множимого и множителя ввести в операционные модули,то устройство будет состоять только из однотипных модулей, что делает его особенно перспективным при разработке высокопроизводительных наращиваемых микропроцессоров и микропроцессорных систем.1038937 Подпис с а г, Ужгород, ул. Проектная Редактор Н.Стащишин 6231/55 ВНИИПИ Госуд по делам 113035, Моск-35, Раушская наб рректор М. Демчи