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

 

ОЛ И САНИ Е

ИЗОБРЕТЕНИЯ

К ABTGPCNQAAV СВИДЕТЕЛЬСТВУ 1ц 482741

Сова Советских

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

Республик (61) Дополнительное к авт. свид-ву ,(22) Заявлено 25.12.73 (21) 1982590/18-24 с присоединением заявки № (23) Приоритет

Опубликовано 30,08.75. Бюллетень ¹ 32

Дата опубликования описания 09.12,75 (51) М. Кл. б 06f 7/52

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

Совета Министров СССР по делам изобретений и открытий (53) УДК 681.325.57 (088.8) (72) Автор изобретения, )

*.

Ю. Л. Берг (71) Заявитель (54) УСТРОЙ СТВО ДЛЯ УМНО)КЕН ИЯ ДВОИЧНЫХ

ЧИСЕЛ

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

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

В других известных устройствах используется схема анализа очередных т групп ðàçрядов множителя, в зависимости от которого проводятся последовательное занесение и суммирование в сумматоре значений множимого, сдвинутых на т разрядов.

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

Входы первой и второй схем управления подключены к выходам регистров множимого и множителя соответственно, выходы обеих схем управления — к входам параллельного сумматора, соединенным с выходами схемы сдвига. Выходы четвертого и пятого вентилей подсоединены к входам первой и второй схем формирования импульсов считывания, входы которых связаны с соответствующими выхо5 дами регистра множителя, а выходы — с входами схемы сдвига и с вторым входом первого управляющего триггера. Входы четвертого и пятого вентилей подключены к выходам дешифратора, входы второго и третьего венти1о лей через элемент задержки — к шине запуска.

Это позволяет повысить быстродействие устройства.

Предложенное устройство реализует следу15 ющие алгоритмы умножения двоичных чисел.

Берут два «и»-разрядных двоичных числа: множимое А, множитель В; проводят анализ количества единиц и нулей во множителе В.

Если количество единиц во множителе

20 больше количества нулей, то для получения произведения берут прямой код множимого

А, справа от которого приписывается столько нулей, сколько разрядов содержит любой из сомножителей. Из полученного числа последо25 вательно вычитают прямой код множимого А и прямой код чисел, полученных путем сдвига множимого А влево на число разрядов, на единицу меньшее номеров тех разрядов, которые содержат нули во множителе В (начиЗО ная с младшего разряда).

482741

10» »010000

10»00»0000 (— ) !

101000000

100»»10000, 1000000» » 1

1000000» 1» (— ) 1000010

Полученное таким образом число является произведением двух чисел (первый алгоритм).

Если количество нулей во множителе больше количества единиц, то для получения произведения берут прямой код множителя

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

В и обратный код чисел, полученных путем сдвига множимого А влево на число разрядов, на единицу меньшее номеров тех разрядов, которые содержат единицы во множителе В (начиная с младшего разряда).

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

Пусть, например, даны множимое А =

= 100001, множитель В = 10» 01. Поскольку в множителе B единиц больше, чем нулей, используем первый алгоритм: а) берем прямой код множимого 100001; б) справа от множимого А приписываем столько нулей, сколько разрядов содержит любой из сомножителей,— 100001000000; в) из полученного числа последовательно вычитаем прямой код множимого А

100001000000 (†) 100001 прямой код чисел, полученных путем сдвига множимого А влево на число разрядов, на единицу меньшее номеров тех разрядов, которые содержат нули во множителе В (в данном случае, таковыми являются второй и пятый разряды) »»10»101, где 1000000 — число А, сдвинутое на один разряд влево, »1»01»01 (†) 1000010000

101» ®1101, где 1000010000 †.число А, сдвинутое на четыре разряда влево.

Результат умножения — 10» 100» 01.

Пусть теперь даны множимое А=»0101 и множитель B= »0000. Поскольку в множителе В число нулей больше, чем число единиц, используем второй алгоритм: а) берем прямой код множителя В»0000; б) справа от множителя В приписываем столько нулей, сколько разрядов содержит любой из сомножителей»0000000000; в) из полученного числа последовательно вычитаем прямой код множителя В

»0000000000 (— )»0000

101 » 1010000

Зо

65 обр атный код чисел, полученных путем сдвига множимого А влево на число разрядов, vа единицу меньшее номеров тех разрядов, которые содержат единицы во множителе В (таковыми являются пятый и шестой разряды): (†) 10100000, где 10100000 — число А, сдвинутое на пять разрядов влево; где 101000000 — число А, сдвинутое на пять разрядов влево.

Результат умножения — 100»» 10000.

Схема устройства изображена на чертеже.

Устройство содержит параллельный сумматор 1, содержащий и старших и и младших разрядов; регистр 2 множимого (на и разрядов); регистр 3 множителя (также íà п разрядов); схему 4 анализа разрядов (множителя); вентили 5 и 6; счетчик 7; дешифратор 8; схемы 9 и 10 формирования импульсов считывания (используемые при реализации первого и второго алгоритмов соответственно); схему » сдвига; схемы 12 и 13 управления для считывания в сумматор 1 прямых кодов множителя и м ножи мого соответственно; вентили 14, 15 и 16; управляющие триггеры 17 и

18; генератор 19 импульсов; триггер 20; элемент 21 задержки; шину 22 запуска.

Устройство работает следующим образом.

После приема множимого на регистр 2 через вход 23 и множителя на регистр 3 через вход 24, по шине 22 поступает импульс запуска устройства, который устанавливает в единичное состояние триггер 18, тем самым разрешая прохождение через вентиль 16 импульсов с генератора 19 на счетчик 7 и дешифратор 8. Одновременно импульс запуска поступает на схему 4 анализа разрядов множителя. Работа схемы анализа заключается в определении преобладания числа единиц над числом нулей в регистре множителя, либо числа нулей над числом единиц. Если число единиц во множителе больше числа нулей, то умножение выполняется по первому алгоритму, если наоборот — по второму. При равном количестве единиц и нулей во множителе (при четном n) может использоваться любой алгоритм. Схема анализа разрядов множителя может быть комбинационной.

Сигнал с выхода схемы 4 подается на единичный вход триггера 20, который разрешает прохождение импульса запуска, задержанного на элементе 21 задержки, либо через вентиль 5 (если единиц во множителе больше, чем нулей), либо через вентиль 6 (в противном случае).

482741

В первом случае импульс запуска с выхода вентиля 5 поступает на схему 13 управления, считывая значения прямого кода множимого с регистра 2 в и старших разрядов сумматора 1. Одновременно прямой код множимого, инвертируясь для вычитания, считывается в и младших разрядах сумматора 1.

При этом одновременно на все единичные входы п старших разрядов сумматора с задержкой, равной времени установления переходных процессов в этих разрядах, проходит импульс, который считывал значение множимого. Тем самым проводится вычитание из значений прямого кода множимого, сдвинутого влево на и разрядов, значений несдвинутого прямого кода множимого. Одновременно импульс запуска устанавливает в нуль триггер 20.

Во втором случае импульс запуска с выхода вентиля 6 поступает на схему 12 управления, считывая значение прямого кода множителя с регистра 3 в и старших разрядов сумматора 1 и значение обратного кода множителя в z младших разрядов сумматора. С приходом импульса на единичные входы старших разрядов сумматора 1 выполняется операция вычитания из значения прямого кода множителя, сдвинутого на и разрядов влево, значений несдвинутого прямого кода множителя, а также подтверждается установка триггера 20 в нулевое состояние.

Одновременно импульс запуска устанавливает в единичное состояние управляющий триггер 17 в случае, когда число единиц во множителе больше числа нулей, или в нулевое состояние в обратном случае, разрешая тем самым прохождение импульсам с дешифратора 8 через вентили 15 или 14 соответственно на схемы 9 или 10.

Особенность работы счетчика 7 и дешифратора 8 заключается в том, что импульсы с выхода дешифратора следуют с периодом, равным времени сложения (вычитания) одного двоичного числа в сумматоре 1. Это определяется соответствующей коммутацией выходных шин дешифратора (т. е. выходные шины могут коммутироваться в сборки через одну, две, три и т. д., в зависимости от времени сложения — вычитания числа в сумматоре).

Первый импульс, проходящий через вентиль 15 при большем числе единиц во множителе или через вентиль 14 (в обратном случае) поступает соответственно на вход либо схемы 9, либо схемы 10, которые управляются регистром 3.

В первом случае данный импульс, последовательно проходя через вентили сквозного переноса схемы 9, управляемые с единичных выходов разрядов регистра 3, отыскивает первый, находящийся в нулевом состоянии разряд этого регистра, устанавливает его в единичное состояние и поступает с выхода схемы 9, соответствующей перебрасываемому разряду, на вход схемы 1 сдвига. С помощью

5

З0

50 схемы 11 импульс считывает в сумматор 1 значения прямого кода множимого, сдвинутого влево на число разрядов, на единицу меньшее номеров тех разрядов, которые содержат нули во множителе.

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

В втором случае импульс, последовательно проходя через вентили сквозного переноса схемы 10, управляемые с нулевых выходов разрядов регистра 3, отыскивает первый находящийся в единичном состоянии разряд этого регистра, перебрасывает его в нулевое состояние и поступает с выходной шины схемы

10, соответствующей перебрасываемому разряду, на вход схемы 11. С помощью этой схемы импульс считывает в сумматор 1 значения обратного кода множимого сдвинутого, влево па число разрядов, на единицу меньшее номеров тех разрядов, которые содержат единицы во множителе.

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

Следующий импульс с дешифратора 8, поступая на вход схемы 9 или 10, проводит аналогичные действия.

Схемы 9 и 10 работают до тех пор, пока не будут установлены в единичные состояния все разряды регистра множителя в первом случае, либо в нулевое состояние во втором случае.

При этом очередной импульс с выхода дешифратора 8, пройдя сквозным переносом через вентили схем 9 или 10, поступает на триггер 18 для установки его в «нулевое» состояние, тем самым прекращая работу устройства.

Произведение двух сомножителей формируется на сумматоре 1.

Таким образом, время выполнения операции умножения является «плавающим», от своего минимального значения при значении множителя 000....0 либо 111... 11, до максимального, при условии равного количества единиц и нулей во множителе.

Предмет изобретения

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

482741

Составитель В. Игнатущенко

Техред 3. Тараненко

Корректор Л. Денискина

Редактор И. Грузова

Заказ 2934/13 Изд. № 1742 Тираж 679 Подписное

ЦНИИПИ Государственного комитета Совета Министров СССР по делам изобретений и открытий

Москва, 7К-35, Раушская наб., д. 4/5

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