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

(22) ИТЕТ СССРЙ И ОТНРЫТИЙ ГОС по ДРСТВЕННЦЙ Н М ИЗОБРЕТЕН ОПИСАНИЕ ИЗОБРЕТЕНИЯ тооймУ СеидеТ 3334469/18-2407.09,8130,07.83, Бюл, УГ.П.Лопато и А.А.Минский радиотехн(54)(57) УСТРС 21 СТВО ДЛЯ уИНОЖЕНИЯ,содержащее регистр множимого, 22 блоков вычисления разрядных значенийпроизведения (Ю - число разрядовмножимого), буферные регистры первой и второй групп, причем входпервого сомножителя каждого блокавычисления разрядных значений произведения соединен с выходом соответствующего разряда регистра множимого, вход второго сомножителякаждого блока вычисления разрядныхзначений произведения соединен с входом множителя устройства, выходызначений мпапшего и старшего разрядов каждого блока вычисленияразрядных значений произведениясоединены с входами соответствующихбуферных регистров первой и второйгрупп, выход первого буферного регистра второй группы подключен квыходу устройства, о т л и ч а ющ е е с я тем, что, с целью повышения быстродействия, устройствадополнительно содержит группу сумматоров, причем входы 1-го сумматора группы (1 1,2 й) соединены с выходами-го буферного регистра первой группы н ( + 1)-го буферного регистра второй группы,входы п -го сумматора группы соединены с выходом И-го буферного регистра первой группы и входом коррекции устройства, выходы суммы ипереноса каждого сумматора группысоединены с входами первого и вго слагаемых младшего разряда светствующего блока вычисления разрядных значений произведения.Изобретение относится к вычислительной технике и может быть использовано при разработке быстродействующих устройств для умножения чисел, .представленных в любой позиционной системе счисления. Особенноэффективно его применение при использовании больших интегральныхсхем,Известно устройство для улножения, содержащее накопитель (блок формирования произведения) и осуществляющее умножение множимого Х на множитель Ч = и, , 2, причемв предварительно очищенный накопитель множимое Х прибавляетсяраэ 5затем оно сдвигается влево на одинразряд и вновь прибавляется в накопительраз и так до тех пор, пока все разряды числане будутобработаны 11,20Недостатком устройства являетсянизкое быстродействие.Наиболее близким к предлагаемомупс технической сущности являетсяустройство для умножения, содержащее регистр множимого, И блоков вычисления разрядных значений произведения И - число разрядов множимого), И буферных регистров первойгруппы и и буферных регистров второй группы, причем вход первогосомножителя каждого блока вычисления разрядных значений произведения соединен с выходом соответствующего разряда регистра множимого,вход второго сомножителя каждого бло.з-ка вычисления разрядных значенийпроизведения соединен с входсм множителя устройства, входы первого ивторого слагаемых младшего ра.зрядакаждого блока вычисления разрядных 40значений произведения соединены с выходами соответствующих буферных регистров Первой и второй групп, выходы значений младшего и старшегоразрядов каждого блока вычисленияразрядных значений произведения соединены с входами соответствующихбуферных регистров первой и второйгрупп, выход первого буферного регистра второй группы подключен квыходу устройства, вход второго .сла"гаемого последнего блока вычисленияразрядных значений произведения соединен с входом коррекции устройства 2,Это устройство предназначено дляперемножения чисел в произвольнойпозиционной системе счисления с основанием Я2, в частности в в-ичнокодированной системе счисления соснованием М =Ь"(в-ичные разряды . 60группируются по К , где 1 - целоечисло и большее единицы ,Недостатком такого устройстваявляется относительно низкое быстро.действие. Это связано с тем, чтос 65 целью увеличения скорости умножения чисел в известном устройстве необходимо стремиться к использованию более высокого основания й = Ь в-ично-кодированной системе счисления, так как это сокращает число тактов работы устройства. Однако сокращение числа тактов эа счет увеличения основания приводит к существенному увеличению как длительности самого такта, так и объема используемого оборудования. Даже при использовании двоично-кодированной шестнадцатиричной системк счисления т.е. когда К =4 и М = 216) для реализации каждого блока вычисления разрядных значенийпроизведения требуется постоянная память емкостью 2 :65536 8-разрядных дво 45ичных слов, А это не позволяет реально обеспечить высокую скорость работы блоков вычисления разрядных значений произведения даже если сняты ограничения на объем используелого в устройстве оборудования. Реализация же в известном устройстве блоков вычисления разрядных значении произведения на основе одно - тактных комбинационных умножителей, например, в виде итеративной сети, также не обеспечивает их высокого быстродействия, так как время формирования результата на их выходах составляет величину 2 К-Ц С, где Т - задержка сигнала на одной ячейке сети.Цель изобретения - повышение быстродействия устройства.Поставленная цель достигается тем, что в устройство для умножения, содержащее регистр множимого, И бло. ков вычисления разрядных значений произведения ( и - число разрядов множимого,), буферные регистры первой и второй групп, причем вход первого сомножителя каждого блока вычисления разрядных значений произведения соединен с выходом соответствующего разряда регистра множимого, вход второго сомножителя каждого блока вычисления разрядных значений произведения соединен с входом множителя устройства, выходы значений младшего и старшего разрядов каждого блока вычисления разрядных значений произведения соединены с входами соответствующих буФерных регистров первой и второй групп, выход первого буферного регистра второй группы подключен к выходу устройства, введена группа сумматоров, причем входы л( -го сумматора группы л =1,2 и в 1 ) соединены с выходами-го буферного регистра первой группы и ( + 1)-го буферного регистра второй группы, входы М-го сумматора группы соединены с выходом И -го буферного регист 103245310 ра первой группы и входом коррекции устройства, выходы суммы и переноса каждого сумматора группы соединены с входами первого и второго слагаемых младшего разряда соответствующего блока вычисления разрядных 5 значений произведения.На фиг. 1 изображена структурная схема устройства для умножения чисел; на фиг. 2 - один иэ возможных вариантов совместной реализации-го блока вычисления разрядных значений произведения=1,2 И) и-го сумматора группы в виде итеративной сети для случая двоичнокодированной шестнадцатиричной 15 системы счисления (к =4 и К=1 б); на фиг, 3 - функциональная схема ячейки, используемой в итеративной сети на фиг. 2.устройство содержит (И -разрядный) регистр 1 множимого, и блоков 2 вы- числения разрядных значений произведения, й буферных регистров 3 первой группы, И буферных регистров 4 второй группы, группу из И, сумматоров 5, вход б множителя и вход 7 коррекции устройства, выход 8 устройства. Вход первого сомножителя )-го блока 2 вычисления разрядных значений произведения (3 =1,2 И) соединен с выходом 9-го разряда регистра 1 множимого, вход второго сомножителя - с входом б множителя устройства, входы первого и второго слагаемых младшего разряда - с выходами суммы и переноса -го сумма тора 5 группы, выход 10 старшего разряда соединен со входом-го буферного регистра 3 первой группы и выход 11 младшего разряда - с входом ) -го буФерного регистра 4 вто О рой группы. Входы 1 -го сумматора 5 группы (1=1,2 и -1) соединены с выходами 1 -го буферного регистра 3 первой группы и (1 +1)-го буферного регистра 4 второй группы, входы 5-го 45 сумматора 5 группы соединены с выходам И-го буферного регистра 3 первой группы и входом 7 коррекции устройства, выход первого буферного регистра 4 второй группы подключен к выходу 8 устройства, Совокупность-го блока 2 вычисления разрядных значений произведения,-го сумматора 5 и ) -ых буферных регистров 3 и 4 может быть конструктивно выдолнена в виде единого модуля 12, 55 реализованного, например, как большая интегральная схема, Йе составляет никакого труда включение в этот модуль, если это будет признано целесообразным, соответствующего 60 разряда регистра 1 множимого в качестве его третьего буферного регист ра. Этим обеспечивается лучшая однародность структуры устройства. 65 В устройстве регистр 1 множимогои буферные регистры 3 и 4 могут быть построены на двухтактных синхронных )3 -триггерах (цепи синхронизации на чертеже не показаны). Предполагается, что все блоки 2 вычисления разрядных значений произведения и все сумматоры 5 устройства комбинационного типа. Они могут бытьпостроены самыми различными способами. На фиг, 2 в качестве примера показана совместная реализация-го блока 2 вычисления разрядных значений произведения и-го сумматора 5 в виде итеративной сети для случая двоично-кодированной шестнадцатиричной системы счисления, т.е. когда К = 4 и М =1 б. Итеративная сеть содержит двадцать (в общем случае К + К)идентичных ячеек 13 и реализует функции-го сумматора 5 и-го блока 2 вычисления разрядных значений произведения ( нижний ряд сети из К ячеек 13 выполняет функцию сумматора 5, а остальная часть сети из К ячеек 13 выполняет функцию блока 2 вычисления разрядных значений произведения . В ней производится умножение двоично-кодированной шестнадцатиричной цифры множимого Х 1 = х) х ххна двоич но-коди 4 Ъ 2 1рованную шестнадцатиричную цифру множителя у = у уу у(возрастание индексов при буквенных обозначениях принято в направлении старших разрядов) и прибавление к младшей двоично-кодированной шестнадцатиричной цифре получившегося при этом про.изведения трех двоично-кодированных шестнадцатиричных, цифр Ь,), Ми М. Цифра множимого Х поступает на вход сети с выхода 9-го разряда регистра 1 множимого, цифра множителя 1) - с входа б устройства, цифры Ь 1 и И- с выхода-го буферного регистра 3 первой группы и цифра К ) - с выхода +1)-го буферного регистра 4 второй группы, На выходе 11 итеративной сети формируется младшая двоично-кодированная шест; надцатиричная цифра результата Р, а на выходе 10 - старшая цифра результат Р в циде двух цифр Р и Рс(цифра Р старшего разряда результата образована поразрядными суммами, а цифра Р - поразрядными переносами).Каждая ячейка 13 сети содержит (Фиг. 3) одноразрядный двоичныйсумматор 14, элемент И 15, и функционирует в соответствии со следующимилогическими выражениямиСумма 6=А ЮЭЮЕПеренос С=А Ъ +(А 6) ЮЕ, где О=С,Переносы С с выходов ячеек 13сети передаются с одного ее рядана другой и нигде не распространяются вдоль ряда справа налево, поэто 1032453му скорость работы итеративной сети определяется величиной к+1)(;, где6 - задержка сигнала на одной ячейке сети.рассмотренный вариант совместной реализации ).-го блока 2 вычисления 5 разрядных значений произведения и -го сумматора 5 не является единственным. Так, например, с целью увеличения быстродействия их можно реализовать в виде дерева определенным 10 образом соединенных одноразрядных двоичных сумматоров (многослойное построение), либо каким-то другим из известных способов, Общим же для всех реализаций является то, 5 что старший разряд результата на выходе 10 формируется н виде двух цифр ( в днухрадном коде).Устройство для умножения работает следующим образом. 20В исходном состоянии буферные регистры 3 и 4 всех модулей 12 обнулены, н регистре 1 множимого хранится без знака И -разрядный 2"-ичный код множимогоИ К -разрядный двоичный код множимого). Здесь предполагается, что сомножители представКлены в двоично-кодированной 2 -ичной системе счисления, т.е. каждый разряд как множимого, так и множителя, представляет собой30 набор из К двоичных цифр.В каждом из И первых тактов рабо,ты устройства на его вход б поступает параллельно К двоичных разрядов множителя, начиная с младших разрядон. При этом в-ом блоке 2 вычисления разрядных значений произведения осуществляется умножение К двоичных разрядов множимого, поступаю щих на его вход первого сомножителя 40с выхода 9-го 2 -ичного разрядакрегистра 1 множимого, на к двоичных разрядов множителя, поступающих на его вход второго сомножителя с входаб устройства, и прибавление к К младшим двоичным разрядам получившегося при этом 2 К -разрядного произведения по его входам первого и второгослагаемых через-ый сумматор 5 Кмладших двоичных разрядов произведе ния)+1)-го блока 2, сформированных в предыдущем такте в однорядном, коде и хранимых в буферном регистре 4 (+1) -го модуля 12 и К старшихдвоичных разрядов произведения 7 -го 55блока 2,сформированных н предыду-. щем такте в двухрядном коде и хранимых в буферном регистре 3 -го модуля 12. После этого сформированные в однорядном коде К младших двоичных раэрядон произнедения-го блока 2 с его выхода 11 записываются в-ый буферный регистр 4, а К старших. разря дов произведения, представленного в двухрядном коде - с его выхода 10 в-ый буФерный регистр 3.65 После выполнения И первых тактов работы устройства на его вход б поступает нулевая информация и далееосуществляется еще дополнительно итактов, н течение которых из устройства выводится с соответствующимпреобразованием информация, хранимая в буферных регистрах 3 и 4 всехмодулей 12, Вывод 2 И -разрядного произведения сомножителей в устройстве осуществляется через его выход8 в параллельно-последовательномкодепо К двоичных разрядов в каждом такте). В рассмотренном случаена вход 7 коррекции устройства вовсех его И дополнительных тактахподается,К -разрядных двоичный код0000. В тех же случаях, когда треКбуется получить округленное И -разрядное произведение, необходимо в первом такте работы устройства на его вход 7 коррекции подать К -разрядный двоичный код,100000. Это позволяет осуществитьоивтуглеи иепроизведения без дополнительных временных затрат. Используя определенным образом вход 7 коррекции устрой. стна можно одновременно выполнять операцию умножения И -разрядных чисел Х и У с суммированием к И старшим разрядам получившегося при этомпроизнедения и -разрядного слагаемого й , т.е. в одном цикле работы устройства выполнять сложную операцию Я =Х 3 + 2 . Для этого необходимо в течение И тактов работы устройства, начиная со второго, подавать н каждом такте на вход 7 коррекции устройства по К двоичных разрядов слагаемого 2 , начиная с его младших разрядов, причем это прибавление слагаемого 2 может осуществляться либо к округленным И стар-, шим разрядам произведения, либо просто к усеченным Й старшим разрядам произведения.Умножение И -разрядных чисел в предлагаемом устройстве (как и в известном) можно выполнять и за (И + 1) тактов, если после выполнения Р -го такта содержимое буферныхрегистров 3 и 4 модулей 12 подать для окончательного суммирования на соответствующие входы быстродействующего трехвходового сумматора на фиг, 1 такой сумматор не показан, а только отмечены штриховыми линиями дополнительные цепи передачи информации с выходов буферных регистров 3 и 4 на входы сумматора). Это может быть особенно целесообразным, если например, арифметико-логическое устройство ЭВМ содержит подобный сумматор.Таким образом, окончательное произведение в предлагаемом устройстве, так же как и н известном; может/52 Тираж 706ВНИИ 11 И Государственного кпо делам изобретений и о 035, Москва, Ж, Раушск Заказ 54 Подписитета СССРкрытий наб., д. е 5 илиад ППП "Патент", г. Ужгород, ул. Проектная,быть сформировано за 2 И или(и+1)тактов. Однако длительность выполнения одного такта в предлагаемом устройстве существенно сокращена, потому что все блоки 2 вычисленияразрядных значений произведения формируют на своем выходе 10 старшуюцифру разрядного произведения ввиде двух цифр, т,е. в двухрядномкоде, а это исключает потери времени на приведение в каждом такте работы устройс:тва двух 1 иднсл с колав однорядный, Так, например, и с лу -чае реализации блоковвычис;ленияразрядных значений произволения ввиде итеративной сети длительнос;тьтакта работы уст 1 ойства-п 1 ототипапримерно равна (2 К -1) в то время как в предлагаемом устройствеона составляет величину с+1) Ггде с", - задержка сигнала на одной ячейке сети.