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

Изобретение относится к вычислительной технике и может быть использовано при разработке быстродействующих устройств для умножения чисел,, представленных в любой позиционной системе счисления. Особенно эффектив но его применение при использовании больших интегральных схем, в частнос ти, при разработке высокопроизводительных наращиваемых микропроцессоро и микропроцессорных систем. Известно устройство для умножения содержащее регистры множимого.и множителя, накапливающий сумматор, п/2 одноразрядных узлов умножения (п-раз рядность множимого Г и блок управления, выходы которого соединены с управляющими входами регистров множимо го, множителя и накапливающего сумматора, первый вход i-ro одноразрядного узла умножения (i t,2,...,п/2 ) соединен с выходом первого разряда регистра множителя, а второй вход выходом (21-1 )-го. разряда регистра множимого, выходы одноразрядных узло умножения соединены с соответствующими входами накапливающего суммато ра. Данное устройство иожет быть использовано для умножения чисел,представленных в произвольной позиционной системе счисления с основанием СП. Основным недостатком известного устройства является низкое быстродействие, вызванное в первую очередь двухшаговым 1принципом обработки одной цифры множителя. Кроме этого для/ устройства характерна низкая эффекти ность при реализации его на больших интегральных схемах (устройство кроме однотипных одноразрядных узлов ум ножения содержит регистры множимого и множителя с цепями сдвига, накапли вающий сумматор с распространением переноса и с цепью сдвига, а также несколько сложный блок управления). Известны устройства для умножения, содержащие регистры множимого и множителя, накапливающий сумматор и п операционных модулей. Эти устройства также предназначены для пе.ремножения чисел в произвол ной позиционной системе счисления с основанием С2,СЗЗ. Основными недостатками устройств являются относительно низкое быстродействие и невысокая эффективность 1 7J при реализации их на больших интегральных схемах. Наиболее близким к предлагаемому является устройство дгя умножения, содержащее п-разрядный регистр множиjMOro, л блоков вычисления разрядных значений произведения, п буферных регистров первой группы и п буферных регистров второй группы,причем входы -буферных регистров первой и второй групп соединены соответственно с выходами старшего и младшего разряда соответствующих блоков вычисления разрядных значений произведения, первый вход i-ro блока вычисления разрядных значений произведения i(n 1,2п) соединен с выходом Ч-го разряда регистра множимого, второй вход - с входом множителя устройства, третий вход - с выходом i-ro буферного регистра первой группы, четвертый вход - с выходом (i + 1 )-го буферного регистра второй группы, выход первого буферного регистра второй группы подключен к выходу устройства, четвертый вход последнего блока вычисления разрядных значений пооизведения соединен с входом коррекции устрюйства. Известное устройство предназначено для перемножения чисел в произвольной позиционной системе счисления с основанием . В частности, интересен случай использования в-ично-кодированной системы счисления с основанием N в(когда в-ичные разряды группи руются по К, где К - целое число и большее единицы), при использовании которой имеется принципиальная возможность повысить быстродействие устройства примерно в К раз по сравнению со случаем использования в-ичной системы счисления. Особый интерес представляет устройство в случае перемножения двоично-кодированных операндов р сис,к теме счисления с основанием N 2 В этом случае каждый разряд.как множимого, так и множителя представляет собой набор из К двоичных цифр, а перемножение двух п-разрядных 2 -ичных чисел эквивалентно перемножению двух п-К-разрядных двоичных чисел, разряды которых сгруппированы по кС ЗНедостатком известного устройства является его ограниченное быстродействие. Это связано с тем, что с целью величения скорости умножения чисел в устройстве необходимо стремиться к

использованию более высокого основания в-ичнокодированной системы счисления, так как это сокращает число тактов работы устройства. Однако

сокращение числа тактов за счет увеличения основания приводит к существенному увеличению длительности самого такта (длительность такта определяется в основном скоростью работы блоков вычисления разрядных зна(Чений произведения).Действительно, Ьусть блоки вычисления разрядных значений произведения в известном устройстве реализованы в виде постоянного запоминающего устройства. Но тогда даже при использовании двоично-кодированной 1б-ричной системы счисления.(т.е. когда , и N 2 t6) для реализации каждого блока вычисления разрядных значений произведения требуется постоянная память емкостью 2 65536 8-разрядных двоичных слов. А это не позволяет pealibHO обеспечить- высокую скорость работы блоков вычисления разрядных значений произведени при сколь-нибудь больших значениях К, даже если снять ограничения на объем используемого в устройстве умножения оборудования. Реализация же блоков вычисления разрядных значений произведения по матричному принципу, например, в виде однородной ячеечной структуры С5 , наряду с многими достоинствами также не обеспрчивает их высокого быстродействия, так как время формирования результата на их выходах при использовании двоично-кодированной системы счисления с основанием составляет величину (2К-1) IT , где t- задержка сигнала на одной ячейке.

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

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

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

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

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

Устройство для умножения (фиг.1) содержит п-разрядный регистр 1 множимого, п блоков 2 вычисления разрядных значений произведения, п буферных регистров 3 первой группы и п буферных регистров k второй группы, вход 5 множителя устройства, вход 6 коррекции устройства и выход 7 устройства. Первый вход 1-го блока вычисления разрядных значений произведения (-Г t,2, . ...,п) соединен с выходом 8 I-го разряда регистра 1 множимого, второй вход - с входом 5 множителя устройства, третий вход - с выходом -го буферного регистра 3 первой группы, четвертый - с выходом I-го буферного регистра Ц второй группы и пятый

0 вход соединен с выходом 9 младшего разряда (i+1)-го блока 2 вычисления разрядных значений произведения. Первый 10 и второй 11 выходы i-ro блока 2 вычисления разрядных значений произве

5 дения соединены с входами i-ых буфер, ных регистров 3 и 1 первой и второй групп соответственно. Пятый вход п-го (самого старшего) блока 2 вычисления разрядных значений произведения соединен с входом 6 коррекции устройства, выход 9 младшего разряда первого (самого младшего) блока 2 вы числения разрядных значений произве дения подключен к выходу 7 устройства. Совокупность i-ro блока 2 вычисления разрядных значений произведения и i-ых буферных регистров 3 и первой и второй групп соответственно может быть конструктивно выполнен в виде единого модуля 12, реализован ного, например, как большая интеграль ная схема. Не составляет особого тру да включение в этот модуль, если это конечно будет признано целесообразным, t-ых разрядов регистра 1 мно жимого и регистра множителя (не пока зан) в качестве его третьего и метшертого буферных регистров. Это обеспечивает однородность устройстра умножения на уровне идентичных модулей 12. Все триггеры устройства могут быть реализованы на двухтактных синхронных D-триггерах (цели синхронизации не показаны). На фиг. 2 показан один из возможных вариантов реализации i-ro блока 2 вычисления разрядных значений произведения в виде однородной ячеечной структуры (здесь предполагается, что в устройстве используется в-ично-кодированная система счисления с основанием ,причем К принято равным четырем) Блок 2 содержит К идентичных ячеек 13.обра зующих итеративную сеть,подобную описанной в С7 3 и фо-рмируЮ1цую старшую в-ично-ко ированную N-ичную цифр разрядного произведения в виде двух в ично-кодированных N-ичных цифр (цифры суммы и цифры переноса), как это сделано, например, в б для случая . В блоке 2 производится умножение в-ично-кодированной N-ично цифры множимого XlXjX2X на в-ич но-кодированнук} Н-ичную цифру множителя 2: (возрастание индексов при буквенных обозначениях принято в направлении старших разрядов), а также прибавление к младше в-ично-кодированной N-ичной цифре по лучившегося при этом разрядного произведения двух, в-ично-кодированных М-ичных цифр М , R и К старшей в-ично-кодированной N-ичной цифре разрядного произведения одной в-ично-кодированной N-ичной цифры . Цифра множимого X поступает на первый вход блока 2 с выхода 8 1-го разряда регистра 1 множимого, цифра множителя У подается на второй вход блока 2 с входа 5 устройства, цифры М , R поступают на третий и четвертый входы блока 2 с выходом i-ых буферных регистров 3 и 4 первой и второй групп соответственно, цифра 1, прдается на пятый вход блока 2 с выхода 9 младшего разряда (1 + 1)то блока 2 вычисления разрядных значений произведения.На выходе 9 i-ro блока 2 вычисления разрядных значений произведения формируется младшая в-ично-кодированная N-ИЧ7 ная цифра разрядного произведения РД, а на выходах 10 и 11 образуется старшая в-ично-кодированная N-ичная цифра разрядного произведения Р в виде двух в-ично-кодиров.анны; N-ичных цифр соответственно Р,, (цифра Р(Образована поразрядными в-ичными суммами, а цифра поразрядными в-ичными переносами ). На фиг. 3 приведена функциональная схема ячейки 13, используемой в блоке 2 вычисления разрядных значений произведения на фиг.2 для случая, когда , т.е. когда в устройстве применяется двоично-кодированная система счисления с основанием N 2 Ячейка 13 содержит одноразрядный двоичный сумматор Т Ц, двухвходовой элемент И 15 и функционирует в соответ:ствии со следующими логическими выражениями:Сумма S c40cl5e Перенос С « Л d V (аф dM е где d d f Устройство для умножения работает следующим образом. В исходном состоянии буферные регистры 3 и всех модулей 12 обнулены, в регистре 1 множимого хранится без Знака п-разрядный в-ичный код множимого (n-k - разрядный вичный код множимого). В каждом из п первых тактов работы устройства на его вход 5 поступает параллельно К в-ичных разрядов множителя, начиная с его младших разрядов (предполагается, что множимое и множитель имеют одинаковую разрядность ).При этом в i-OM блоке 2 вычисления разрядных значений произведения осуществляется умножение К в-ичных разрядов множителя, поступающих на его второй вход с входа 5 устройства, на К в-ичных разрядов множимого, поступающих на его первый .вход с выхода 8 1-го в -ичного разряда регистра 1 множимого, и прибавление к К младшим в-ичным разрядам получившегося при этом 2К-разрядного произведения через третий и четвертый входы К старших в-ичных разрядов произведения i-ro блока 2,.сформированных в предыдущем такте в двухрядном коде и хранимых в буферных регистрах 3 и 4 i-ro модуля 12, а также прибавление через пятый вход К к старшим в-ичным разрядам 2К-разрядного произведения К младших в-ичных разрядов 2К-разряд ного произведения i-ro модуля 12, формируемых в данном такте на выходе 9 (i + l)-ro блока 2 вычисления раз рядных значений произведения. После этого К старших в-ичных разрядов 2Кразрядного произведения, представлен ных в двухрядном коде, с выходов 10 и 11 i-ro блока 2 записываются в i-ые буферные регистры 3 и 4 соответственно. После выполнения п первых тактов работы устройства на его вход 5 поступает нулевая информация и далее осуществляется еще дополнительно п такто.в, в течение которых из устро ства выводится с соответствующим преобразованием информация, хранимая в буферных регистрах 3 и 4 всех моду лей 12. Вывод 2п-разрядного произведения сомножителей в устройстве осуществляется через его выход 7 в п раллельно-последовательном коде (по К в-ичных разрядов в каждом такте).В рассмотренном случае на вход 6 коррекции устройства во всех его п дополнительных тактах подается К-раз рядный в-ичный код .00... 000 . В тех К случаях, когда тре6уетч;я получить округленное п-разрядное произведение необходимо в самом начале процесса умножения (например, до приема сомножителей) пбдать на вход 6 коррекции устройства К-разрядный в-ичный код Jb/20.-.000, и произвести с не -j которой задержкой запись результатов, сформированных на выходах блоков 2 вычисления разрядных произведе ний, в буферные регистры 3 и t модулей 12. В результате этого в буфер1078 ном регистре 3 последнего модуля 12 будет записан код .Ъ/2 О... 000.. котоii-r.mi -I рый и позволит в процессе умножения осуществить округление результата без дополнительных временных затрат. Очевидно, что используя определенным образом вход 6 коррекции устройства, можно одновременно осуществлять операцию умножения п-разрядных в -ичных чисел X и У с суммированием п-разряднопо в -ичного слагаемого Z, т.е. в одном цикле работы устройства , полнять сложную функцию С XY + Z . Дпя этого необходимо в течение п первых тактов работы устройства подавать на его вход 6 коррекции в каждом такте К в-ичных разрядов слагаемогоЕ, начиная с его младших разрядов, причем это прибавление может рсуществляться либо к округленным п старшим разрядам произведения Х«У, либо просто к усеченным его п старшим разрядам. Следует особо отметить, что умножение п-разрядных чисел в предла- . гаемом устройстве, можно выполнять за (п+1) тактов, если после выполнения пто такта содержимое буферных регистров 3 и всех модулей 12 подать для окончательного суммирования на соответствующие входы быстродейст-вующего двухвходового сумматора (на фиг. 1 эти дополнител4 ные цепик передачи информации с выходов буферных регистров 3 и Ц отмечены штриховыми линиями),Это мбжет быт1э целесообразным,если,например,арифметико-логическое устройство ЭВМ содержит подобный быстродействующий сумматор. Таким образом,окончательное произведение в предлагаемом устройстве, так же как и в С) может быть сформировано за 2п или (n+l) тактов,Однако длительность выполнения одного такта в предлагаемом устройстве существенно сокращена. Действительно, пусть в известном и предлагаемом устройствах применяется в-ично-кодированная в -ичная система счисления и при реализации блоков вычисления разрядных значений произведения в известном устройстве используется быстродействующая однородна ячеечная структура, подобная описанной в{ 73-13 в предлагаемом устройстве - ячеечная структура, изображенная на rtinr.Z (основное отличие структур,показанных на фиг.2,3 от структур, описа нных в 73 состоит в что во-первых,старшая в -ичная цифра разрядного произведения формируется в виде двух цифр, т.е. в двухрядном коде, в то время, i-как, во-вторых- структурах эта цифра образуется в однорядном коде). Тогда в предлагаемом устройстве длительность одного такта работы примерно равна ((ц в то время, как в известном устройстве эта длительность составляет величину (ZK-Ot , так как на приведение переносов при формировании в -ичной старшей в-ично кодированной цифры разрядного произведения в его блоках вычисления разрядных значений произведения затрачивается время (IC-I )Т .(здесь через обозначена задержка информации в одной ячейке блока вычисления разрядных значений произведения). 10 7 Предлагаемое уст|эойство для умножения чисел при том же объеме используемого оборудования обеспечивает в (2К-1 )К раза более высокое быстродействие, чем известное. Оно может быть изготовлено из множества однотипных взаимоз аменяемых модулей, каждый из которых удобен для реализации в виде БИС, причем переход от уст;ройства с большим к устройствам с форматом обрабатываемой информации и наоборот фактически сводится к пропорциональному уменьшению либо увеличению числа используемых модулей. Если соответствующие разряды регистров множимого и множителя ввести в операционные модули,то устройство будет состоять только из однотипных модулей, что делает особенно перспективным при разработке высокопроизводительных наращиваемых микропроцессоров и микропроцессорных систем.;

УСТРОЙСТВО ДЛЯ УМНОЖЕНИЯ, содержащее п-разрядный регистр множимого, п блоковвычисления разрядных значений произведения, п буферных тп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-го буферного регистра второй группы, а пятый вход - с выходом младшего разряда