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

 

УСТРОЙСТВО ДЛЯ УМНОЖЕНИЯ, содержащее регистры множимого и множителя , матрицу элементов И, группу элементов ИЛИ, накапливающий суьматор и блок выделения младшего разряда , причем выхода разрядов регистра множимого соединены с первыми входами элементов И соответствукадих столбцов матрицы, выход j-ro эле . мента И i-й строки матрицы- (t 1,.,,, ,...,ri; n- разрядность сомножителей ), кроме первого элемента И первой строки матрицы и п-го элемента И п-й строки матрицы, подключен ко входу (t + j -2)-го элемента ИЛИ групгал, о тличающ е е с я тем, что, с целью повышения быстродействия, в устройство введены два буферных регистра и блок управления, содержащий счетчик, два элемента И и элемент ИЛИ, блок выделения младшего разряда содержит п ,зпементов И, а накашшвакщ й сумматор выполнен как сумматор с запоми- .нанием переносов, при этом входы k-ro элемента И блока выделения млад;шего разряда ( 1.,..., к-1) соединены с прямым выходом f1 +n-ro разряда регистра множителя и инверсными выходами всех предыдущих разрядов регистра множителя, входы п-го элемента И блока выделения младшего разряда соединены с инверсными выходами всех разрядов регистра множителя , прямой выход первого разряда которого подключен к информационному входу первого разряда первого буферного регистра, выход k-ro элемента И блока выделения младшего разряда подключен к информационному входу (k+l)-ro разряда первого буферного регистра, выход каяадого разряда которого соединен со вторыми входами элементов И соответствующей § строки матрицы, выход первого элемента И первой строки матрицы соединен с информационным входом первого разряда второго буферного регистра, выход р-го элемента ИЛИ группы (В,..., 2n-3j соединен с информационным входом (К+1)-го разряда второго буферного регистра, инфорСО мационный вход

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

В В

РЕСПУБЛИК

09) (И) 4 (5!) G06 F 7 52

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ

ОПИСАНИЕ ИЗОБРЕТЕНИЯ н латасном с еидетвъств и (2!) 3518860/24-24

{22) 06.12.82 (46) 30.01.85.Бюл.Ф 4 (72) Л.Г.Лопато и А.А.Шостак (71) Минский радиотехнический институт (53) 681.325.5 (088.8) (56) 1..Авторское свидетельство СССР

В 623204, кл. С Об F 7/52, 1977.

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

В 993255, кл. 6 06 F 7/52, 1981, (прототип). (54)(57) УСТРОЙСТВО ДЛЯ УМНОЖЕНИЯ, содержащее регистры множимого и множителя, матрицу элемеитов И, группу элементов ИЛИ, накапливающий сумматор и блок выделения младшего разряда, причем выходы разрядов регистра множимого соединены с первыми входами элементов И соответствующих столбцов матрицы, выход j-го эле- . мента И i-й строки матрицы. i 1,..., 1»..., ; и†разрядность сомножителей ), кроме первого элемента И первой строки матрицы и n -ro элемента И и-й строки матрицы, подключен ко входу (!+ j -2)-го элемента ИЛИ группы, о т л и ч а ю— щ е е с я тем, что, с целью повышения быстродействия, в устройство введены два буферных регистра и блок управления, содержащий счетчик, два элемента И и элемент ИЛИ, блок выделения младшего разряда содержит и ,зпементов И, а накапливающий сумматор выполнен как сумматор с запоми,нанием .переносов, при этом входы, Ь-го элемента И блока выделения млад.шего разряда (3<=- 1. .., h — 1! соединены с прямым выходом (М +1)-го разряда регистра множителя и инверсными выходами всех предыдущих разрядов регистра множителя, входы и -ro элемента И блока выделения младmего разряда соединены с инверсными выходами всех разрядов регистра множителя, прямой выход первого разряда которого подключен к информационному входу первого разряда первого буферного регистра, выход k-ro элемента И блока выделения младшего разряда подключен к информационному входу (1 +!)-го разряда первого буферного регистра, выход каждого разряда которого соединен со вторыми входами элементов И соответствующей строки матрицы, выход первого элемента И первой строки матрицы соединен с информационным входом первого разряда второго буферного регистра, выход Р-го элемента ИЛИ группы (0 =1,..., 2n-3! соединен с информационным входом ((+!! -го разряда второго буферного регистра, информационный вход(2n-!1- ro разряда которого подключен к выходу и-го элемента И и-й строки матрицы, выхо-, ды .разрядов второго буферного регистра подключены ко входам соответствующих разрядов накапливающего сумматора, выход и-го элемента И блока выделения младшего разряда подключен к первому входу первого элемен та И блока управления, второй вход которого соединен со входом синхронизации устройства и первым входом второго элемента И блока управления, второй вход которого соединен с выходом элемента ИЛИ блока управления, а выход — со входами синхронизации буферных регистров, накапливающего

1137463 сумматора. и регистра множителя, входы со входами элемента ИЛИ, прямой выобнуления разрядов которого соедине- ход второго разряда и выход переполны с информационными входами соот- нения второго разряда счетчика блока ветствущцих разрядов первого буфер- управления подключены соответственного регистра, выход первого элемен- но ко входу управления сквозным та И блока управления подключен ко переносом накапливающего сумматора входу счетчика блока управления, пря- и выходу индикации окОнчания мой выход первого и инверсный выход операции умножения устройствторого разрядов которого соединены ва.

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

Известно устройство для умножения, содержащее регистры множимого и множителя, накапливающий сумматор, матрицу элементов И, две группы элементов ИЛИ,. две группы элементов И и 10 группу элементов задержки 13.

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

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

KIH группу элементов И, накапливающий сумматор и блок выделения млад- 20 шего разряда, причем выходы регистра множимого соединены с первыми входами элементов И соответствующих столбцов матрицы, выход 1-го элемента И i-й строки матрицы 25 (- °

1=1, ° ° ° y,pj j 1,..., и; п — разрядность сомножителей ), кроме первого элемента И первой строки матрицы и n--ro элемента И,п-й строки матрицы подключены к входу (1+1-2 }-го: щ элемента ИЛИ группы, выходы элементов ИЛИ группы подключены соответственно к входам разрядов с 2-го по (2h — 2}-й накапливающего сумматора, входы -го и (2 h — I)-ro разрядов которого подключены соответственно к выходам первого элемента И первой строки матрицы и и-го элемента И и-й строки матрицы, входы блока выделения младшего разряда соеди- 40 иены с инверсными выходами соответствующих разрядов регистра множителя,. а выходы соединены с первыми входами соответствующих элементов И группы, вторые входы которых соединены с прямыми выходами соответствующих разрядов регистра множителя, а третьи входы объединены и соединены с входами синхронизации регистра множителя и накапливающего сумматора и с входом синхронизации устройL ства, выходы элементов И группы соединены с вторыми входами элементов И соответствующей строки матрицы и с входами обнуления соответствующих разрядов регистра множителя (21.

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

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

Поставленная цель достигается тем, что в устройство для умножения, содержащее регистры множимого и множителя, матрицу элементов И, группу элементов ИЛИ, накапливающий сумматор и блок выделения младшего разряда, причем выходы разрядов регистра множимого соединены с первыми входами элементов И соответствующих столбцов матрицы, выход j -ro элемента И 1-й строки матрицы (1= 1,..., fly j= 1...,; п — разрядность сомножителей), кроме перво

3 1137 го элемента И первой строки матрицы и и-го элемента И и-й строки матрицы, подключен к входу (1+1 -2)-го элемента ИЛИ группы, введены два буферных регистра и блок управления, содержащий счетчик, два элемента И и элемент ИЛИ, блок выделения младшего разряда содержит и элементов И, а накапливающий сумматор выполнен как сумматор с запоминанием переносов, при этом входы % -го элемента И блока выделения младшего разряда (1с = 1,..., и -1} соединены с прямым выходом (1 +1)-ro разряда регистра множителя и инверсными выходами всех предыдущих разрядов регистра множителя, входы п -го элемента И блока выделения младшего разряда соединены с инверсными выходами всех разрядов регистра множителя, прямой выход первого разряда которого подключен к информационному входу первого разряда первого буферного регистра, выход %-ro элемента И блока выделения младшего разряда подключен к информационному входу (Ъ+1) -го разряда первого буферного регистра, выход каждого разряда которого соединен с вторыми входами элементов И .соответствующей строки матрицы, выход первого элемента И первой строки матрицы . соединен с информационным входом первого разряда второго буферного регистра выход E --ro элемента ИЛИ

Э

35 группы (0= 1,..., 2h-3) соединен с

: информационным входом (3+1}-ro разряда второго буферного регистра, информационный вход (2n — 1) -го разряда которого подключен к выходу п -го 4 элемента Н и -й строка матрицы, выходы разрядов второго буферного регистра подключены к входам соответствующих разрядов накапливающего сумматора, выход и-го элемента И блока выделе45 ния младшего разряда подключен к первому входу первого элемента И блока управления, второй вход которого соединен со входом синхронизации устройства и первым входом второго элемента И блока управления, второй вход которого соединен с выходом элемента ИЛИ блока управления, а выход - со входом синхронизации буферных регистров, накапливающего Ы сумматора и регистра множителя, входы обнуления разрядов которого соединены с информационными входами соот463 4 ветствующих разрядов первого буферного регистра, выход первого элемента И блока управления подключен к входу счетчика блока управления, прямой выход первого и инверсный выход второго разрядов которого.соединены с входами элемента ИЛИ, прямой выход второго разряда и выход переполнения второго разряда счетчика блока управления подключены соответственно к входу управления сквозным переносом накапливающего сумматора и выходу индикации окончания операции умножения устройства.

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

Устройство содержит (фиг.l} ре,— гистры 1,2 соответственно множимого и множителя, первый буферный регистр 3, второй буферный регистр 4, накапливающий сумматор реализованный з виде комбинационного сумматора 5 и регистра 6 результата с соответствующими связями, матрицу 7 элементов И 8, группу 9 элементов

ИЛИ 10, блок 11 выделения младшего разряда, блок 12 управления, вход 13 синхронизации устройства и выход 14 индикации окончания операции умножения устройства. Выходы разрядов регистра 1 множимого соединены с первыми входами элементов И 8 соответствующих столбцов матрицы 7, а выходы разрядов первого буферного регистра 3 соединены с вторыми входами элементов И 8 соответствующих строк матрицы 7, выход } -ro элемента И 8 i-й строки матрицы 7 (1= 1,..., 4; j=- 1,..., 4), кроме первого элемента И 8 первой строки матрицы 7 и четвертого элемента И 8 четвертой строки матрицы 7, подключен к входу (1+j -2)-ro элемента ИЛИ 10 группы 9, выход первого элемента И 8 первой строки матрицы 7 соединен с информационным входом первого разряда второго бу|ферного регистра 4, выход t -го элемента ИЛИ 10 группы 9 (3 =l °,5) . соединен с информационным входом (1 + 1) -ro разряда второго буферно1137463!

Все регистры устройства могут быть построены на двухтактных синхронных 11 .-триггерах, причем в каж3S дом разряде регистра 6 результата накапливающего сумматора используется два таких триггера (один триггер предназначен для хранения раз40 рядных сумм сумматора 5, а другой— для запоминания его же разрядных переносов ). Сумматор 5 выполнен комбинационным типа с запоминанием разрядных переносов и с возможностью .45 их сквозной передачи на последнем щаге умножения путем подачи соответствующего сигнала на его управляю À вход.

Блок I l выделения младшего разря- 5О да предназначен для последовательного выделения единиц и --разрядного двоичного кода множителя, начиная с его младших разрядов, хранимого в регистре 2 множителя. Он содер жит (фиг.2) h элементов И 15 н функционирует в,соответствии со следующими логическими выражениями

555

ro регистра 4, информационный. вход седьмого разряда которого подключен к выходу четвертого элемента И 8 четвертой строки матрицы 7, выходы разрядов второго буферного регистра 4 подключены к входам соот-. ветствующих разрядов накапливающего сумматора, прямые и инверсные выходы разрядов регистра 2 множителя соединены с входами блока ll выде- 1б ления младшего разряда, выходы которого подключены к информационным входам соответствующих разрядов первого буферного регистра 3 и к входам обнуления соответствующих разрядов 15 регистра 2 множителя, выход окончания выделения блока 11 выделения мпадшего разряда соединен с первым. входом блока. 12 управления, второй вход которого соединен с входом 13 синхронизации устройства, первый выход блока 12 управления подключен к входам синхронизации буферных регистров 3 и 4, накапливающего сумматора и регистра 2 множителя, вто- г рой выход блока . 12 управления подключен к входу управления сквозным переносом накапливающего сумматора, а третий выход блока 12 управления подключен к выходу 14 ин" дикации окончания операции умножения устрбйства.

Il1=y; П2= ; l13=yy ; A4=yg y y

234 где П1, П, Пз, П4 признаки выделе" ния соответственно первого, второго третьего и четвертого значащих разрядов регистра 2 множителя; ϻ— признак окончания выделения значащих разрядов регистра 2 множителя; у у у у1 — двоичные цифры множите- ° ля, причем возрастание индексов при буквенных обозначениях принято

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

П » окончания выделения значащих разрядов в группах. Это позволяет даже при .n 56 и существующей элементной базе обеспечить время выделения значащего разряда, не превышающее величину 3 Т, где ь — з адерж ка сигнала на одном логическом элементе.

Блок 12 управления содержит (фиг.З)первый элемент И 16, второй элемент И l7, элемент ИЛИ 18 и двухразрядный двоичный счетчик 19(разрядность счетчика может быть и другой, причем первый вход . блока 12 управления соединен с первым входом первого элемента И 16, второй

/ вход которого соединен с вторым входом блока 12 управления и с первым входом второго элемента И 17, второй вход которого соединен с выходом элемента ИЛИ 18, а.выход является первым выходом блока 12 управления, выход первого элемента И 16 подключен к входу счетчика 19, прямой выход первого и инверсный выход второго разрядов которого соединены с входами элемента ИЛИ 18, прямой выход второго разряда и выход переполнения второго разряда счетчика 12 являются соответственно вторым и третьим выходами блока 12 управления.

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

7 !1374

Пусть требуется умножить и — разрядное множимое Х на п — разрядный множитель з = 1010. В исходном состоянии в регистре 1 множимого хранится двоичный код числа Х без знака, в регистре 2 множителя — двоичный код числа У без знака, буферные регистры 3,4, регистр 6 результата накапливающего сумматора и счетчик 19 блока 12 управления обнуле- !О ны °

В первом такте работы устройства на выходе блока !1 выделения младшего разряда формируется признак

П2-"1 выделения второго значащего раз- IS ряда регистра 2 множителя. Первый такт заканчивается с приходом на вход 13 синхронизации устройства первого синхроимпульса, по которому на выходе второго элемента И 17 20 блока 12 управления формируется управI ляющий сигнал, с разрешения которого по признаку П2=1 устанавливается в ноль второй разряд регистра 2 множителя и записывается единица во 25 второй разряд первого буферного регистра 3.

Во . втором такте работы устройства на выходе блока II выделения младшего разряда формируется приз30 нак П4=-1 выделения четвертого значащего разряда регистра 2 множителя, и одновременно с этим под дейст- . вием потенциала логической единицы, записанной во втором разряде первого буферного. регистра 3, осуществляется передача соответствующим образом сдвинутого множимого с выходов элементов И 8 второй строки матрицы 7 через элементы ИЛИ 10 группы 9 4О на информационные входы второго буферного регистра 4. Второй такт заканчивается с приходом на вход 13 синхронизации второго синхроимнульса по которому на выходе второго элемента И 17 блока 12 управления формируется управляющий сигнал, с разрешения которого осуществляется за-.: пись информации во второй буферный регистр 4 с его информационных входов, а также по признаку П4=1 устанавливается в нуль четвертый разряд регистра 2 множителя и записывается . единица в четвертый разряд первого буферного регистра 3 (второй разряд буферного регистра 3 обнуляется, так как его триггеры работают как 3 — триггеры7.

В третьем такте работы устройства на выходе окончания выделения блока I I выделения младшего разряда формируется признак П = 1, означающий, что закончено выделение значащих разрядов регистра 2 множителя, и одновременно с этим под действием потенциала логической единицы, записанной в четвертом разряде первого буферного регистра 3, осуществляется передача соответствующим образом сдвинутого множимого с выходов элементов И 8 четвертой строки матрицы 7 непосредственно и через элементы ИЛИ 10 группы 9 на информационные входы .второго буферного .регистра 4, и, кроме этого, в сумматоре 5 в режиме запоминания переносов выполняется суммирование содержимого второго буферного регистра 4 и регистра 6 результата (содержимое регистра 6 результата в этом такте еще равно нулю ), после чего резуль-. тат сумматора 5 в двухрядном коде поступает на информационные входы регистра 6 результата. Третий такт заканчивается с приходом на вход 13 синхронизации третьего синхроимпульса, по которому на выходе первого элемента И 16 блока 12 управления формируется сигнал, уста-. навливающий счетчик !9 блока 12 управления в единицу, а на выходе второго элемента И !7 блока 12 управления формируется управляющий сигнал, с разрешения которого производится запись информации во второй буферный регистр 4 и в регистр 6 результата с их информационАХ ВХОДОВ.

В четвертом такте работы устройства в сумматоре 5 производится суммирование в режиме запоминания переносов содержимого второго буферного регистра 4 и регистра 6 результата, после чего получившийся на его выходах результат в двухрядном коде поступает на информационные входы регистра 6 результата,. Такт заканчивается с приходом на вход 13 синхронизации четвертого синхроимпульса, по которому на выходе второго элемента И 17 блока 12 управления образуется управляющий сигнал, с разрешения которого осуществляется запись информации в регистр 6 результата с его информационных входов, а на выходе первого элемента

9 11374

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

В пятом такте работы устройства 10 в сумматоре 5 выполняется суммирование содержимого регистра 6 результата в режиме со сквозным переносом. Пятый такт заканчивается с при.ходом на вход 13 синхронизации пятого синхроимпульса, по которому только на выходе первого элемента

И 16 блока 12 управления формируется сигнал, устанавливающий счетчик 19 через его вход счета в сос- 20 тояние, равное трем.

В этом такте на выходе второго элемента И 17 блока 12 управления управляющий . сигнал не образуется и потому запись информации во все регистры устройства не производится. .В шестом такте продолжается процесс суммирования со сквозным переносом содержимого регистра 6 резуль- 30 тата, который бып начат еще в начале пятого такта. Здесь предполагается, что к концу шестого такта на выходах сумматора 5 формируется окончательный результат в однорядном коде, который поступает соответствующим образом на информационные входы регистра 6 результата.

Шестой такт заканчивается с приходом на вход 13 синхронизации шесто- 40 го синхроимпульса, по которому на выходе второго элемента И 17 блока 12 управления формируется управляющий сигнал, с разрешения которого производится запись окончатель- 45 ного результата в регистр 6 результата с его информационных входов, а на выходе первого элемента И 16 блока 12 управления образуется сигнал, который, поступая через вход 50 счета счетчика 19 сбрасывает его в нуль и вызывает на выходе переполнения счетчика 19 единичный сигнал, означающий, что закончено умножение в устройстве рассматриваемых чисел.

t0

63

На фиг. 4 приведена упрощенная временная диаграмма работы устройства при перемножении в нем рассмотренных выше чисел. На ней через СИ обозначены синхроимпульсы, поступающие на вход 13 синхронизации устройства; сигналы УС1, УС2 и УСЗ соответствуют управляющим сигналам соответственно на первом, втором и третьем выходах блока 12 управления; П вЂ” признак окончания выделеМ ния, формируемый в блоке 11 выделения младшего разряда; через С 16 обозначен сигнал, который образуется на выходе первого элемента И 16 блока 12 управления в процессе работы устройства.

Среднее время умножения двух

h- разрядных чисел в предлагаемом устройстве, в предположении что ,появление нуля и единицы во всех разрядах множителя равновероятно, составляет величину

Т Ф +41 где t — длительность одного такта работы предлагаемого устройства. Составляющая 4-й в приведенном выражении вызвана использованием в устройстве конвейерного принципа обработки информации, а также потерей времени на сквозную передачу переносов в сумматоре в конце выполнения операции умножения (суммирование со сквозным переносом в сумматоре может быть выполнено в течение двух тактов работы устройства).

Хотя в предлагаемом устройстве для умножения двух и-разрядных двоичных чисел и требуется выполнить на четыре такта больше, чем в устройстве-прототипе, однако оно имеет значительно более высокое быстродействие, так как .длительность его такта работы сведена к минимуму (длительность такта работы предлагаемого устройства определяется временем записи информации в регистры 2,3,4,6 и временем задержки информации либо на блоке 11 выде ления младшего разряда, либо на матрице 7 элементов И 8 и на элементах ИЛИ 10 группы 9, либо на сумматоре 5 работающе..l в режиме запоминания переносов,).

1 l 37463

1137463

1137463

Г \

Составитель АЛ1астак

Техред Т.Дубиичак

Корректор О. Билак

Редактор А.Долииич

Подписное фкпиал ППП "Патент", г.ужгород, ул.Проектная, 4

Заказ 10525/36 Тираж 710.ВНИИПИ Государственного комитета СССР по делам изобретений и открытий

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