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

ОП ИСАНИЕИЗОБРЕТЕНИЯК АВТОРСКОМУ СВИДЕТЕЛЬСТВУ Соки Советски кСоциалистическихРеслублии 4683-в 22) Заявлено 05.01.78 (21) 2566 с присоединением зая Гооударстееииый к СССР во деин изобрет и открытий-РАЗРЯДНЫХ ЧИСЕЛ МНОЖЕ 54) УСТРОЙСТВ ос- со более бл едлагаем щее сумм теля, пер оизведен образова хнической сущносся устройство, состры множимого, ержащее и частиче логическую схеизким по те ому являет атор, реги еносов, сод ий, а такж ния 3. На ти кп держа множи у п Изобретение относится к вычислительной технике и предназначено для умножения двоичных чисел, представленных параллельным кодом, и может быть использовано при построении арифметических устройств специализированных и универсальных ЦВМ.Известны устройства для умножения двоичных чисел, в которых ускорение процесса умножения достигается за счет выполнения операции умножения с запоминанием переносов при одновременной расшифровке одной или нескольких пар разрядов множителя 1 и 2.Недостатками устройств умножения с расшифровкой одной пары разрядов множиТеля являются неполная загрузка (что не позволяет добиться оптимального быстродей. ствия), значительные затраты оборудования и необходимость использования сложных узлов вычислительной техники. Это устройство обеспечивает выполнение умножения одновременно на два разряда множителя с запоминанием переносов.Умножение на всю разрядную сетку множителя происходит за п/2 тактов, где ив число разрядов множителя, при этом п ледний такт суммирования производится всеми сквозными переносами.Недостатком известного устройства является то, что в первом и втором тактах не обеспечивается максимальная загрузка сумматора, и он работает соответственно либо на передачу множимого, либо на суммирование только двух чисел, что ограничивает быстродействие данного устройства.Цель изобретения - повышение быстродействия устройства умножЕния.Цель достигается тем, что в устройство содержащее (и + 2) -разрядные регистры множимого, множителя и переносов, блока анализа множителя, триггер инверсной передачи множимого, (п + 4) -разрядный регистр частичных произведений, сумматор, состоящий из (и+ 2)-х основных и двух дополнительных разрядов, причем выходы регистра множимого подключены к первым входам основных разрядов сумматора, выходы сум16 35 2 О 23 30 Ф 33 ае 45 И мы которых подключены к входам регистра частотных произведений, выходы переносов )-тых основных разрядов сумматора соединены с (+1)-ыми входами регистра переносов= 1 в :-(и - 1), (и1, выход переноса первого дополнительного разряда сумматора соединен с первым входом второго дополнительного разряда сумматора, выход переноса второго дополнительного разряда сумматора соединен с входом первого разряда регистра переносов, выход которого соединен со вторым входом первого дополнительного разряда сумматора, а выходы суммы первого и второго дополнительных разрядов сумматора соединены со старшими разрядами регистра множителя, дополнительно содержит пять элементов ИЛИ, триггер преобразования кода, триггер такта, два блока коммутации, два элемента И, элемент И - НЕ, дополнительный разряд в регистре переносов, третий и четвертый дополнительные разряды в сумматоре и два дополнительных разряда в регистре частичных произведений, при этом выходы суммы третьего и четвертого дополнительных раздов сумматора соединены с входами двух дополнительных разрядов регистра частичных произведений, выход переноса третьего дополнительного разряда сумматора соединен с входом четвертого дополнительного разряда сумматора, выход перноса которого объединен с входом дополнительного разряда регистра переносов, вход (п + 1)-го разряда регистра переносов соединен с выходом первого элемента И, вход которого соединен с выходом переноса п-го разряда сумматора, выходы первого (и + 2)-го разрядов первого блока коммутации соединены с третьими входами разрядов сумматора, начиная с первого дополнительного разряда, а выходы (и 1. 3) -го и (и+ 4) -го разрядов первого блока коммутации соединены с входамипервого и второго элементов ИЛИ, выходы которых соединены с входами (п+ 1) -го и и-го разрядов сумматора, вторые входы ) основных =1 - :п) и третьего и четвертого дополнительных разрядов сумматора соединены с выходами второго блока коммутации, первая группа информационных входов которого, соединена с соответствующей группой входов первого блока коммутации и подключена к выходам регистра м ножи мого, а вторая группа (и+2) -х информационных входов второго блока коммутации соединена с Ю-ми выходами (к=2-:и+2) основных и выходом дополнительного разрядов регистра переносов, вторая группа информационных входов первого блока коммутации соединена с выходами регистра частичных произведений, первый вход первого дополнительного разряда сумматора соединен с входами первых четырех элементов ИЛИ и первым входом элемента И - НЕ и подключен к выходу блока анализа множителя, первые управляющие входы блоков коммутации соединены с входом блока анализа и с первым выходом триггера такта, второй выход которого подключен ко вторым управляющим входам блока коммутации, входам второго элемента И и блока анализа, второй выход которого соединен с входами третьего, четвертого и пятого элементов ИЛИ и со вторым входом элемента И - НЕ, соединенного своим выходом с входом первого элемента И, третий выход блока анализа соединен с входами третьего элемента ИЛИ и триггера преобразования кода, выход которого соединен с входом пятого элемента ИЛИ, выход третьего элемента ИЛИ соединен с входом триггера инверсной передачи множимого, выход которого соединен с входом второго элемента И, соединенного своим выходом с входами двух старших разрядов сумматора, выходы четвертого и пятого элементов ИЛИ соединены соответственно со входами двух старших и входом третьего дополнительного разрядов сумматора. На чертеже представлена схема устройства,Устройство содержит (п+ б) -разрядный сумматор 1, (и+4) -разрядный регистр 2 частичных произведений, (и+3) -разрядный регистр 3 переносов, (п+2) - разрядные регистры 4 и 5 множимого и множителя; два блока 6 и 7 коммутации, блок 8 анализа, элемент И 9, элементы ИЛИ 10,1, 12, 13 и 14, элемент И 15, элемент И-НЕ 16, триггер 17 инверсной передачи множимого, триггер 18 преобразования кода и триггер 19 такта.Устройство работает следующим образом.В исходном состоянии в регистрах 4 и 5 множимого и множителя хранятся сомножители, триггеры 17, 18 и 9, регистры 2 и 3 обнулены. При этом инверсный выход триггера 19 такта разрешает блоку 8 анализа, а также блокам 6 и 7 коммутации, работу в первом такте. В результате в этом такте три пары младших разрядов с регистра 5 множителя одновременно поступают в блок 8 анализа (на чертеже соответствующая связь не показана), который обеспечивает расшифровку и анализ возможных комбинаций поступающих пар разрядов, а по результатам анализа осуществляется управление преобразованием множимого, Затем множимое с регистра 4 поступает на первый вход сумматора через схему логического преобразования множимого (на чертеже не показана), начиная с первого основного разряда; на второй вход - через первый сигнальный вход блока 7 коммутации, начиная с третьего дополнительного разряда; на третий вход сумматора 1 через первый сигнальный вход блока 6, начиная с первого дополнительного разряда. При этом вид передачи множимого зависит от результатаанализа соответственно третьей, второй и первой пар разрядов множителя, осуществляемого в блоке 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, то преобразование множимого в дополнительный ход производится в следующем (втором) такте умножения. Получающаяся в первом также умножения сумма по гпод 2 с выхода сумматора 1 записывается в регистр 2 частичных произведений, а поразрядные переносы с выходом переносов того же сумматора 1 - в регистр 3 переносов. Поразрядные переносы, которые образуются на выходе первого и третьего дополнительных разрядов сумматора 1, поступают соответственно на первые входы второго и четвертого дополнительных разрядов сумматора 1, т,е. названные разряды сумматора охвачены попарно сквозным переносом. Перенос же с выхода п-го разряда сумматора 1 записывается в (и+1)-ый разряд регистра 3 переносов через элемент И 9, открываемый нулевым сигналом с выхода элемента И - НЕ 16 при наличии на его входах хотя бы одного нулевого потенциала с выхода блока 8 анализа, т.е. при отсутствии в двух младших анализируемых парах хотя бы одной комбинации 11. В случае же, если эти две комбинации указанных пар разрядов 11, то элемент И - НЕ 16 закрывает схему управления перекосом 9, обеспечивая тем самымЬзапись в(п+ 1)-ый разряд регистра переносов 3 нуля кода.Таким образом в первом такте получается частичное произведение от умножения множимого на 6 младших разрядов множителя.На втором такте триггер 19 определения такта устанавливается в единичное состояние и сигнал с прямого выхода этого триггера переводит устройство умйожения в режим работы с анализом одной пары разрядов множителя и запоминанием переносов. Частичное произведение, полученное в первом такте и записанное в регистр 2 поступает через блок 6 коммутации, открытый по первому управляющему входу сигналом с прямого выхода триггера 19, на третьи входы (п - 2)-х основных и четырех дополнительных разрядов сумматора 1, При этом в (и - 1) -й и п-й основные разряды сумматорра произведение передается через входы элементов ИЛИ 10 и 11, на другие входы которых поступает нулевой сигнал с первои 2 О тор 1. При комбинации 11, ачализируемой во втором такте пары разрядов множителя, преобразование обратного кода множимого в го выхода блока 8 анализа (при работе на втором и последующих тактах на первых двух выходах блока анализа 8 - нулевой потенциал). Записанные в регистр 3 переносы в свою очередь поступают на вторые входы и основных, а также третьего и четвертого дополнительных разрядов сумматора 1, через блок 7 коммутации, открытый по второму управляющему входу сигналом с прямого выхода триггера 19 такта. Перенос из первого разряда регистра 3 поступает непосредственно на второй вход первого дополнительного разряда сумматора 1.На этом же такте осуществляется преобразование множимого в дополнительный код в случае, когда комбинация третьей пары зз разрядов множителя, анализ которой производился в первом такте, 11. При этом из блока 8 анализа (третий выход) единица подается через триггер 18 преобразования кода, обнуляемый в каждом такте работы устройства умножения, и элемент ИЛИ 14, в третий дополнительный разряд, сумматора 1 по первому входу, обеспечивая преобразование обратного кода в дополнительный, Единица записывается также в два старших разряда сумматора 1 по третьим входам, что обеспечивается триггером 17 инверсной передачи множимого, в который единица записывается через элемент ИЛИ 12, если хотя .бы одна из анализируемых в первом такте пар разрядов множителя - 11. При этом триггер 17 запоминает и обеспечиваф ет передачу единичного сигнала через элемент И 15 в два старших разряда сумматора 1 во всех последующих тактах независимо от вида передачи множимого на суммадополнительный код производится в последующем (третьем) такте. При этом в третий дополнительный разряд сумматора 1 из блока 8 анализа (третий выход) через триггер 18 преобразования кода, элемент ИЛИ14 подается единица, преобразующая обратный код в дополнительный. Кроме того, с того же выхода блока 8 анализа единица записывается через схему ИЛИ 12 в триггер 17 инверсной передачи множимого, обеспечивая тем самым передачу единицы на третьи входы двух старших разрядов 11 сумматора 1, через элемент И 15, при этом триггер 17 аналогично предыдущему такту запоминает и обеспечивает запись единиц в эти два старших разряда сумматора 1 также во всех последующих тактах.В третьем, четвертом и последующих тактах устройство 7 умножения работает так же, как и во втором такте до тех пор; пока не закончится умножение множимого на всю разрядную сетку множителя.Получающиеся в каждом такте умноже ния два разряда произведения записываются в старшие освободившиеся разряды регистра 5 множителя.В результате предлагаемое устройство для умножения обеспечивает перемножение двух п-разрядных чисел за ( - - - 2)тв. И тактов, при этом на последнем такте сумматор работает со всеми сквозными переносами.Таким образом, введение новых элементов позволяет повысить быстродействие уст,ройства при более полном использовании оборудования (сумматора) . Это преимущество особенно проявляется при проектировании специализированных ЦВМ, где арифметические операции осуществляются над кодами с небольшим числом разрядов.Формула изобретенияУстройство для умножения и-разрядных чисел, содержащее (п+2) -разрыдные регистры множимого, множителя и переносов, блок анализа множителя, триггер инверсной передачи множимого, (п+4) -разрядный регистр частичных произведений, сумматор, состоящий из (п+2)-х основных и двух дополнительных разрядов, причем выходы регистра множимого подвключены к первым входам основных разрядов сумматора, выходы суммы которых подключены к входам регистра частотных произведений, выходы переносов 1-тых основных разрядов сумматора соединены (1+1)-ыми входами регистра переносов (1=1 - :(п - 1), (и+1), выход переноса первого дополнительного разряда сумматора соединен с первым входом второго дополнительного разряда, сумматора, выход переноса второго дополнительного разряда сумматора соединен с входом первого разряда регистра переносов, выход которого соединен со вторым входом первого дополнительного разряда сумматора, а выходы суммы первого и второго дополнительных разрядов сумматора соединены со старшими разрядами регистра множителя, отличающееся тем, что, с целью повышения быстродействия, в него дополнительно введены пять элементов ИЛИ, триггер преобразования кода, триггер такта, два блока коммутации, два элемента И, элемент И-НЕ, дополнительный разряд в регистр переносов, третий и четвертый дополнительные разряды в сумматор и два дополнительных разряда в регистр частичных произведений, при этом выходы суммы третьего и четвертого дополнительных разрядов сумматора соединены с входами двух дополнительных разрядов регистра частичных произведений, выход переноса третьего дополнительного разряда сумматора соединен с входом четвертого, дополнительного разряда сумматора, выход переноса которого объединен с входом дополнительного разряда регистра переносов, вход (п + 1)-го разряда регистра переносов соединен с выходом первого элемента И, вход которого соединен с выходом переноса п-го разряда сумматора, выходы первого в :(п+2)-го разрядов первого блока коммутации соединены с третьими входами разрядов сумматора, начиная с первого дополнительного разряда, а выходы (и+3)-го и (п+4)-го разрядов первого блока коммутации соединены с входами первого и второго элементов ИЛИ, выходы которых соединены с входами (п+1)-го и п-го суммтора, вторые входы 1 основных (1=1-;и) и третьего и четвертого дополнительных разрядов сумматора соединены с выходами второго блока коммутации, первая группа информационных входов которого соединена с сортветствующей группой входов первого блока коммутации и подключена к выходам регистра множимого, а вторая группа (п+2) -х информационных входов второго блока коммутации соединена с к-ми входами (к=2+и+ +2) основных и выходом дополнительного разрядов регистра переносов, вторая группа информационных входов первого блока коммутации соединена с выходами регистра частичных произведений, первый вход первого дополнительного разряда сумматора соединен с входами первых четырех элементов ИЛИ и первым входом элемента И - НЕ и подключен к выходу блока анализа множителя, первые управляющие входы блоков коммутации соединены с входом блока анализа и с первым выходом триггера такта, второй выход которого подключен ко вторым управляющим входам блоков коммутации, входам второго элемента И и блока анализа, второй вь ход которого соединен с входами третьего, четвертого и пятого элементов ИЛИ и со вторым входом элемента И - НЕ, соединенного своим выходом с вхо дом первого элемента И, третий выход блоРедактор 3. ШубенкоЗаказ 2221/11ЦНИИПИпо дел13035, Москфилиал ППП П ка анализа соединен с входами третьего элемента ИЛИ и триггера преобразования кода, выход которого соединен с входом пятого элемента ИЛИ, выход третьего элемента ИЛИ соединен с входом триггера инверсной передачи множимого, выход которого соединен с входом второго элемента И, соединенного своим выходом с входами двух старших разрядов сумматора, выходы четвертого и пятого элементов ИЛИ соединены соответственно со входами двух старших и входом третьего дополнительного разрядовсумматора,Источники информации,принятые во внимание при экспертизе1. Дроздов Е. А. МногопрограммныеЦВМ, М., Военное изд-во, 1974.2. Авторское свидетельство СССРМо 281004, кл. 6 06 Р 7/39, 1969.3. Авторское свидетельство СССРМо 357561, кл. Сг 06 Г 7/39, 1970 (прототип).1 О итель Г. Плешев, Шуфрич Корректор Н51 Подписноекомитета СССРи открытийшская наб., д. 4/5од, ул. Проектная, 4