Устройство для умножения п-разряд-НыХ чиСЕл Советский патент 1981 года по МПК G06F7/52 

1

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

Известно устройство, содержащее регистры множимого и множителя, сумматор Щ .

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

Известно также устройство, содержащее матрицу вентилей, регистры. . множимого и множителя на -триггерах, (2п-1)-разрядный накапливающий сумматор, элементы ИЛИ, поразрядные элементы И и шину тактовых импульсов. Единичный выход каждого i-ro разряда регистра множителя (,...,n) соединен через первый поразрядный элемент

и разряда со входс1ми вентилей j-го столбца матрицы и с нулевым входом того же разряда регистра-множителя, нулевой выход J-го разряда регистра множителя связан через второй поразрядный элемент И J-ro разряда со входами обоих пора;эрядных элементов И (j+l)-ro разряда, выхода первых поразрядных элементов И всех разрядов с шиной тактовых импульсов

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

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

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

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

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

второй вход которого подключен к тактовому входу устройства, а выход ко вторым входам элементов И I-го столбца матрицы, наосодящихся в четных строках, и ко входу сброса -го разряда первого буферного регистра, инверсный выход которого через i-ый узел дифференцирования подключен ко вторым входам элементов И i-ro столбца матрицы, находящихся в нечетных ее строках, выходы элементов И j-ой диагонали матрицы (j l,..i, 2к-1) соединены со входами j-ro элемента ИЛИ, причем выходы первых двух элементов И каждой 1-ой диагонали матрицы (1 2,...,2к-2) подключены ко входам 1-го элемента ИЛИ непосредственно, а выходы остальных элементов И 1-ой диагонали матрицы соединены со входами 1-го элемента ИЛИ через элементы задержки, выходы элементов ИЛИ являются выходами блока перемножения к-разрядных чисел.

На фиг.1 показана функциональная схема устройства для умножения п-разрядных чисел; на фиг.2 - принципиальная схема формирования единичного импульса a(t) и задержанного на а (t -fit); на фиг.З - матрица произведений двух 8-разрядных чисел.

Устройство для умножения п-разрядных чисел содержит п-разрядные регистры сомножителей 1 и 2, выходы которых, сгруппированные по к разрядов (к - разрядность групп множимого и Множителя) подключены к информационным входам коммутаторов 3 и 4 групп разрядов множимого и множителя,управляющие входы коммутаторов 3 и 4 подключены соответственно к первому 5 и второму б управляющим входам устройства, а быходы подключены соответственно ко входам множимого и множителя блока 7 перемножения к-разрядных чисел, выходы которого подключены к информационным входам коммутатора 8 частичных произведений, управляющие входы которого подключены соотве5гстве.нно к первому 5 и второму 6 управляющим входам устройства, а выходы подключены к входс1М накапливающего сумматора 9. Блок 7 перемножения к-разрядных чисел содержит буферные регистры 10 и 11, матрицу 12 элементов И, дифференцирующие узлы 13, элементы И 14, ИЛИ 15, задержки 16, причем входы первого буферного регистра 10 и второго буферного регистра 11 подключены соответственно ко входам множимого и множителя блока 7 перемножения к-разрядных чисел соответственно, выход i-ro разряда второго буферного регистра 11 (,..,к) подключен к первым входсш элементов И i-Ьй строки матрицы 12, прямой выход i-ro разряда первого буферного регистра 10 соединен с первым входом I-го Элемента И 14, второй вход которого подключен к тактовому входу 17

устройства, а выход - ко вторым входам элементов И i-ro столбца мйтрицы 12, находящихся в чет-ыых строках, и ко входу сброса i-ro разряда первого буферного регистра 10, инверсный которого через i -ый узел 13 дифференцирования подключен ко вторым входам элементов И i-го столбца матрицы 12, находящихся в нечетных ее строках, выход элементов И j-ой диагонали матрицы 12 (j 1,..,,2к-1) соединены со входами j-го элемента ИЛИ 15, причем выходы первых двух элементов И каждой 1-ой диагонали матрицы 12 (, 2к-2) подключены ко входам 1-го элемента ИЛИ 15 непосредственно, а выходы остальных элементов И 1-ой диагонгши. матрицы 12 соединены со входами 1-го элемента ИЛИ 15 через элемент задержки 16, выходы элементов ИЛИ 15 являются выходами блока 7 перемножения к-разряд.ных чисел,

В двоичной позиционной системе счисления число представляется в виде многочлена N 2 где h - число разрядов; а . ,Г°.,ао - значения соответствующих разрядов числа и равных 1 или 0. Следовательно, произведение двух сумм можно представить

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

На ФИГ..З представлены слагаемые произведений двоичных чисел N и Ngv заданных 8-разрядньй щ кодами и разбитых на две части по четыре разряда в каждой, т.е. числа N. а а., а g .представлены первой и второй частями соответственно Эр , а Nj- Ь Ь bg 64 b jbj.b Ьр аналогично b7b b5b4;JH , Ьо. Произведение N, N может быть осуществлено последовательно за четыре микрокоманды для результата с двойной

ТОЧНОСТЬЮРассмотрим работу устройства для, сомножителей N 10110011,N5 10110ilO, 87 1, а О, а5 1, а 1, а О, a,j О, а 1, Ь7 1, Ь О, Ьд 1, Ьд 1, bj О , bj 1, b, 1, bg - О.

: liiiiiif. l°ll} MS5Po« : : rПосле обнуления регистров 1 и 2 сомножителей, буферных-регистров 10 и 11 и накапливающего сумматора 9 .. записываются числа N и N 5 в регистры 1 и 2 соответственно. По приходу управляющих сигналов f и fj по первому 5 и второму б управляющим входам

в коммутаторах 3 и 4 групп формируются микрокоманды по структурным формулам

. fla f. fa V fj f,, ;

т a V f f, ;

5 ia I a V f fi :

FT a V 1

под действием которых в буферные ре-, гистры 10 и 11 соответственно записываются lal или laii .или Па1 или На 11

iO части кодов сомножителей, Единицы bj поступсцот на первые входы элементов И i-ой строки матрицы 12. Единицы а по приходу тактового импульса 17 пройдут через элементы 14 и поступят на

If вторые Bxd; И i-ro сто.пбца матрицы 12, находящихся в четных строках и на вход сброса i-го разряда буферного регистра 10, при этом при переключении триггера на его инверсном выходе появляется импульс, который про20 идя i-ый узел 13 дифференцирования поступит на вторые входы э.лементов И i-ro столбца матрицы 12, находящихся в нечетных ее строках, на выходах элементов. И j-ой диагонали матрицы 12

5 (J 1,,,,,2к-1) появится импульс, который для первых двух элементов И каждой 1-ой диагонали матрицы 12 (1 2,,,,,2к-2) Пройдет на входы

. 1-го элемента ИЛИ. 15 непосредственно,

Q а импульсы на выходах остальных элементов И 1-ой диагонали матрицы 12 пройдут на входы 1-го элемента ИЛИ 15 через элементы Зсщержки 16, Выходные импульсы элементов ИЛИ 15 поступают

r на.информационные входы коммутатора 8 частичных произведений, в котором по управляющим сигналам f, и fj соответственно структурным формулам Y fi ; , Vf, fa; Y f, fj. формируются микрокоманды, которые

0 пропускают импульсы результата частичных перемножений в соответствующие разряды накапливающего сумматора 9, После выполнения всех микрокоманд в накапливающем сумматоре 9 устанавливается результат перемножения всех частей сомножителей.

Использование нового элемента коммутатора 8 частичных произв-еДений с организацией связей его с блоком 7

0 перемножения к-разрядных чисел и накапливающим сумматором 9, построение блока перемножения к-разрядных чисел из буферных регистров 10 и 11, матрицы 12 элементов И, дифференцирующих

г узлов 1.3, элементов И 14, ИЛИ 15 и

задержки -16 позволйют увеличить быстродействие. Например, для перемножения дву-х 32-разрядных чисел при за четыре микрокоманды при за шесть микрокоманд, что по сравнению 0 с известным устройством увеличивает

Кбыстродействие и -- раз.

Формула изобретения Устройство для умножения п-разряд5 :ных чисел, содержоШ1ее п-разрядные регистры множимого и множителя, комму таторы групп разрядов множимого и множителя, блок перемножения к-разрядньис чисел (к - разрядность групп (множимого и множителя) и накапливающий сумматор, причем выходы регистро множимого и множителя, сгруппированные по к разрядов, подключены к информационным входам коммутаторов групп разрядов множимого и.множителя соответственно, управляющие входа которых подключе ны соответственно к первому и второму управляющим входам устройства, а выходы подключены соответственно ко входёш множимого и множителя блока перемножения К-разрядных чисел, отличающее с я тем, что, с целью повышения быстродействия, устройство содержит коммутатор частичных произведений, информационные, входы которого пбдключены к выходам блока Перемножения к-разрядных чисел, управляющие входы - кпервому и второму управляющим вхбдс1М устройства, а выходы ко входсил накапливающего сумматора, блок перемножения к-разрядных чисел содержит буферные регистры, матрицу элементов И, дифференцирующие узлы, элементы И, ИЛИ и Зсшержки, причем входы первого и второго буферных регистров подклх 1чены соответственно ко входам множимого и множителя блока перемножения к-разрядныхчисел соответственно, вьжод 1-го разряда второго буферного регистра (,,.,к подключен к первым входам элементов

И i-ой строки матрицы, прямой выход i-го разряда первого буферного регистра соединен с первым входом i-ro элемента И, второй вход которого подключен к тактовому входу устройства, а выход - ко вторым входги элементов И -го столбца матрицы,находящихся в четных строках, и ко входу сброса i-ro разряда первого буферного регистра, инверсный выход которого через i-ый узел дифференцирования подключен ко вторым входам элементов И 1-го столбца матрицы, находящихся в нечетных ее строках, выходы элементов И j-ой диагонали матрицы (J 1,,..,2к-1) соединены со

5 входами JTO элемента ИЛИ, причем выходы первых .двух элементов И каждой 1-ой диагонали матрицы (,..., 2к-2) подключены ко входам J-ro элемента ИЛИ непосредственно, а выходы

0 остальных элементов и 1-ой диагонали матрицы соединены со входами 1-го элемента ИЛИ через элементы задержки выходы элементов ИЛИ являются выходами блока перемножения к-разрядных чиc сел.

Источники информации, принятые во внимание при экспертизе

1.Самофалов К.Г. и др. Электрон HbSfe тжЛоовые вычислительные машины.

К,, Вища школа, 1976, с.476.

2.Авторское свидетельство СССР 482740, кл.С 06 F 7/52, 1974.

3.патент США 3670956, кл.235/164, опублик.1972 (прототип).

Сброс

17

IS

Oifi)

ai()

Clgoc

/V, 0,05050 03020,00 N uyugb b bjb b, bo