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

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

Иллюстрации

Показать все

Реферат

 

Союз Советских

Социалистических

Республик

ОПИСАНИЕ

ИЗОБРЕТЕНИЯ (u>833417

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (63) Дополнительное к авт. свид-ву— (22) Заявлено 100878 (21) 2653825/18-24 (53)м. коз с присоединением заявки Hо—

G 06 F 7/52

Государствеииый комитет

СССР яо делам язобретеиий и открытий (23) Приоритет

Опубликовано 1503.81. Бюллетень М 10

Дата опубликования описания 150381 (53) УДК 681. 325 (088.8) (72) Автор изобретен и я

В.М.Лукашенко

f

f (71) Заявитель (54) УСТРОЙСТВО ДЛЯ УМНОЖЕНИЯ и-РАЗРЯДНЫХ

ЧИСЕЛ

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

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

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

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

Единичный выход каждого i-ro разряда регистра множителя (=1,...,n) соеди" нен через первый поразрядный элемент

И J -ro разряда со входами вентилей

j --ro столбца матрицы и. с нулевым входом того же разряда регистра-множителя, нулевой выход J --го разряда регистра множителя связан через второй поразрядный элемент И )-ro разряда со входами обоих поразрядных элементов

И (3+1)-го разряда, выходы первых поразрядных элементов И всех разоядов— с шиной тактовых импульсов (2) .

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

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

35

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

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

32-разрядных чисел осуществляется за

64 такта.

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

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

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

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

И 1-ой диагонали матрицы соединены со входами 1-го элемента ИЛИ через элементы задержки, выходы элементов

ИЛИ являются выходами блока перемножения к-разрядных чисел.

На фиг.1 показана функциональная схема устройства для умножения и-разрядных чисел; на фиг.2 — принципиальная схема формирования единичного импульса а(с) и задержанного на а(e +М); на фиг.3 - матрица произведений двух 8-разрядных чисел.

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

13, элементы И 14, ИЛИ 15, задержки

16, причем входы:первого буферного регистра 10 и второго буферного регистра 11 подключены. соответственно ко входам множнмого и множителя блока

7 перемножения к-разрядных чисел соответственно, выход i-го разряда второго буферного регистра 11.(i-=1,,к) подключен к первым входам элементов

И i-ой строки матрицы 12, прямой вы"ход i-ro разряда первого буферного регистра 10 соединен с первым входом

i-ro элемента И 14, второй вход которого подключен к тактовому входу 17. 813417

П устройства, а выход — ко вторым входам элементов И i-го столбца матрицы:

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

ИЛИ 15 через элемент задержки 16, выходы элементов ИЛИ 15 являются выходами блока 7 перемножения к-разряд.ных чисел.

В двоичной позиционной системе счисления число представляется в виКа -< де многочлена N g g.»", где a .— чисКО ло разрядов; а „,,..., а о — значения соответствующих разрядов числа и равных 1 или О. Следовательно, произведение двух сумм MQMHo представить как перемножение — частей сомножитеК лей по к разрядов в каждой. Тогда алгоритм сводится к последовательному суммированию слагаемых произведений малоразрядных частей .сомножите- лей.

На фиг.3 представлены слагаемые 35 произведений двоичных чисел К, и И, заданных 8-разрядными кодами и разбитых на две части по четыре разряда в каждой, т.е. числа И,. = а„ аь аза4 а . а2а ао представлены первой и второй 4() частями соответственно 1" а а„а а4) и (a>a>a„ap) à Ny bybp Ьз Ь4ЬЗЬ» Ь, bg аналогично (by Ьь Ь6Ь4) и (Ь Ь» Ь, bp)

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

Рассмотрим работу устройства для сомножителей N4=10110011,Ng10110110„ з- = 1, аь= О, аб 1, а4= 1, а = О, а» = О, а = 1, Ь = 1, Ь = О, 66= 1, b4 1, Ь3= О, Ь»= 1, Ь„= 1, bo=-0.

Ь b ba b4 = 1911 часъ и мноЬ,Ь, Ь, Ь,— 01100) После обнуления регистров 1 и 2 сомножителей, буферных регистров 10 60 и 11 и накапливающего сумматора 9 записываются числа й, и и » в регистры 1 и 2 соответственно. По приходу управляющих сигналов, и 1 по пер-. вому 5 и второму 6 управляющим входам 6$ в коммутаторах 3 и 4 групп Формируются микрокоманды по структурным формулам ба » ЬЬ т 4 » » ф 1

Fgо, fg f» y f„fg „ у V <, fg. под действием которых в буферные ре-, гистры 10 и 11 соответственно записываются ХаХ или Ха11 или Па1 или 1?аП части кодов сомножителей. Единицы Ь поступают на первые входы элементов

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

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

i--го столбца матрицы 12, находящихся в нечетных ее строках, на выходах элементов H j-ой диагонали матрицы 12 (j = 1,...,2к-1) появится импульс, который для первых двух элементов И каждой 1-ой диагонали матрицы 12 (1 = 2,...,2к-2) пройдет на входы

1-ro элемента ИЛИ 15 непосредственно, а импульсы на выходах остальных элементов И I îé диагонали матрицы 12 пройдут на входы 1-го элемента ИЛИ 1 через элементы задержки 16. Выходные импульсы элементов ИЛИ 15 поступают на информационные входы коммутатора

8 частичных произведений, в котором по управляющим сигналам f и f» соответственно структурным формулам

Y,=f„ ; 1,=Г „Ч t, f<, формируются микрокоманды, которйе пропускают импульсы результата частичных перемножений в соответствующие разряды накапливающего сумматора 9 °

После выполнения всех микрокоманд в накапливающем сумматоре 9 устанавливается результат перемножения всех частей сомножителей. Использование нового элемента коммутатора 8 частичных произведений с организацией связей его с блоком 7 перемножения к-разрядных чисел и накапливающим сумматором 9, построение блока перемножения к-разрядных чисел из буферных регистров 10 и 11, матрицы 12 элементов И, дифференцирующих узлов 13, элементов И 14, ИЛИ 15 и задержки -16 позволяют увеличить быстродействие. Например, для перемножения двух 32.-разрядных чисел при к=16 за четыре микрокоманды. при к=8 за шесть микрокоманд, что по сравнению с известным устройством увеличивает

К ,быстродействие в — раз. п

Формула изобретения

Устройство для умножения п-разрядных чисел„ содержащее п-разрядные ре813417 гистры множимого и множителя, коммутаторы групп разрядов множимого и множителя, блок перемножения к-разрядных чисел (к — разрядность групп (множимого и множителя} и накапливающий сумматор, причем выходы регистров множимого и множителя, огрупщ рованные по к разрядов, подключены к информационным вхсщам коммутаторов групп разрядов множимого и.множителя соответственно, управляющие входы которых подключены соответственно к первому и второму управляющим входам устройства, а выходы подключены соответственно ко входам множимого и множителя блока перемножения к-разрядных чисел, о т л и ч а ю щ е ес я тем, что, с целью повышения быстродействия, устройства содержит коммутатор частичных произведений, информационные. входы которого пддключены к выходам блока перемножения к-разрядных чисел, управляющие входы — к первому и второму управляю-. щим входам устройства, а выходыко входам накапливающего сумматора, блок пЕремножения к-разрядных чисел содержит буферные регистры, матрицу элементов И, дифференцирующие узлы, элементы И, ИЛИ и задержки, причем входы первого и второго буферных .регистров подключены соответственно ко входам множимого и множителя блока перемножения к-разрядных чисел соответственно, выход i-го разряда второго буферного регистра (i=1. ..к) подключен к первым входам элементов

И i-ой строки матрицы, прямой выход

i-ro разряда первого буферного регистра соединен с первым входом

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

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

Я остальных элементов И 1-ой диагонали .матрицы соединены со входами i-го

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

1. Самофалов Е.Г. и др. ЭлектронныЬ ттиАоовые вычислительные машины.

З К., "вища школа", 1976, с.476.

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

М 482740, кл.G 06 F 7/52, 1974.

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