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

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

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

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

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

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

Кроме того, блок анализа содержит два п-разрядных регистра, два (п-1)разрядных блока элементов И и узел сравнения, причем первого и второго регистров соединены соответственно с первой и второй группами входов блока анализа, а их выходы соединены соответственно с первой и второй группой входов узла сравнения первый и второй выходы которого соед нены соответственно с первым и вторым выходами блока анализа, единичный выход i-ro разряда и нулевой выход ( j+1)-ro разряда каждого из регистров соединены соответственно с дервым и вторым входами i-oro элеrfeHTa И соответствующего блока, выход которого соединен с нулевым входом л-го разряда и единичным входом (i+1)-ro разряда данного регистра (i 1 - п-1).

На чертеже представлена структурная схема устройства для умножения п-разрядных чисел (для п 4).

Устройство содержит матрицу 1 из элементов И, первый блок 2 элементов ИЛИ, регистр 3 множителя, регистр 4 множимого, накапливающий сумматор 5,

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

и 15, элемент 16 задержки, элемент ИЛИ 17, блок 18 анализа, содержащий .два п-разрядных регистра 19 и 20, два (п-1)-разрядных блока 21 и 22 И, узел 23 сравнения.

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

Операнды записываются в регистры 3 и 4, а также в регистры 19 и 20 блока 18 анализа. После записи one-.

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

Q Если i+1-й разряд регистра 19 (20) (: 1, 2, ..., п-1) находится в нулевом состоянии, а i-й разряд регистра - в единичном состоянии, то з-й элемент И блока 21 (22) открыт и

5 единичный сигнал с его выхода уста навливает л+1-й разряд регистра в единичное, а i-й разряд этого регистра в нулевое состояние. Таким образом, устанавливается такое состояние регистров 19 и 20, при котором все единицы кода операндов находятся в старших разрядах, а нули кода в младших разрядах. Из двух чисел, записанных .в регистрах 19 и 20, большее то, у которого большее количест5б во единиц. Коды чисел из регистров 19 и 20 поступают на узел 23 сравнения.

Если количество единиц в коде множителя меньше или равно количеству

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

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

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

5 импульс с элемента ИЛИ 17 поступает через первый элемент И блока 7 и эле мент ИЛИ блока 10 в слелующий разряд Поскольку триггер старшего разряда регистра 3 находится в нулевом состоянии, первый элемент И блока б не пропускает управляющий импульс. В остальных разрядах устройство работает аналогично. Если количество единиц в коде мно жителя больше, чем в коде множимого то на первом выходе узла 23 сравнения единичный сигнал, который поступает на второй вход элемента И 14. Управляющий импульс с входа 24 поступает через элемент И 14 на входы элементов И третьего и четвертого блоков 8 и 9. Код из регистра 3 множителя через блок 13 элементов задержки и блок 8 элементов И записывается в регистр 4 множимого, а код множимого - из регистра 4 через элeменты задержки блока 12 и элементы И блока 9 в регистр 3 множителя. Величина задержки на блоках 12 и 13 равна длительности импульса. С выхода элементов И 14 управляющий импульс, задержанный на один такт на элементе 16 задержки, поступает на вход элемента ИЛИ 17. Далее устройстйо работает описанным выше способом. Появление импульса на.шине 25 выхода означает, что процесс умножения закончен, В сумматоре 5 формируется результат умножения. Для умножения чисел требуется чис ло тактов, равное количеству единиц в.регистре множителя, если множитель имеет меньшее или равное с множимым количество единиц и на один такт больше, чем число единиц множимого, если оно имеет меньше единиц, чем множитель. Таким образом, быстродействие предложенного устройства определяется минимальным количеством единиц в одном из операндов и, следовательно, среднее быстродействие устройства при умножении чисел выше, чем быстродействие известного устройства Формула изобретения 1. Устройство для умножения двух п-разрядных чисел по авт. св. № 623204, отличающееся тем, что, с целью- повышения быстродействия, дополнительно содержит третий и четвертый п-разрядные блоки элементов И, второй и третий п-разрядные блоки элементов задержки, два элемента И, элемент ИЛИ, элемент задержки и блок анализа, при.чем первый и второй выходы блока анализа соединены соотйетственно с первыми входами первого и второго элементов И, вторые входы которых соединены с шиной начала работы устройства, выход первого элемента И соединен с первыми входами элементов И третьего и четвертого блоков и через элемент задержки с первым входом .элемента ИЛИ, второй вход которого соединен с выходом второго элемента И, а выход подключен к вторым входам элементов И первого разряда первого и второго блоков, единичные выходы регистра множимого через элементы задержки второго блока соединены соответственно с вторыми входами элементов И четвертого блока, выходы которых соединены соответственно, с входами регистра множителя, единичные выходы которого через элементы задержки третьего блока соединены соответственно с вторыми входами элементов И третьего блока, выходы которых соединены соответственно с входами регистра Множимого, первая и вторая группы входов блока анализа соединены соответственно с входными шинами первого и второго сомножителей устройства. 2. Устройство по п. 1, о т л ичающееся тем, что блок анализа содержит два п-разрядных регистра, два Сп-1) разрядных блока элементов И и узел сравнения, причем входы первого и второго регистров соединены соответственно с первой и второй группами входов блока айализа, а их выходы соединены соответственно с первой и второй группой входов узла сравнения, первый и второй выхода которого соединены соответственно с первым и вторым выходами блока анализа, единичный выход i-ro и нулевой выход (i+1)-ro разрядов каждого из регистров соединены соответственно с первым и вторым входами i-ro элемента И соответствуюшего блока, выход которого соединен с нулевым входом i-ro разряда и единичным входом (it-l)-ro разряда даннох о регистра (1 1 - п-1). Источники информации, принятые во внимание при экспертизе 1. Авторское свидетельство СССР 623204, кл. G 06 F 7/52, 1977 fпрототип). ,