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

СОЮЗ СОВЕТСНИХСОЦИАЛИСТИЧЕСНИХРЕСПУБЛИК 3(59 6. 06 Р 7/52 ОПИСАНИЕ ИЗОБРЕТЕНИЯИ АВТОРСКОМУ СВИДЕТЕЛЬСТВУ ГосудАРственный Комитет сссрПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ(56) 1, Авторское свидетельство СССРВ 482740, кл. С 06 Р 7/52, 1973.2. Авторское свидетельство СССРУ 993255, кл. С 06 Р 7/52, 1981.3. Авторское свидетельство СССРУ 1022155, кл. С 06 Р 7/52, 1981(54)(57) УСТРОЙСТВО ДЛЯ УМНОЖЕНИЯ. и-РАЗРЯДНЫХ ЧИСЕЛ, содержащее й -разрядный регистр множимого и и-разряд" ный регистр множителя,(и+21-разрядный регистр утроенного множимого, 2 Н -разрядный накапливающий сумматор, первую группу из 2 -4 элемен-тов ИЛИ, вторую группу из и/2 элемен. тов ИЛИ, первую группу из п/2 элементов И, группу и/2 дешифраторов и 1 и +2 коммутаторов, причем первые, вторые и третьи информационные входы коммутаторов соединены соответственно с разрядными выходами и-разрядного регистра множимого и и+2 - разрядного регистра утроенного мно" жимого, выходы (2 и в .4)элементов ИЛИ первой группы соединены соответственно с разрядными входами с третьего по (2 и -2) -й 2 и -разрядного накапливающего сумматора, выходыкаждой пары разрядов-разрядного регистра множителя соединены с пер 1вым и вторым входами соответствующего элемента ИЛИ второй группы и с первым и вторым входами соответствующего дешифратора, вход разрешения записи О -разрядного регистрамножителя соединен с тактовымвходом О -разрядного накапливающегосумматора и тактовым входом устройства, о т л и ч а ю щ е е с я тем,что, с целью сокращения аппаратурных затрат, устройство содержитматрицу из (и/2 +и 1 элементов И,содержащую 11/2. строк и(и+2) столбцов, блок выделения младшего значащего разряда содержащий первый, второй и третий элементы И, вторуюгруппу из и /2 элементов И, первыйи второй элементы ИЛИ, элемент КЛИНЕ, причем выходы коммутаторов соединены соответственно с первымивходами элементов И столбцов матри"цы, вторые входы элементов И первойстроки матрицы соединены с прямымвыходом первого элемента ИЛИ второйгруппы, вторые входы элементов Ивторой и третьей строк матрицысоединены с выходами соответственно первого и вторрго элементов Иблока выделения младшего значащегоразряда, входы м "го элемента ИЛИпервой группы соединены с выходами(К+2- 2 (ъ - 1)-х элементов И 1-хстрок матрицы, выходы первого,второго элементов И первой строкиматрицы и(и+1) -гои (и+2) -го элементов И последней строки матрицысоединены соответственно с первым,вторым,(2 и - 1)-м и 2 и -м разряднымивходами накапливающего сумматора,первые выходы и/2 дешифраторов соединены соответственно с первыми входами элементов И первой группы, вторыевыходы дешифраторов соединены соответственно с первыми входами элементов И второй группы, вторые входыэлементов И первой и второй группсоединены соответственно с прямымвыходом первого элемента ИЛИ второйгруппы и выходами первого и ьторогоэлементов И блока выделения младшегозначащего Разряда и с входами установки в ноль П/2 пар разрядовб"разрядного регистра множителя,выходы элементов И первой группысоединены с входами первого элементаИЛИ, выходы элементов И второй группысоединены с входами второго элементаИЛИ, выход первого элемента ИЛИ соединен с первым входом элемента ИЛИНЕ и с первыми управляющими входамикоммутаторов, выход второго элемента ИЛИ соединен с вторым входом эле"мента ИЛИ-НЕ и с вторыми управляющими входами коммутаторов, выходэлемента ИЛИ-НЕ соединен с третьимиуправляющими входами коммутаторов,прямые выходы второго и третьегоэлементов ИЛИ второй группы соединены соответственно с первыми входамипервого и второго элементов И блокавыделения младшего значащего разряда, вторые входы первого и второгоэлементов И и первый вход третьегоэлемента И блока выделения младшегозначащего; разряда соединены с инверсным выходом первого элемента ИЛИвторой группы, инверсный. выход вто- Фрого элемента ИЛИ второй группы соединен с третьим входом второго элемента И и вторым входом третьего элеМента И блока выделения младшегозначащего: разряда, третий входтретьего:элемента И которого соединен с инверсным выходом третьегоэлемента ИЛИ второй группы, выходтретьего элемента И блока выделениямладшего значащего разряда соединен свыходом окончания умножения устройства.Изобретение относится к вычислительной технике и может быть использовано при разработке быстродействую щих устройств. умножения асинхронного типа.Известно устройство для умножения о-разрядных чисел, содержащее й-разрядные регистры множимого и множителя, 2 о -разрядный накапливающий сумматор, матрицу иэ о-элементов И, (2 о -3) -разрядный блок элементов ИЛИ и два о -разрядных блока элементов И. Умножение двух чисел в этом устройстве выполняется в среднем за .и/2 тактов 1.1Недостатком данного устройства является низкое быстродействие как из-за большого числа его тактов работы, так и из-за большой длительности тактапоскольку длительность такта работы определяется временем переходного процесса в блоке элементов И, образующих последовательную цепь.Известно также устройство для умножения й -разрядных чисел, содержащее-разрядные регистры множимого и множителя, 2 -разрядный накапливающий и и-разрядный комбинационный сумматоры, матрицу изэлементов И, 1 2 и -3 - разрядный блок элементов ИЛИ и о -разрядный блок эле 5 ментов И. В этом устройстве умножение двух чисел также производитсяв среднем за и /2 тактов Г 23.Недостатком этого устройства является его.относительно низкое быст 10 родействие из-за большого числа,тактов работы,Наиболее близким по техническойсущности к.предлагаемому являетсяустройство для умножения И -разряд 15 ных чисел, содержащее 11 -разрядныерегистры множимого и множителя,(О +21-разрядный регистр утроенногомножимого, 2 -разрядный накапливающий сумматор, первый (2 и -41 -раз 20 рядный и второй 1/2-разрядный блокиэлементов ИЛИ, о /2-разрядный блокэлементов И, /2-разрядный блокдешифраторов и (и+21-разрядный блоккоммутирующих узлой, причем вторые25 и третьи информационные входы коммутирующих узлов блока соединены соответственно с разрядными выходамирегистров множимого и утроенногомножимого, выходы элементов ИЛИпервого блока соединены соответственно с разрядными входами с третьегопо(2 и -2) -й накапливающего сумматора,выходы каждой пары разрядов регистрамножителя соединены с первым и вторымвходами соответствующего .элементаИЛИ второго блока и с первым ивторым входами соответствующегодешифратора блока, вход разрешениязаписи регистра множителя соединенс управляющим входом накапливающегосумматора и с шиной синхронизации,устройства. Умножение двух чиселвыполняется.в среднем за Зи/8 тактов 131.Недостатком известного устройстваявляются большие аппаратурные затраты при его реализации,Цель изобретения - сокращениеаппаратурных затрат при реализацииустройства.Поставленная цель достигается тем, что в устройство для умножения И-разрядных чисел, содержащее и -разрядный регистр множимого и И -разрядный регистр множителя,(и +21 -разрядный регистр утроеНного множимого, 2 и -разрядный накапливающий сумматор, первую группу иэ (2 и -41 элементов ИЛИ,вторую группу из и/2 элементовИЛИ, первую группу из И/2 элементов И, группу 11/2 дешифраторов и (и+2) коммутаторов, причем первые, вторые и третьи информационные входы коммутаторов соединены соответственно с разрядными выходами и -разрядного регистра множимого и(и+2 -разрядного регистра утроенного множимого, выходы (2 пэлементов ИЛИ первой группы соединены соответственно с разрядными входами с третьего по(2 и -2)-й 2 и -разрядного накапливающего сумматора, выходы каждой пары разрядов И-разрядного регистра множителя соединены с первым и вторым входами соответствующего элемента ИЛИ второй группы и с первым и вторым входами соответствующего дешифратора, вход разрешения записи И -разрядного регистра множителя соединен с тактовым входом 2 И -разрядного накапливающего сумматора и тактовым входом устройства, введены матрица из (и(2+ И )элементов И, содержащая И/2 строк и(И+2) столбцов, блок выделения .младшего значащего разряда, содержащий. первый, второй и третий элементы И, вторая группа из и /2 элементов И, 1 О 15 и ( 1 ъ +21-го элементов И последнейстроки матрицы соединены соответственно с первым, вторым, (2 и-ми 2 и -м разрядными входами накапливающего сумматора, первые выходыи/2 дешифраторов соединены соответственно с первыми входами элементовИ первой группы, вторые выходы дешифраторов соединены соответственнос первыми входами элементов И второйгруппы, вторые входы элементов Ипервой и второй групп соединены соответственно с прямым выходом первого элемента ИЛИ второй группы и выходами первого и второго элементовИ блока выделения младшего значащегоразряда и с входами установки вноль и/2 пар разрядов и -разрядногорегистра множителя, выходы элементовИ первой группы соединены с входамипервого элемента ИЛИ, выходы элементов И второй группы соединены с входами второго элемента ИЛИ, выходпервого элемента ИЛИ соединен спервым входом элемента ИЛИ-НЕ и спервыми управляющими входами коммутаторов, выход второго элемента ИЛИсоединен с вторым входом элементаИЛИ-НЕ и с вторыми управляющимивходами коммутаторов, выход элемента ИЛИ-НЕ соединен с третьими управляющими входами коммутаторов, прямыевыходы второго и третьего элементовИЛИ второй группы соединены соответственно с первыми входами первогои второго элементов И блока выделения младшего значащего разряда,20 25 30 35 40 45 50 55 вторые входы первого и второго элементов И и первый вход третьего элемента И блока выделения младшего значащего разряда соединены с инверсным выходом первого элемента первый и второй элементы ИЛИ, элемен ИЛИ-НЕ, причем выходы коммутаторов соединены соответственно с первыми входами элементов И столбцов матрицы, вторые входы элементов Ипервой строки матрицы соединены с прямым выходом первого элемента ИЛИ второй группы, вторые входы элементов И второй и третьей строк матрицы соединены с выходами соответственно первого и второго элементов .И блока выделения младшего значащего разряда, входы к-го элемента 11 ЛИ первойгруппы соединены с выходами (к+2 -21-х элементов И(-х строк матрицы, выходы первого, второго элементов И первой строки матрицы и (и+11 - гоИПИ второй группы, инверсный выходвторого элемента ИЛИ второй группысоединен с третьим входом нторогоэлемента И и вторым входом третьегоэлемента И блока выделения младшегозначащего разряда, третий входтретьего элемента И которого соединен с инверснь 1 м выходом третьегоэлемента ИЛИ второй группы, выходтретьего элемента И блока выделениямладшего значащего разряда соединенс выходом окончания умножения устройства. 1 О 45 На фнг. 1 приведена структурная 15 схема устройства для умножения й - разрядных чисел для случая и =6; на фиг. 2 - функциональная схема . блока выделения младшего значащего разряда; на фиг. 3 - функциональная 20 схема коммутатора.УстройстВо содержит 6-разрядный регистр 1 множимого, 6-разрядный регистр 2 множителя, 8-разрядный регистр 3 утроенного множимого, 25 12-разрядный накапливающий сумматор 4, первую группу 5 из восьми элементов ИЛИ 6, вторую группу 7 из трех элементов ИЛИ 8-8 , группу 9 из восьми коммутаторов 1 О, матрицу 11 ЗО из 24 элементов И 12, группу 3 из трех дешифраторов 4, - 14, первую 3-разрядную группу 15 элементов И, вторую 3-разрядную группу 6 элементов И, первый элемент ИЛИ 17, второй элемент ИЛИ 18, элемент ИЛИ-НЕ 19, блок 20 выделения младшего значащего разряда, выход 21 индикации окон.чания операции умножения и шину 22 синхронизации, причем первые инфор О мационные входы первых шести коммутаторов 10 группы 9 соединены с соответствующими разрядными выходами регистра 1 множимого, вторые информационные входы коммутаторов 1 О с второго по седьмой соединены соответственно с разрядными выходами регистра 1 множимого, третьи информационные входы коммутаторов 10 с первого по восьмой группы 9 соединены соответственно с разрядными ныходами регистра 3 утроенного множимого, управляющие входы коммутаторов 10 группы 9 соединены с ее шиной управления, выходы коммутаторов 10 . соединены соответственно с первой55 группой входов матрицы 11 элементов И 12, выходы 3-101 -го разрядон кото-рой соединены соответственно с входами элементов ИЛИ 6 группы 5, выходы 1,2,11 и 12-го разрядов матрицы 11 элементов И 12 соединены соответственно с 1,2,1 и 12-м разрядными входами накапливающего суммато" ра, 4, выходы каждой из трех пар разрядов регистра 2 мноЖителя соеди" иены с первым и вторым входами соответствующего элемента ИЛИ 84 -8 группы 7 и с первым и вторым входами соответствующего. дешифратора 14 н) первые выходы дешифраторон 144- 14 соединены соответственно с первыми входами элементов И 15, вторые выходы дешифраторов 14 - 14 Зсоедине-, ны соответственно с первыми входами элеменгов И 16, выходы элементов И 15 соединены с входами первого элемента ИЛИ 17, выходы элементов И 16 соединены с входами второго элемента ИЛИ 18, выход первого элемента ИЛИ 17 соединен с первым входом эле-. мента ИЛИ-НЕ 19 и с первым входом шины управления группы 9 коммутаторов 1 О, выход второго элемента ИЛИ.18 соединен с вторым входом элемента ИЛИ-НЕ 19 и с вторым входом шины управления группы 9 коммутаторов 10, выход элемента ИЛИ-НЕ 19 соединен с третьим нходом шины управления группы 9 коммутаторов 10, прямые выходы элементов ИЛИ 8-8 соединены соответственно с первой группой входов блока 20 выделения младшего значащего разряда, вторая группа входон кото" рого соединена соответственно с ин-. версными выходами элементов ИЛИ 8) - 8, выходы блока 20 выделения младшего значащего разряда соединены соответственно с второй группой входов матрицы 11 элементов И 12, с входами установки в ноль трех пар разрядов регистра 2 множителя и с вторыми входами элементов И 5 и 16, выход П блока 20 выделения младшеФго значащего разряда является выходом 21 индикации окончания опера-. ции умножения, вход разрешения записи регистра 2 множителя соединен с управляющим входом накапливающего сумматора 4 и с шиной 22 синхронизации устройства. Блок 20 выделения младщего знача. щего . разряда предназначен для последовательного выделения единиц из 3-разрядного двоичного кода А= аЬ, а, а, начиная с его млад - ших разрядов, и сформированногона прямых выходах элементов ИЛИ 18 -85(здесь и далее возрастание индексов при буквенных обозначениях принято в направлении старших разря" дов). Блок 20 содержит(фиг, 2) три элемента И 23 - 235 и функционирует в соответствии со следующими логическими выражениями:П 4 = а, П=Сд П=О,С 1 ь, П"=сбригде П П П - признаки вьщеления соответственно первого,второго и третьегозначащих: разрядовдвоичного кода,1,4.П - признак окончания вьщеления значащих Разрядов кода А . Этот вариант построения блока 20 выделения .младшего значащего разряда обладаетисключительновысоким быстродействием, особенно при малых значенияхразрядности обрабатываемой информации. При больших же значенияхиз-за ограниченных возможностей логических элементов целесообразно вблоке 20 использовать принципразбиения его на группы с последо-.вательной либо параллельной. передачей между группами признаков Г 1 окончания выделения значащих разрядовв группах. Это позволяет при существующей элементной базе обеспечитьв большинстве практических случаеввремя вьщеления значащего разряда,не превышающее величину (2-3/)где- задержка сигнала на одномлогическом элементе. Коммутатор 1 -го разряда группы 9 содержит(фиг; 3)три элемента И 244- 245 и элемент ИЛИ 25, причем первые входы элементов И 24 - 245 являются соответственно первым, вторым и третьим информационными входами 1,-го коммутатора(на первый информационный вход подается значение ъ -го разряда регистра 1 множимого Х, на второй информационный вход - значение Я)-го разряда регистра 1 множимого х, т.е. 1, -ый разряд удвоенного множимого 2 Х ,на третий информационный вход поступает значение ъ-го разряда регистра 3 утроенного множимого 3 х), вторые управляющие входы элементов И 24,- 245 соединены соответственно с первым 26 , вторым 26 и третьим 265 выходами шины управления группы 9 коммутаторов 10 (первый выход 261шины управления является выходомпервого элемента ИЛИ 17, второйвыход 26 шины управления - выходом5 второго элемента ИЛИ 18, а третийвыход 26 шины управления - выходомэлемента ИЛИ-НЕ 19)Таким образом, если сигнал логической единицы образуется на выходепервого элемента ИЛИ 17, то группа9 коммутаторов 10 передает соответствующим образом на первуюгруппувходов матрицы 11 элементов И 12одинарное множимое 1 х, если сигнал15 логической единицы образуется на выходе второго элемента ИЛИ 18 - удвоенное множимое 2 )(,если сигнал логической единицы формируется на выходе элемента ИЛИ-НЕ 19, то группа 920 коммутаторов 10 подает соответствующим образом на первую группу входовматрицы 11 элементов И 12 утроенноемножимое 3 х(сигнал логической единицы может образоваться только на25 одном из выходов элементов ИЛИ 17и 18 и элемента ИЛИ-НЕ 19, т.е. либотолько на выходе первого элементаИЛИ 17, либо только на выходе второго элемента ИЛИ 18, или же толькона выходе элемента ИЛИ-НЕ 19 ).Каждый из дешифраторов 144- 4 зможет быть реализован с использованием двух двухвходовых элементов И,причем сигнал логической единицы формируется на его первом выходе тогда,когда значение соответствующей парыразрядов регистра 2 множителя равноединице, и на его втором выходе тогда, когда значение соответствующей4 пары разрядов регистра 2 множителяравно двум.Устройство работает следующимобразом.В исходном состоянии в регистрах45 1 и 2 хранятся без знаков 6-разрядныесоответственно множимое Х и множитель у , в регистре 3 - 8- разрядноеутроенное множимое 3 и (оно можетбыть предварительно сформировано50либо на сумматоре 4, либо с использованием дополнительной комбинационной схемы ), накапливающий сумматор4 обнулен,Детально работу устройства рас511 смотрим на примере умножения;1 ножимогоХна множитель=110001.С учетомэтого в исходном состоянии на первомвыходе дешифратора 14 формируетсясигнал логической единицы, а на прямых выходах элементов ИЛИ 8" 8 образуется двоичный код 4 =101, из которого в блоке 20 осуществляется выделение младшего значащего разряда, что приводит к образованию сиг нала признака П. По этому сигналу на выходе первого элемента ИЛИ 17 формируется сигнал логической едини" цы, который, поступая по шине управления группы 9 на управляющие входы его коммутаторов 10, произво- дит передачу на выходы одинарного множимого 1 , которое далее по" ступает на первую группу входов матрицы 11 элементов И 12 и переда ется с разрешения того же сигнала признака П через первую линейку. элементов И 12 матрицы 11 и элементы ИЛИ 6 с определенным сдвигом на соответствующие информационные входы 20 накапливающего сумматора 4.Собственно работа устройства начинается с момента прихода первого синхроимпульса на шину 22 синхронизации устройстваС разрешения этого 25 синхроиипульса осуществляется установка в ноль первой (самой младшей). пары разрядов регистра 2 множителя по сигналу признака П и производится прием информации в накапливающий сумматор 4 с его информационных входов. По окончании действия первого синхроимпульса на шине 22 устрой.ства одновременно с суммированием в накапливающем сумматоре 4 первого частичного произведения в устройстве выполняются следующие действия: на всех выходах дешифраторов 14 - 14 образуются сигналы логического нуля и одновременно с этим на прямых выходах элементов ИЛИ 81-85 формируется двоичный код А,=100, по которому в дальнейшем на третьем выходе блока 20 выделения младшего значащего; разряда формируется сигнал признака П ; так как на всех выходах дешифраторов 14 в А сформированы сигналы логического нуля, то на выходах первого и второго элементов ИЛИ 17 и 18 также присутству 50 ют сигналы логического нуля, а следовательно, на выходе элемента ИЛИ-НЕ 19 возникает сигнал логической еди-, ницы, который, поступая по шине управления группы 9 на управляющие входы его коммутаторов 10, произво 55 дит передачу на выходы группы 9 утроенного множимого Зф, которое далеепоступает на первую группу входовматрицы 1 элементов И 12; утроенноемножимое 3по сигналу признака Ппередается с определенным сдвигомчерез третью линейкУ элементов И12 матрицы 11 и элементы ИЛИ 6 насоответствующие информационные входынакапливающего сумматора 4. На этомпервый такт работы устройства заканчивается,Во втором такте с разрешения вто"рого синхроимпульса на шине 22синхронизации устройства осуществля-.ется установка в ноль третьей(самойстаршейпары разрядов регистра 2множителя по сигналу признака П ипроизводится прием информации внакапливающий сумматор 4 с его,информационных входов, По окончании действия второго синхроимпульса на шине22 устройства одновременно с суммированием в накапливающем сумматоре4 второго частичного произведенияна прямых выходах элементов ИЛИ8-85 формируется двоичный кодй ==000, по которому,на выходе окончания выделения блока 20 выделениямладшего значащего разряда Формируется сигнал признака П, Этот сигналпоступает на выход 21 устройства,сигнализируя об окончании умножениячисел. Таким образом, умножение в.устройстве двух рассмотренных 6-разрядных чисел выполнено за два такта.В общем же случае умножение двухЮ -разрядных чисел в предлагаемомустройстве, так же как и в известном3 1 выполняется в среднем за 3 и/8тактов, причем длительность тактаопределяется либо временем сложения,6 421-разрядных чисел в накапливающем сумматоре 4, либо задержкойинформации в блоках 5,7,9,15,20, вматрице 11 и на элементах 17 и 19.Технико-экономическое преимущество предлагаемого устройства в сравнении с прототипом состоит.в значительно меньших аппаратурных затратахпри его реализации. Так, например,при =32 в устройстве при его реали-.зации требуется в 1,7 раза меньшеаппаратуры. Скорость же работы пред;лагаемого устройства не ниже скорости работы прототипа,1111,153 Составитель В,ВиноградовТехред М.Надь, Корректо гор актор М.Петр Заказ 6 Филиал ППП "Патент", г. Ужгород, ул. Проектная,4/39 Тираж 698ВНИИПИ Государственнпо делам. изобретен113035, Москва, Ж"35 Юр Рр Подписиго комитета СССРй и открытийРаушская. наб., д.4/