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

Изобретение относится к ВЕЛЧИСЛИтельной технике и может быть исполь зовано при разработке быстродействующих устройств для умножения чисел, -представленных в любой позиционной системе счисления. Особенно эффективно его применение при использовании больших интегральных схем. Известно устройство для умножения, содержащее накопитель (блок фо мирования произведения) и осуществляющее умножение множимого X на мн житель N 1:)и г f причем в предварительно очищенный накопитель множимое X прибавляется раз затем оно сдвигается влево на один разряд и вновь прибавляется в нако, питель S2. раз и так до тех пор/ пока все разряды числа не будут обработаны Недостатком устройства является низкое быстродействие. Наиболее близким к предлагаемому ПС технической сущности является устройство для умножения, содержащее регистр множимого, и блоков вычисления разрядных значений произведения (И - число разрядов множимого), И буферных регистров первой группы и ц буферных регистров второй группы, причем вход первого сомножителя каждого блока вычисления разрядных значений произведения соединен с выходом соответствую щего разряда регистра множимого, вход второго сомножителя каждого бл ка вычисления разрядных значений произведения соединен с входом множителя устройства, входы первого и второго слагаемых младшего разряда каждого блока вычисления разрядных значений произведения соединены с в ходами соответствующих буферных регистров первой и второй групп, выходы значений младшего и старшего разрядов каждого блока вычисления разрядных значений произведения со динены с входами свЪтветствующих буферных регистров первой и второй групп, выход первого буферного регистра второй группы подключен к выходу устройства, вход второго .сл гаемого последнего блока вычислени разрядных значений произведения сое динен с входом коррекции устройства 2. , Это устройство предназначена дл перемножения чисел в произвольной позиционной системе счисления с ос ванием N 2, в частности в в-ично кодированной системе счисления с основанием N ЬТв-ичные разряды . группируются по К , где К - цело число и большее единицы. Недостатком такого устройства является относительно низкое быстр действие. Это связано с тем, что/с целью увеличения СКОРОСТИ умножения чисел в известном устройстве необходимо стремиться к использованию более высокого основания Ы Ъ в-ично кодированной системе счисления, так как это сокращает число тактов работы устройства. ОднакЪ сокращение числа тактов за счет увеличения основания приводит к существенвюму увеличению как длительности самого такта, так и объема используемого оборудования. Даже при использовании двоично-кодированной шестнадцатиричной системьл счисления 1т.е.- когда К 4 и N 2 1б) для реализации каждого- блока вычисления разрядных значенийпроизведения требуется постоянная память емкостью 65536 8-разрядных двоичных слов. А это не позволяет реально обеспечить высокую скорость работы блоков вычисления разрядных значений произведения даже если сняты ограничения на объем используемого в устройстве оборудования. Реализация же в известном устройстве блоков вычисления разрядных значений произведения на основе одно - тактных комбинационных умножителей, например, в виде итеративной сети, также не обеспечивает их высокого быстродействия, так как время формирования резуль тата на их выходах составляет величину (2-K-l)f , где Т - задержка сигнала на одной ячейке сети. Цель изобретения - повышение быстродействия устройства. Поставленная цель достигается тем, что в устройство для умножения, содержащее регистр множимого, И блоков вычисления разрядных значений произведения (и- число разрядов множимого, буферные регистры первой и второй групп, причем вход первого сомножителя каждого блока вычисления разрядных значений произведения соединен с выходом соответствующего разряда регистра множимого, вход второго сомножителя каждого блока вычисления разрядных значений произведения соединед с входом множителя устройства, выходы значений младшего и старшего разрядов каждого блока вычисления разрядных значений произведения соединены с входами соответствующих буферных регистров первой и второй групп, выход первого буферного регистра второй группы подключен к выходу устройства, введена группа сумматоров, причем входы -f -го сумматора группы (.1 1,2,,.., и-l) соединены с выходагуш i -го буферного регистра первой и (-ь буферного регистра второй группы, входы сумматора группы соединены с выходом И-го буферного регистpa первой группы и входом коррекции устройства, выходы суммы и переноса каждого сумматора группы соединены с входами первого и второго слагаемых младшего разряда соответствую-щего блока вычисления разрядных значений произведения.

. Па фиг. 1 изображена структурная схема устройства для умножения чисел; на фиг. 2 - один из возможных вариантов совместной реализации j-го блока вычисления разрядных значений произведения ( ,2 ,.. . , И и j-го сумматора группы в виде итеративной сети для случая двоичнокодированной шестнадцатиричной системы счисления (,Y- 4 и )1 на фиг. 3 - функциональная схема ячейки, используемой в итеративной сети на фиг. 2.

Устройство содержит (и -разрядный) регистр 1 множимого, и блоков 2 вычисления разрядных значений произведения, in буферных регистров 3 первой группы, и буферных регистров 4 второй группы, группу из И сумматоров 5, вход б множителя и вход 7 коррекции, устройства, выход 8 устройства. Вход первого сомножителя j-ro блока 2 вычисления разрядных значений произведения (У 1, 2,...,И) соединен с выходом 9 j -го разряда регистра 1 множимого, вход второго сомножителя - с входом 6 множителя устройства, входы первого и второго слагаемых младшего разряда - с выходами суммы и переноса j-го сумматора 5 группы, выход 10 старшего разряда соединен со входом j -го буферного регистра 3 первой группы и выход 11 младшего разряда - с входом j-ro буферного регистра 4 второй группы. Входы 1 -го сум 1атора 5 группы (,2,..., и -1) соединены с выходами 1-го буферного регистра 3 первой группы и (i+lj-ro буферного регистра 4 второй группы, входы tf-ro сумматора 5 группы соединены с выходом -И-го буферного регистра 3 перво группы и входом 7 коррекции устройства, выход первого буферного регистра 4 второй группы подключен к выходу 8 устройства. Совокупность j-го блока 2 вычисления разрядных значений произведения, j-го су лматора 5 и 3-ых буферных регистров 3 и 4 может быть конструктивно выдолнена в виде единого модуля 12, реализованного, например, как большая интегральная схема. Не составляет никакого труда включение в этот модуль, если это будет признано целесообразным, соответствующего разряда регистра 1 множимого в качестве его третьего буферного регистра. Этим обеспечивается лучшая однародность структуры устройства.

в устройстве регистр 1 множимого и буферные регистры 3 и 4 могут быть построены на двухтактных синхронных D -триггерах (цепи синхронизации на чертеже не показаны К Предполагается, что все блоки 2 вычисления разрядных значений произведения и все сумматоры 5 устройства комбинационного типа. Они могут быть построены самыми различными спосо0бами. На фиг. 2 в качестве примера показана совместная реализация /j -го блока 2 вычисления разрядных значений произведения и j-го сумматора 5 в виде итеративной сети для случая двоично-кодировалной шестнадцатирич5ной системы счисления, т.е. когда

К 4 и . Итеративная сеть содержит двадцать (в общем случае

К + к) идентичных ячеек 13 и реализует функции j -го сумматора 5 и

0 j-го блока 2 вычисления разрядных значений произведения (нижний ряд сети из К ячеек 13 выполняет функцию сумматора 5, а остальная часть сети из К ячеек 13 выполняет функцию

5 блока 2 вычисления разрядных значений произведения . В ней производится умножение двоично-кодированной шецтнадцатиричной цифры множимого X на двоично-коди0рованную шестнадцатиричную цифру

множителя Y у| у| у, (возрастание индексов при буквенных обозначениях принято в направлении старших разрядов) и прибавление к младшей дво5ично-кодированной шестнадцатиричной цифре получившегося при этом произведения трех двоично-кодированных шестнадцатиричных .цифр U, , М иМ. Цифра множимого Х поступает на

0 вход сети с выхода 9 j -го разряда регистра 1 множимого, цифра множителя. V - с, входа 6 устройства, цифры Ь и М - с выхода j-ro буферного регистра 3 первсэй группы и цифра N - с выхода (j + l)-ro буферного

5 регистра 4 второй группы. На выходе 11 итеративной сети формируется младшая двоично-кодированная шест,надцатиричная цифра результата Р , а на выходе 10 - старшая цифра ре0зультата р, в чиде двух цифр Р и (цифра Р, старшего разряда результата образована поразрядными суммами, а цифра РД - поразрядными переносами).

5

Каждая ячейка 13 сети содержит (фиг. З) одноразрущный двоичный сумматор 14, элемент И 15, и функционирует в соответствии со следующими логическими выражениями

0

Сумма

Перенос Т) (Л© WE, где ,

Переносы С с выходов ячеек 13 сети передаются с одного ее ряда на другой и нигде не распространя5ются вдоль ряда справа налево, поэтоMy скорость работы итеративной сети определяется величиной (K.+l) , где Т - задержка сигнала на одной ячей ке сети. Рассмотренный вариант совместной реализации j.-ro блока 2 вычисления разрядных значений произведения и i-ro сумматора 5 не является единст венным. Так, например, с целью увел чения быстродействия их можно реали зовать в виде дерева определенным образом соединенных одноразрядных двоичных, сумматоров (многослойное Построение), либо каким-то другим из известных способов. Общим же для всех реализаций является то, что стариий разряд результата на выходе 10 формируется в виде двух цифр (в двухрадном коде). Устройство для умножения работает следующим образом. В исходном состоянии буферные регистры 3 и 4 всех модулей 12 обнулены, в регистре 1 множимого хранится без знака и -разрядный 2 -ичный код множимого(п1 -разрядный двоичный код множимого). Здесь предполагается, что сомножители предстазвлены в двоично-кодирован. ной 2 -ичной системе счисления, т.е. каждый разряд как множимого, так и множителя, представляет собой набор из К двоичных цифр. В каждом из И первых тактов рабо .ты устройства на его вход 6 поступае параллельно К двоичных разрядов мнохсителя, начиная с младших разрядов. При этом в j-ом блоке 2 вычисления разрядных значений произведения осуществляется умножение К двоичных разрядов множимого, поступаю щих на его вход первого сомножителя с выхода 9 j -го 2 -ичного разряда регистра 1 множимого, на к двоичных разрядов множителя,поступающих на его вход В.ТОРОГО сомножителя с входа 6 устройства, и прибавление к К млад шим двоичным разрядам получившегося при этом 2-И -разрядного произведения по его входам первого и второго слагаемых через ;) -ни сумматор 5 К млсщших двоичных разрядов пройзведения { j+lj-ro блока 2, сформированных в предыдущем такте в однорядном коде и хранимых в буферном регистре 4 (j + i)-ro модуля 12 и Кч старших двоичных разрядов произведения j -го блока 2, сформированных в предыдущем такте в двухрядном коде и хранра ых в буферном регистре 3 j-ro модуля 12. После этого сформированны в однорядном коде К младших двоичных разрядов произведения j -го блока 2 с его выхода 11 записываются в j-ый буферный регистр 4, а К старших, разр дов произведения, представленного в двухрядном коде - с его выхода 10 в j. ый буферный регистр 3. После выполнения и первых тактов работы устройства на его вход 6 поступает нулевая информация и далее осуществляется еще дополнительно и тактов, в течение которых из устройства выводится с соответствующим .преобразованием информация, хранимая в буферных регистрах 3 и 4 всех модулей 12. Вьшод 2 И-разрядного произведения сомножителей в устройстве осуществляется че.рез его выход 8 в параллельно-последовательном коде { по К двоичных разрядов в каждом такте). В рассмотренном случае на вход 7 коррекции устройства во всех его и дополнительных тактах подается .К -разрядных двоичный код О...ОС. В тех же случаях, когда тре К буется получить округленное И -разрядное произведение, необходимо в первом такте работы устройства на его вход 7 коррекции подать /К-разрядный двоичный код .1....ООД. Это позволяет осуществить округление произведения без дополнительных временных затрат. Используя определенным образом вход 7 коррекции устройства можно одновременно выполнять операцию умножения И -разрядных чисел X и У с суммированием к и старшим разрядам получившегося при этом произведения и-разрядного слагаемого t , т.е. в одном цикле работы устройства выполнять сложную операцию О Х + 2 . Для этого необходимо в течение ц тактов работы устройства, начиная со второго, подавать в каждом такте на вход 7 кор-рекции устройства по У. двоичных разрядов слагаемого 2 , начиная с его младших разрядов,.причем это прибавление слагаемого 2 может осуществляться либо к округленным и стар-, шим разрядам произведения, либо просто к усеченным и старшим )азрядам произведения. Умножение и -разрядных чисел в предлагаемом устройстве {как и в известном) можно выполнять и за (и + 1) тактов, если после выполнения И -го такта содержимое буферных регистров 3 и 4 модулей 12 подать для окончательного суммирования на соответствующие входы быстродействующего трехвходового сумматораfна фиг. 1 такой сумматор не показан, а только отмечены штриховыми линиями дополнительные цепи передачи информации с выходов буферных регистров 3 и 4 на входы сумматора). Это может быть особенно целесообразным, если например, арифметико-логическое устройство ЭВМ содержит подобный сумматор. Таким образом, окончательное произведение в предлагаемом устройстве, так же как и в известном; может

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

10

работы устройсгтва двухридшлч icivi i в однорял1и-.й. Так, наприме1,5, в смтучае реализации блоков 2 вкачис;лсния разрядных значений произроления п виде итеративной сети длительность такта pa6oTtJ устройства-прототипа примерно равна (2-К-1)Г , в то время как в предлагаемом устройстве она составляет величину (| + 1/Г , где ТГ - задержка сигнала Fia одной ячейке сети.

УСТРОЙСТВО ДЛЯ УМНОЖЕНИЯ содержащее регистр множимого, i бл ков вычисления разрядных значений произведения (У число разрядов множимого), буферные регистры первой и второй групп, причем вход первого сомножителя каждого блока вычисления разрядных значений прои ведения соединен с выходом соответствующего разряда регистра множимого, вход второго сомножителя каждого блока вычисления разрядных значений произведения соединен с . tt ВХОДОМ множителя устройства, выходы значений млалшего и старшего разрядов каждого блока вычисления разрядных значений произведения соединены с входами соответствующих буферных регистров первой и второй групп, выход первого буферного регистра второй группы подключен к выходу устройства, отличающееся тем, что, с целью повышения быстродействия, устройство дополнительно содержит.группу сумматоров, причем входы ч-го сумматора группы (,2,..., м-1) соединены с выходами -i -го буферного регистра первой группы и (-1 + 1)-го буферного регистра второй группы, входы и-го сумматора группы соединены с выходом И-го буферного регистра первой группы и входом коррекции устройства, выходы суммы и переноса каждого сумматора группы соединены с входами первого и второго слагаемых младшего разряда соответствующего блока вычисления разрядных значений произведения. t

I

Vm.

N