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

 

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

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

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

РЕСПУБЛИК (19) (111

1

v

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

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

ПО ДЕЛАМ ИЗОБ ЕТЕНИй И ОТНРЫТИй и вто сномм свидетыьству (21) 3334469/18-24 (22) 07.09.81 (46) 30,07. 83. Бюл. М 28 (72) Г . П . Лопато и A.A. Мастак (71) Минский радиотехнический инсти- тут (53) 681.325 (088.8) (56) 1. Бут Э. и Бут К. Автоматические цифровые машины. И., ГИФМЛ, 1959, с. 74-75.

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

9 888109, кл. G 06 F 7/52, 1978 (прототип). (54)(57) УСТРОЙСТВО ДЛЯ УМНОЖЕНИЯ, содержащее регистр множимого, И блоков вычисления разрядных значений произведения (Ю вЂ” число разрядов множимого}, буферные регистры первой и второй групп, причем вход первого сомножителя каждого блока вычисления разрядных значений произведения соединен с выходом соответствующего разряда регистра множимого, вход второго сомножителя каждого блока вычисления разрядных значений произведения соединен с входом множителя устройства, выходы значений млапшего и старшего разрядов каждого блока вычисления .разрядных значений произведения соединены с входами соответствующих буферных регистров первой и второй групп, выход первого буферного регистра второй группы подключен к выходу устройства, о т л и ч а ю щ е е с я тем, что, с целью повышения быстродействия, устройства дополнительно содержит группу сумматоров, причем входы -ro сумматора группы (1 1,2,..., и-1) соединены с выходами i -го буферного регистра первой группы и (i + 1)-ro буферного регистра второй группы, входы И -го сумматора группы соединены с выходом И-ro буферного регистра первой группы и входом коррекции устройства, выходы суммы и переноса каждого сумматора группы соединены с входами первого и второго слагаемых младшего разряда соответствующего блока вычисления разрядных значений произведения.

1032453

Изобретение относится к вычислительной технике и может быть исполь. зовано при разработке быстродействующих устройств для умножения чисел, -представленных в любой позиционной системе счисления. Особенно эффективно его применение при использовании больших интегральных схем, Известно устройство для у лножения, содержащее накопитель (блок фор- 10 мирования произведения) и осуществляющее умножение множимого Х на множитель Ч = и,..., 2 л, причем в предварительно очищенный накопитель множимое X прибавляется Ч„ раэ,, 5 затем оно сдвигается влево на один разряд и вновь прибавляется в накопитель раз и так до тех пор, пока все разряды числа не будут обработаны (11.

Недостатком устройства является низкое быстродействие.

Наиболее близким к предлагаемому пс технической сущности является устройство для умножения, содержащее регистр множимого, И блоков вычисления разрядных значений произведения (И вЂ” число разрядов множимого), И буферных регистров первой группы и и буферных регистров второй группы, причем вход первого сомножителя каждого блока вычисления разрядных значений произведения соединен с выходом соответствующего разряда регистра множимого, вход второго сомножителя каждого бло-З- ка вычисления разрядных значений произведения соединен с входсм множителя устройства, входы первого и второго слагаемых младшего ра.зряда каждого блока вычисления разрядных 40 значений произведения соединены с выходами соответствующих буферных регистров Первой и второй групп, выходы значений младшего и старшего разрядов каждого блока вычисления разрядных значений произведения соединены с входами соответствующих буферных регистров первой и второй групп, выход первого буферного регистра второй группы подключен к выходу устройства, вход второго .слагаемого последнего блока вычисления разрядных значений произведения соединен с входом коррекции устройства (2).

Это устройство предназначено для перемножения чисел в произвольной позиционной системе счисления с основанием 9 > 22, в частности в в-ичнокодированной системе счисления с основанием М =Ь"(в-ичные разряды 60 группируются по К, где К вЂ” целое число и большее единицы ).

Недостатком такого устройства является относительно низкое быстродействие. Это связано с тем, что с 65 целью увеличения скорости vMHoReния чисел в известном устройстве необходимо стремиться к использованию более высокого основания и = Ь в-ично-кодированной системе счисления, так как это сокращает число тактов работы устройства.

Однако сокращение числа тактов эа счет увеличения основания приводит к существенному увеличению как длительности самого такта, так и объема используемого оборудования. Даже при использовании двоично-кодированной шестнадцатиричной систеж к счисления (т.е. когда К =4 и N = 2

16) для реализации каждого блока вычисления разрядных значений произведения требуется постоянная память емкостью 2 =65536 8-разрядных дво15 ичных слов. A это не позволяет реально обеспечить высокую скорость работы блоков вычисления разрядных значений произведения даже если сняты ограничения на объем используе лого в устройстве оборудования.

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

Т вЂ” задержка сигнала на одной ячейке сети.

Цель изобретения — повышение быстродействия устройства.

Поставленная цель достигается тем, что в устройство для умножения, содержащее регистр множимого, И блоков вычисления разрядных значений произведения (и — число разрядов множимого), буферные регистры первой и второй групп, причем вход первого сомножителя каждого блока вычисления разрядных значений произведения соединен с выходом соответствующего разряда регистра множимого, вход второго сомножителя каждого блока вычисления разрядных значений произведения соединен с входом множителя устройства, выходы значений младшего и старшего разрядов каждого блока вычисления разрядных значений произведения соединены с входами соответствующих буферных регистров первой и второй групп, выход первого буферного регистра второй группы подключен к выходу устройства, введена группа сумматоров, причем входы л -го сумматора группы (i =1,2,..., и †1 ) соединеиы с выходами i --ro буферного регистра первой группы и (+ 1)-го буферного регистра второй группы, входы М-го сумматора группы соединены с выходом И -го буферного регист1032453

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

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

f -го блока вычисления разрядных значений произведения (g =1,2,..., <) и j --ro сумматора группы в виде итеративной сети для случая двоичнокодированной шестнадцатиричной 15 системы счисления (к =4 и К=16); на фиг. 3 — функциональная схема ячейки, используемой в итеративной сети на фиг. 2.

Устройство содержит (И -разрядный) регистр 1 множимого, vl блоков 2 вы= числения разрядных значений произведения, и буферных регистров 3 первой группы, tl буферных регистров 4 второй группы, группу из И сумматоров 5, вход б множителя и вхол 7 коррекции устройства, выход 8 устройства. Вход первого сомножителя

1-го блока 2 вычисления разрядных значений произведения (y =1,2,..., И) соединен с выходом 9 -го разряда регистра 1 множимого, вход второго сомножителя — с входом 6 множителя устройства, входы первого и второго слагаемых младшего разряда — с выходами суммы и переноса j го сумма- 35 тора 5 группы, выход 10 старшего разряда соединен со входом у -го буферного регистра 3 первой группы и выход 11 младшего разряда — с входом ) -го буФерного регистра 4 вто- 4Q рой группы. Входы 1 -ro сумматора 5 группы (1=1,2,..., и -1) соединены с выходами 1 -го буферного регистра

3 первой группы и (1 +1)-го буферного регистра 4 второй группы, входы ф-го 45 сумматора 5 группы соединены с выходам И-го буферного регистра 3 первой группы и входом 7 коррекции устройства, выход первого буферного регистра 4 второй группы подключен к выходу 8 устройства. Совокупность у -го блока 2 вычисления разрядных значений произведения, -ro сумматора 5 и 4-ых буферных регистров

3 и 4 может быть конструктивно вы долнена в виде единого модуля 12, 55 реализованного, например, как большая интегральная схема. Не составляет никакого труда включение в этот модуль, если это будет признано целесообразным, соответствующего 60 разряда регистра 1 множимого в качестве его третьего буферного регист. ра. Этим обеспечивается лучшая однародность структуры устройства. 65

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

5 в виде итеративной сети для случая двоично-кодированной шестнадцатиричной системы счисления, т.е. когда

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

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

1 -го блока 2 вычисления разрядных значений произведения (нижний ряд сети из К ячеек 13 выполняет функцию сумматора 5, а остальная часть т сети из К ячеек 13 выполняет функцию блока 2 вычисления разрядных значений произведения . В ней производится умножение двоично-кодированной шестнадцатиричной цифры множимого Х = х х х х на двоично-коди4 Ъ 2 1 рованную шестнадцатиричную цифру множителя Y = у 4 у у у1 (возрастание индексов при буквенных обозначениях принято в направлении старших разрядов ) и прибавление к младшей двоично-кодированной шестнадцатиричной цифре получившегося при этом произведения трех двоично-кодированных шестнадцатиричных. цифр Ь1), М и N .

Цифра множимого Х поступает на вход сети с выхода 9 j -ro разряда регистра 1 множимого, цифра множителя М) — с входа 6 устроиства, цифры Ь 1 и È вЂ” с выхода j -го буферного регистра 3 первой группы и цифра )() — с выхода (j+1)-го буферного регистра 4 второй группы. На выходе

11 итеративной сети формируется младшая двоично-кодированная шест; надцатиричная цифра результата Р, а на выходе 10 — старшая цифра результата Р в циде двух цифр

Р) и Р „ (цифра Р старшего разряда результата образована поразрядными суммами, а цифра Р „ — поразрядными переносами).

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

Сумма 6 = А Ю Э Ю Е

Перенос С=А Ъ +(А6) _#_E, где =(р, Переносы С с выходов ячеек 13 сети передаются с одного ее ряда на другой и нигде не распространяются вдоль ряда справа налево, поэто1032453 му скорость работы итеративной сети определяется величиной (К+1), где

6 — задержка сигнала на одной ячейке сети.

Рассметренный вариант совместной реализации ).-го блока 2 вычисления разрядных значений произведения и

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

Устройство для умножения работа ет следующим образом. 20

B исходном состоянии буферные регистры 3 и 4 всех модулей 12 обнулены, в регистре 1 множимого хранится без знака И -разрядный

2"-ичный код множимого(И К -разрядный двоичный код множимого). Здесь предполагается, что сомножители представлены в двоично-кодированной 2 -ичной системе счисления, т.е. каждый разряд как множимого, так и множителя, представляет собой

30 набор из К двоичных цифр.

В каждом из И первых тактов .ра6о.ты устройства на его вход б поступает параллельно К двоичных разрядов множителя, начиная с младших разрядов. При этом в j --ом блоке 2 вычисления разрядных значений произведения осуществляется умножение К двоичных разрядов множимого, поступаю щих íà его вход первого сомножителя 40 с выхода 9 j -го 2 -ичного разряца к регистра 1 множимого, на к двоичных разрядов множителя, поступающих на его вход второго сомножителя с входа

6 устройства, и прибавление к К млад-45 шим двоичным разрядам получившегося при этом 2 К -разрядного произведения по его входам первого и второго слагаемых через -ый сумматор 5 K младших двоичных разрядов произведе- g0 ния (j+1)-го блока 2, сформированных в предыдущем такте в однорядном, коде и хранимых в буферном регистре

4 (+1) -го модуля 12 и K. старших двоичных разрядов произведения j --го с5 блока 2, сформированных в предыду-. щем такте в двухрядном коде и хранимых в буферном регистре 3 j-го модуля 12. После этого сформированные в однорядном коде К младших двоичных разрядов произведения j -го блока 2 с его выхода 11 записываются в j -ый буферный регистр 4, а К старших. разря. дов произведения, представленного в двухрядном коде — c его выхода 10 в j -ый буферный регистр 3. i 65

После выполнения И первых тактов работы устройства на его вход 6 поступает нулевая информация и далее осуществляется еще дополнительно И тактов, в течение которых из устройства выводится с соответствующим преобразованием информация, хранимая в буферных регистрах 3 и 4 всех модулей 12. Вывод 2 И -разрядного произведения сомножителей в устройстве осуществляется через его выход

8 в параллельно-последовательном коде (по К двоичных разрядов в каждом такте). В рассмотренном случае на вход 7 коррекции устройства во всех его и дополнительных тактах подается,К -разрядных двоичный код

0...000. В тех же случаях, когда треК буется получить округленное И -разрядное произведение, необходимо в первом такте работы устройства на его вход 7 коррекции подать К -разрядный двоичный код,100...000. Это позволяет осуществитьоивтуглеи ие произведения без дополнительных временных затрат. Используя определенным образом вход 7 коррекции устройства можно одновременно выполнять операцию умножения И -разрядных чисел Х и у с суммированием к И старшим разрядам получившегося при этом произведения и -разрядного слагаемого 1, т.е. в одном цикле работы устройства выполнять сложную опеРацию Q =X 3 + Z . Для этого необходимо в течение И тактов работы устройства, начиная со второго, подавать в каждом такте на вход 7 коррекции устройства по К двоичных разрядов слагаемого «Z, начиная с его младших разрядов, причем это прибавление слагаемого Z может осуществляться либо к округленным И стар-, шим разрядам произведения, либо просто к усеченным Й старшим Разрядам произведения.

Умножение И -разрядных чисел в предлагаемом устройстве (как и в известном) можно выполнять и за (n + 1) тактов, если после выполнения Vl --го такта содержимое буферных регистров 3 и 4 модулей 12 подать для окончательного суммирования на соответствующие входы быстродействующего трехвходового сумматора (на фиг, 1 такой сумматор не показан, а только отмечены штриховыми линиями дополнительные цепи передачи информации с выходов буферных регистров 3 и 4 на входы сумматора).

Это может быть особенно целесообразным, если например, арифметико-логическое устройство ЭВМ содержит подобный сумматор.

Таким образом, окончательное произведение в предлагаемом устройстве, так же как и в известном; может

1. 032 1

10

Составитель А.Иостак

Редактор О.Сопко Техред И.Гайду Корректор A.Ïoâõ

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

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

113035, Москва, Ж-35, Раушская наб., д. 4/5 филиал ППП "Патент", r. Ужгород, ул. Проектная, 4 быть сформировано за 2 И или(»+1) тактов. Однако длительность выполнения одного такта в предлагаемом устройстве существенно сокращена, потому что все блоки 2 вычисления разрядных значений произведения формируют на своем выходе 10 старшую цифру разрядного произведения в виде двух цифр, т.е. в двухрядном коде, а это исключает потери времени на приведение в каждом такте работы устройства двух1идно с кола в однорядный. Так, например, в оп чае реализации блоков ? вычисления разрядных значений проиçl-олен»я II виде итеративной сети длительность такта работы устройства-п1 ототипа примерно равна (2 К -1) <., в то время как в предлагаемом устройстве она составляет величину (К +1) Г где à — задержка сигнала на одной ячейке сети.