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

СОЮЗ СОВЕТСКИХСОЦИАЛИСТИЧЕСКИРЕСПУБЛИК 07481 1)5 606 Р РЕТЕНИ ОСУДАРСТВЕННОЕ ПАТЕНТН ВЕДОМСТВО СССРГОСПАТЕНТ СССР) ПИСАНИЕ И АВТОРСКОМУ СВИДЕТЕЛЬСТВУ(71) Научно-исследовательский институт электронных вычислительных машин (72) А,А.Шостак и В.В.Яскевич(56) Авторское свидетельство СССР М 763897, кл, 6 06 Р 7/52, 1978.Авторское свидетельство СССР . М 754412, кл, 6 06 Р 7/52, 1970,(54) УСТРОЙСТВО ДЛЯ УМНОЖЕНИЯ (57) Изобретение относится к вычислительной технике и может быть использовано и ри разработке быстродействующих устройств умножения чисел, удобных для изготовления с применением БИС и СБИС, Цель изоИзобретение относится к вычислительной технике и может быть использовано при разработке быстродействующих устройств умножения чисел, представленных в любой позиционной системе счисления,Цель изобретения - повышение быстродействия за счет сокращения длительности такта.Поставленная цель достигается тем, что в устройство для умножения, содержащееи одноразрядных узлов умножения (и - разрядность множимого), и комбинационных сумматоров первой группы, и + 1 комбинационных сумматоров второй группы и и+ 1 регистров промежуточного результата, причем вход множителя -го одноразрядного узла умножения ( = 1, , и) соединен с входом множителя устройства, вход множимого - с 1-м разрядом входа множимого устройства,бретения - повьшение быстродействия уст- ройства за счет сокращения длительности такта. Устройство содержит и одноразрядных узлов умножения (и - разрядность множимого), и комбинационных сумматоров первой группы,(п+ 1) комбинационных сумматоров второй группы, (п + 1) регистров промежуточного результата и нововведенные и триггеров переноса и (и -1) коммутаторов, введение которых позволило организовать вычислительный процесс так, что возникающие в каждом такте переносы не распространяются через всю цепь сумматоров, а запоминаются в соответствующих триггерах переноса, чем уменьшается длительность такта работы устройства. 2 ил,выход младшего разряда )-го одноразрядного узла умножения ( = 2, и) соединен с входом первого слагаемого 0 - 1)-го комбинационного сумматора первой группы, выход суммы 1-го комбинационного сумматора первой группы соединен с входом первого слагаемого ( + 1)-го комбинационною сумматора второй группы. выход суммы М-го комбинационного сумматора второй группы (1 = 1, ., и + 1) соединен с входом 1-го регистра промежуточного результата, выход младшего разряда первого одноразрядного узла умножения соединен с входом первого слагаемого первого комбинационного сумматора второй группы, вход второго слагаемого которого соединен с выходом второго регистра промежуточного результата, вход переноса второго комбинационного сумматора второй группы соединен с выходом переноса первого комбинационногосумматора второй группы, выход первогорегистра промежуточного результата подключен к первому выходу устройства, входконстанты которого соединен с входом первого слагаемого и-го комбинационного сумматора первой группы, вход второгослагаемого которого соединен с выходомстаршего разряда и-го одноразрядного узлаумножения, второй выход устройства соединен с выходами регистров промежуточногорезультата со второго по и-й. введены итриггеров переноса и и - 1 коммутаторов,.причем выход старшего разряда 1-го одноразрядного узла умножения (с = 1 п - 1) 15соединен с входом второго слагаемого (1 +1)-го комбинационного сумматора второйгруппы, выход переноса которого соединенс входом 1-го триггера переноса и первыминформационным входом 1-го коммутатора, 20второй информационный вход которого соединен с выходом переноса 1-го комбинационного сумматора первой группы, входвторого слагаемого которого соединен с выходом (1 + 2)-го регистра промежуточного 25результата, вход переноса 1-го комбинационного сумматора первой группы соединенс выходом 1-го триггера переноса, вход и-готриггера переноса соединен с выходом (и+1)-го комбинационного сумматора второй 30группы, вход второго слагаемого (и + 1)-гокомбинационного сумматора второй группысоединен с входом коррекции устройства,управляющий вход которого соединенс управляющим входом т-го коммутатора, выход 35которого соединен с входом переноса (т +2)-го комбинационного сумматора второйгруппы.Заявляемое устройство содержит следующие отличительные признаки, не обнаруженные ни в одном из известныханалогичных устройств:. 1) оно дополнительно содержит и триггеров переноса и и - 1 коммутаторов;2) выходы переноса комбинационных 45сумматоров второй группы соединены спервыми информационными входами соответствующих коммутаторов и входами соответствующих триггеров переноса, выходыкоторых соединены с входами переноса соответствующих комбинационных сумматоров первой группы;3) выходы старшего разряда одноразрядных узлов умножения соединены с входами второго слагаемого соответствующих 55комбинационных сумматоров второй группы, а выходы регистров промежуточного результата - с входами второго слагаемогосоответствующих комбинационных сумматоров первой группы,В результате в предлагаемом устройс. ве возникающие в каждом такте переносы не распространяются через всю цепь сумматоров, а запоминаются в соответствующих триггерах переноса, чем уменьшается длительность такта работы устройства, Кроме того, если одноразрядные узлы умножения реализованы так, что младшая цифра разрядного произведения формируется быстрее, чем старшая (это возможно при комбинационной структуре одноразрядных узлов умножения), то третий отличительныйпризнак обеспечивает параллельное формирование результатов комбинационныхсумматоров первой группы и старшей цифры произведения одноразрядных узлов умножения, чем также сокращается длительность такта работы устройства,Таким образом, в заявляемом техническом решении имеются отличительные признаки, обеспечивающие достижение поставленной цели и не обнаруженные ни в одном другом известном аналогичном техническом решении, поэтому оно соответствует критерию "существенные отличия",На фиг, 1 приведена структурная схема предлагаемого устройства для умножения; на фиг, 2 - функциональная схема коммутатора,Предлагаемое устройство для умножения содержит и одноразрядных узлов 1 умножения (и - разрядность множимого), и комбинационных сумматоров 2 первой группы, и + 1 комбинационных сумматоров 3 второй группы, и+ 1 регистров 4 промежуточного результата, и триггеров 5 переносаи и - 1 коммутаторов 6, входы 7, 8, 10 и 11множителя. множимого, константы, коррекции и управляющий устройства соответственно. первый 12 и .второй 13 выходы устройства. Вход множителя -го узла 1 ( =1, , и) соединен с входом 7 устройства, вход множимого - с -.м разрядом. входа 8 устройства, выход 15 младшего разряда )-го узла 1= 2, и) соединен с входом первогослагаемого О -1)-го сумматора 2, вход второго слагаемого которого соединен с выходом 22 Ц + 2)-го регистра 4, выход 14 старшего разряда с-го узла 1(1= 1, , и -1) соединен с входом второго слагаемого (с+ 1)-го сумматора 3, выход 19 переноса которого соединен с входом 1-го триггера 5 и первым информационным входом 1-го коммутатора 6, второй информационный вход которого соединен с выходом 16 переноса т-го сумматора 2, выход 17 суммы -го сумматора 2соединен с входом первого слагаемого ( + 1)-го сумматора 3, выход 20 суммы -го сумматора 3 (К = 1, , и + 1) соединен с входом к-го регистра 4, выход 15 первого узла 1ме условно не показаны цепи синхрониза- с соединен с входом первого слагаемого первого сумматора 3, вход второго слагаемого которого соединен с выходом 22 второго регистра 4, вход переноса второго сумматора 3 соединен с выходом 19 переноса пер ваго сумматора 3, выход 20 суммы которого соединен с входом первого регистра 4, вы. ход 22 которого подключен к первому выходу 12 устройства, вход 19 константы которого соединен с входом первого слага емого и-го сумматора 2, вход второго слагаемого которого соединен с выходом 14 и-го узла 1, вход второго слагаемого (и + 1)-го сумматора 3 соединен с входом .10 коррекции устройства, управляющий вход 11 кото рого соединен с управляющим входом 1-го коммутатора 6, выход 21 которого соединен с входом переноса (с + 2)-го сумматора 3, выход 19 переноса (и + 1)-го сумматора 3" соединен с входом (и - 1)-го триггера 5, вы ход 18 которого соединен с входом переноса п-го сумматора 2, выходы 22 регистров 4 со второго по п-й подключены ко второму выходу 13 устройства.Рассмотрим функциональное назначе ние и реализацию узлов и блоков предлагаемого устройства.Узлы 1 комбинационного типа предназначены для вычисления произведения соответствующих разрядов сомножителей и 30 могут быть реализованы любыми известными. способами.Сумматоры 2 и 3 комбинационного типа предназначены для вычисления разрядов сумм частичных произведений сомиожите лей, Они могут быть реализованы любым известным способом, например в виде сумматора с параллельным переносом.Регистры 4 предназначены для хранения информации, формируемой на выходах 40 20 суммы соответствующих сумматоров 3, и могут быть реализованы. на синхронных двухтактных О-триггерах с входами установки в нулевое состояние.Триггеры 5 предназначены для хране ния переносов, возникающих при работе сумматоров 3, и могут быть реализованы на синхронных двухтактных О-триггерах с входами установки в нулевое состояние,Коммутаторы 6 предназначены для пе редачи информации на выходы 21 (входы переноса сумматоров 3) со своих первого и второго информационных входов (выходов 19 и 16 переноса соответственно сумматоров 3 и 2) в зависимости от сигнала на их 55 управляющих входах (входе 11 устройства). Они могут быть реализованы на элементах 2 И 23 - 2 ИЛИ 24, как показано на фиг. 2, В целях упрощения на структурной схеции и установки в нулевое состояние регистров 4 и триггеров 5 устройства, однако можно отметить, что имеется общая цепь синхронизации и общая цепь установки в ,нулевое состояние регистров 4.и триггеров 5,Устройство для умножения работает следующим образом.В исходном состоянии регистры 4 и триггеры 5 обнулены, на входе 8 устройства присутствует без знака и-разрядный 2 -ич 1( ный код множимого (пк - разрядный двоичный код множимого), Предполагается, что множимое и множитель представлены в двоично-кодированной 2 -ичной системексчисления, т.е. каждый разряд как множи-. мого, так и множителя представляет собой набор из 1 двоичных цифр, На вход 9 устрой-. ства подана нулевая константа, а на вход 11 устройства - сигнал, настраивающий коммутаторы 6 на передачу информации только с их вторых информационных входов (с выходов 16 сумматоров 2). Умножение в устройстве осуществляется за и + 1 тактов,В каждом из и первых тактов работы устройства на его вход 7 поступает один 2 К-ичный разряд множителя (параллельно К двоичных разрядов), При этом на выходах 14 и 15 -го узла 1 формируются соответственно старший и младший разряды двухразрядного произведения соответствующего разряда множителя, поступающего на его вход множителя с входа 7 устройства, на 1-й разряд множимого, поступающий на его вход множимого с -го разряда входа 8 устройства. Младший разряд произведения /- го угла 1 Д = 2, . и) поступает на вход первого слагаемого Д - 1)-го сумматора 2, а младший разряд произведения первого узла 1 - на вход первого слагаемого первого сумматора 3. Эти младшие разряды суммируются с соответствующими разрядами суммы частичных произведений, сформи рован ными в и редыдущем такте и хранимыми в ссответствующих регистрах 4. В сумматорах 2, кроме того, подсуммируются соответствующие разряды переносов, сформированные в предыдущем такте нэ выходах 19 сумматоров 3 и хранимые в соответствующих триггерах 5. С выхода 17 1-го сумматора 2 (1 = 1, , и - 1) разряд суммы поступает на вход первого слагаемого (1 + 1)-го сумматора 3, где суммируется с поступающим на его вход второго слагаемого старшим разрядом произведения 1-го узла 1 и поступающим на его вход переноса разрядом переноса соответствующего сумматора 2 (для второго сумматора 3 на вход переноса поступает информация с выхода 19 переноа первого сумматора 3), сформированного10 задержку гумн = 70 нс 20 30 35 результата (астр); т,е 40 45 50 55 в этом же такте на выходе 16 соответствующего сумматора 2, В и-м сумматоре 2 к старшему разряду произведения и-го узла. 1 подсуммируется нуль с входа 9 устройства и разряд переноса (и + 1)-го сумматора 3, сформированный в предыдущем такте и хранимый е и-м триггере 5. По окончании каждого такта с выходов 19 и 20 сумматоров 3 в соответствующие триггеры 5 и регистры 4 записываются разряды суммы частичных произведений сомножителей в двухрядном коде.После выполнения и первых идентичных тактов работы устройства нэ его вход 7 множителя поступает нулевая информация, 1 а на его вход 11 - сигнал, настраивающий коммутаторы 6 на передачу информации с их первых и вторых информационных входов (с выходов 19 сумматоров 3 и выходов 16 сумматоров 2) и далее осуществляется еще один такт, в течение которого в сумматорах 2 и 3 суммируется информация, хранимая в соответствующих регистрах. 4 и триггерах 5. Следует отметить, что на выходах 16 и 19 переносов сумматоров 2 и 3 е 2 этом такте переносы не могут возникнуть одновременно, Это позволяет упростить структуру коммутаторов б и осуществить формирование однорядного кода произведения в течение одного такта.Вывод и+ 1 младших 2 -ичных разрядов(2 и-разрядного произведения в устройстве осуществляется через его выход 12 по одному разряду в каждом такте работы устройства, вывод и - 1 старших 2 -ичных разрядовпроизведения - через выход 13 в (и + 1)-м такте работыустройства.В рассматриваемом случае на вход 10 устройства во всех и + 1 тактах его работы подавалась нулевая инфорМация. Если же требуется подсуммировать к вычисляемому произведению дополнительные слагаемые, . например, при округлении или при введении коррекции по знакам множимого и множителя при умножении чисел, представленных в дополнительном коде, то необходимо подать на соответствующий вход 10 требуемую информацию, что обеспечит подсуммирование без дополнительных временных затрат.Произведем сравнение предлагаемого устройства и устройства-прототипа по быстродействию выполнения операции умножения 14-разрядных 2 -ичныхксомножителей (56-разрядных двоичных сомножителей, т.е. и = 14, 1 = 4)Пусть регистры промежуточного результата сравниваемых устройств и триггеры переноса предлагаемого устройства реализованы на микросхемах типа К 555 ТМ 8, представляющих из себя 4 синхронных О-триггера с входами установки в нулевое состояние, имеющие задержку ттр = 28 нс.Пусть для реализации одноразрядных узлов 1 умножения используются ПЗУ типа 556 РТ 5 емкостью 512 л 8. В этом случае на одной микросхеме можно построить 4-разрядный двоичный умножитель, имеющий Пусть комбинационные сумматоры первой и второй групп реализованы на 4-разрядных сумматорах с ускоренным переносом типа К 555 ИМ 6, имеющим следующие величины задержек;. а) от входа до выхода переноса тс 1 = 17 нс; б) от входа до ВЫХОДа СУММЫ тс 2 = 24 НС,Пусть коммутаторы. предлагаемого устройства реализованы на микросхемах К 555 КП 11, представляющих из себя четыре двухвходовых мультиплексора с задержкой тк = 18 нс, Длительность такта работы известного устройства складывается из задержки на одноразрядном узле умножения умн),задержки на комбинационных сумматорах первой группы, включающей время на формирование сигнала переноса е первом сум- МатОРЕ (тс 1), ВРЕМЯ На РаСПРОСтРаНЕНИЯ переноса через исумматоров и время на формирование значения суммы в и-м сумматоре (1 с 2), задержки на комбинационных сумматорах второй группы, равной времени на формирование значения суммы е (и+ 1)-м СУММатОРЕ (1 с 2), ПОСКОЛЬКУ ОСтаЛЬНЫЕ И КОМбинационных сумматоров второй группь; работают параллельно с и комбинационными сумматорами первой группы, а также задержки на запись суммы частичных произведений в регистры промежуточного т =1 умн+1 с 1+(И) Сс 1+ с 2+ Сс 2+ астр ==70 + 17 и + 7) + 24 + 22 = 17 и + 123.(нс). При и = 56/4 = 14 длительность такта работы известного устройства составляет с" = 17 т:14+ 123 = 361 (нс). Произведение формируется за п тактов, поэтому время выполнения операции умножения 56-разрядных сомножителей равно: Ти" = 1 Ф и = 361114 = 5054 (нс),Для реализации известного устройства требуется 14 микросхем 556 РТ 5 (одноразрядные узлы умножения), 29 микросхем К 555 ИМ 6(комбинационные сумматоры первой и второй групп) и 15 микросхем К 555 ТМ 8 (регистры промежуточного результата), т.е. всего 58 микросхем,10 1807481 формирования результатов комбинационных сумматоров первой группы и старшей цифры произведения одноразрядных узлов умножения. Следует особо отметить, что аппаратурные затраты на реализацию предлагаемого устройства возросли всего на 14 о/ т.е. предложенное техническое решение явДлительность каждого из п первых тактов работы предлагаемого устройства скла.дывается из задержки на одноразрядном узле умножения (сумн), задержки на комбинационном сумл 1 аторе первой группы от его входа до его выхода переноса (сс 1), задержки на коммутаторе (тк), задержки на формирование суммы в комбинационном сумматоре второй группы (та), а также задержки на запись суммы частичных произведений в регистры промежуточного результата и триггеры переноса (астр), т.е. ляется высокоэффективным. Технико-экономическое преимущество 10 предлагаемого устройства для умножения в сравнении с известным заключается в его более высоком быстродействии (при вычислении произведения 56-разрядных двоичных сомножителей с использованием Сп р =гумн+ тс 1+1 к+ сс 2+Стр =70+ 17++ 18 + 24 + 22 = 151 (нс). 4-разрядных узлов и блоков предлагаемое устройство имеет в 1,9 раза выше быстро 15 Длительность (и + 1)-го такта определяется задержкой на формирование суммы в комбинационных сумматорах первой группы (1 с 2), (одновременно работает первый комбинационный сумматор второй группы), задержкой на распространение переноса через и - 2 комбинационных сумматоров второй группы (1 С 1) и и - 2 коммутаторов (1,), задержкой на формирование суммы в и-м комбинационном сумматоре второй группы (та), а также задержки на запись и старших разрядов произведения в регистры промежуточного результата (ьр), т,е. действие, чем известное) Формула изобретенияУстройство для умножения, содержащее и одноразрядных узлов умножения (и - разрядность множимого), и комбинационных сумматоров первой группы, (и+ 1) комбинационных сумматоров второй группы и 20(и+ 1) регистров промежуточного результа 25 30 та, причем вход множителя -го одноразрядного узла умножения ( = 1, ,. и) соединен с входом множителя устройства, вход множимого -го одноразрядного узла умножения соединен с входом 1-го разряда множимого устройства, выход младшего разряда 1-го оп+1 = 1 с 2 + (и - 2)с 1 + (и - 2)1 к + 1 с 2 + +1 тр = 24+ 17 и - 34+ 18 и - 36 + 24+ 22 = 35 и (нс),одноразрядного узла умножения (1 = 2,и) соединен с входом первого слагаемого О)-го комбинационного сумматора. первой группы, выход суммы -го комбинационного Время выполнения операции умножения 56-разрядных сомножителей (и = 14) равно: . сумматора первой группы соединен с вхо 35 дом первого слагаемого(+1)-го комбинационнсго сумматора второй группы, выход суммы К-го комбинационного сумматора зультата, выход младшего разряда первого Для реализации предлагаемого устройства требуется 14 микросхем 556 РТ 5 (одноразрядные узлы умножения), 29 микросхем К 555 ИМ 6 (комбинационные сумматоры первой и второй групп), 19 микросхем К 555 ТМ 8 (регистры промежуточного результата и триггеры переноса) и 4 микросхемы К 555 КП 11 (коммутаторы), т.е. всего 66 микросхем.Таким образом, быстродействие в предлагаемом устройстве будет в Тиз/ТлРедл = =5054/2601 = 1,9 раза выше, чем в известном, Следует отметить, что выигрыш в быстродействии будет еще более значительным при реализации одноразрядных узлов умножения в виде комбинационных схем, в которых младшая цифра произведения разрядов сомножителей формируется быстрее, чем старшая, за счет параллельного одноразрядного узла умножения соединен с входом первого слагаемого первого комбинационного сумматора второй группы, вход второго слагаемого которого соединен 45 с выходом второго регистра промежуточного результата, вход переноса второго комбинационного сумматора второй группы соединен с выходом переноса первого кол 1- бинационного сумматора второй группы, выход первого регистра промежуточного результата подключен к первому выходу ус 50 тройства, вход. константы которого соединен с входом первого слагаемого и-го комбинационного сумматора первой группы, вход второго слагаемого которого.сое 55 динен с выходом старшего разряда и-го однораэрядно;о узла умножения, второй выход устройства соединен с выходами регистров промежуточного результата с втоТ"ред" = Ь и + Ь+1 "ред" = 151 л 14+ второй группы (К =. 1, , и + 1) соединен с1807481 . 12 фи 8, 2рректор Н.Гуньк итель А.ШостакМ. Моогентал Со Те Редактор Заказ 1381 Тираж Подписное ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СС 113035, Москва, Ж, Раушская наб 4/5 оизводственно-издательский комбинат "Патент", г. Ужгород, ул.Гагарина. 101 рого по и й, Отл и ч а ю ще е с я тем, что, с целью повыаения быстродействия устройства. в него введены и триггеров переноса и Й - 1 кОммутаторов, причем ВыхОд старшего разряда 1-ГО ОднОразряднОго узла умнОжения (1 = 1,и - 1) соеДинен с ВХОДОМ второго слагаемого ", + 1)-го комбинационного сумматора второй группы, выход переноса которого соединен с входом т-го триггера переноса и первым информационным входом 1-го коммутатора, второй информационный вход которого соединен с выходом переноса т-го комбинационного сумматора первой группы, Вход второго слагаемого которого соединен с выходом ( + 2)-го регистра промежуточного результата, вход переноса -го комбинационного сумма 1 ора первой группы соединен с выходом 1-го 5 тригтера переноса, вход первого триггера переноса соединен с выходом (и+ 1)-го комбинационного сумматора второй группы, вход второго слагаемого (и + 1)-го комбинационного сумматора второй группы соеди нен с входом коррекции устройства, управляющий вход которого соединен с управляющим входом 1-го коммутатора, выход которого соединен с входом переноса(1+ 2)-го комбинационного сумматора второй группы. О