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

ОПИСАНИЕИЗОБРЕТЕНИЯК АВТОРСКОМУ СВИДЕТЕЛЬСТВУ Союз СоветскихСоциалистическихРеснублик 11991418(22) Заявлено 15.1081(21) 3350192/18-24 РМ К з с присоединением заявки Йо(23) Приоритет -С 06 Р 7/52 Государственный комитет СССР по делам изобретений и открытийДата опубликования описания 23. 01. 83 ьф+а(54) УСТРОИСТВО ДЛЯ УМНОЖЕНИЯ ДВУХ и-РАЗРЯДНЫХ ЧИСЕЛИзобретение относится к вычислительной технике и может быть использовано для выполнения операции умножения двоичных чисел в арифметических устройствах.По основному авт. св. Р 623204известно устройство для умножения двух и-разрядных чисел, которое. содержит матрицу из элементов И, празрядный регистр множимого, и-раз рядный регистр множителя, (2 п)-разрядный первый блок элементов ИЛИ, (2 п) -разрядный накапливающий сумматор, первый и второй и-разрядные .блоки элементов И, п-разрядный второй блок элементов ИЛИ, и-разрядный первый блок элементов задержки, причем выходы регистра множимого соединены с первой группой входов матрицы из элементов И, выходы разрядов которой с второго по (2 п)-й соединены с соответствующими входами элементов ИЛИ первого блока, выходы которого соединены с соответствующими входами сумматора, входы первого и (2 п 1)-го разрядов которого соединены с выходами соответствующих разрядов матрицы иэ элементов И, единичные и нулевые выходы регистра множителя соединены соответственно с первыми входами элементов И первого и второго блоков, выходы, элементов И первого блока соединены соответственно с второй группой входов матрицы из элементов И, выходы элементов И первого блока через элементы задержки первого блока соединены соответственно с первыми входами элементов ИЛИ второго блока, выходы элементов ИЛИ с первого по (и)-й которого соединены с вторыми входами элементов,И первого и второго блоков с вто.рого по и-й соответственно, выходы элементов И второго блока соединены соответственно с вторыми входами эле.ментов ИЛИ второго блока, выход и-го элемента ИЛИ второго блока являетсявыходом устройства 1Быстродействие известного устройства определяется количеством единиц в коде множителя. В случаях, когда количество единиц в коде множителя больше, чем количество единиц в коде множимого, данное устройство облада ет низким быстродействием. Целью изобретения является повышение быстродействия устройства за счетназначения множителем операнда, име- ЗО ющего меньшее количество единиц в ко991418во единиц. Коды чисел из регистров де, что уменьшает среднее число тактов работы устройства.Поставленная цель достигается тем,что устройство для умножения двухи-разрядных чисел дополнительно содержит третий и четвертый и-разрядные 5блоки элементов И, второй и третийП-разрядные блоки элементов задержкипервый и второй элементы И, элементзадержки, элемент ИЛИ и блок анализа,причем первый и второй выходы блока 10анализа соединены соответственно спервыми входами первого и второгоэлементов И, вторые входы которыхсоединены с шиной начала работы устройства, выход первого элемента Исоединен с первыми входами элементовИ третьего и четвертого блоков и через элемент задержки с первым входомэлемента ИЛИ, второй вход которогосоединен с выходом второго элементаИ, а выход подключен к вторым входамэлементов И первого разряда первогои второго блоков, единичные выходырегистра множимого через элементызадержки второго блока соед.нены соответственно с вторыми входами элементов И четвертого блока, выходыкоторых соединены соответственно свходами регистра множителя, единичные выходы которого через элементызадержки третьего блока соединенысоответственно с вторыми входами элементов И третьего блока, выходы которых соединены соответственно с входами регистра множимого, первая и вторая группа входов блока анализа со" З 5единены соответственно с входнымишинами первого и второго сомножителей устройства.Кроме того, блок анализа содержитдва и-разрядных регистра, два (и)- 40разрядных блока элементов И и узелсравнения, причем входы первого ивторого регистров соединены соответственно с первой и второй группамивходов блока анализа, а их выходы 45соединены соответственно с первой ивторой группой входов узла сравнения,первый и второй выходы которого соединены соответственно с первым и вторым выходами блока анализа, единич Оный выход 1-го разряда и нулевой выход ( +1)-го разряда каждого из регистров соединены соответственно спервым и вторым входами д-ого элемента И соответствующего блока, выход которого соединен с нулевым входом з-го разряда и единичным входом(1+1)-го разряда данного регистра(1 = 1 - и-).На чертеже представлена структурная схема устройства для умноженияи-разрядных чисел (для и = 4),Устройство содержит матрицу 1 изэлементов И, первый блок 2 элементовИЛИ, регистр 3 множителя, регистр 4множимого, накапливающий сумматор 5, 65 первый, второй, третий и четвертыйблоки 6-9 элементов И, второй блок10 элементов ИЛИ, первый, второй итретий блоки 11-13 элементов задержки, первый и второй элементы И 14и 15, элемент 16 задержки, элементИЛИ 17, блок 18 анализа, содержащий два и-разрядных регистра 19 и 20, два(и)-разрядных блока 21 и 22 И, узел 23 сравнения.Устройство работает следующим об-. разом.Операнды записываются в регистры 3 и 4, а также в регистры 19 и 20 блока 18 анализа, После записи операндов в регистрах 19 и 20 блока анализа формируется код, у которого все единицы располагаются рядом, начиная со старшего разряда, следующим образом.Если 1+1-и разряд регистра 19 (20) ( 3 = 1, 2.и) находится в нулевом состоянии, а 1-й разряд регистра - в единичном состоянии, то -й элемент И блока 21 (22) открыт и единичный сигнал с его выхода уста-, навливает +1-й разряд регистра в единичное, а 1-й разряд этого регист. ра в нулевое состояние. Таким образом, устанавливается такое состояние регистров 19 и 20, при котором все единицы кода операндов находятся в старших разрядах, а нули кода - в,младших разрядах. Из двух чисел, записанных в регистрах 19 и 20, большее то, у которого большее количест 19 и 20 поступают на узел 23 сравнения.Если количество единиц в коде множителя меньше или равно количеству единиц в коде множимого, то на втором выходе узла 23 сравнения единичный сигнал, который поступает на второй вход элемента И 15. Управляющий импульс, поданный на вход 24, поступает через элементы И 15 и ИЛИ 17 на входы первых элементов И первого и второго блоков б и 7. Если триггер старшего разряда. регистра множителя находится в единичном состоянии, то импульс появляется на выходе .первого элемента И блока б и суммирует соот-, ветственно сдвинутый код множимого на сумматоре 5. Импульс с выхода первого элемента И блока б, задержанный на первом элементе задержки блока 11 на один такт, через первый элемент ИЛИ блока 10 поступает в следующий разряд множителя. Поскольку триггер старшего разряда множителя находится в состоянии единицы, первый элемент И блока 7 не пропускает управля ющий импульс на вход первого элемента ИЛИ блока 10. Если триггер старшего разряда множителя находится в нулевом состоянии, то управляющий импульс с элемента ИЛИ 17 поступаетчерез первый элемент И блока 7 и элемент ИЛИ блока 10 в следующий разряд.Поскольку триггер старшего разряда регистра 3 находится в нулевомсостоянии, первый элемент И блока бне пропускает управляющий импульс.В остальных разрядах устройство работает аналогично.Если количество единиц в коде множителя больше, чем в коде множимого,то на первом выходе узла 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 соответственно с вторыми входами эле.ментов И третьего блока., выходы которых соединены соответственно с входами регистра множимого, первая ивторая группы входов блока анализаЗО соединены соответственно с входнымишинами первого и второго сомножителей устройства.2. Устройство по п. , о т л ич а ю щ е е с я тем, что блок анаЗ 5 лиза содержит два и Разрядных Регистра, два (и) разрядных блока элементов И и узел сравнения, причем входыпервого и второго регистров соединены соответственно с первой и второйгруппами входов блока аиализа, а ихвыходы соединены соответственно спервой и второй группой входов узласравнения, первйй и второй выходыкоторого соединены соответственнос первым и вторым выходами блока ана 45 лиза, единичный выход 1-го и нулевойвыход (1+1)-го разрядов каждого нзрегистров соединены соответственнос первым и вторым входами 1-го элемента И соответствующего блока, вы 50 ход которого. соединен с нулевым входом 1-го разряда и единичным входом(1+1)-го разряда данного регистра(1 д 1 -и),55 Источники информации,принятые во внимание при экспертизе1. Авторское свидетельство СССРР 623204, кл. С 06 Р 7/52, 1977991418 Составитель А, Клюевдактор Т Кугрыаева ТехредТ.фанта Корректор М, Чар Подписнта СССР Зак аб филиал ППП "Патент", г. Ужгород, ул. Проектная,135/67 ВНИИПИ Госу по делам 113035, МосквТираж 704 арственного коми зобретений и откЖ, Раушская