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

Изобретение относится к вычислительной технике и может быть использовано при разработке быстродействующих устройств умножения чисел, представленных в любой позиционной системе счисления,

Цель изобретения - повышение быстродействия за счет сокращения длительности такта.

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

выход младшего разряда j-ro одноразрядного узла умножения (j 2. .... п) соединен с входом первого слагаемого Q - 1)-го комбинационного сумматора первой группы, выход суммы i-ro комбинационного сумматора первой группы соединен с входом первого слагаемого (i + 1)-го комбинационного сумматора второй группы, выход суммы k-ro комбинационного сумматора второй группы (к . 1, ..., п + 1) соединен с входом k-ro регистра промежуточного результата, выход младшего разряда первого одноразрядного узла умножения соединен с входом первого слагаемого первого комбинационного сумматора второй группы, вход второго слагаемого которого соединен с выходом второго регистра промежуточного результата, вход переноса второго комбинационного сумматора второй группы соединен с выхоV|

00

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

триггеров переноса и п - 1 коммутаторов,

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

1)-го комбинационного сумматора второй группы, вход второго слагаемого (п + 1)-го комбинационного сумматора второй группы соединен с входом коррекции устройства, управляющий вход которого соединен с управляющим входом t-ro коммутатора, выход которого соединен с входом переноса (t +

2)-го комбинационного сумматора второй группы.

Заявляемое устройство содержит следующие отличительные признаки, не обна- руженные ни в одном из известных аналогичных устройств:

. 1) оно дополнительно содержит п триггеров переноса и п - 1 коммутаторов;

2) выходы переноса комбинационных сумматоров второй группы соединены с первыми информационными входами соответствующих коммутаторов и входами соответствующих триггеров переноса, выходы которых соединены с входами переноса со- ответствующих комбинационных сумматоров первой группы;

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

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

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

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

Предлагаемое устройство для умножения содержит п одноразрядных узлов 1 умножения (п - разрядность множимого), п комбинационных сумматоров 2 первой группы, п + 1 комбинационных сумматоров 3 второй группы, п + 1 регистров 4 промежуточного результата, п триггеров 5 переноса и п - 1 коммутаторов б, входы 7, 8, 10 и 11 множителя, множимого, константы, коррекции и управляющий устройства соответственно, первый 12 и .второй 13 выходы устройства. Вход множителя i-ro узла 1 ( 1, ..., п) соединен с входом 7 устройства, вход множимого - с i-м разрядом-входа 8 устройства, выход 15 младшего разряда j-ro узла 1Q 2,.... п)соединен с входом первого слагаемого Q - 1)-го сумматора 2, вход второго слагаемого которого соединен с выходом 22 0 + 2)-го регистра 4, выход 14 старшего разряда t-ro узла 1 (t 1, .... п- 1) соединен с входом второго слагаемого (t + 1)-го сумматора 3,-выход 19 переноса которого соединен с входом t-ro триггера 5 и первым информационным входом t-ro коммутатора 6, второй, информационный вход которого соединен с выходом 16 переноса t-ro сумматора 2, выход 17 суммы i-ro сумматора 2 соединен с входом первого слагаемого (i + 1)-го сумматора 3, выход 20 суммы k-ro сумматора 3 (к 1, ..., п + 1) соединен с входом k-ro регистра 4, выход 15 первого узла 1

соединен с входом первого слагаемого пер- вого сумматора 3, вход второго слагаемого которого соединен с выходом 22 второго регистра 4, вход переноса второго сумматора 3 соединен с выходом 19 переноса пер- вого сумматора 3, выход 20 суммы которого соединен с входом первого регистра 4, вы- . ход 22 которого подключен к первому выходу 12. устройства, вход 19 константы которого соединен с входом первого слага- емого n-го сумматора 2, вход второго слагаемого которого соединен с выходом 14 п-го узла 1, вход второго слагаемого (п + 1)-го сумматора 3 соединен с входом .10 коррекции устройства, управляющий вход 11 кото- рого соединен с управляющим входом t-ro коммутатора 6, выход 21 которого соединен с входом переноса (t + 2)-го сумматора 3, выход 19 переноса (п + 1)-го сумматора 3 соединен с входом (п - 1)-го триггера 5, вы- ход 18 которого соединен с входом переноса n-го сумматора 2, выходы 22 регистров 4 со второго по n-й подключены ко второму выходу 13 устройства.

Рассмотрим функциональное назначе- ние и реализацию узлов и блоков предлагаемого устройства.

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

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

Регистры 4 предназначены для хранения информации, формируемой на выходах 20 суммы соответствующих сумматоров 3, и могут быть реализованы, на синхронных двухтактных D-триггерах с входами установки в нулевое состояние.

Триггеры 5-предназначены для хране- ния переносов, возникаюаи-ix при работе сумматоров 3, и;могут быть реализованы на синхронных двухтактных D-триггерах с входами установки в нулевое состояние.

Коммутаторы б предназначены для пе редачи информации на выходы 21 (входы переноса сумматоров 3) со своих первого и второго информационных входов (выходов 19 и 16 переноса соответственно сумматоров 3 и 2) в зависимости от сигнала-на их управляющих входах (входе 11 устройства). Они могут быть реализованы на элементах 2И23 - 2ИЛИ24, как показано на фиг. 2.

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

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

В исходном состоянии регистры 4 и триггеры 5 обнулены, на входе 8 устройства присутствует без знака п-разрядный 2 -ич- ный код множимого ( - разрядный двоичный код множимого). Предполагается, что множимое и множитель представлены в двоично-кодированной 2 -ичной системе счисления, т.е. каждый разряд как множимого, так и множителя представляет собой набор из k двоичных цифр. На вход 9 устройства подана нулевая константа, а на вход 11 устройства - сигнал, настраивающий коммутаторы 6 на передачу информации только с их вторых информационных входов (с выходов 16 сумматоров 2). Умножение в устройстве осуществляется за п + 1 тактов,

В каждом из п первых тактов работы ус ройства на его вход 7 поступает один 2к-ичный разряд множителя (параллельно k двоичных разрядов). При этом на выходах 14 и 15 i-ro узла 1 формируются соответственно старший и младший разряды двухразрядного произведения соответствующего разряда множителя, поступающего на его вход множителя с входа 7 устройства, на i-й разряд множимого, поступающий на его вход множимого с i-ro разряда входа 8 устройства. Младший разряд произведения J- го угла 1 (j 2, ..., п) поступает на вход первого слагаемого (j - 1)-го сумматора 2, а младший разряд произведения первого узла 1 - на вход первого слагаемого первого сумматора 3. Эти младшие разряды суммируются с соответствующими разрядами сум- мычастичных произведений, сформированными в предыдущем такте и хранимыми в соответствующих регистрах 4. В сумматорах 2, кроме того, подсуммируют- ся соответствующие разряды переносов, сформированные в предыдущем такте на выходах 19 сумматоров 3 и хранимые в соответствующих триггерах 5. С выхода 17 t-ro сумматора 2 (t 1. ..., п - 1) разряд суммы поступает на вход первого слагаемого (t + ,1)-го сумматора 3, где суммируется с поступающим на его вход второго слагаемого старшим разрядом произведения t:ro узла 1 и поступающим на его вход переноса разрядом переноса соответствующего сумматора 2 (для второго сумматора 3 на вход переноса поступает информация с выхода 19 переноса первого сумматора 3), сформированного

в этом же такте на выходе 16 соответствующего сумматора 2. В n-м сумматоре 2 к старшему разряду произведения п-го узла. 1 подсуммируется нуль с входа 9 устройства и разряд переноса (п + 1)-го сумматора 3, сформированный в предыдущем такте и хранимый в n-м триггере 5. По окончании каждого такта с выходов 19 и 20 сумматоров

3 в соответствующие триггеры 5 и регистры

4 записываются разряды суммы частичных произведений сомножителей в двухрядном коде. ..

После выполнения п первых идентичных тактов работы устройства на его вход 7 множителя поступает нулевая информация, а на его вход 11 - сигнал, настраивающий коммутаторы 6 на передачу информации с их первых и вторых информационных входов (с выходов 19 сумматоров З и выходов 16 сумматоров 2) и далее осуществляется еще один такт, в течение которого в сумматорах 2 и 3 суммируется информация, хранимая в соответствующих регистрах. 4 и триггерах 5. Следует отметить, что на выходах 16 и 19 переносов сумматоров 2 и 3 в этом такте переносы не могут возникнуть одновременно. Это позволяет упростить структуру коммутаторов 6 и осуществить формирование однорядного кода произведения в течение одного такта.

Вывод п + 1 младших 2k-H4Hbix разрядов 2п-разрядного произведения в устройстве осуществляется через его выход 12 по одному разряду в каждом такте работы устройства, вывод п - 1 старших 2и-ичных разрядов произведения - через выход 13 в (п + 1)-м такте работы устройства.

В рассматриваемом случае на вход 10 устройства во всех п + 1 тактах его работы подавалась нулевая информация. Если же требуется подсуммировать к вычисляемому произведению дополнительные слагаемые, например, при округлении или при введении коррекции по знакам множимого и множителя при умножении чисел, представленных в дополнительном коде, то необходимо подать на соответствующий вход 10 требуемую информацию, что обеспечит подсуммирование без дополнительных временных затрат.

Произведем сравнение предлагаемого устройства и устройства-прототипа по быстродействию выполнения операции умножения14-разрядных 2k-H4Hbix сомножителей (56-разрядных двоичных со- множителей, т.е. п 14, k А).

Пусть регистры промежуточного результата сравниваемых устройств и триггеры переноса предлагаемого устройства реализованы на микросхемах типа

К555ТМ8, представляющих из себя 4 синхронных D-триггера с входами установки в нулевое состояние, имеющие задержку- tip 28 не.

Пусть для реализации одноразрядных узлов 1 умножения используются ПЗУ типа 556РТ5 емкостью 512л 8. В этом случае на одной микросхеме можно построить 4-разрядный двоичный умножитель, имеющий за держку гумн 70 не.

Пусть комбинационные сумматоры первой и второй групп реализованы на 4-разрядных сумматорах с ускоренным переносом типа К555ИМ6, имеющим следующие величины задержек: а) от входа до выхода переноса tci 17 не; б) от входа до выхода суммы tC2- 24 не.

Пусть коммутаторы.предлагаемого устройства реализованы на микросхемах К555КП11, представляющих из себя четыре двухвходовых мультиплексора с задержкой tx 18 не. Длительность такта работы известного устройства складывается из задержки на одноразрядном узле умножения (хумн), задержки на комбинационных сумматорах первой группы, включающей время на формирование сигнала переноса в первом сумматоре (tci), время на распространения переноса через п-2 сумматоров и время на формирование значения суммы в n-м сумматоре (tC2), задержки на комбинационных сумматорах второй группы, равной времени на формирование значения суммы в (п + 1)-м сумматоре (tea), поскольку остальные п комбинационных сумматоров второй групт.: работают параллельно с п комбинационными сумматорами первой группы, а также задержки н а запись суммы частичных произведений в регистры промежуточного результата (tTp), т.е.

tM3B tyMH + tc1 + (П - 2) tci + tc2 + tc2 + tip 70 + 17n + 7 + 24 + 22 17n + 123 .(не).

При п 56/4 14 длительность такта работы известного устройства составляет 17г. 14 + 123 361 (не). Произведение формируется за п тактов, поэтому время выполнения операции умножения 56-разрядных сомножителей равно:

Тизв tM3D# п 5054 (не).

Для реализации известного устройства требуется 14 микросхем 556 РТ5 (одноразрядные узлы умножения). 29 микросхем К555ИМ6(комбинационные сумматоры первой и второй групп) и 15 микросхем К555ТМ8 (регистры промежуточного результата), т.е. всего 58 микросхем.

Длительность каждого из п первых тактов работы предлагаемого устройства скла- дывается из задержки на одноразрядном узле умножения (т.умн), задержки на комбинационном сумматоре первой группы от его входа до его выхода переноса (tci), задержки на коммутаторе (tK), задержки на формирование суммы в комбинационном сумматоре второй группы (tC2), а также задержки на запись суммы частичных произведений в регистры промежуточного результата и триггеры переноса (tTp), т.е.

tn

предл.

: 1умн + tc1 + tK + tc2 + trp 70 + 17+

+ 18 + 24 + 22 151 (не).

Длительность (n + 1)-го такта определяется задержкой на формирование суммы в комбинационных сумматорах первой группы (tea), (одновременно работает первый комбинационный сумматор второй группы), задержкой на распространение переноса через п - 2 комбинационных сумматоров второй группы (tci) и п - 2 коммутаторов (t), задержкой на формирование суммы в п-м комбинационном сумматоре второй группы (tc2), а также задержки на запись п старших разрядов произведения в регистры промежуточного результата (tTp). т.е.

1п+1предл tc2 + (п - 2)tci + (п - 2)tK + tea + +tTp. 24 + 17n - 34 + 18n - 36 + 24 + 22 - 35n (не).

Время выполнения операции умножения 56-разрядных сомножителей (п 14) равно: .

упредл {ппредл n + tn+1 предл 151л14 + 2601 (не).

Для реализации предлагаемого устройства требуется 14 микросхем 556 РТ5 (одноразрядные узлы умножения), 29 микросхем К555ИМ6 (комбинационные сумматоры первой и второй групп), 19 микросхем К555ТМ8 (регистры промежуточного результата и триггеры переноса) и 4 микросхемы К555КП11 (коммутаторы), т.е. всего 66 микросхем.

Таким образом, быстродействие в предлагаемом устройстве будет в тизв/Тпредл 5054/2601 1,9 раза выше, чем в известном. Следует отметить, что выигрыш в быстродействии будет еще более значительным при реализации одноразрядных узлов умножения в виде комбинационных схем,в которых младшая цифра произведения разрядов сомножителей формируется быстрее, чем старшая, за счет параллельного

формирования результатов комбинационных сумматоров первой группы и старшей цифры произведения одноразрядных узлов умножения. Следует особо отметить, что ап- 5 паратурные затраты на реализацию предлагаемого устройства возросли всего на 14 %, т.е. предложенное техническое решение является высокоэффективным.

Технико-экономическое преимущество

0 предлагаемого устройства для умножения в сравнении с известным заключается в его более высоком быстродействии (при вычислении произведения 56-разрядных двоичных сомножителей с использо.ванием

5 4-разрядных узлов и блоков предлагаемое устройство имеет в 1,9 раза выше быстродействие, чем известное).

Формула изобретени-я Устройство для умножения, содержа0 щее п одноразрядных узлов умножения (п - разрядность множимого), п комбинационных сумматоров первой группы, (п + 1) комбинационных сумматоров второй группы и (п + 1) регистров промежуточного результа5 та, причем вход множителя i-ro одноразрядного узла умножения (i 1, .... п) соединен с входом множителя устройства, вход множимого i-ro одноразрядного узла умножения соединен с входом i-ro разряда множимого

0 устройства, выход младшего разряда j-ro одноразрядного узла умножения (j 2, ..., п) соединен с входом первого слагаемого 0 - 1)-го комбинационного сумматора, первой группы, выход суммы ijro комбинационного

5 сумматора первой группы соединен с входом первого слагаемого (i + 1)-го комбинационного сумматора второй группы, выход суммы К-ro комбинационного сумматора второй группы (К 1, .... п + 1) соединение

0 входом К-го регистра промежуточного результата, выход младшего разряда первого одноразрядного узла умножения соединен с входом первого слагаемого первого комбинационного сумматора второй группы,

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

5 комбинационного сумматора первой группы, вход второго слагаемого которого соединен с выходом старшего разряда п-го одноразрядного узла умножения, второй выход устройства соединен с выходами регистров промежуточного результата с втоporo no n-й, отличающееся тем, что, с целью повышения быстродействия устройства, з него введены г. триггеров переноса и п - коммутаторов, причем выход старшего разряда t-ro одноразрядного узла умножения (t 1, ,.., п -1}соединен с входом второго слагаемого (t + 1)-го комбинационного сумматора второй группы, выход переноса которого соединен с входом t-ro триггера переноса и первым информационным входом t-ro коммутатора, второй информационный вход которого соединен с выходом переноса t-ro комбинационного сумматора первой группы, вход второго слагаемого которого соединен с выходом (t + 2)-го регистра промежуточного результата, вход переноса i-ro комбинационного сумматора первой группы соединен с выходом i-ro

триггера переноса, вход первого триггера переноса соединен с выходом (п + 1)-го комбинационного сумматора второй группы, вход второго слагаемого (п + 1)-гр комбинационного сумматора второй группы соединен с входом коррекции устройства, управляющий вход которого соединен с управляющим входом t-ro коммутатора, выход которого соединен с входом переноса (t+2)-ro комбинационного сумматора второй группы.

Изобретение относится к вычислительной технике и может быть использовано при разработке быстродействующих устройств умножения чисел, удобных для изготовления с применением БИС и СБИС. Цель изобретения - повышение быстродействия устройства за счет сокращения длительности такта. Устройство содержит п одноразряд- . ных узлов умножения (п - разрядность множимого), п комбинационных сумматоров первой группы, (п + 1) комбинационных сумматоров второй группы, (п + 1) регистров промежуточного результата и нововведенные п триггеров переноса и (п - 1) коммутаторов, введение которых позволило организовать вычислительный процесс так, что возникающие в каждом такте переносы не распространяются через всю цепь сумматоров, а запоминаются в соответствующих триггерах переноса, чем уменьшается длительность такта работы устройства. 2 ил.

21

г чч«чг

&

23

19

16