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

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

Иллюстрации

Показать все

Реферат

 

ОП ИСАНИЕ

ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

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

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

Реслублии

4683 (61) Дополнительное к авт. свид-ву— (22) Заявлено 05.01.78 (21) 2566836/18 — 24 с присоединением заявки №вЂ” (23) Приоритет—

Опубликовано 15.05.80. Бюллетень № 18

Дата опубликования описания 17.05.80 л 2

F 7/39

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

СССР

К 681.325

8) ве делам изобретений и открытий

Г. В. Дивин. Ю. Н. Иртегов, Л. А. Канова, Е. В. Орехова и А. В. Солодилов (72) Авторы изобретения (71) Заявитель (54) УСТРОЙСТВО ДЛЯ УМНОЖЕНИЯП-РАЗРЯДНЫХ ЧИСЕЛ

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

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

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

Наиболее близким по технической сущности к предлагаемому является устройство, со- Ю держащее сумматор, регистры множимого, множителя, переносов, содержащее и частичных произведений, а также логическую схему преобразования (3).

Это устройство обеспечивает выполнение умножения одновременно на два разряда множителя с запоминанием переносов.

Умножение на всю разрядную сетку множителя происходит за и/2 тактов, где ив число разрядов множителя, при этом последний такт суммирования производится со всеми сквозными переносами.

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

Цель изобретения — повышение быстродействия устройства умножЕния.

Цель достигается тем, что в устройство содержащее (п + 2) -разрядные регистры множимого, множителя и переносов, блока анализа множителя, триггер инверсной передачи множимого, (и + 4) -разрядный регистр частичных произведений, сумматор, состоящий из (и+ 2)-х основных и двух дополнительных разрядов, причем выходы регистра множимого подключены к первым входам основных разрядов сумматора, выходы сум734683

1О

15 гв мы которых подключены к входам регистра частотных произведений, выходы переносов

j-тых основных разрядов сумматора соединены с („ + 1) -ыми входами регистра переносов (j =1 —:-(и — 1), (и+ 1)), выход переноса первого дополнительного разряда сумматора соединен с первым входом второго дополнительного разряда сумматора, выход переноса второго дополнительного разряда сумматора соединен с входом первого разряда регистра переносов, выход которого соединен со вторым входом первого дополнительного разряда сумматора, а выходы суммы первого и второго дополнительных разрядов сумматора соединены со старшими разрядами регистра множителя, дополнительно содержит пять элементов ИЛИ, триггер преобразования кода, триггер такта, два блока коммутации, два элемента И, элемент И вЂ” НЕ, дополнительный разряд в регистре переносов, третий и четвертый дополнительные разряды в сумматоре и два дополнительных разряда в регистре частичных произведений, при этом выходы суммы третьего и четвертого дополнительных раздов сумматора соединены с входами двух дополнительных разрядов регистра частичных произведений, выход переноса третьего дополнительного разряда сумматора соединен с входом четвертого дополнительного разряда сумматора, выход перноса которого объединен с входом дополнительного разряда регистра переносов, вход (п 4 1)-го разряда регистра переносов соединен с выходом первого элемента И, вход которого соединен с выходом переноса п-го разряда сумматора, выходы первого (и+2)-го разрядов первого блока коммутации соединены с третьими входами разрядов сумматора, начиная с первого дополнительного разряда, а выходы (и + 3) -го и (и+ 4) -ro разрядов первого блока коммутации соединены с входами первого и второго элементов

ИЛИ, выходы которых соединены с входами (п+ 1) -го и и-го разрядов сумматора, вторые входы ) основных (j =1 —.п) и третьего и четвертого дополнительных разрядов сумматора соединены с выходами второго блока коммутации, первая группа информационных входов которого .соединена с соответствующей группой входов первого блока коммутации и подключена к выходам регистра м ножи мого, а вторая группа (и+2) -х информационных входов второго блока коммутации соединена с х-ми выходами (к=2:n+2) основных и выходом дополнительного разрядов регистра переносов, вторая группа информационных входов первого блока коммутации соединена с выходами регистра частичных произведений, первый вход первого дополнительного разряда сумматора соединен с входами первых четырех элементов ИЛИ и первым входом элемента И вЂ” НЕ и подключен к выходу блока анализа множителя, первые управляю2S

Ф

ЗЗ

56

Ы щие входы блоков коммутации соединены с входом блока анализа и с первым выходом триггера такта, второй выход которого подключен ко вторым управляющим входам блока коммутации, входам второго элемента И и блока анализа, второй выход которого соединен с входами третьего, четвертого и пятого элементов ИЛИ и со вторым входом элемента И вЂ” НЕ, соединенного своим выходом с входом первого элемента И, третий выход блока анализа соединен с входами третьего элемента ИЛИ и триггера преобразования кода, выход которого соединен с входом пятого элемента ИЛИ, выход третьего элемента ИЛИ соединен с входом триггера инверсной передачи множимого, выход которого соединен с входом второго элемента И, соединенного своим выходом с входами двух старших разрядов сумматора, выходы четвертого и пятого элементов ИЛИ соединены соответственно со входами двух старших и входом третьего дополнительного разрядов сумматора.

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

Устройство содержит (n+ б) -разрядный сумматор 1, (и+4) -разрядный регистр 2 частичных произведений, (и -3) -разрядный регистр 3 переносов, (п+2) - разрядные регистры 4 и 5 множимого и множителя; два блока 6 и 7 коммутации, блок 8 анализа, элемент И 9, элементы ИЛИ 10, 11, 12, 13 и 14, элемент И 15, элемент И-HE 16, триггер 17 инверсной передачи множимого, триггер 18 преобразования кода и триггер

19 такта.

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

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

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

734683 анализа соответственно третьей, второй и первой пар разрядов множителя, осуществляемого в блоке 8 анализа. При комбинациях любой из трех анализируемых пар разрядов множителя вида 00, 01, 10 множимое передается на сумматор 1 следующим образом:

00 не передается, 01 — в прямом коде, 10 — со сдвигом на один разряд влево.

При комбинации же вида 11 множимое передается в сумматор 1 в обратном коде, с дальнейшим преобразованием в дополнительный код. Причем, если первая пара разрядов множителя 11, то для преобразования множнмого, записанного в сумматор по третьему входу, в первы и дополнительный разряд сумматора из блока 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. В случае же, если эти две комбинации указанных пар разрядов 11, то элемент И вЂ” HE 16 закрывает схему управления переносом 9, обеспечивая тем самым

Ь запись в(п+ 1)-ый разряд регистра переносов

3 нуля кода.

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

На втором такте триггер 19 определения такта устанавливается в единичное состояние и сигнал с прямого выхода этого триггера переводит устройство умйожения в режим работы с анализом одной пары разрядов множителя и запоминанием переносов.

Частичное произведение, полученное в первом такте и записанное в регистр 2 поступает через блок 6 коммутации, открытый по первому управляющему входу сигналом с прямого выхода триггера 19, на третьи входы (п — 2)-х основных и четырех дополнительных разрядов сумматора 1. При этом в (ll — 1) -й и fl-й основные разряды сумматог ра произведение передается через входы элементов ИЛИ 10 и 11, на другие входы которых поступает нулевой сигнал с перво1s го тор 1.

При комбинации 11, ачализируемой во втором такте пары разрядов множителя, преобразование обратного кода множимого в го выхода блока 8 анализа (при работе на втором и последующHx тактах HH первых двух выходах блока анализа 8 — нулевой потенциал). Записанные в регистр 3 переносы в свою очередь поступают на вторые входы и основных, а также третьего и четвертого дополнительных разрядов сумматора 1, через блок 7 коммутации, открытый по второму управляющему входу сигналом с прямого выхода триггера 19.такта. Перенос из первого разряда регистра 3 поступает непосредственно на второй вход первого дополнительного разряда сумматора 1.

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

3s разрядов множителя, анализ которой производился в первом такте, 11. При этом из блока 8 анализа (третий выход) единица подается через триггер 18 преобразования кода, обнуляемый в каждом такте работы устройства умножения, и элемент ИЛИ 14, в третий дополнительный разряд, сумматора

1 по первому входу, обеспечивая преобразование обратного кода в дополнительный. Единица записывается также в два старших разряда сумматора 1 по третьим входам, что обеспечивается триггером 17 инверсной передачи множимого, в который единица записывается через элемент ИЛИ 12, если хотя бы одна из анализируемых в первом такте пар разрядов множителя — 11. При этом триггер 17 запоминает и обеспечивало ет передачу единичного сигнала через элемент И 15 в два старших разряда сумматора 1 во всех последующих тактах независимо от вида передачи множимого на сумма734683

14 подается единица, преобразующая обратный код в дополнительный. Кроме того, с того же выхода блока 8 анализа единица записывается через схему ИЛИ 12 в триггер 17 инверсной передачи множимого, обеспечивая тем самым передачу единицы на третьи входы двух старших разрядов 1© сумматора 1, через элемент И 15, при этом триггер 17 аналогично предыдущему такту запоминает и обеспечивает запись единиц в эти два старших разряда сумматора 1 также во всех последующих тактах.

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

Получающиеся в каждом такте умноже- 2о ния два разряда произведения записываются в старшие освободившиеся разряды регистра 5 множителя.

В результате предлагаемое устройство для умножения обеспечивает перемножение двух п-разрядных чисел за (— - — 2) тв. И тактов, при этом на последнем такте сумматор работает со всеми сквозными переносами.

Формула изобретения дополнительный код производится в последующем (третьем) такте. При этом в третий дополнительный разряд сумматора 1 из блока 8 анализа (третий выход) через триггер 18 преобразования кода, элемент ИЛИ

Таким образом, введение новых элементов позволяет повысить быстродействие уст,ройства при более полном использовании оборудования (сумматора) . Это преимущество особенно проявляется при проектировании специализированных ЦВМ, где арифметические операции осуществляются над кодами с небольшим числом разрядов.

Устройство для умножения и-разрядных чисел, содержащее (п+2)-разрыдные регистры множимого, множителя и переносов, блок анализа множителя, триггер инверсной передачи множимого, (п+4) -разрядный регистр частичных произведений, сумматор, состоящий из (п+2)-х основных и двух дополнительных разрядов, причем выходы регистра множимого подвключены к первым входам основных разрядов сумматора, выходы суммы которых подключены к входам регистра частотных произведений, выходы переносов j-тых основных разрядов сумматора соединены (j+1)-ыми входами регистра переносов (1=1 —:(п — 1), (и+1), выход переноса первого дополнительного разряда сумматора соединен с первым входом второго дополнительного разряда, сумматора, выход переноса второго дополнительного разряда сумматора соединен с входом первого разряда регистра переносов, выход которого

46

56

$!| соединен со вторым входом первого дополнительного разряда сумматора, а выходы суммы первого и второго дополнительных разрядов сумматора соединены со старшими разрядами регистра множителя, отличаюшееся тем, что, с целью повышения быстродействия, в него дополнительно введены пять элементов ИЛИ, триггер преобразования кода, триггер такта, два блока коммутации, два элемента И, элемент И-НЕ, дополнительный разряд в регистр переносов, третий и четвертый дополнительные разряды в сумматор и два дополнительных разряда в регистр частичных произведений, при этом выходы суммы третьего и четвертого дополнительных разрядов сумматора соединены с входами двух дополнительных разрядов регистра частичных произведений, выход переноса третьего дополнительного разряда сумматора соединен с входом четвертого, дополнительного разряда сумматора, выход переноса которого объединен с входом дополнительного разряда регистра переносов, вход (п + 1)-го разряда регистра переносов соединен с выходом первого элемента И, вход которого соединен с выходом переноса п-го разряда сумматора, выходы первого †:(п+2)-го разрядов первого блока коммутации соединены с третьими входами разрядов сумматора, начиная с первого дополнительного разряда, а выходы (и+3)-го и (п+4)-го разрядов первого блока коммутации "îåäèíåíû с входами первого и второго элементов ИЛИ, выходы которых соединены с входами (п+1)-го и п-го суммтора, вторые входы j основных (j = 1+и) и третьего и четвертого дополнительных разрядов сумматора соединены с выходами второго блока коммутации, первая группа информационных входов которого соединена с сортветствующей группой входов первого блока коммутации и подключена к выходам регистра множимого, а вторая группа (n -+-2) -х информационных входов второго блока коммутации соединена с к-ми входами (к=2+и+

-+2) основных и выходом дополнительного разрядов регистра переносов, вторая группа информационных входов первого блока коммутации соединена с выходами регистра частичных произведений, первый вход первого дополнительного разряда сумматора соединен с входами первых четырех элементов

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

И†HE, соединенного своим выходом с вхо дом первого элемента И, третий выход бло734683

Составитель Г. Плешев

Редактор 3. Шубенко Техред К.Шуфрич Корректор Н. Стец

Заказ 2221/11 Тираж 75! Подписное

ЦНИИПИ Государственного комитета СССР по делам изобретений и открытий! 13035, Москва, Ж вЂ” 35, Раушская наб., д. 4/5

Филиал ППП «Патент> г, Ужгород, ул. Проектная, 4 ка анализа соединен с входами третьего элемента ИЛИ и триггера преобразования кода, выход которого соединен с входом пятого элемента ИЛИ, выход третьего элемента ИЛИ соединен с входом триггера инверсной передачи множимого, выход которого соединен с входом второго элемента И, соединенного своим выходом с входами двух старших разрядов сумматора, выходы четвертого и пятого элементов ИЛИ соединены соответственно со входами двух старших и входом третьего дополнительного разрядов сумматора.

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

1. Дроздов Е. А. Многопрограммные

ЦВМ, M., Военное изд-во, 1974.

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

3. Авторское свидетельство СССР № 357561, кл. G 06 F 7/39, 1970 (прототип) . î