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

 

ОПИСАНИЕ

ИЗОБРЕТЕНИЯ

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

Союз Советских

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

Реснублик 1в991418 (61) Дополнительное к авт. свид-ву 9 623204 (22) Заявлено 15. 10. 81(21) 3350192/18-24

Р М К з с присоединением заявки Йо(23) Приоритет—

G. 06 F 7/52

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

СССР по делам изобретений и открытий

Опубликовано 230183. Бюллетень Йо 3 ($3) УДК 681. 325 (088.8) Дата опубликования описания 23. 01. 83 (72) Автор изобретения

Н. И. Крылов (71) Заявитель (54) УСТРОИСТВО ДЛЯ УМНОЖЕНИЯ ДВУХ и-РАЗРЯДНЫХ ЧИСЕЛ

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

По основному авт. св. Р 623204 известно устройство для умножения двух и-разрядных чисел, которое. содержит матрицу из элементов И, празрядный регистр множимого, и-разрядный регистр множителя, (2п-3)-раз. рядный первый блок элементов ИЛИ, (2п-1) -разрядный накапливающий сумматор, первый и второй и-разрядные блоки элементов И, и-разрядный второй блок элементов ИЛИ, и-разрядный первый блок элементов задержки, причем выходы регистра множимого соединены с первой группой входов матрицы из элементов И, выходы разрядов которой с второго по (Zn-2)-й соединены с соответствующими входами элементов ИЛИ первого блока, выходы которого соединены с соответствующими входами сумматора, входы первого и (Zn»1)-го разрядов которого соединены с выходами соответствующих разрядов матрицы иэ элементов И, единичные и нулевые выходы регистра множителя соединены соответственно с первыми входами элементов И первого и второго блоков, выходы. элементов И первого блока соединены соответственно с второй группой входов матрицы из элементов.И, выходы элементов И первого блока через элементы задержки первого блока соединены соответственно с первыми входами элементов

ИЛИ второго блока, выходы элементов

ИЛИ с первого по (и-1)-й которого соединены с вторыми входами элементов,И первого и второго блоков с второго по и-й соответственно, выходы элементов И второго блока соединены соответственно с вторыми входами элементов ИЛИ второго блока, выход и-го элемента ИЛИ второго блока является выходом устройства (1j.

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

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

6 во единиц. Коды чисел из регистров де, что уменьшает среднее число тактов работы устройства.

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

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

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

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

Кроме того, блок анализа содержит два и-разрядных регистра, два (n-1)- 40 разрядных блока элементов И и узел сравнения, причем входы первого и второго регистров соединены соответственно с первой и второй группами входов блока анализа, а их выходы 45 соединены соответственно с первой и второй группой входов узла сравнения, первый и второй выходы которого соединены соответственно с первым и вторым выходами блока анализа, единич- ц ный выход i-ro разряда и нулевой выход (i+I)-го разряда каждого из регистров соединены соответственно с первым и вторым входами т-ого элемента И соответствующего блока, выход которого соединен с нулевым входом i-го разряда и единичным входом (i+1)-ãî разряда данного регистра (i = 1 - n-!).

На чертеже представлена структурная схема устройства для умножения и-разрядных чисел (для п = 4), Устройство содержит матрицу 1 из элементов И, первый блок 2 элементов

ИЛИ, регистр 3 множителя, регистр 4 множимого, накапливающий сумматор 5, первый, второй, третий и четвертый блоки 6-9 элементов И, второй блок

10 элементов ИЛИ, первый, второй и третий блоки 11-13 элементов задержки, первый и второй элементы И 14 и 15, элемент 16 задержки, элемент

)ИЛИ 17, блок 18 анализа, содержащий два и-разрядных регистра 19 и 20, два (n-1)-разрядных блока ?1 и 22 И, узел

23 сравнения.

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

Операнды записываются в регистры

3 и 4, а также в регистры 19 и 20 блока 18 анализа. После записи операндов в регистрах 19 и 20 блока анализа формируется код, у которого все единицы располагаются рядом, начиная со старшего разряда, следующим образом.

Если i+1-и разряд регистра 19 (20) (i = 1, 2, ° ., n-1) находится в нулевом состоянии, а i-й разряд регистра — в единичном состоянии, то >-й элемент И блока 21 (22) открыт и единичный сигнал с его выхода уста-, навливает i+1 и разряд регистра в единичное, а i-й разряд этого регистра в нулевое состояние. Таким образом, устанавливается такое состояние регистров 19 и 20, при котором все единицы кода операндов находятся в старших разрядах, а нули кода— в,младших разрядах. Из двух чисел, записанных в регистрах 19 и 20, большее то, у которого большее количест19 и 20 поступают на узел 23 сравнения.

Если количество единиц в коде множителя меньше или равно количеству единиц в коде множимого, то на втором выходе узла 23 сравнения единичный сигнал, который поступает на второй вход элемента И 15. Управляющий импульс, поданный на вход 24, поступает через элементы И 15 и ИЛИ 17 на входы первых элементов И первого и второго блоков б и 7. Если триггер старшего разряда регистра множителя находится в единичном состоянии, то импульс появляется на выходе .первого элемента И блока б и суммирует соот-, ветственно сдвинутый код множимого на сумматоре 5. Импульс с выхода первого элемента И блока б, задержанный на первом элементе задержки блока 11 на один такт, через первый элемент

ИЛИ блока 10 поступает в следующий разряд множителя. Поскольку триггер старшего разряда множителя находится в состоянии единицы, первый элемент И блока 7 не пропускает управля. ющий импульс на вход первого элемента ИЛИ блока 10. Если триггер старшего разряда множителя -находится в нулевом состоянии, то управляющий импульс с элемента ИЛИ 17 поступает

991418 через первый элемент И блока 7 и элемент ИЛИ блока 10 в следующий разряд.

Поскольку триггер старшего разряда регистра 3 находится в нулевом состоянии, первый элемент И блока 6 не пропускает управляющий импульс.

В остальных разрядах устройство работает аналогично.

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

Управляющий импульс с входа 24 поступает через элемент И 14 на вхс0цы элементов И третьего и четвертого блоков 8 и 9. Код из регистра 3 множителя через блок 13 элементов задержки и блок 8 элементов И записывается в регистр 4 множимого, а код множимого — из регистра 4 через эле- менты задержки блока 12 и элементы

И блока 9 в регистр 3 множителя. Величина задержки на блоках 12 и 13 равна длительности импульса. С выхода элементов И 14 управляющий импульс, задержанный на один такт на элементе 16 задержки, поступает на вход элемента ИЛИ .17.

Далее устройство работает описанным выше способом.

Появление импульса на.шине 25 выхода означает, что процесс умножения закончен. В сумматоре 5 формируется результат умножения.

Для умножения чисел требуется число тактов, равное количеству единиц в .регистре множителя, если множитель имеет меньшее или равное с множимым количество единиц и на один такт больше, чем число единиц множимого, если оно имеет меньше единиц, чем множитель.

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

Формула изобретения

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

М 623204, о т л и ч а ю щ е е с я тем, что, с целью. повышения быстродействия, дополнительно содержит третий и четвертый и-разрядные блоки элементов И, второй и третий и-разрядные блоки элементов задержки, два элемента И, элемент ИЛИ, элемент задержки и блок анализа, при.чем первый и второй выходы блока анализа соединены соответственно с

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

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

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

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

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

З0 соединены соответственно с входными шинами первого и второго сомножителей устройства.

2. Устройство по п., о т л ич а ю щ е е с я тем, что блок ана35 лиз а содержит два и-разрядных ре ги стра, два (n-1) разрядных блока элементов И и узел сравнения, причем входы первого и второго регистров соединены соответственно с первой и второй группами входов блока аиализа, а их выходы соединены соответственно с первой и второй группой входов узла сравнения, первйй и второй выходы которого соединены соответственно с первым и вторым выходами блока ана45 лиза, единичный выход i-ro и нулевой выход (i+1)-го разрядов каждого нз регистров соединены соответственно с первым и вторым входами i-го элемента И соответствующего блока, вы50 ход которого. соединен с нулевым входом i-го разряда и единичным входом (i+1)-го разряда данного регистра (1 = 1 - n-1).

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

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

Р 623204, кл. G 06 F 7/52, 1977 (прототип) .. 991418

Составитель A. Клюев

Редактор Т., Кугрыаева ТехредТ.фанта Корректор М. лароши

Заказ 135/67 Тираж 704 Подписное

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

113035, Москва, Ж-35, Раушская наб, д. 4/5 филиал ППП "Патент", r. Ужгород, ул. Проектная, 4