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

Изобретение относится к вычислительной технике и мозкет быть использовано при построении арифметических устройств.Известно устройство для умножения чисел в обратном коде, содержащее сумматор/ perifCTpH сомножителей и результата, блок формирования сигналов прямой и инверсной передачи множимого Q в сумматор, блок совпадения нулевого значения, блок коррекции млйдшей части произведения, триггер/ блоки совпадения и неравнозначности l3 .

Данное устройство обладает невысо- 15 КИМ быстродействием

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

Быстродействие этого устройства также невелико.

Наиболее близким к изобретению яв 25 ляется устройство для умножения двоичных чисел, содержащее регистры множимого и множителя,пераллельный сумма тор,1лок анализа разрядов, счетчик, дёшшрратор, два блока формиро- 30

-вания импульсов считывания, два блока управления считыванием, блок сдвига, генератор, элемент задержки, пять элементов И, три триггера, причем выход .генератора соединен с перВЕЛм входом первого элемента И, второй вход , которого соединен с единичнымвыходом первого триггера, а выход соединен с. входом счетчика и управлякщим входом дешифратора, информационные входа которого соединены с разрядными выходами счетчика, а выходы дешиЗатора подключены к первым входам второго элемента И и третьего элемента И, вторые входы которых подключены соответственно к нулевому и единичному выходагл второго триггера, а выходы соединены соответственно с управляющими входами первого и второго блоков формирования импульсов считывания, информационные входы которых соединены с соответствующими выходами регистра множителя, а выходы соединены с входами блока сдвига и с нулевым ВХОДСН4 первого триггера, единичный вход которого соединен с шиной .запуска устройства, с управляющим входом блока анализа разрядов н flxo|цом элемента задержки, выход которого подключен к первым входам четвертого и пятого элементов И, вторые входы которых соединены соответственно с единичным и нулевым выходами третьего триггера, а выходы подключе ны к нулевому входу третьего триггера и соответственно к единичному и нулевому входам второго триггера, к управляющим входам первого и второго блоков управления, информационные входы которых соединены соответственно с выxoдiaми регистров множимого и множителя, а выходы соединены с входают параллельного сумматора, сое диненными с выходами блока сдвига, входы которого соединены с соответствующими выходами регистра множимого, выходы регистра множителя подключены к входам блока анализа разрядов, выход которого подключен к единичному входу третьего Тригге- ; ра, входы регистров сомножителей являются входами устройства, а выходы параллельного сумматора - выходами устройства 3}. Данное устройство производит анализ множителя на преобладание в нем единиц или нулей и осуществляет умножение соответственно с использованием прямого или обратного кодов мно жимого. Вследствие жесткого разделения сомножителей на множитель и множимое быстродействие устройства умен шается при приближении к равенству нулей и Идиниц в множителе. Цель изобретения - повышение быст родействия устройства. Цель достигается тем, что устройство для умнохсения двоичных чисел,со держащее регистр множителя, регистр множимого, параллельный сумматор, блок анализа разрядов, блок сдвига, два блока управления, генератор тактовых импульсов, два блока формирования импульсов считывания, элемент задержки, пять элементов И, счетчик, дешифратор, три триггера, причем выход генератора тактовых имп/льсов со единен с первым входом первого элемента И, второй вход которого соединен с единичным выходом нулевого .три гера, а выход соединен с входом счет чика и управляк 1им входом дешифратора, информационные входы которого соединены с разрядными выходами счет чика, а выход дешифратора подключен к первым входам второго и третьего элементов И, вторые входы которых подключены соответственно к нулевому и единичному выходам второго триггера, а выходы соединены соответственно с управляющими входами первого и второго блоков формирования импульсов считывания, информационные входы которых соединены с соответствующими выходами регистра множителя, а выходы соединены с входами блока сдвига и с нулевым входом первого триггера, единичный вход которого соединен с шиной запуска устройства и с входом элемента задержки, выход которого подключен к первым входгии четвертого и пятого элементов И, вторые входы которых соединены соответственно с нулевым и единичным выходами третьего триггера, а выходы подключены к нулевому входу третьего триггера и соответственно к единичному и нулевому входам второго триггера, к управляющим входам первого и второго блоков управления, соответственно, информационные входы которых соединены соответственно с выходг1ми регистров множимого и множителя, а выходы соединены соответственно с входами параллельного сумматора,соединенными с соответственно с выходг1ми блока сдвига, входы которого соединены с соответствующими выходами регистра множимого, первый управляющий выход блока анализа разрядов подключен к единичному входу третьего триггера, выходы параллельного сумматора являются выходами устройства, содержит коммутатор сомножителей, причем первая группа его выходов подключена к соответствующим разрядным входам регистра множителя, вторая группа выходов подключена к соответствующим разрядным входам регистра множимого, первая группа информационных выходов блока анализа разрядов подключена соответственно к первым информационным входам первой и втррой групп коммутатора сомножителей, вторая группа информационных выходов блока анализа разрядов соединена соответственно со вторыми информационныгли входами первой и второй групп комг утатора сомножителей, второй управляющий выход блока анализа разрядов подключен к второму и первому управляющим входам первой и второй группы коммутатора сомножителей соответственно, третий управляющий выход блока анализа разрядов подключен к второму и первому управляющим входам первой и второй группы коммутатора сомножителей соответственно, выход элемента задержки подключен к входу разрешения коммутатора сомножителей, первые и вторые информационные входы блока анализа разрядов соединены соответственно с входами первого и второго операндов устройства. Кроме того, блок анализа разрядов содержит два регистра, два преобразователя двоичного кода в уплотненный, элемент сравнения, два элемента ИЛИ, причем первые и вторые информационные входы блока соединены соответственно с входами первого и второго регистров, выходы которых подключены соответственно к входам первого и второго преобразователей двоичного кода в уплотненный и к первой и второй группе информационт ных выходов блока, прямле выходы первого и второго преобразователей двоичного кода в уплотненный подключены соответственно к входам . первого и второго чисел элемента оравнения г инверсные выходы первого и второго преобразователей двсжчного кода в уплотненный подключены соответственно к входа третьего и четвертого чисел элемента- сравнения,пер вый вход первого элемента ИЛИ подключей к первому выходу элемента сра нения, второй его вход подключен к третьему выходу элемента сравнения, прямой выход первого элемента ИЛИ со динен со вторым управлякшшм выходом (блока, а инверсный выход первого эле мента ИЛИ соединен с третьим управля ющим выходом блока, первый вход второго элемента ИЛИ соединен с третьим выходом элемента сравнения, второй ааход соединен с четвертым выходом элемента сравнения/ а выход подклю чен к первому управляющему выходу блока. На фиг. 1 представлена схема устройства для умножения двоичных чисел на фиг. 2 - схема блока анализа разрядов. Устройство содерлмт регистр множимого 1, блок сдвига 2, генератор тактовшс импульсов 3, элемент И 4, счетчик 5, дешифратор б, триггегил 7 ,и 8, элементы И 9 к 10, триггер 11, (элементы И 12 и 13, блоки управления бчитыванием 14 и 15, регистр множите ля 16, параллельный сумматор 17, блок формирования импульсов считывания 18 и 19, элемент задержки 20, блок анализа разрядов 21, к ф«утатор сомножителей 22, шиИы операндов 23, 24 тину запуска 25. Блок анализа разрядов содержит реги стр 26,преобразователи двоичного кода в уплотненный 27 и 28, элемент сравнения 29, элементы ИЛИ ЗО и 31, вьпсоды первого и второго регистров 32 и 33, первый управлякяоий выход блока 34, Ьторой и третий управлякхдае .выходы (блока 35 и 36, регистр 37. Предложенное устройство реализует сладуюсцие алгоритмы умножения .двоичных чисел. Беру-т два п -раэрядных двоичных числа и выбирают в качертве множителя число с наименьшим количеством единиц или нулей. .Если количество единиц в множителе больше количества нулей, то для получения произведения берут прямой код множимого, справа от которого приписывается столько нулей,сколько/ разрядов содержит множитель. Из полученного числа последовательно вычита1ют прямой код множимого и прямой код чисел, полученных путем сдвига множимого влево на число разрядов, на единицу меньше номеров тех разр5шов, которые содержат нули во множителей (начиная с младшего разряда).Полученное таким образом число является произведением двух чисел (первый алгоритм). Если количество нулей во множителе больше количества единиц, то для получения произведения берут прямой код множителя, справа от которого приписывается столько нулей, сколько разрядов содержит множимое. Из полученного числа последовательно кгаитают прямой код множителя и обратный код чисел, полученных путем сдвига множимого влево на число разрядов, на единицу меньше номеров тех разрядов, котсфые содержат единицы во мноямтеле (начиная с младшего разряда). Полученный результат является произведением двух сомножителей (второй алгоритм). Устройство работает следующим образом. После приема сомножителей на шины приема.операндов 23 и 24 в любом порядке по шине запуска 25 поступает импульс запуска устройства, который устанавливает в единичное состояние триггер 7, тем самым разрааая прохождение через элемент И 4 и яlyльcoв .а 3 йа счетчик 5 и даиифратор 6. Работа блока анализа разрядов 21 (г, 2) заключается в определении, из двух соьшожителей числа сч аименьшим количеством информационных единиц или нулей с тем, что&1 выбранное число затем использовать в качестве множителя. При этом используются преобразователи двоичного кода в уплотненшй 27 и 28, осуществляющие сдвиг единиц в сомнолителях к границе разрядной сетки, на щ}як«х выхо-. дах тгишм образом получаются коды, |содержащие единица в крайних позициях, количество КОТОЕЖЛХ равно числу единиц в исходном коде, Hai инверсных же . выходах тфеобразователей получаются коды, сод жаир1е ёдо1ницы в крайних позициях, количество которых равно числу нулей в исходном коде. ПолученЕоге коды поступают на входы элемента сравнения 29, где определяются какой из кодов меньше, т.е. какой из сомножителей будет выбран как множитель и какой алгоритм будет применен. С выхода элемента ИЛИ 31 снимается сигнал -преобладания количества единиц над количеством нулей в множителе. С прямого выхода 35 элемента }1ПИ 30 снимается сигнал использования первого сомножителя как м ожитея, с ююсода 36 - второго Ьомножитея как множителя. прихода импульса запуска (шина 25), задержанного на элементе адержки 20, в коммутатор сомножителей 22 и в зависимости от сочетания Ьыходных импульсов элемента ИЛИ 30 коммутатор сомножителей 22 производи распределение и считывание исходных, чисел, равное записанным в регистры 26 и 37, в регистры множимого 1 и множителя 16 соответственно или инфо мация регистров 26 и 37 считывается в регистр множителя 16 и множимого 1 соответственно. , После анализа множителя в блоке анализа разрядов 21 выделяется управ лякяция импульс, который подается на единичный вход триггера В, размещающий прохождение импульса запуска, за держанного на элементе задержки 20, либо через элемент И 9 (если число единиц во множителе больше, чем нулей) либо через элемент И 10 в противном случае). В первом случае импульс запуска с выхода элемента И 9 поступает на блок управления считыванием 14, считывая значения прямого кода множимог с регистра множимого 1 в п старших разрядов сумматора 17. Одновременно прямой код множимого,инвертируясь для вычитания, считывается в п млацщтх разрядов сумматора 17. При этом одновременно на все единичные вхбды п старший разрядов сумматора 17 с задержкой, равной вре мени установления переходных процессов в разрядах, проходит импуль который считывал значение множимого Тем самым проводится вычитание из значений прямого кода множимого,сдви нутого влево на п разрядов, значений несдвинутого прямого кода множимого. Одновременно импульс запуска устанавливает в нуль триггер 8. Во втором случае импульс запуска с выхода элемента И 10 поступает на блок управления считыванием 15,считывая значения прямого кода йножителя с регистра множителя 16 в п старши разрядов сумматора 17 и значение обратного кода множителя в п младших разрядов сумматора 17. С приходом импульса на единичные входы старших разрядов сумматора 17 выполняется операция вычитания из значения прямо го кода множителя, сдвинутого на п разрядов влево,значений несдвинутог прямого кода множителя, а также подтверждается установка триггера 8 в нулевое состояние. Одновременно импульс запуска устанавливает в единичное состояние управляющий триггер 11 и случае, когда число единиц во множителе больше числа нулей, или в нулевое состояние в обратном случае, разрешая тем самым прохождение импульсов с дешифратора 6 через элементы 13 ил 12 соответственно на блоки формирова ния импульсов считывания 18 или 19. Особенность работы счетчика 5 и дешифратора 6 заключается в том, что импульсы с выхода дешифратора следуют с периодом, равным времени сложения (вычитания) одного двоичного числа в сумматоре 17. Это определяется соот-. вегстБующей коммутацией выходных шин дешифратора 6 (т.е. выходные шины могут коммутироваться в сборке через одну, две, три и т.д. в зависимости от времени сложения-вычитания числа в сумматоре 17). .Первый иьтульс, проходящий через элемент И 13 при большем числе единиц во множителе или через элемент И 12 (в обратном случае) поступает соответственно на вход либо лока формирования импульсов считывания 18, либо блока 19, которые управляются регистром множителя 16. В первом случае данный импульс, последовательно проходя через элементы И сквозного переноса блока 18, управляемые с единичным выходов разрядов регистра 16, отыскивает первый, находящийся в нулевом состоянии разряд блока 18, устанавливает его в единичное состояние и поступает с выхода блока 18, соответствующего перебрасываемому разряду на вход блока сдвига 2. С помощью блока 2 импульс считывает в сумматор 17 значения прямого кода множимого, сдвинутого влево На число разрядов, на единицу меньше номеров тех разрядов, которые содержат нули во множителе. Сдвиг осуществляется за счет соответствующей коммутации потенциальных выходов разрядов регистра множимого 1 с иг/тульсныют выходными шинами блока 18, в соответствии с изложенным принципом получения произведения по первому алгоритму. Во втором случае импульс, последовательно проходя через элементы И сквозного переноса блока 19, управляемые с нулевых выходов разрядов регистра 16, отыскивает первый находящийся в единичном состоянии разряд блока 19, перебрасывает его в нулевое состояние и поступает с выходной шины блока 19, соответствующей перебрасываемому разряду, на вход блока сдвига 2. С помощью этого блока импульс считывает в сумматор 17 значения обратного кода множимого сдвинутого влево на число разрядов, на единицу меньше номеров тех разрядов,которые содержат единицы во множителе. . Сдвиг осуществляется за счет соответствуквдай коммутации потенциальных илходов разрядов регистра множимого с импульсными выходными шинами блока 19, в соответствии с. изложенным принципом получения произведения по второму алгоритму. Следующий импульс с дешифратора 6, поступая на вход блока 18 или 19, проводит аналогичные действия. Блоки 18 и 19 работают до тех пор, пока не будут установлены в единичное состояние все разряды блока 18 в первом случае, либо в нулевом состоянии все разряды блока 19 во втором случае.При этом очередной импульс с выхода дешифратора б, пройдя сквозным переносом через элементы И блоков 18 или 19, поступает на триггер 7 для установки его в нулевое состояние, тем самым прекращая работу устройства. Произведение двух сомножителей формируется на сумматоре 17. Предлагаемое устройство для умножения двоичных чисел позволяет повысить быстродействие устройств данного класса за счет выбора из двух сомножителей в качестве множителя числа с минимальным количеством единиц или нулей. Формула изобретения 1, Устройство для умножения двоичных чисел, содержащее регистр множи:теля, регистр множимого, параллельный сумматор, блок анализаразрядов,(Злок сдвига, два блока управления, генератор тактовых импульсов, два блока формирования импульсов считывания, 1элемент задержки, пять элементов И, счетчик, дешифратор, три триггера, причем выход генератора тактовых импульсов соединен с первым входом первого элемента И, второй вход которого соединен с единичным выходом первого триггера, а выход соединен с входом счетчика и управляющим входом дешифратора, информационные входы которого соединены с различными выходами счетчика, а выход дешифратора подключен к первым входам второго и третьего элементов И, вторые входы которых под ключены соответственно к нулевому и единичному выходам второго триггера,, а выходы соединены соответственно с управляющими входами первого и второго блоков Формирования импульсов считывания, информационные входы которых соединены с соответствующими выходами регистра множителя, а выходы соединены с входами блока сдвига и с нулевым входом первого триггера, единичный вход которого соединен сшйной запуска устройства и с входом элемента задерж ки, выход которого подключен к первым входам четвертого и пятого элементов Ц вторые входы которых соединены соответственно с нулевым и единичным выходами третьего триггера, а выходы подключены к нулевому входу третьего три гера и соответственно я единичному и нулевому входам второго триггера, к управляющим входам первого и второ:го блоков управления соответственног информационные входы которых соединены соответственно с выходами регистров множимого и множителя, а выходы соединены с соответствукнцими входами параллельного сумматора, соединенными с соответствующими выходами блока сдвига, входы которого соединены с соответствующими выходами регистра множимого, первый управляющий выход блока анализа разрядов подключен к единичному входу третьего триггера, выходы параллельного сумматора являются выходами устройства, отличающееся тем, что, с целью покушения быстродействия, устройство содержит коммутатор сомножителей, причем первая группа его выходов подключена к соответствующим разрядным входам регистра множителя, вторая группа выходов подключена к соответствукхдим разрядным входам регистра множимого, первая группа информационных выходов блока анализа разрядов подключена соответственно к первым информгихионным входам первой и второй групп коммутатора сомножителей, вторая группа информационных выходов блока анализа разрядов сое:динена со вторыми информационталми вхо|дами первой и второй rpynlrt коммутатора сомножителей соответственно, управляющий выход блока анализа разрядов подключен к первому и второму управляющим входам первой и второй группы коммутатора сомножителей соответственно, третий управляющий выход блока анализа разрядов пбдключен к второму и первому управлякяцим входам первой и второй группы коммутатора сомножителей соответственно, выход элемента задержки подключен к BKOfiy разрешения коммутатора сомножителей, первые и вторые )нформационные входы блока анализа разрядов соединены соответственно с рходами первого и второго операндов устройства. 2, Устройство по п.1, отличающееся тем, что, блок анализа разрядов содержит два регистра, два преобразователя двоичного кода в уплотненный, элемент сравнения, два элемента ИЛИ, причем первые и вторае информационные входы блока соединею соответственно с входами пфвого и второго регистров, выходы которых подключены соответственно к входам первого и второго преобразователей двоичного кода в уплотненffiift и к первой и второй группе выходов блока, прягое шлсоды первого и второго преобразователей двоичного кода в уплотненный подключены соответственно к входам первого и второго чисел элемента сравнения, инверсные выходы первого и iBTOporo преобразователей двоичного

кода в уплотненный подключены соответственно к входамтретьего и четвертого чисел элемента сравнения, 11ервый вход первого элемента ИЛИ под ключен к первому выходу элемента орав нения, второй его вход подключен к « ;третьему алходу элемента сравнения,пря |мой выход первого элемента ИЛИ соединён бо вторым управлятшм выходом блокд, а инверсный выход первого элемента ИЛИ соединен с третьим управляющим выходом блока, первый вход ВТ.ОРОГО элемента ИЛИ соединен с третьим выходом элемента сравнения, второй

вход соединен с четвертые выходом элемента сравнения, а выход подключен к первому управляютему выходу блока.

Источники информации, принятые во внш4ание при экспертизе .

1.Авторское свидетельство -СССР 273520,101. G 06 F 7/52, 1971.

2.Авторское свидетельство СССР 478305, кл.С 06 F 7/52, 1973.

3.Авторское свидетельство СССР

I 482741,, кл.С 06 F 7/52, 1973 (прототип)

:

37

23

27

28

:

26

,я

36

. «

: J