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

Изобретение отнасится к вычислительной технике и предназначено для умножения двоичных чисел, представленных параллельным кодом, и может быть использовано при построении арифметических устройств специализированных и универсальных ЦВМ. Известны устройства для умножения двоичных чисел, в которых ускорение процесса умножения достигается за счет выполнения операции умножения с запоминанием переносов при одновременной расшифровке одной или нескольких пар разрядов множителя 1 и 2. Недостачами устройств умножения с расшифровкой одной пары разрядов множителя являются неполная загрузка (что не позволяет добиться оптимального быстродействия), значительные затраты оборудования и необходимость использования сложных узлов вычислительной техники. Наиболее близким по технической сушности к предлагаемому является устройство, содержащее сумматор, регистры множимого, множителя, переносов, содержашее п частичных произведений, а также логическую схему преобразования 3. Это устройство обеспечивает выполнение умножения одновременно на два разряда множителя с запоминанием переносов. Умножение на всю разрядную сетку множителя происходит за п/2 тактов, где п - число разрядов множителя, при этом последний такт суммирования производится со всеми сквозными переносами. Недостатком известного устройства является то, что в первом и втором тактах не обеспечивается максимальная загрузка сумматора, и он работает соответственно либо на передачу множимого, либо на суммирование только двух чисел, что ограничивает быстродействие данного устройства. Цель изобретения - повышение быстродействия устройства умножения. Цель достигается тем, что в устройство содержаш.ее (п 4-2)-разрядные регистры множимого, множителя и переносов, блока анализа множителя, триггер инверсной передачи МНОЖИМОГО, (п 4-4)-разрядный регистр частичных произведений, сумматор, состоящий из (п + 2)-х основных и двух дополнительных разрядов,причем выходы регистра МНОЖИМОГО подключены к первым входам основных разрядов сумматора, выходы суммы которых подключены к входам регистра частотных произведений, выходы переносов j-тых основных разрядов сумматора соединены с (j + 1)-ыми входами регистра переносов (J ), (П4-1)), выход переноса первого дополнительного разряда сумматора соединен с первым входом второго дополнительного разряда сумматора, выход переноса второго дополнительного разряда сумматора соединен с входом первого разряда регистра переносов, выход которого соединен со вторым входом первого дополнительного разряда сумматора, а выходы суммы первого и второго дополнительных разрядов сумматора соединены со старшими разрядами регистра множителя, дополнительно содержит пять элементов ИЛИ, триггер преобразования кода, триггер такта, два блока коммутации, два элемента И, элемент И-НЕ, дополнительный разряд в регистре переносов, третий и четвертый дополнительные разряды в сумматоре и два дополнительных разряда в регистре частичных произведений, при этом выходы суммы третьего и четвертого дополнительных раздов сумматора соединены с входами двух дополнительных разрядов регистра частичных произведений, выход переноса третьего дополнительного разряда сумматора соединен с входом четвертого дополнительного разряда сумматора, выход перноса которого объединен с входом дополнительного разряда регистра переносов, вход (п 4-1)-го разряда регистра переносов соединен с выходом первого элемента И, вход которого соединен с выходом переноса п-го разряда сумматора, выходы первого (п + 2).-го разрядов первого блока коммутации соединены с третьими входами разрядов сумматора, начиная с первого дополнительного разряда, а выходы (п + 3)-го и (п44)-го разрядов первого блока коммутации соединены с входами первого и второго элементов ИЛИ, выходы которых соединены с входами (п+1)-го и п-го разрядов сумматора, вторые входы j основных (j ) и третьего и четвертого дополнительных разрядов сумматора соединены с выходами второго блока коммутации, первая группа информационных входов которого.соединена с соответствующей группой входов первого блока коммутации и подключена к выходам регистра множимого, а вторая группа (п + 2)-х информационных входов второго блока коммутации соединена с Я-ми выходами (к + 2) основных и выходом дополнительного разрядов регистра переносов, вторая группа информационных входов первого блока коммутации соединена с выходами регистра частичных произведений, первый вход первого дополнительного разряда сумматора соединен с входами первых четырех элементов ИЛИ и первым входом элемента И-НЕ и подключен к выходу блока анализа множителя, первые управляющие входы блоков коммутации соединены с входом блока анализа и с первым выходом триггера такта, второй выход которого подключен ко вторым управляющим входам блока коммутации, входам второго элемента И и блока анализа, второй выход которого соединен с входами третьего, четвертого и пятого элементов ИЛИ и со вторым входом элемента И-НЕ, соединенного своим выходом с входом первого элемента И, третий выход блока анализа соединен с входами

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

5 которого соединен с входом второго элемента И, соединенного своим выходом с входами двух старших разрядов сумматора, выходы четвертого и пятого элементов ИЛИ соединены соответственно со входами двух старших и входом третьего дополнительного

0 разрядов сумматора.

На чертеже представлена схема устройства.

Устройство содержит (п +6)-разрядный

J сумматор 1, (n-f 4)-разрядный регистр 2 частичных произведений, (п + 3)-разрядный регистр 3 переносов, (п + 2)- разрядные регистры 4 и 5 множимого и множи1«ля; два блока 6 и 7 коммутации, блок 8 анализа, элемент И 9, элементы ИЛИ 10, 1,

0 12, 13 и 14, элемент И 15, элемент И-НЕ 16, триггер 17 инверсной передачи множимого, триггер 18 преобразования кода и триггер

19 такта.

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

В исходном состоянии в регистрах 4 и 5 множимого и множителя хранятся сомножители, триггеры 17, 18 и 19, регистры 2 и 3 обнулены. При этом инверсный выход триггера 19 такта разрешает блоку 8 анализа,

0 а также блокам 6 и 7 коммутации, работу в первом такте. В результате в этом такте три пары младших разрядов с регистра 5 множителя одновременно поступают в блок 8 анализа (на чертеже соответствующая связь не показана), который обеспечивает

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

0 вход сумматора через схему логического преобразования множимого (на чертеже не показана), начиная с первого основного разряда; на второй вход - через первый сигнальный вход блока 7 коммутации, начиная с третьего дополнительного разряда;

S на третий вход сумматора 1 через первый сигнальный вход блока 6, начиная с первого дополнительного разряда. При этом вид передачи множимого зависит от результата

анализа соответственно третьей, второй и первой пар разрядов множителя, осуществляемого в блоке 8 анализа. При комбинациях любой из трех анализируемых пар разрядов множителя вида 00, 01, 10 множимое передается на сумматор 1 следующим образом; 00 не передается, 01 - в прямом коде, 10 - со сдвигом на один разряд влево. При комбинации же вида 11 множимое передается в сумматор 1 в обратном коде, с дальнейшим преобразованием в дополнительный код. Причем, если первая пара разрядов множителя 11, то для преобразования множимого, записанного в сумматор 1 по третьему входу, в первый дополнительный разряд сумматора из блока 8 анализа (первый выход) подается сигнал, преобразующий обратный код в дополнительный. Данный сигнал подается также через первые входы элементов ИЛИ 10 и 11 на третьи входы соответственно (п-1)-го и п-го разрядов сумматора 1 и через вход элемента ИЛИ 13 на вторые входы (п + 1)-го и (п + 2)-го разрядов сумматора 1. Если вторая пара разрядов множителя 11, то для преобразования множимого, поступающего на вход сумматора 1, в его третий дополнительный разряд по первому входу из блока 8 анализа (второй выход) через вход элемента ИЛИ 14 подается сигнал, преобразующий обратный код в дополнительный. С того же выхода блока 8 анализа сигнал подается через элемент ИЛИ 13 на вторые входы двух старших разрядов сумматора 1. В случае, если третья пара разрядов множителя, анализируемых в этом первом такте 11, то преобразование множимого в дополнительный ход производится в следующем (втором) такте умножения.

Получающаяся в первом также умножения сумма по mod 2 с выхода сумматора 1 записывается в регистр 2 частичных произведений, а поразрядные переносы с выходом переносов того же сумматора 1 - в регистр 3 переносов. Поразрядные переносы, которые образуются на выходе первого и третьего дополнительных разрядов сумматора 1, поступают соответственно на первые входы второго и четвертого дополнительных разрядов сумматора 1, т.е. названные разряды сумматора охвачены попарно сквозным переносом. Перенос же с выхода п-го разряда сумматора 1 записывается в (п + 1)-ый разряд регистра 3 переносов через элемент И 9, открываемый нулевым сигналом с выхода элемента И-НЕ 16 при наличии на его входах хотя бы одного нулевого потенциала с выхода блока 8 анализа, т.е. при отсутствии в двух младщих анализируемых парах хотя бы одной комбинации 11. В случае же, если эти две комбинации указанных пар разрядов И, то элемент И-НЕ 16 закрывает схему управления переносом 9, обеспечивая тем самым

запись в(п+1)-ый разряд регистра переносов 3 нуля кода.

Таким образом в первом такте получается частичное произведение от умножения множимого на 6 младщих разрядов множителя.

На втором такте триггер 19 определениятакта устанавливается в единичное состояние и сигнал с прямого выхода этого триггера переводит устройство умножения в режим работы с анализом одной пары разря0 дов множителя и запоминанием переносов. Частичное произведение, полученное в первом такте и записанное в регистр 2 поступает через блок 6 коммутации, открытый по первому управляющему входу сигналом с прямого выхода триггера 19, на третьи вхо ды (п-2)-х основных и четырех дополнительных разрядов сумматора I. При этом в (п-1)-й.и п-й основные разряды сумматора произведение передается через входы элементов ИЛИ 10 и 11, на другие входы Q которых поступает нулевой сигнал с первого выхода блока 8 анализа (при работе на втором и последующих тактах на первых двух выходах блока анализа 8 - нулевой потенциал). Записанные в регистр 3 переносы в свою очередь поступают на вторые входы п основных, а также третьего и четвертого дополнительных разрядов сумматора 1, через блок 7 коммутации, открытый по второму управляющему входу сигналом с прямого выхода триггера 19 такта. Переg нос из первого разряда регистра 3 поступает непосредственно на второй вход первого дополнительного разряда сумматора 1. На этом же такте осуществляется преобразование множимого в дополнительный код в случае, когда комбинация третьей пары 5 разрядов множителя, анализ которой производился в первом такте, 11. При этом из блока 8 анализа (третий выход) единица подается через триггер 18 преобразования кода, обнуляемый в каждом такте работы устройства умножения, и элемент ИЛИ 14, в третий дополнительный разряд, сумматора 1 по первому входу,обеспечивая преобразование обратного кода в дополнительный. Единица записывается также в два старщих разряда сумматора i по третьим входам, что обеспечивается триггером 17 инверсной передачи множимого, в который единица записывается через элемент ИЛИ 12, если хотя .бы одна из анализируемых в первом такте пар разрядов множителя - 11. При этом триггер 17 запоминает и обеспечивает передачу единичного сигнала через элемент И 15 в два старщих разряда сумматора 1 во всех последующих тактах независимо от вида передачи множимого на сумматор 1.

55

При комбинации 11, анализируемой во втором такте пары разрядов множителя, преобразование обратного кода множимого в дополнительный код производится в последующем (третьем) такте. При этом в третий дополнительный разряд сумматора 1 из блока 8 анализа (третий выход) через триггер 18 преобразования кода, элемент ИЛИ 14 подается единица, преобразующая обратный код в дополнительный. Кроме того, с того же выхода блока 8 анализа единица записывается через схему ИЛИ 12 в триггер 17 инверсной передачи множимого, обеспечивая тем самым передачу единицы на третьи входы двух старших разрядов сумматора 1, через элемент И 15, при этом триггер 17 аналогично предыдущему такту запоминает и обеспечивает запись единиц в эти два старших разряда сумматора 1 также во всех последующих тактах. В третьем, четвертом и последующих тактах устройство 7 умножения работает так же, как и во втором такте до тех пор, пока не закончится умножение множимого на всю разрядную сетку множителя. Получающиеся в каждом такте умножения два разряда произведения записываются в старшие освободившиеся разряды регистра 5 множителя. В результате предлагаемое устройство для умножения обеспечивает перемножение двух п-разрядных чисел за (- - 2) тактов, при этом на последнем такте сумматор работает со всеми сквозными переносами. Таким образом, введение новых элементов позволяет повысить быстродействие уст,ройства при более полном использовании оборудования (сумматора). Это преимущество особенно проявляется при проектировании специализированных ЦВМ, где арифметические операции осуществляются над кодами с небольщим числом разрядов. Формула изобретения Устройство для умножения п-разрядных чисел, содержащее (n-f 2)-разрыдные регистры множимого, множителя и переносов, блок анализа множителя, триггер инверсной передачи множимого, (п +4)-разрядный регистр частичных произведений, сумматор, состоящий из (п-ь2)-х основных и двух дополнительных разрядов, причем выходы регистра множимого подвключены к первым входам основных разрядов сумматора, выходы суммы которых подключены к входам регистра частотных произведений, выходы переносов j-тых основных разрядов сумматора соединены (j-t-l)-biMH входами регистра переносов (j l-H(n-I), (п-ь1), выход переноса первого дополнительного разряда сумматора соединен с первым входом второго дополнительного разряда .сум.матора, выход переноса второго дополнительного разряда сумматора соединен с входом первого разряда регистра переносов, выход которого соединен со вторым входом первого дополнительного разряда сумматора, а выходы суммы первого и второго дополнительных разрядов сумматора соединены со старшими разрядами регистра множителя, отличающееся тем, что, с целью повышения быстродействия, в него дополнительно введены пять элементов ИЛИ, триггер преобразования кода, триггер такта, два блока коммутации, два элемента И, элемент И-НЕ, дополнительный разряд в регистр переносов, третий и четвертый дополнительные разряды в сумматор и два дополннтельных разряда в регистр частичных произведений, при этом выходы суммы третьего и четвертого дополнительных разрядов сумматора соединены с входами двух дополнительных разрядов регистра частичных произведений, выход переноса третьего дополнительного разряда сумматора соединен с входом четвертого, дополнительного разряда сумматора, выход переноса которого объединен с входом дополнительного разряда регистра переносов, вход (п + 1)-го разряда регистра переносов соединен с выходом первого элемента И, вход которого соединен с выходом переноса п-го разряда сумматора, выходы первого -Цп + 2)-го разрядов первого блока коммутации соединены с третьими входами разрядов сумматора, начиная с первого дополнительного разряда, а выходы (п + 3)-го н (п + 4)-го разрядов первого блока коммутации соединены с входами первого и второго элементов ИЛИ, выходы которых соединены с входами (п + 1)-го и п-го суммтора, вторые входы j основных (i ) и третьего и четвертого дополнительных разрядов сумматора соединены с выходами второго блока коммутации, первая группа информационных входов которого соединена с соответствующей группой входов первого блока коммутации и подключена к выходам регистра множимого, а вторая группа (п + 2)-х информационных входов второго блока коммутации соединена с к.-ыц входами (к: 2ч-п-«+ 2) основных и выходом дополнительного разрядов регистра переносов, вторая группа информационных входов первого блока коммутации соединена с выходами регистра частичных произведений, первый вход первого дополнительного разряда сумматора соединен с входами первых четырех элементов ИЛИ и первым входом, элемента И-НЕ и подключен к выходу блока анализа множителя, первые управляющие входы блоков коммутации соединены с входом блока анализа и с первым выходом триггера такта, второй выход которого подключен ко вторым управляющим входам блоков коммутации, входам второго элемента И и блока анализа, второй выход которого соединен с входами третьего, четвертого и пятого элементов ИЛИ и со вторым входом элемента И-НЕ, соединенного своим выходом с вхо. дом первого элемента И, третий выход блока анализа соединен с входами третьего элемента ИЛИ и триггера преобразования кода, выход которого соединен с входом пятого элемента ИЛИ, выход третьего элемента ИЛИ соединен с входом триггера инверсной передачи множимого, выход которого соединен с входом второго элемента И, соединенного своим выходом с входами двух старших разрядов сумматора, выходы четвертого и пятого элементов ИЛИ соединены соответственно со входами двух старших и

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

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

1.Дроздов Е. А. Многопрограммные ЦВМ, М., Военное изд-во, 1974.

2.Авторское свидетельство СССР № 281004, кл. G 06 F 7/39, 1969.

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

№ 357561. кл. Q 06 F 7/39, 1970 (прототип).