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

Союз Сфветскик Социалистических РеспубликОПИСАНИЕ ИЗОБРЕТЕНИЯ оо 813417 К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ(5 ЦМ. Клз с присоединением заявки Нов О 06 Г 7/52 Государственный комитет СССР яо делам язобретеиий н открытий(54) УСТРОЙСТВО ДЛЯ УМНОЖЕНИЯ и-РАЗРЯДНЫХ ЧИСЕЛИзобретение относится к вычислительной технике и может быть использовано в информационно-измерительных системах, в специализированных вычислительных устройствах и комплексах в быстродействующих многопроцессорных вычислительных системах высокой производительности и др.Известно устройство, содержащее регистры множимого и множителя, сумматор 1(.Однако процесс умножения двух и-разрядных сомножителей этого устройства представляется как процесс суммирования слагаемых, которые в 15 простейших случаях образуются путем сдвига множимого на 1,2,празряда, Максимальное количество слагаемых равно и . Процессом суммирования управляют цифры множителя. Поэто му для многоразрядных чисел быстродействие такого устройства мало.Использование методов ускоренного умножения требует значительных дополнительных затрат оборудования, . 25Известно также устройство, содержащее матрицу вентилей, регистры.множимого и множителя на триггерах, (2 о)-разрядный накапливающий сумматор, элементы ИЛИ, поразрядные зле менты И и шину тактовых импульсов. Единичный выход каждого 1-го разряда регистра множителя (=1в) соеди" нен через первый поразрядный элемент И-го разряда со входами вентилей д -го столбца матрицы и. с нулевым входом того же разряда регистра-множителя, нулевой выход )-го разряда регистра множителя связан через второй поразрядный элемент И )-го разряда со входами обоих поразрядных элементов И (3+1)-го разряда, выходы первых поразрядных элементов И всех разоядов - с шиной тактовых импульсов (2 .Однако если о-разрядный множитель двоичного числа содержит количество единиц, близкое к и , то быстродействие падает, аппаратурные затраты растут, надежность устройства снижает.ся.Наиболее близким по технической сущности к предлагаемому является устройство для умножения и-разрядных чисел, содержащее о-разрядные регистры множимого и множителя, коммутаторы групп разрядов множимого и мно" жителя, блок перемножения к-разрядных чисел (к - разрядность групп множимого и множителя) и накапливающий сумматор, причем выходы регист 81341735 40 ров множимого и множителя, сгруппированные по к разрядов, подключены к ииформационньщ входам коммутаторов групп разрядов множимого и множителя соответственно, управляющие входы которых подключены соответственно к первому и второму управляющим входам устройства, а выходы подключены соответственно ко входам множимого и множителя блока перемножения к-разрядных чисел, выходы последнего под-, ключены к соответствующим входам на" капливающего сумматора, представляющего собой совокупность комбинационного сумматора и регистра, причем управляющие входы регистра соединены с соответствующими тактовыми выхода ми 1.31.Недостатком этого устройства. является малое быстродействие. Запись результата перемножения в каждый раздел выходного регистра осуществляется по)следовательно под действием тактовыхимпульсов. Например, перемножение 32-разрядных чисел осуществляется за 64 такта.Цель изобретения - повышение быстродействия. Поставленная цель достигается тем,что в устройство для умножения я-разрядных чисел, содержащее и-разрядные регистры множимого и множителя, коммутаторы групп разрядов множимого имножителя, блок перемноженияк-разрядных чисел (к- разрядность группмиожимого и множителя) и накапливающий сумматор, причем выходы регистров множимого и множителя, сгруппированные по к. разрядов, подключены к информационным входам коммутаторов групп разрядов множимого и множителясоответственно, управляющие входыкоторых подключены соответственно кпервому и второму управляющим входам устройства, а выходы подключены соответственно ко входам множимого и множителя блока перемножения к-разрядных чисел, введен коммутатор частичных произведений, информационные входы которого подключены к выходам блока перемножения кразрядных .чисел,управляющие входы - к первому и второму управляющим входам устройства,а выходы - ко входам накапливающегосумматора, блок перемножения к-разрядных чисел содержит буферные регистры, матрицу элементов И, дифференцирующие узлы, элементы Й, ИЛИ изадержки, причем входы первого и второго буФерных регистров подключенысоответственно ко входам множимого и множителя блока перемножения к-разрядных чисел соответственно, выход 1-го разряда второго буферного регистра (1= 1к) подключен к первым входам элементов И 1-ой строки матрицы, прямой выход 1-го разряда первого буферного регистра соединен с первым входом 1-го элемента И,второй вход которого подключен к тактовому входу устройства, а выход - ко вторым входам элементов И 1-го столбца матрицы, находящихся в четных строках, и ко входу сброса 1-го разряда первого буферного регистра, инверсный выход которого через 1-ый узел дифференцирования подключен ко вторым входам элементов И 1-.го столбца матрицы, находящихся в нечетных ее строках, выходы элементов И 1-ой диагонали матрицы (3= 1.2 к) соединены со входами 1-го элемента ИЛИ, причем выходы первых двух элементов И каждой 1-ой диагонали матрицы (1= 22 к"2) подключены ко входам 1-го элемента ИЛИ непосредственно, а выходы остальных элементов И 1-ой диагонали матрицы соединены со входами 1-го элемента ИЛИ через элементы задержки, выходы элементов ИЛИ являются выходами блока перемножения к-разрядных чисел.На фиг.1 показана функциональная схема устройства для умножения и-разрядных чисел; на Фиг.2 - принципиальная схема формирования единичного импульса а(й) и задержанного на а(с +М); на Фиг.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 перемножения к-разрядных чисел соответственно, выход 1-го разряда второго буферного регистра 11 (1=1, ,к) подключен к первым входам элементов И 1-ой строки матрицы 12, прямой выход 1-го разряда первого буферного регистра 10 соединен с первым входом1-го элемента И 14, второй вход которого подключен к тактовому входу 17устройства, а выход - ко вторым входам элементов И 1-го столбца матрицы: 12, находящихся в четных строках, и ко входу сброса 1-го разряда первого буферного регистра 10, инверсный выход которого через 1-ый узел 13 дифференцирования подключен ко вторым входам элементов И 1-го столбца матрицы 12, находящихся в нечетных ее строках, выход элементов И )-ой диагонали матрицы 12 = 12 к) соединены со входами ).-го элемента О ИЛИ 15, причем выходы первых двух элементов И каждой 1-ой диагонали матрицы 12 (1=2, 2 к) подключены ко входам 1-го элемента ИЛИ 5 непосредственно, а выходы остальных эле ментов И 1-ой диагонали. матрицы 12 соединены со входами 1-го элемента ИЛИ 15 через элементзадержки 16, выходы элементов ИЛИ 15 являются выходами блока 7 перемножения к-разряд- зо .ных чисел.В двоичной позиционной системе счисления число представляется в виМв 3 з-де многочлена МХ"оЖ где и - чиск:о фло разрядов; а , а- значения соответствующих разрядов числа и равных 1 или О. Следовательно, произведение двух сумм можно представить как перемножение - частей сомножитеоКлей по к разрядов в каждой. Тогда ЗО алгоритм сводится к последовательному суммированию слагаемых произведений малоразрядных частей .сомножите-лей.На фиг.3 представлены слагаемые 35 произведений двоичных чисел М, и М ,. , заданных 8-разрядныМи кодами и разбитых на две части по четыре разряда в каждой, т.е, числа М, = а.,а,а а а а а ар,представлены первой и второй 40 частЯми соответственно 1 а аазаД иаааао, а М Ь.Ь Ьз ЬЬзЬ Ь, Ьоаналогично Ь Ьь Ь 6 ЬД и Ь Ьд Ь, Ь. Произведение М, Мможет быть осуществлено последовательно за четыре микрокоманды для результата с двойной точностью.Рассмотрим работу устройства для сомножителей М,=10110011,М 10110110, а =1, аь=О, а 6=1, а =1, а=О, а = О, а= 1, Ь= 1, Ь= О, Ь 6= 1, Ь 4 щ 1, Ь 3= О, Ьд= 1, Ь= 1, ЬО=.О. 1 П 551011Ь,Ь, Ь, Ь, - 01100) После обнуления регистров 1 и 2 сомножителей, буферных регистров 10 60 и 11 и накапливающего сумматора 9 записываются числа М, и Мв регистры 1 и 2 соответственно, По приходу управляющих сигналов Г, и 1 по пер-. вому 5 и второму 6 управляющим входам 6 в коммутаторах 3 и 4 групп Формируются микрокоманды по структурным Формулам5 а фФ % ябГт - Ю,ЧУ,У,Паф%УдЬ1 уФ Упод действием которых в буферные ре-,гистры 10 и 11 соответственно записываются 1 а 1 или ХаЫ или Па 1 или 11 аПчасти кодов сомножителей. Единицы Ьпоступают на первые входы элементовИ 1-ой строки матрицы 12. Единицы апо приходу тактового импульса 17 пройдут через элементы 14 и поступят навторые входы И 1-го столбца матрицы12, находящихся в четных строках ина вход сброса 1-го разряда буферного регистра 10, при этом при переключении триггера на его инверсном выходе появляется импульс, который пройдя 1-ый узел 13 дифференцированияпоступит на вторые входы элементов И1-го столбца матрицы 12, находящихсяв нечетных ее строках, на выходахэлементов И )-ой диагонали матрицы 12= 12 к) появится импульс,который для первых двух элементов Икаждой 1-ой диагонали матрицы 12(1 = 22 к) пройдет на входы1-го элемента ИЛИ 15 непосредственно,а импульсы на выходах остальных элементов И 1-ой диагонали матрицы 12пройдут на входы 1-го элемента ИЛИ 1"через элементы задержки 16. Выходныеимпульсы элементов ИЛИ 15 поступаютна.информационные входы коммутатора8 частичных произведений, в которомпо управляющим сигналам Г, и 1 соответственно структурным Формулам91 фформируются микрокоманды, которйепропускают импульсы результата частичных перемножений в соответствующиеразряды накапливающего сумматора 9После выполнения всех микрокоманд внакапливающем сумматоре 9 устанавливается результат перемножения всехчастей сомножителей.Использование нового элемента коммутатора 8 частичных произведений сорганизацией связей его с блоком 7перемножения к-разрядных чисел и накапливающим сумматором 9, построениеблока перемножения к-разрядных чиселиз буферных регистров 10 и 11, матрицы 12 элементов И, дифференцирующихузлов 13, элементов И 14, ИЛИ 15 изадержки 16 позволяют увеличить быстродействие. Например, для перемножения двух 32.-разрядных чисел при к=16за четыре микрокоманды: при к=8 зашесть микрокоманд, что по сравнениюс известным устройством увеличиваетК,быстродействие в - раз.иФормула изобретенияУстройство для умножения и-разрядных чисел содержащее и-разрядные ре 813417гнстры множимого и множителя, коммутаторы групп разрядов множимого имножителя, блок перемножения к-разрядных чисел (к - разрядность групп(множимого имножителя) и накапливающий сумматор, причем выходы регистровмножимого и множителя, огрупщрованные по к разрядов, подключены к информационным вхсщам коммутаторовгрупп разрядов множимого и.множителясоответственно, управляющие входыкоторых подключены соответственно кпервому и второму управляющим входамустройства., а выходы подключены соответственно ко входам множимого имножителя блока перемножения к-разрядных чисел, о т л и ч а ю щ е ес я тем, что, с целью повышениябыстродействия, устройства содержиткоммутатор частичных произведений,информационные. входы которого пддключены к выходам блока перемноженияк-разрядных чисел, управляющие входы - кпервому и второму управляющим входам устройства, а выходыко входам накапливающего сумматора,блок перемножения к-разрядных чиселсодержит буферные регистры, матрицуэлементов И, дифференцирующие узлы,элементы И, ИЛИ и задержки, причемвходы первого и второго буферныхрегистров подключены соответственноко входам множимого и множителя блока перемножения к-разрядных чиселсоответственно, выход 1-го разрядавторого буферного регистра (1=1. к)подключен к первым входам элементов И 1-ой строки матрицы, прямой выход 1-го разряда первого буферного регистра соединен с первым входом 1-го элемента И, второй вход которого подключен к тактовому входу уст-ройства, а выход - ко вторым входамэлементов И -го столбца матрицы,находящихся в четных строках, и ко входу сброса 1-го разряда. первого буферного регистра, инверсный выход которого через -ый узел дифференцирова ния подключен ко вторым входам элементов И 1-го столбца матрицы, находящихся в нечетных ее строках, выходы элементов И -ой диагонали матриць (3 = 12 к) соединены со % входами )-го элемента ИЛИ, причемвыходы первых .двух элементов И каждой 1-ой диагонали матрицы (1=2,., 2 к) подключены ко входам )-го элемента ИЛИ непосредственно, а выходы Я остальных элементов И 1-ой диагонали .матрицы соединены со входами 1-го Элемеита ИЛИ через элементы задержки выходы элементов ИЛИ являются выходами блока перемножения к-разрядных чисел. Источники информации,принятые во внимание при экспертизе 1, Самофалов Е.Г. и др. ЭлектронныЬ 11 идоовые вычислительные машины. Зф к свища школаф, 1976, с.476. 2, Авторское свидетельство СССР М 482740, кл.С 06 Р 7/52, 1974. 3. Патент США 9 3670956,кл.235/164, опублик.1972 (прототип).