Устройство для умножения двоичных чисел Советский патент 1975 года по МПК G06F7/52 

1

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

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

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

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

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

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

Берут два «« -разрядных двоичных числа:

множимое А, множитель В; проводят анализ

количества единиц и нулей во множителе В.

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

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

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

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

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

Пусть, например, даны множимое Л 100001, множитель 6 101101. Поскольку в множителе В единиц больше, чем нулей, используем первый алгоритм:

а)берем прямой код множимого 100001;

б)справа от множимого А приписываем столько нулей, сколько разрядов содержит любой из сомножителей,- 100001000000;

в)из полученного числа носледовательно вычитаем прямой код множимого Л

100001000000 (-) 100001

100000011111

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

100000011111 (-) 1000010

11111011101,

где 1000000 - число А, сдвинутое на один разряд влево,

11111011101 (-) 1000010000

lOlliaOllOl,

где 1000010000 - число А, сдвинутое на четыре разряда влево.

Результат умножения - 10111001101.

Пусть теперь даны множимое Л 110101 и множитель В 110000. Поскольку в множителе В число нулей больше, чем число единиц, используем второй алгоритм:

а)берем прямой код множителя В 110000;

б)справа от множителя В приписываем столько нулей, сколько разрядов содержит любой из сомножителей 110000000000;

в)из полученного числа последовательно вычитаем прямой код мнол ителя В

110000000000 (-) 110000

101111010000

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

101111010000

(-) 10100000,

где 10100000-число Л, сдвинутое на пять разрядов влево;

101100110000

(-)

101000000

100111110000,

где 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 (в противном случае).

В первом случае импульс запуска с выхода вентиля 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 сдвига. С помощью

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

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

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

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

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

изложенным принципом получения произведения по второму алгоритму.

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

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

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

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

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

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

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

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

с выходами счетчика, первый управляющий

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

управления соединены с входами параллельного сумматора, соединенными с выходами схемы сдвига, выходы четвертого и пятого вентилей соединены с входами первой и второй схем формирования импульсов считывания,

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