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

разрядов регистра множителя соединены дами 3-го и К-го элементов И первой, второйсо входами блока расшифровки состояний и третьей групп(1=2,4,6 п).пар двоичных разрядов множителя и управ- Дополнительно введенные дешифратоления умножением, Первая группа венти- ры состоянийпар двоичных разрядов мнолей передает на сумматор прямой код 5 кимогои блокформирования пардвоичныхмнокимого, вторая группа вентилей - код разрядов утроенного значения множителяудвоенно 1 о- значения. множимого, третья позволяют выполнять умножение в прямыхгруппа - обратный код мнокимого. кодах и исключить три знаковых разрядаНедосгаткойгэтогоустройства является накапливающего сумматора, что ведет кпойикенное быстродействие, особенно при 10 уменьшению быстродействия устройства,п(18-24), из-за наличия в накапливающем На фиг, 1 приведена структурная схемасумматоре трех дополнительных старшихустройства; на фиг. 2 - пример конкретнойразрядов, необходимых для обработки мно- реализации блока формирования пар двоичжимого, представленного в модифициро- ных разрядов утроенного значения множиванном двоичном коде. 15 теля; на фиг, 3 - пример умножения,Целью изобретения является повыше- Устройство (фиг, 1) содержит и-разрядние быстродействие устройства. ный регистр 1 мнокимого, сдвиговый реПоставленная цельдостигаетсятем,что гистр 2 мнокителя, имеющий разряды с.; в устройство фмнокения двоичных чисел, нулевого по и, первую группуЗ элементов И,содержащее и-разрядный регистр мноки включающую в себя нечетные 4 и четные 5мого (и-разрядность сомнокителей), сдви- элементы И; вторую группу 6 элементов И,говый регистр множителя, три группы по и включающую в себя нечетные 7 и четные 8элементов И и и-разрядный /трехвходовой элементы И, третью группу 9 элементов И,накапливающий сумматор, причем выходы включающую в себя нечетные 10 и четные1-х элементов И первой, второй и третьей 25 11 элементы И, и-разрядный трехвходовойгрупп"соединены соответственно с первым,накапливающий сумматор 12, блок 13 фор-вторым и третьим входами 1-горазряда и- мирования пар двоичных разрядов утроенразрядного трехвходового накапливающе- ного значения множителя, дешифраторы 14го сумматора ( = 1,2, и), дополнительно состояний пар двоичных разрядов множивведены блок формирования пар двоич мого,выход 15 нулевогоразрядасдвиговоных" разрядОв утроенного значения мно- го регистра мнокителя соединен с первымикителя и п/2 дешифраторов состояний входами нечетных элементов И 7 второйпар двоичных разрядов множимого, а группы 6 элементов И и первым входом 25, сдвиговый регистр множителя имеет раз- блока 13 формирования пар двоичныхразрядность с нулевого по и-й разряды, при рядов утроенного значения множителя,чем выход нулевого разряда сдвигового второй вход 26 которого соединен с перрегистра множителя соединен с первыми выми входами четных элементов И 8 втовходаминечетныхэлементовИвторойгруп- рой группы 6 элементов И и нечетныхпы и первым входом блока формирования элементов И 4 первой группы 3 элементовпар, двоичных разрядов утроенного значе И и выходом 16 первого разрядасдвиговогония множителя, второй вход которого сое- регистра множителя, выход 17 второго раэ дийен с первыми входами четных элементов ряда которого соединен с первыми входамиИ второй группы и нечетных элементов И четныхэлемейтов И 5 первой группы 3 элепервой группы и выходом первоо разряда ментов И и третьим входом 27 блока 13сдвигового регистра множителя, выход 45 формирования пардвоичных разрядовутровторого разряда которого соединен с пер- енного значения множителя, первый 18 ивыми входами четных элементов И первой второй 19 выходы которого соединены сгруппы и третьим входом блока формирова- первыми входами соответственно нечетныхния пар двоичных разрядов утроенного зна и четных 11 элементов И третьей группычения множителя, первый и второй выходы 50 9 элементов И, выход 20 )-го и выход 21которогосоединеныспервымивходамисо- Я+1)-го разрядов и-разрядного регистраответственно нечетных и четных элементов. множимого соединены соответственно сИ третьей группы, выходы )-го и Д+1)-го первыми вторым входами а-годешифраторазрядов и-разрядного регистра множи- ра 14 состояний пар двоичных разрядовмого соединены соответственно с первым 55 множимого Д = 1, 3, 5, п, в = 1, 2, 3, ,и вторым входами в-го дешифратора со- и/2), первый 22, второй 23 и третий 24 выхостояний пар двоичных разрядов множи- ды которого соединены соответственно сомого=- 1, 3, 8, , п, а = 1, 2, и/2), вторыми входами )-го и 1-го элементов Ипервый, второй и третий выходы которого первой 3, второй 6 итретьей 9 групп элеменсоединены соответственно со вторыми вхо- тов И (с = 2, 4, 6, , и),На фиг, 2 представлен прймер конкрет- ды 20 и 21 дешифратора 14, формируют сигнойреализацииблока 13 формированияпар нал логической едйницы на выходе 22 дедвоичных разрядов утроенного значенияшифратора, если на входах 21 и 20множителя. Блок содержит три инвертора"присутствует сочетание сигналов 01, или48 - 50,триггер 28, первуюлогическуасхему 5 формирует сигналединицы на выходе 23,29, включающую в себя четыре элемента И если на входах 21 й 20 присутствует сочета 30 - ЗЗиэлементИЛИ 34,вторуюлогическую ние сигналов 10, йлй на выходе 24, еслисхему 35, включающую в себя пять. элемен- прйсутствует комбийация 11. В случае ком-тов И 36-40 и элемент ИЛИ 41, и третьюбинации 00 йе будет состояния логическойлогическую схему 42; состоящую из четырех 10 единицы ни на одном иэ выходов дешифраэлементов И 43-46 и элемента ИЛИ 47;тора. В зависимости от того, на каком изПервый вход 25 блока 13 соединен со . выходов т-го дешифратора будет присутствходом инвертора 48 и первыми входами вовать логическая единица,"йа входы т-йэлемейтов И 30, 33, 38, 39, 43, 46, второй пары разрядовнакапливающего сумматоравход 26 соединен со входом инвертора 49, 15 12 будут передаваться либо пара разрядовпервыми входами элементов И 37, 44; 45 икода множителячерезэлементы И 4,5, либовторыми входами элементов И 30,32,40,43, параразрядов кода- удвоенного значениятретий вход 27 подключен ко входу инвер- множителя через элементы И 7, 8, либо. тора 50, вторым входам элементов И 37, 38, пара разрядов кода утроенного значения44, 46 и третьему входу элемента И 36; вы множителя через элементы И 10, 11 и/2ход инвертора 48 соединен с первыми вхо- .: . пар разрядов, одновременно передаваедами элементов И 31, 32, 36, 40, выход мыхчерез элементы"И на входы накапливаинвертора 49 подключен ко вторым входам .ющего сумматора "составляют и-разрядное "элементов И 31, 33, 36, 39, выход инвертара . частичное произведений. Сформирован 50 соединен с третьими входами элементов 25 ное частичное произведение суммируетсяИ 39, 40, прямой выход триггера 28 подклю- с содержимым накапливающего сумматочен ко второму входу элемента И 45;треть-рй, которое на первом"такте: равно нулю,им входам элементов И 30. 31, 37, 46 иПосле окончанияраспространения в накапчетвертамувходуэлемента И 39, инверсный ливающем сумматоре переносов, произвовыход триггера соединен с третьими входа дится сдвиг содержимого накапливающегоми.элементов И 32, 33, 38 и четвертым вхо-: сумматора и содержимого" регистра множидом элемента И 40, выходу элементов И "теля на два разряда в сторону младших раз 30 - 33 подключены ко входам элемента ИЛИрядов.34, выход которого соединен с. первым вы- - Второй и последующие такты отличаютходом 18 блока 13, выходы элеменгов И 35 ся от первого такта тем; что на выходах 16 и36 - 40 подключены ко входам элемента ИЛИ17 появляются логйческие сигналы последу 41., выход которого соединен со вторым вы- . ющих пар разрядовкода множителя; на выходом 19 блока 13, выходы элементов И: ходах 18 и 19 блока 13 формируются43-46 подключены ко входам элемента ИЛИ . последующие пары разрядов кода утроен 47, выход которого соединен со входом ус, ного значения мйожителя, а на входах на-тановки в единицу триггера 28;. капливающего суммагора" образуютсяУстройство для умножения двоичных . второе и последующие частичные произвечисел работает следующим образом, Мно- дения.жимое размещается в регистре 1 (фиг. 1), . Так как кодудвоенногоили утроенногомножитель - в регистре 2. В первом такте 45 значения множителя может иметь дополниумножения на выходах пйрвого 16 и второго тельную старшую (а/2 + 1)-ю пару разря 17 разрядов регистра 2 формируются логи- дов, то количество тактов умножения равноческие сигналы первого и второгодвойчных . и/2 + 1,разрядов множителя, которые поступаЮт Блок 13 (фиг, 2) формирования пардво на входы элементов И 4, 5, 8. а также на 50 ичных разрядов утроенного значения мновторой 26 и третий 27 входы блока 13. Нажителя представляет собой параллельныйвыходе 15 нулевого разряда регистра 2 вдвухразрядный двоичный сумматор, Онпервом такте присутствует сигнал логиче-: . формирует очередную пару двоичных разского нуля, который подается на входы эле- рядов кода утроенного значения мйожителяментов И 7 и на первый вход 25 блока 13, 55 путем суммирования очередных пар двоичБлок 13 формирует на своих выходах 18 и 19 . ных разрядов кода множителя и кода удвопервые два разряда кода утроенного значе- енного значения -множителя, Удвоениения множителя, значения множителя осуществляетсяЛогические сигналы пары двоичныхсдвигом кода множителяна один разряд вразрядов множимого, поступающие на вхо-. сторону старших разрядов влево), следова17849737тельно, блок 13 образует сумму пары 0+1)- . пара - из пары разрядов кода удвоенного го,)-го разрядов кода множит лж теля и пары)-го значения множителя, поступивших с выхонного кода множите- дов 15 и 16 регистра множителя через. , О)-го разрядов удвоенногля. Таким образом, на блок 13 должны пода- элементы И 7 и 8. Таким же образом обрац 1)-, )- и 1-1)-й разряды кода 5 зуются остальные частичные пройзведения множителя. Сигналы этих разрядов снима- после очередных сдвигов множителя в реги- ются с выходов 17, 16 и 15 регистра множи- стре множителя.. Общее время умножения в.заявляемом .Младший разряд пары двоичных разря- устройстве Тэу = сзу(п/2+1), где тзу - время, дов кода утроенного зн ченго значения множителя 10 затрачиваемое.на один такт умножения вв ебя формируется логической хской схемой 29 которая заявляемом устройстве, включающее в се я представляет со ои трехвхоб е входовой однораз- время формирования частичного произверядный двоичный сумматорматорбез схемы пере- дения, время суммирования в накапливаю- носа в следующии разряд.азряд. Схема переноса щем сумматоре и время, затрачиваемое на перенесена влогическуюсхему 35, которая 15 сдвиг. Если задержка сигналов на одном формирует старшии разряд.разряд. Логическая элементе И или на одном элементе ИЛИ схема представля35 тавляет собой одноразряд- равна т,товремя формированиячастичного ный двоичныйчный сумматор с внесенной в нее произведения включает в себя время рассхемой. предыдущего переноса, при этом пространения сигналов в блоке ( г) ( сумматор не содее содержит схему переноса в 20 учетом того, что инверсные сигналй входовий азряд. Логическая схема 42 блока 13 могут быть, сняты с инверсных выформирует перенос из старшего разряда, ходов соответствующих разряд р ря ов егист а который запоминается нз триггере 28 и учи.- множителя) плюс время т передачи сигнатывается при обработке следующей пары лов через элементы И групп элементов И, двоичных разрядов множителя. 25 процессе суммирования время суммироНа фиг. 3 приведен пример умножения вания определяется временем распрост- . двух восьмирсьмиразрядных чисел в процессе ранения сквозного переноса через ит, Так формирования первого (фиг, 3, а), второго .разрядов накапливающего сумматора, ак (3, б), третьего (3, в), четвертого (3, г) и как в сумматоресигнал задерживается йапятого(З,д)частичныхпроизведений, пока одном элементе И и на одном элементезано размещение кодов самого множите- ИЛИ в каждом разряде, то общая задержкаля, удвоенного и утроенного значения при расйространении переноса составит .множителя, кода множимого, кодов в накап п с. Затраты времени на сдвиг займут 3 т,ливающем сумматоре перед прибавлением так как триггеры могут быть представлены вк нему очередного частичного произведе вире двух последовательно соединенныхния и очередные частичные произведения. элементов И-НЕ с задержкой на каждом по состоястоящие из 4-х пар двоичных разрядов, т, плюс задержка тна элементе И, переда й,Младшая пара двоичных разрядов множи- ющем сигналы с одного триггера на друго,мого содержит сочетанйе 01. которое воз- В сумме время,затрачиваемое в заявляеб ждает логическую единицу на выходе 22 40 мом устройстве на один такт, равно тзУ =.ужпервого дешифратора, вторая пара содер- =3 г + 2 п т+ 3 т = 2 п т+ 6.% а время,жит сочетание 11, логическая единица затрачиваемое на и/2+1 тактов составляетформируется на выходе 24 второго дешиф-Тзу = (2 п х+ 6 фп/2+ 1) = п 2 т+ 5 п.т+ 6 сратора, третья пара - комбинацию 00 - на . Так как формирование произведения в повцходахтретьегодешифратораформируют. следнем такте умножения заканчиваетсяся логические нули, четвертая пара разря- прибавлением частичного произведения идов множимого содержит сочетание 10, на в дальнейшем сдвиг готового произведевыходе 23 четвертого дешифратора.появля- ния производить не нужно, время послед.ется логическая единица. Поэтому младшая него сдвига (3 т) исключается из Тзу. Таким ; пара двоичных разрядов первого частич образом, время выполнения операцииного произведения(фиг, 2 а) будет состоять умножения в заявляемом устройстве Тзу"из пары младших разрядов кода множите- =и + 5 п т + 3 сгля, поступивших с выходов 16 и 17 через эле- В устройстве-прототипе время, затраменты И 4 и 5, вторая пара двоичных чивземоенаформированиечастичногопроразрядов частичного произведения будет 55 изведения такое же, как и в заявляемомсостоять из пары двоичных разрядов кода устройстве, так как вместо блока 13 в устутроенного значения множителя, поступив- ройстве-прототипе имеется блок выработкиших с выходов т 8 и 19 блока 13 через зле- сигналов управления группами вентилей,менты И 10 и 11, третья пара двоичных. содержащий четыре логических схемы Иоазрядов будет состоять из нулей, четвертая. ИЛИ и триггер переноса, и задерживающий причем выходы 1-х элементов И первой, втосигналы на 2 х. Затраты времени на сдвиг рой и третьей групп соединены соответстостанутся теми же, что и в заявляемОм уст- венно с первым, вторым и третьим входами ройстве 3). Время распространения сквоз-го разряда и-разрядного трехвходового ногопереносавнакапливающемсумматоре 5 накапливающего сумматора ( = 1,; и), в устройстве-прототипе больше по сравне- о т л и ч а ю щ е е с я тем, что."с целью нию с временем в трех старших знаковых повышения быстродействия, а сдвиговый разрядах сумматора без учета последнегоретистр множителя имеет разрядность с нупереноса, который отбрасывается, т.е, на левого по и разряды, оричем выход нуле с Количество тактов умножения остается 10 ваго разряда сдвигового регистра тем же. Длительность такта умножения в множителя соединен с первыми входами устройстве-прототипе равна асуп - 3 т+ нечетных элементов И второй группы и+2 п х+5 т + 3 ю = 2 п т + 11 ю, а вЕмя первым входом блока формирования парвыполнения (пР 2+1) тактов - Туп - и т+. двоичных разрядов утроенного значения +7,5 п Г+ 11 т. В последнем такте сдвиг 16 множителя, второй вход которого соедиготового произведения не производится, нен с первыми входами четных элементовТаким образом, время выполнения опе-: И второй группы инечетныхэлементов И рации умножения в устройстве-прототипепервой группы и выходом перваго разряда Т - п т+ 7,5 п т +8 с сдвигового регистра множителя, выход втоСравнительные данные по затратам 20. рого разряда которого соединен с первыми времени йа умножение в зависимости отвходами четных элементов И первой группы величины и для заявляемого устройства ии третьим входом блока формирования пар устройства-прототипа приведены в табли- двоичных разрядов утроенного значения . це: . множе, первый и второй од кото- Из данных таблицы видно, что время 25 рого соединены с первыми входами соотвыполнения операции умножения в эаявдя- ветственно нечетных и четных элементов И емом устройстве в 1;04 - 1,23 раза меньше;третьей группы, выходы)-го и Д+1)-го разрячем в устройстве-прототипе, . дов и-разрядного регистрамножимого соединены соответственнО с первым и вторымФ о р м ул а и з о б р е т е н и я 30 входами е-го дешифратора состояний пар., Устройство для умножения двоичных .двоичных разрядов множимого Ц = 1, 3, 5, чисел, содержащее и-разрядный регистр,.п. е - 1, 2, ., и 2) первый, второй и множимого (и - разрядность сомножите- третий выходы которого соединены соотлей), сдвиговыйрегистр множителя, триветственно с вторыми входами )-го и К-го группы по и элементов И и и-разрядный 35 элементовИпервой,второйитретьейгрупп трехвходовой накапливающий сумматор, 0(= 2 4 6. - и).Техред М.Моргентал Корректор О, Кравцова Редакт Заказ 4365Тираж Подписное ВНИИПИ Государственного комитета по изобретениям й открытиям при ГКНТ ССС 113035, Москва, Ж-ЗБ, Раушская наб 4 В Производственно-издательский комбинат "Патент", г. Ужгород, ул.Гагарина Наидллибдющий суиндеор, с Ъредидущин чосяитинмьроийе 3 еицеиНоБое т,античное ироизЫвииенд Ьподдн чрии олелееащо,ВД 6 шиодрояори -Рее,исвр мйожииоео Вы 8, Блока 3 Вмоды д;ирегистра Л