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

 

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

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

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

РЕСПУБЛИК (я)5 G 06 F 7/52

ГОСУДАРСТВЕННОЕ ПАТЕНТНОЕ

ВЕДОМСТВО СССР (ГОСПАТЕНТ СССР) ОПИСАНИЕ ИЗОБРЕТЕНИ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4922288/24 (22) 29.03.91 (46) 07.04,93, Бюл, N- 13 (71) Научно-исследовательский институт электронных вычислительных машин (72) А,А.Шостак и В.B.ßñêåâè÷ (56) Авторское свидетельство СССР

N 763897, кл, G 06 F 7/52, 1978.

Авторское свидетельство СССР . N 754412, кл, G 06 F 7/52, 1970. (54) УСТРОЙСТВО ДЛЯ УМНОЖЕНИЯ (57) Изобретение относится к вычислительной технике и может быть использовано и ри разработке быстродействующих устройств умножения чисел, удобных для изготовления с применением БИС и СБИС, Цель изоИзобретение относится к вычислительной технике и может быть использовано при разработке быстродействующих устройств умножения чисел, представленных в любой позиционной системе счисления, Цель изобретения — повышение быстродействия за счет сокращения длительности такта.

Поставленная цель достигается тем, что в устройство для умножения, содержащее и одноразрядных узлов умножения (n — разрядность множимого), и комбинационных сумматоров первой группы, n + 1 комбинационных сумматоров второй группы и и + 1 регистров промежуточного результата, причем вход множителя i-го одноразрядного узла умножения (i = 1, ..., n) соединен с входом множителя устройства, вход множимого — с -м разрядом входа множимого устройства, . Ы„1807481 Al бретения — повь шение быстродействия уст- ройства за счет сокращения длительности такта. Устройство содержит и одноразрядных узлов умножения (n — разрядность множимого), п комбинационных сумматоров первой группы, (и + 1) комбинационных сумматоров второй группы, (п + 1) регистров промежуточного результата и нововведенные и триггеров переноса и (n — 1) коммутаторов, введение которых позволило организовать вычислительный процесс так, что возникающие в каждом такте переносы не распространяются через всю цепь сумматоров, а запоминаются в соответствующих триггерах переноса, чем уменьшается длительность такта работы устройства. 2 ил. выход младшего разряда j-го одноразрядного узла умножения (j = 2, ..., n) соединен с входом первого слагаемого (j — 1)-го комбинационного сумматора первой группы, выход суммы I ãî комбинационного сумматора первой группы соединен с входом первого слагаемого (i + 1)-го комбинационного сумматора второй группы. выход суммы k-го комбинационного сумматора второй группы (k = 1, ..., n + 1) соединен с входом k ro регистра промежуточного результата, выход младшего разряда первого одноразрядного узла умножения соединен с входом первого слагаемого первого комбинационного сумматора второй группы, вход второго слагаемого которого соединен с выходом второго регистра промежуточного результата, вход переноса второго комбинационного сумматора второй группы соединен с выхо1807481 дом переноса первого комбинационного сумматора второй группы, выход первого регистра промежуточного результата подключен к первому выходу устройства, вход константы которого соединен с входом первого слагаемого и-го комбинационного сумматора первой группы, вход второго слагаемого которого соединен с выходом старшего разряда n-ro одноразрядного узла умножения, второй выход устройства соединен с выходами регистров промежуточного результата со второго по и-й. введены и триггеров переноса и и - 1 коммутаторов, .причем выход старшего разряда t-го одноразрядного узла умножения (t = 1, ..., n - 1) 15 соединен с входом второго слагаемого (1 +

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

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

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

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

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

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

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

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

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

Предлагаемое устройство для умножения содержит и одноразрядных узлов 1 умножения (n — разрядность множимого), и комбинационных сумматоров 2 первой группы, n + 1 комбинационных сумматоров

3 второй группы, n+ 1 регистров 4 промежуточного результата, и триггеров 5 переноса и n - 1 коммутаторов 6, входы 7, 8, 10 и 11 множителя. множимого, константы, коррекции и управляющий устройства соответственно. первый 12 и .второй 13 выходы устройства. Вход множителя i-го узла 1 (i =

1, ..., и) соединен с входом 7 устройства, вход множимого — с i-.ì разрядом-входа 8 устройства, выход 15 младшего разряда j-ro узла 1 (j = 2, „., n) соединен с входом первого слагаемого (j — 1)-ro сумматора 2, вход второго слагаемого которого соединен с выходом

22 (j + 2)-ro регистра 4, выход 14 старшего разряда t ro узла 1 (t = 1, ..., и - 1) соединен с входом второго слагаемого (t+ 1)-го сумматора 3,. выход 19 переноса которого соединен с входом t-го триггера 5 и первым информационным входбм t-lo коммутатора

6, второй информационный вход которого соединен с выходом 16 переноса t-го сумматора 2, выход 17 суммы i-го сумматора 2 соединен с входом первого слагаемого (i +

1)-ro сумматора 3, выход 20 суммы k-го сумматора 3 (k = 1, ..., n + 1) соединен с входом

k-ro регистра 4, выход 15 первого узла 1

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

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

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

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

Регистры 4 предназначены для хранения информации, форл ируемой на выходах 40

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

Триггеры 5. предназначены для хране- 45 ния переносов, возникающих при работе сумматоров 3, и могут быть реализованы на синхронных двухтактных 0-триггерах с входами установки в нулевое состояние, Коммутаторы 6 предназначены для пе- 50 редачи информации на выходы 21 (входы переноса сумматоров 3) со своих первого и второго информационных входов (выходов

19 и 16 переноса соответственно сумматоров 3 и 2) в зависимости от сигнала на их 55 управляющих входах (входе 11 устройства).

Они могут быть реализованы на элементах

2И23 — 2ИЛИ24, как показано на фиг. 2.

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

5.

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

В исходном состоянии регистры 4 и триггеры 5 обнулены, на входе 8 устройства присутствует без знака и-разрядный 2 -ичk ный код множимого (n k — разрядный двоичный код множимого). Предполагается, что множимое и множитель представлены в двоично-кодированной 2 -ичной системе

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

2k-ичный разряд множителя (параллельно k двоичных разрядов). При этом на выходах 14 и 15 i-го узла 1 формируются соответственно старший и младший разряды двухразрядного произведения соответствующего разряда множителя. поступающего на его вход множителя с входа 7 устройства, на i-й разряд множил ого, поступающий íà его вход множимого с I-го разряда входа 8 устройства. Младший разряд произведения )го угла 1 (j = 2, ..., n) поступает на вход первого слагаемого (j - 1)-го сумматора 2, а младший разряд произведения первого узла 1 — на вход первого слагаемого первого сумматора 3. Эти младшие разряды суммируются с соответствующими разрядами суммы частичных произведений, сформированными в предыдущем такте и хранимыми в ссответствующих регистрах 4.

В сумматорах 2, кроме того. подсуммируются соответствующие разряды переносов, сформированные в предыдущем такте на выходах 19 сумматоров 3 и хранимые в соответствующих триггерах 5. С выхода 17 t-го сумматора 2 (t = 1, ..., n — 1) разряд суммы поступает на вход первого слагаемого (t +

1)-го сумматора 3, где суммируется с поступающим на его вход второго слагаемого старшим разрядом произведения t-ro узла 1 и поступающим на его вход переноса разрядом перекоса соответствующего сумматора

2 (для второго сумматора 3 на вход переноса поступает информация с выхода 19 переноа первого сумматора 3), сформированного

1807481

20

35

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

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

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

После выполнения п первых идентичных тактов работы устройства на его вход 7 множителя поступает нулевая информация, 1 а на его вход 11 — сигнал, настраивающий коммутаторы 6 на передачу информации с их первых и вторых информационных входов (с выходов 19 сумматоров 3 и выходов

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

Вывод п+ 1 младших 2 -ичных разрядов

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

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

Произведем сравнение предлагаемого устройства и устройства-прототипа по быстродействию выполнения операции умножения 14-разрядных 2 -ичных

k сомножителей (56-разрядных двоичных сомножителей, т.е. n = 14, k = 4)

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

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

t p = 28 нс.

Пусть для реализации одноразрядных узлов 1 умножения используются ПЗУ типа

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

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

К555КП11, представляющих из себя четыре двухвходовых мультиплексора с задержкой

tK = 18 нс, Длительность такта работы известного устройства складывается из задержки на одноразрядном узле умножения (ty«), задержки на комбинационных сумматорах первой группы, включающей время на формирование сигнала переноса в первом сумматоре (т ), время на распространения переноса через и-2 сумматоров и время на формирование значения суммы в п-м сумматоре (tc2). задержки на комбинационных сумматорах второй группы, равной времени на формирование значения суммы s (и+ 1)-м сумматоре (tcz), поскольку остальные и комбинационных сумматоров второй группь; работают параллельно с и комбинационными сумматорами первой группы, а также задержки на запись суммы частичных произведений в регистры промежуточного результата (t»); т,е т = tyMH+ (tc1+ (и — 2) tct + tc2)+ tc2+ астр =

=70 + (17n + 7) + 24 + 22 = 17n + 123.(нс).

При n = 56/4 = 14 длительность такта работы известного устройства составляет

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

T " = t ë: n = 361 14 = 5054 (нс).

Для реализации известного устройства требуется 14 микросхем 556 РТ5 (одноразрядные узлы умножения). 29 микросхем

К555ИМ6 (комбинационные сумматоры первой и второй групп) и 15 микросхем

К555ТМ8 (регистры промежуточного результата), т.е. всего 58 микросхем.

1807481 формирования результатов комбинационных сумматоров первой группы и старшей цифры произведения одноразрядных узлов умножения. Следует особо отметить, что аппаратурные затраты на реализацию предлагаемого устройства возросли всего на 14, т.е. предложенное техническое решение явДлительность каждого из и первых тактов работы предлагаемого устройства скла.дывается из задержки на одноразрядном узле умножения (tyM<), задержки на комбинационном сумматоре первой группы от его входа до его выхода переноса (t«), задержки на коммутаторе (tK), задержки на формирование суммы в комбинационном сумматоре второй группы (tcQ), а также задержки на запись суммы частичных произведений в регистры промежуточного результата и триггеры переноса (tTp), т.е. ляется высокоэффективным.

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

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

tn Р = гумн + tc) + 1к + tc2 + 1» = 70 + 17+

+ 18 + 24 + 22 = 151 (нс).

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

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

Устройство для умножения, содержащее и одноразрядных узлов умножения (n— разрядность множимого), п комбинационных сумматоров первой группы, (п+ 1) комбинационных сумматоров второй группы и

20 (n+ 1) регистров промежуточного результа25

30 та, причем вход множителя i-го одноразрядного узла умножения (i = 1, „,. n) соединен с входом множителя устройства, вход множимого i-ro одноразрядного узла умножения соединен с входом I-го разряда множимого устройства, выход младшего разряда j-го

tn+1 = tc2 + (n 2)tc1 + (n - 2)tx + тс2 +

+tzp = 24 + 17n — 34 + 18n — 36 + 24 + 22 = 35n (нс), одноразрядного узла умножения (j = 2, .... и) соединен с входом первого слагаемого (j1)-го комбинационного сумматора. первой группы, выход суммы i-го комбинационного

Время выполнения операции умножения 56-разрядных сомножителей (n = 14) равно: . сумматора первой группы соединен с вхо35 дом первого слагаемого (i+ 1)-го комбинационнс го сумматора второй группы, выход суммы К-ro комбинационного сумматора зультата, выход младшего разряда первого

Для реализации предлагаемого устройства требуется 14 микросхем 556 РТ5 (одноразрядные узлы умножения), 29 микросхем

К555ИМ6 (комбинационные сумматоры первой и второй групп), 19 микросхем К555ТМ8 (регистры промежуточного результата и триггеры переноса) и 4 микросхемы

К555КП11 (коммутаторы). т.е. всего 66 микросхем.

Таким образом, быстродействие в предлагаемом устройстве будет в Т" /Т Р "" =

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

45 с выходом второго регистра промежуточного результата, вход переноса второго комбинационного сумматора второй группы соединен с выходом переноса первого комбинационного сумматора второй группы, выход первого регистра промежуточного результата подключен к первому выходу ус50 тройства, вход. константы которого соединен с входом первого слагаемого и-го комбинационного сумматора первой группы, вход второго слагаемого которого.сое55 динен с выходом старшего разряда и-го одноразрядного узла умножения, второй выход устройства соединен с выходами регистров промежуточного результата с втоТ"Р " = 1 "Р л" и+1+ "Р л" = 151: 14+ второй группы (К =. 1, .... и + 1) соединен с

+35 14 = 2601 (нс). 40 входом К-го регистра промежуточного ре1807481 .

12 фи . 2

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

Техред M.Ìîðãåíòàë Корректор Н.Гунько

Редактор

Заказ 1381 Тираж Подписное

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

113035, Москва, Ж-35, Раушская наб., 4/5

Производственно-издательский комбинат "Патент", г. Ужгород, ул.Гагарина. 101 рогопоп-й,отл" ч-- ющеe-я тем,что, с целью повыыения быстродействия устройства, в него введены и триггеров переносВ и и - 1 коммутаторов, причем выход старшего разряда t-го одноразрядного узла умножения (t = 1, „„n - 1) соединен с входом второго слагаемого (t + 1)-го комбинационного сумматора второй группы, выход переноса которого соединен с входом t-го триггера переноса и первым информационным входом t-ro коммутатора, второй информационный вход которого соединен с выходом переноса t-ro комбинационного сумматора первой группы, вход второго слаreeMolo которого соединен с выходом (t +

2)-го регистра промежуточного результата, вход переноса i-ro комбинационного сумматора первой группы соединен с выходом i-го

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