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

111) 482741 Сова Советских Социалистических Республик(51) М. Кл. б 061 7/5 с присоединением заявк Государственнык комитет Совета Министров СССРДата опубликования описан 9,12,7(71) Заявител УСТРОЙСТВО ДЛЯ УМНОЧИСЕЛ Я ДВОИЧНЫ носится к области вычислипредназначено для умно- чисел, заданных параллельИзобретение оттельной техники икения двоичныхными кодами.Известны устройства для умножения двоичных чисел, построенные на основе регистров сдвига множимого, на которые параллельно заносятся значения множимого с регистра множимого, в зависимости от числа единиц в разрядах множителя, с последующим сложением этих значений в сумматоре.В других известных устройствах используется схема анализа очередных т групп разрядов множителя, в зависимости от которого проводятся последовательное занесение и суммирование в сумматоре значений множимого, сдвинутых на т разрядов.Предложенное устройство отличается от известных тем, что выход схемы анализа разрядов соединен с входом триггера, выход второго вентиля - с первым входом второго управляющего триггера и с входом первой схемы управления, выход третьего вентиля - с вторым входом второго управляющего триггера и с входом второй схемы управления. Входы первой и второй схем управления подключены к выходам регистров множимого и множителя соответственно, выходы обеих схем управления - к входам параллельного сумматора, соединенным с выходами схемы сдвига, Выходы четвертого и пятого вентилеи подсоединены к входам первой и второй схем формирования импульсов считывания, входы которых связаны с соответствующими выхо дами регистра множителя, а выходы - с входами схемы сдвига и с вторым входом первого управляющего триггера. Входы четвертого и пятого вентилей подключены к выходам дешифратора, входы второго и третьего венти лей через элемент задержки - к шине запуска,Это позволяет повысить быстродействие устройства.Предложенное устройство реализует следу ющие алгоритмы умножения двоичных чисел.Берут два п-разрядных двоичных числа; множимое А, множитель В; проводят анализ количества единиц и нулей во множителе В.Если количество единиц во множителе 20 больше количества нулей, то для полученияпроизведения берут прямой код множимого А, справа от которого приписывается столько нулей, сколько разрядов содержит любой из сомножителей. Из полученного числа последо вательно вычитают прямой код множимого Аи прямой код чисел, полученных путем сдвига множимого А влево на число разрядов, на единицу меньшее номеров тех разрядов, которые содержат нули во множителе В (начи- ЗО ная с младшего разряда).( в ) 5 101000000 100111110000,100000011111 100000011111 ( - ) 1000010 Полученное таким образом число является произведением двух чисел (первый алгоритм).Если количество нулей во множителе больше количества единиц, то для получения произведения берут прямой код множителя В, справа от которого приписывается столько нулей, сколько разрядов содержит любой из сомножителей. Из полученного числа последовательно вычитают прямой код множителя В и обратный код чисел, полученных путем сдвига множимого А влево на число разрядов, на единицу меньшее номеров тех разрядов, которые содержат единицы во множителе В (начиная с младшего разряда),Полученный результат является произведением двух сомножителей второй алгоритмы.Пусть, например, даны множимое А = =100001, множитель В=101101. Поскольку в множителе В единиц больше, чем нулей, используем первый алгоритм:а) берем прямой код множимого 100001; б) справа от множимого А приписываем столько нулей, сколько разрядов содержит любой из сомножителей, - 100001000000;в) из полученного числа последовательно вычитаем прямой код множимого А100001000000( в ) 100001 прямой код чисел, полученных путем сдвига множимого А влево на число разрядов, на единицу меньшее номеров тех разрядов, которые содержат нули во множителе В (в данном случае, таковыми являются второй и пятый разряды) 11111011101,где 1000000 - число А, сдвинутое на один разряд влево,1111101110110111 а 01101,где 1000010000 в .число А, сдвинутое на четыре разряда влево,Результат умножения - 10111001101.Пусть теперь даны множимое А=110101 имножитель В=110000. Поскольку в множителе В число нулей больше, чем число единиц, используем второй алгоритм:а) берем прямой код множителя В 110000;б) справа от множителя В приписываемстолько нулей, сколько разрядов содержитлюбой из сомножителей 110000000000;в) из полученного числа последовательновычитаем прямой код множителя В110000000000( в ) 110000101111010000 20 25 зо 35 40 45 50 55 бо 65 обратный код чисел, полученных путем сдвига множимого А влево на число разрядов, на единицу меньшее номеров тех разрядов, которые содержат единицы во множителе В (таковыми являются пятый и шестой разряды):( в ) 10100000,где 10100000 - число А, сдвинутое на пять разрядов влево;где 101000000 - число А, сдвинутое на пятьразрядов влево.Результат умножения - 100111110000.Схема устройства изображена на чертеже.Устройство содержит параллельный сумматор 1, содержащий и старших и и младшихразрядов; регистр 2 множимого (на и разрядов); регистр 3 множителя (также на и разрядов); схему 4 анализа разрядов (множителя); вентили 5 и 6; счетчик 7; дешифратор 8;схемы 9 и 10 формирования импульсов считывания (используемые при реализации первого и второго алгоритмов соответственно); схему 11 сдвига; схемы 12 и 13 управления длясчитывания в сумматор 1 прямых кодов множителя и множимого соответственно; вентили 14, 15 и 16; управляющие триггеры 17 и18; генератор 19 импульсов; триггер 20; элемент 21 задержки; шину 22 запуска.Устройство работает следующим образом.После приема множимого на регистр 2 через вход 23 и множителя на регистр 3 черезвход 24, по шине 22 поступает импульс запуска устройства, который устанавливает вединичное состояние триггер 18, тем самымразрешая прохождение через вентиль 16 импульсов с генератора 19 на счетчик 7 и дешифратор 8. Одновременно импульс запускапоступает на схему 4 анализа разрядов множителя. Работа схемы анализа заключаетсяв определении преобладания числа единицнад числом нулей в регистре множителя, либочисла нулей над числом единиц. Если числоединиц во множителе больше числа нулей, тоумножение выполняется по первому алгоритму, если наоборот - по второму. При равномколичестве единиц и нулей во множителе(при четном и) может использоваться любойалгоритм. Схема анализа разрядов множителя может быть комбинационной.Сигнал с выхода схемы 4 подается на единичный вход триггера 20, который разрешаетпрохождение импульса запуска, задержанного на элементе 21 задержки, либо через вентиль 5 (если единиц во множителе больше,чем нулей), либо через вентиль 6 (в противном случае),55 50 65 В первом случае импульс запуска с выходавентиля 5 поступает на схему 13 управления,считывая значения прямого кода множимого с регистра 2 в и старших разрядов сумматора 1. Одновременно прямой код множимого, инвертируясь для вычитания, считывается в и младших разрядах сумматора 1.При этом одновременно на все единичныевходы и старших разрядов сумматора с задержкой, равной времени установления переходных процессов в этих разрядах, проходитимпульс, который считывал значение множимого. Тем самым проводится вычитание иззначений прямого кода множимого, сдвинутого влево на и разрядов, значений несдвинутого прямого кола множимого. Одновременноимпульс запуска устанавливает в нуль триггер 20,Во втором случае импульс запуска с выхода вентиля 6 поступает на схему 12 управления, считывая значение прямого кода множителя с регистра 3 в г старших разрядовсумматора 1 и значение обратного кода множителя в г младших разрядов сумматора. Сприходом импульса на единичные входы старших разрядов сумматора 1 выполняется операция вычитания из значения прямого кодамножителя, сдвинутого на и разрядов влево,значений несдвинутого прямого кода множителя, а также подтверждается установкатриггера 20 в нулевое состояние.Одновременно импульс запуска устанавливает в единичное состояние управляющийтриггер 17 в случае, когда число единиц вомножителе больше числа нулей, или в нулевое состояние в обратном случае, разрешаятем самым прохождение импульсам с дешифратора 8 через вентили 15 или 14 соответственно на схемы 9 или 10.Особенность работы счетчика 7 и дешифратора 8 заключается в том, что импульсы свыхода дешифратора следуют с периодом,равным времени сложения (вычитания) одного двоичного числа в сумматоре 1. Это определяется соответствующей коммутацией выходных шин дешифратора (т, е. выходные шины могут коммутироваться в сборки через одну, две, три и т, д в зависимости от времени сложения - вычитания числа в сумматоре).Первый импульс, проходящий через вентиль 15 при большем числе единиц во множителе или через вентиль 14 (в обратном случае) поступает соответственно на вход либосхемы 9, либо схемы 10, которые управляютсярегистром 3,В первом случае данный импульс, последовательно проходя через вентили сквозного переноса схемы 9, управляемые с единичныхвыходов разрядов регистра 3, отыскивает первый, находящийся в нулевом состоянии разряд этого регистра, устанавливает его в единичное состояние и поступает с выхода схемы 9, соответствующей пер ебрасываемомуразряду, на вход схемы 1 сдвига. С помощью 5 10 15 20 25 Зо 35 40 45 50 схемы 11 импульс считывает в сумматор 1значения прямого кода множимого, сдвинутого влево на число разрядов, на единицуменьшее номеров тех разрядов, которые содержат нули во множителе.Сдвиг осуществляется за счет соответствующей коммутации потенциальных выходовразрядов регистра 2 множимого с импульсными выходными шинами схемы 9, в соответствии с изложенным принципом получения произведения по первому алгоритму.В втором случае импульс, последовательнопроходя через вентили сквозного переносасхемы 10, управляемые с нулевых выходовразрядов регистра 3, отыскивает первый находящийся в единичном состоянии разряд этого регистра, перебрасывает его в нулевое состояние и поступает с выходной шины схемы10, соответствующей перебрасываемому разряду, на вход схемы 11. С помощью этой схемы импульс считывает в сумматор 1 значения обратного кода множимого сдвинутого,влево па число разрядов, на единицу меньшее номеров тех разрядов, которые содержат единицы во множителе,Сдвиг осуществляется за счет соответствующей коммутации потенциальных выходовразрядов регистра множимого с импульснымивыходными шинами схемы 10, в соответствии сизложенным принципом получения произведения по второму алгоритму.Следующий импульс с дешифратора 8, поступая на вход схемы 9 или 10, проводит аналогичные действия.Схемы 9 и 10 работают до тех пор, покане будут установлены в единичные состояниявсе разряды регистра множителя в первомслучае, либо в нулевое состояние во второмслучае.При этом очередной импульс с выхода дешифратора 8, пройдя сквозным переносомчерез вентили схем 9 или 10, поступает натриггер 18 для установки его в нулевое состояние, тем самым прекращая работу устройства.Произведение двух сомножителей формируется на сумматоре 1.Таким образом, время выполнения операции умножения является плавающим, от своего минимального значения при значении множителя 0000 либо 111 11, до максимального, при условии равного количества единици нулей во множителе. Предмет изобретения Устройство для умножения двоичных чисел, содержащее регистр множимого, выходы которого соединены с входами схемы сдвига, регистр множителя, выходы которого соединены с входами схемы анализа разрядов, генератор импульсов, выход которого соединен через первый вентиль с входами счетчика и дешифратора, входы последнего соединены с выходами счетчика, первый управляющий482741 ставитель В. Игнатущен ректор Л. Денискин Техред 3. Тараненко актор И. Гр Тираж 679тета Совета Министров ССС ний и открытийская наб., д. 4/5 Изд, Хо 1742сударствениого ком по делам изобре Москва, Ж, Рау дписное каз 2934 ИПИ Г Типография, пр. Сапунова триггер, выход которого соединен с входом первого вентиля, а вход соединен с шиной запуска, соединенной с входом анализа разрядов, триггер, выходы которого соединены с входами второго и третьего вентилей, второй управляющий триггер, выходы которого соединены с входами четвертого и пятого вентилей, параллельный сумматор, элемент задержки, схемы управления и схемы формирования импульсов считывания, о т л и ч а ю щ е еся тем, что, с целью повышения быстродействия, выход схемы анализа разрядов соединен с входом триггера, выход второго вентиля соединен с первым входом второго управляющего триггера и с входом первой схемы управления, выход третьего вентиля соединен с вторым входом второго управляющего триггера и с входом второй схемы управления, входы первой и второй схем управления соединены с выходами регистров множимого и множителя соответственно, выходы обеих схем управления соединены с входами параллельного сумматора, соединенными с выходами схемы сдвига, выходы четвертого и пятого вентилей соединены с входами первой и второй схем формирования импульсов считывания, 1 О входы которых соединены с соответствующими выходами регистра множителя, а выходы соединены с входами схемы сдвига и с вторым входом первого управляющего триггера, входы четвертого и пятого вентилей соедине ны с выходами дешифратора, входы второгоитретьего вентилей соединены через элемент задержки с шиной запуска.