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

 

(54) УСТРОЙСТВО ДЛЯ УМНО%ЕНИЯ ДВОИЧНЫХ ЧИСЕЛ

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

Известны устройства умножения

:двоичных чисел, содержащие регистры множимого и множителя, связанные через схему образования частичных произведений и пирамиду сумматоров с выходами устройства (1).

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

Наиболее близким к предлагаемому является устройство умножения, содержащее регистры множимого и множителя, блок формирования кратных множимого, анализатор групп раэря" дов множителя и блок суммирования (31.

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

Цель изобретения - повышение быстродействия, Для достижения поставленной цели

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

50 вания управляющих кодов суммирования, (Q-2) блоков формирования кратных множимого с третьего по Й-й (! в число разрядов множителя ), (Ф -2 ) анализаторов кодов групп разрядов множителя с третьего по Ъ-й, входы которых соединены с выходами соответствующих групп разрядов регистра множителя, а первые выходы подключены к управля-ющим входам соответствующих блоков 1о формирования кратных множимого,входы которых подключены к выходам регист" ра множимого. а выходы - к соответствующим входам блока суммирования, в состав которого входит пирамида сумматоров, информационные входы первого ряда которых соединены со взятыми попарно входами блока суммирования, выходы взятых попарно сумматоров каждого ряда пирамиды соединены с информационными входами сумматора последующего ряда, выход сумматора последнего ряда пирамиды является выходом блока суммирования и выходом устройства, блок формирования управляющих кодов суммирования содержит пирамиду табличных преобразователей знаковых разрядов в управляющие коды сумматора, входы первого ряда которых соединены с вторыми выхозо дами взятых попарно анализаторов кодов групп разрядов множителя, первые выходы табличных преобразователей знаковых разрядов в управляющие коды сумматора соединены с управляющими входами соответствующих суммато- З5 ров соответс гву>ощего ряда пирамиды блока суммирования, вторые выходы табличных преобразователей знаковых разрядов в управляющие коды сумматора каждого ряда пирамиды, взятых попарно, соединены с входами табличных преобразователей знаковых разрядов в управляющие коды сумматора последующего ряда пирамиды.

На фиг,! представлена схема устройства для случая умножения на одиннадцатираэрядный множитель; на фиг.2 показан пример выполнения блока формирования кратных множимого; на фиг ° 3 — то же анализатора.

Устройство содержит регистр 1 множителя, регистр 2 множимого, блоки

3-6 формирования кратных множимого, сумматоры 7-9, анализаторы 10-13 групп разрядов множителя, табличные 55 преобразователи 14-16 знаковых разрядов в управляющие коды сумматоров.

Суммагоры 7-9 образуют блок 17 сумми

9 4 рбвания, преобразователи 14-16 образуют, блок 18 формирования управляющих сигналов блока суммирования, Выход регистра 2 соединен с информационными входами блоков 3-6 фоамирования кратных множимого, управляющие входы которых соединены с первыми выходами анализаторов 10-13 соответственно, а выходы блоков 3-6, взятые попарно, соединены соответственно с входами сумматоров 7 и 8 первой ступени. Выходы сумматоров 7 и

8 соединены с информационными входами сумматора 9. Управляющие входы сумматоров 7,8 и 9 соединены с первыми выходами преобразователей 14,15 и 16 соответственно, причем входы преобразователей 14 и 15 соединены соответственно с парами вторых выходов анализаторов 10, 11 и 12, 13, а входы преобразователя - с вторыми выходами преобразователей 14 и 15 соответственно, Число групп разрядов множителя и соответственно анализаторов этих !

rpynn и блоков формирования кратных множимого равно k (R+1)/3 (с округлением до ближайшего большего цело- . го), где Й - разрядность множителя.

Разряды регистра множителя группируются по три. К каждой тройке применяется следующее правило преобраэо"., вания: если старшая цифра в анализируемой тройке равна "1" иэ тройки вычитается 8, э если старшая цифра следующей справа тройки равна "1", то к анализируемой тройке прибавляет ся "1", Возможны значения преобразованного множителя О, й1, + 2, + 3, и 4, Этим значениям соответствуют следующие режимы работы блоков формирования кратных множимого, о

"0" - формирование нуля;

"1!" - формирование 1-кратного множимого; Ф2" " формирование 2-кратного множимого

"+3" - формирование 3-кратного множимого

"+4" - формирование 4-кратного множимого, Соответствующие управляющие сигналы вырабатываются на первых выходах анализаторов, выходы каждого иэ которых соединены с выходами соответствующих троек разрядов множителя и старшего разряда следующей тройки.

5 9324

Пля цифр -1", "-2" "-3" и "-4" на выходе требуемое кратное множимого получается с противоположным знаком. Знаковые разряды кратных формируются на вторых выходах анализаторов и учитываются при организации работы соответствующей ступени пирамиды сумматоров. Если на вход сумматора поступают слагаемые с обоими верными или обоими противоположными знаками, то этот сумматор работает в режиме сложения; если одно слагаемое имеет верный, а другое противоположный знак,.сумматор работает в режиме вычитания. Если в первом случае оба слагаемых имеют противоположный знак, или во втором случае большее слагаемое имеет противоположный знак, то на выходе сумматора результат также будет с 26 противоположным знаком, что учитывается в следующей ступени табличных преобразователей. знаковых разрядов в управляющие коды сумматоров.

Блок формирования кратных множимого может быть реализован на упсавляемом арифметико-логическом устройстве АЛУ, на первый вход которого подается код множимого со сдвигом на один разряд влево 30 (удвоенный), на второй вход - несдви. нутый код мнсжимого, а управляющий вход соединен с первым выходом анализатора соответствующей группы. Цифрам преобразованного множителя "0", ".Ц", "12", "13", "+4" сопоставляютl ся режимы ра6оты АЛУ: формирование ! када нуля, передача второго слагаемого, передача первого слагаемого, сложение, удвоение первого слагаемого.

Пример выполнения блока формирования кратных мнсжимого (фиг.2).

Этот блок содержит сумматор 19, группу элементов ИЛИ 20, группы элементов И 21-23, дешифратор 24, элементы ИЛИ 25 и 26, информационные входы 27 и 28, управляющий вход 29, выход 30. При работе блока дешифратор

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

30 после прямого прохождения множимо-

„И

ro или его удвоенного значения (с входов 28, 27), или после их суммирования, или после суммирования удвоенного значения множимого с самим собой.

Работа анализаторов 10-!3 описывается в табл.l, работа преобразователей 14-16 в табл. 2 ..

В последнем столбце табл.! и 2 приведены значения выходных сигналов преобразователей для случая, когда блоки 3-6 и сумматоры 7-9 реализуются на микросхемах типа А-55 ИП-3.

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

Схемы анализаторов и преобразователей могут быть реализованы либо многовыходными переключательными схемами, построенными в соответствии с табл.l и 2, либо в виде каскадного соединения дешифратора и шифратора, либо в виде постоянного ЗУ небольшой емкости. Реализация с помощью ПЗУ при современной технической базе наиболее экономична. Так каждый преобразователь первой ступени может быть выполнен на одной микросхеме ПЗУ средней степени интеграции, например, ИИС 155 РЕ"1.

Пример выполнения анализатора (фиг.3), Анализатор содержит дешифратор 31, выходы 32-47 которого соединены с входами элементов ИЛИ 48-52 в соответствии с табл.!. При этом выходы элементов ИЛИ 48-51, соединенные с шинами 48-51 образуют первый выход анализатора, а выход элемента

ИЛИ 52, соединенный с шиной 53 образует второй выход анализатора, Работу. устройства рассматриваем на следующем примере. Пусть значение, записанное в регистре 1, .равно с дополнительным фиктивным разрядом слева) 011.110,011.001 1945 . Ана-< лизаторы 10" 13 управляются разрядами соответственно первой, второи, треть. ей и четвертой тройки и старшим разрядом следующей тройки (для последней тройки этз циФра равна нулю).

В соо",såòñòâèè с изложенными выше правилами преобразования цифры пре" образованного множителя равны +4,-2, +3 и +1. Анализатор 10 задает для блока 3 режим учетверения множимсгс анализатор ll для блока 4 - режим удвоения, анализатор .2 для. блока

5 - режим утроения, анализатор 13 для блока 6 - режим прямой передачи.

Ка выходах блоков 3-6 имеем соотПервый выход анализаЦифра преобразованного множителя

Режим работы блока формирова" ния кратных множимого

Второй выход анализатора

Комбинация разрядов множителя тора

00111

10101

0010

10101

00000

ООII

00000

0100

10010

А+В

0101

0110

10010

А+В

+4

I1ООО

2А

1000

10010

А+В

10010

А+В

1 010

ООООО

1011

ООООО

1100

10101

1101

1110

00111

Таблица

Режим работы Второй выход сумматора преобразователя

Входные сигналы преоб.разователя

Первый выход преобразователя

О О

10010

А+В

01100

А-В О

7 932489 ветственно с учетом весов разрядов мйожителя следующие кратные множимого И: 4 8 И 2048 М; 2>8 128 М;

3 8М = 24 М; 1 И.

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

Сумматор 8 работает в режиме сложения. На выходах сумматоров 7 и 8 1о

25И. Преобразователь 16 задает для сумматора 9 режим сложения, На его выходе (получается значение 1945И, то есть истинное значение произведения.

Предлагаемое устройство в зависимости от разрядности сомножителей обеспечивает увеличение быстродействия по сравнению с известном устройством в 2-4 раза. . Таблица 1

932489

Продолжение табл. 2

Первый выход преобразователя

Второй выход преобразователя

Режим работы сумматора

Входные сигналы преобразователя

01100

1 0

А"В

10010

А+В формула изобретения

Устройство для умножения двоичных чисел, содержащее регистр множимого, регистр множителя, блок формирования кратных множимого, первый и второй анализаторы кодов групп разрядов множителя, входы которых соединены с выходами соответствующих групп разрядов множителя, а первые выходы подключены к управляющим . входам соответствующих .блоков формирования кратных множимого, информационные входы которых соединены с выходами регистра множимого, а выходы подключены к соответствующим входам блЬка суммирования, о т л ич а ю щ е е с я тем, что, с целью повышения быстродействия, устройство содержит дополнительно блок формирования управляющих кодов суммиро»: вания, (4,-2) блоков формирования .кратных множимого с третьего no 3$

k-й (k - число.разрядов множителя},, (k-2) анализаторов кодов rpynn разрядов множителя с третьего по ф -й входы которых соединены с выходами соот-.

1 ветствующих групп разрядов регистра 4Е множителя, а первые выходы подключе" ны к управляющим входам соответствуюших блоков формирования кратных множимого, входы -xotopsx подключены к выходам регистра множимого, а вы-, ходы - к соответствующим входам блока суммирования, в состав которого входит пирамида сумматоров, информационные входы первого ряда которых соединены со взятыми попарно входами блока суммирования, выходы взятых попарно сумматоров каждого ряда пирамиды соединены с информационными входа ми сумматора последующего ряда,. выход сумматора последнего ряда пирамиды является выходом блока суммирования и выходом устройства, блок формирования управляющих кодов суммирования содержит пирамиду табличных преобразователей знаковых разрядов в управляющие коды сумматора, входы первого ряда которых соединены с вторыми выходами взятых попарно анализаторов кодов групп разрядов множителя, первые выходы табличных преобразователей знаковых разрядов в управляющие коды сумматора соединены с управляющими входами соответствующих сумматоров соответствующего ряда пирамиды блока суммирования, вторые выходы табличных преобразователей знаковых разрядов в управляющие коды сумматора ка.ндого ряда пирамиды, взятых попарно,соеди" иены с входами табличных преобразователей знаковых разрядов в управляющие коды сумматора последующего ряда пирамиды.

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

1. карцев H.A. Арифметика цифровых машин. И., "Наука", 1969, с. 4. р3-456.

2. Патент С16А М 3о96496„ кл. 2Я-1Я, опублик. 1Я, 3, Авторское свидетельство СССР по заявке И .2628106/18-24, .кл. 6 06 F 1752, 1978 (прототип).

932489

Составитель В.Березкин

Редактор Е.llann Техред А. Ач Корректор Г.Огар

Заказ 3785/69 Тираж 732 Подписное

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

313035, москва, N-35, Рауаская наб., д. 4/5

Филиал ППП "Патент", r. Ужгород, ул. Проектная, 4