Накапливающий сумматор

М 32 Р 7 ПИСАНИЕ ИЗОБРЕТЕ АВТОРСКОМУ О госуда ствснный номиткт ссср по дклдю изоьретений и открыт(56) Авторское свидетельство СССР У 455340, кл. С 06 Р 7/49, 1974.Авторское свидетельство СССР У 577528, кл. С 06 Р 7/49, 1977. (54) НАКАПЛИБАЮЩИЙ СУММАТОР (57) Изобретение относится к области вычислительной техники и может быть использовано для параллельного суммирования многоразрядных двоичных чисел. Цель изобретения - расширение функциональных возможностей за счет суммирования двоичных чисел, представленных в минимальной системе счисления при сохранении функциисуммирования двоичных чисел в традиционной и "Фибоначчиевой" системахсчисления. Сумматор содержит шестьэлементов ИЛИ, одиннадцать элементов И, два сумматора по модулю два,элемент задержки. Бремя сложения вдвоичной минимальной системе счисления в отличие от других известныхдвоичных позиционных систем счисления составляет один такт. Это позволяет значительно уменьшить времявыполнения арифметических операцийв вычислительных устройствах или,что аналогично, сократить число процессов в мультипроцессорных системах при сохранении одинакового времени решения задач. 1 ил,1 1278835 2Изобретение относится к области с(1) + с(1) = с(.) + с(1-2) + вычислительной техники и может быть + с(1. - 3),(2) Иэ сказанного вытекает алгоритмсложения чисел, представленных вминимальной системе счисления. ПосЛюбое натуральное число А в минимальной системе счисления представляется. в виде многочлена: Выходные сигналы пе- Я Р реноса л=-"1 где а,Е О,0 0 0 О а; с 1(л.) р 50 О 1О, при 101, при 0(Ы 1с(-2) + с (1-3),при х 1. 0 1 0 0 1 1 1 1 1 155 П р и м е ч а н и е. Б - сигнал, участвующий в сложении наравне со слагаемыми данного -го разряда; Р сигнал переноса,использовано для параллельного суммирования многоразрядных двоичных чисел.Цель изобретения - расширение функциональных возможностей накапливающего сумматора за счет способности суммирования двоичных чисел, представленных в минимальной системе счисления при сохранении функции суммирования двоичных чисел в традиционной и "Фибоначчиевой" системах счисления.На чертеже представлена функциональная схема. сумматора.Сумматор содержит триггер 1 со счетным вхоцом, элементы И 2-4, элементы И 5 и б, элемент 7 задержки, первый сумматор 8 по модулю два, выходы .-ых разрядов первого и второго операндов 9 и 10, вход 11 переноса из (.-1,) - го разряда, вход 12 переноса из (х+2)-го разряда", выход 13 в (+1)-й разряд, выход 14 переноса в (-3) -й разряд, выход 15 переноса в (.-2)-й разряд, вход 16 сброса сумматора, вход 17 разрешения суммирования в минимальной и "Фибоначчиевой" системах счисления, выход 18 переноса в 1-й разряд, выходы 19 и 20 результата, вход 21 разрешения суммирования в традиционной и "Фибоначчиевой" системах счисления, вход 22 разрешения суммирования в минимальной системе счисления, вход 23 переноса из .-го разряда, выход 24 переноса из (х+3)-го разряда, элементы И 25-27, элемент ИЛИ 28, второй сумматор 29 по модулю два, элементы ИЛИ 30-32, элемен ты И 33-37. Значение с, (и+1) является мощностью п-разрядного минимального кода, предлагаемый способ сложения основан на соотношении вытекающем из реккуррентного соотношения (1) следовательно, правило сложения представляется выражением0+0=00+1=1(3)1+0=1О 1+ 1=1011 тупление единичных разрядов слагаемых на вход данного разряда сумматора приводит к выдаче суммы данногох-го разряда и сигналов переноса вх-й, (.-2)-й, (.-3)-й разряды сум 20 матора. Промежуточвые суммы не возникают.Особенностью предлагаемого способа сложения является поступлениепереносов в х-й разряд сумматора из25 -го, (х+2)-го, (.+3) -го разрядовпри использовании накапливающего типа суммирования и формирования изсигналов переноса сигнала, участвующего в сложении наравне со слагаемыми данного разряца, и сигнала переноса из данного разряда,При поступлении двух нулевых иодного единичного сигналов переносав данный разряд сумматора сигнал,участвующий в сложении, равен 1, асигнал переноса равен О.При поступлении одного нулевого идвух единичных сигналов переносасигнал, участвующий в сложении,равен О, а сигнал переноса равен 1,При трех единичных сигналах сигнал, участвующий в сложении, и сигнал переноса равны 1, что нагляднопредставлено в табл.45 Таблица 13 12Использование соотношения (2) длясложения чисел приводит к определенным особенггостям, обусловлеггным тем,что формирование суммы данного разряда осуществляется по правилуО О=О0+1=1(4)1+ 0=11+1=1Этой особенностью и вызвана необходимость в шине переноса в т-й разряд, т.е, на вход данного д-го разряда сумматора, дающая возможностьсумматору выполнять возложенные нанего задачи.Триггер со счетпым входом предназначен для сложения поступающих наего вход слагаемых и выдачи результата сложения и его запоминания.Элемент ИЛИ 5 служит для формирования сигнала, поступающего на счетный вход триггера из слагаемых данного разряда, и сигналов переноса,поступающих из соседних разрядов.Элемент И 3 формирует сигнал переноса, возникающий в,цанном разрядесумматора,Элемент ИЛИ 6 формирует сигналпереноса с учетом сигнала, сформированного из сигналов переноса,Элемент 7 задержки предназначендля задержки сигналов переноса изданного разряда на величину времени,необходимуго для перехода триггеровв устойчивое состояние.Элементьг И 35 и 36 разрешают прохождение сигналов суммы данного разряда и переноса в (+1)-й разряд приработе сумматора в традиционной и"Фибоначчиевой" системах счисления.Элемент И 4 предназначен для прохождения сигнала переноса в (т)-Йразряд при суммировании чисел в "Фибоначчиевой и минимальной системахсчислени. Элементы И 25-27, элемент ИЛИ 28 представляют собой электронный ключ, производящий коммутацию шин сигналов переноса в зависимости от того, в какой системе счисления представлены суммирующие числа, Элементы И 25 и 26, элемент ИЛИ 28 в зависимости от сигналов на управлягощих шинах 21 и 22 производят коммутацию входов данного разряда сумматора с шинами переноса либо из (.-1)-го, либо из .-го разрядов сумматора при работе соответственно в традиционной, "Фи 78835боначчиевой" или минимальной системах счисления.Элемент И 27 производит подключение шины переноса из (.+3)-го разряда суммирования чисел, представленных в минимальной системе счисления,Сумматоры 8 и 29 по модулю дваформируют из сигналов переноса сигнал, участвующий в сложении в соот ветствии со столбцом Я табл.1,Элементы ИЛИ 30-32, элементы И 2и 23 формируют из сигналов переносасигнал переноса из данного разрядав соседние в соответствии со столбцом Р табл.1Устройство работает следующимобразом.При сложении чисел, представленных в традиционной системе счисле ния, логическая "1" подается лишьна вторую управляющую шину, на первой и третьей управляющих шинах присутствует ноль. При этих условияхсумматор осуществляет алгоритм сложенияггпу(1) + Ч(з.) = ггг(1+1)Следовательно, имеют смьгсл сигнал данного т-го разряда, сигнал пе реноса в старший разряд (ь+1)-й,сигнал переноса из (-1)-го разряда в данный разряд сумматора.Процесс сложения разрядов первого и второго слагаемых без учета сигнала переноса является очевидным: триггер со счетным входом формирует сигнал суммы данного ь-го разряда, поступающий на вход элемента И 35, разрешагащего его выдачу. Сигнал пере носа вырабатывается следующей цепочкой: элемент И 3, элемент ИЛИ 6, элемент 7 задержки, элемент И 36 разрешает его выдачу в (+1)-й разряд.Сигнал переноса из (х)-го разряда 45 поступает на элемент И 25, далее -на вход элемента ИЛИ 28, после - на вход сумматора по модулю два, который без изменения выдает его на вход элемента ИЛИ 5, подключенного к счет ному входу триггера и сумьяруется созначением данного разряда.На входах элементов И 26и 27постоянно присутствует логический 55 нОгг, так как они подклгочены к третьей управляющей шине на шине переноса из (1-2)-го разряда также присутствует логический "О", обусловленный тем, что элемент И 4 (з.-2)-го12рд з 1 эядй 5 Одслгэтеьнь.и 1 с це)13)Йтп 1 элт 3 ляющей юине это о )с,)ллр 5 ттл пя выходе имеет логичест.;.ии "О", цаличием ц 3 юПе пе)эецОса 1.1"2) "1 с) )э;л ряД 3 цуЛ 5 ГгбЬ)ТС 1 ЯСЭТС 5 р або ц ГумьЯТО)Э. 8 ПО МОДЛю,т 13 Л. Кс ЭПСгЕЭПТЯ И.Ит д постоя)иля пода. а с вьтхотта эле ЕН 1 Я И 2 ц.тт 1 ЕВОГО СИГНЯЛ т 1 а ВХОД элемента 1)ТИ) э 05.5 с 5 ес 5 тс 3 м что на входы элемента 1 ШИ 31 подается два нулевьх с;гнала,11 ри суммировании в тгэддивионпойСИСТЕМЕ СЧИСЛЕЦИЯ СИГНац ПСРЕт)с)СЯ ИЗ(з.-1)-го разряда. учас.твует лппв )эСЛОжЕЦШ 1 ЦЕ ВЛГГЯ 5 Ца ПОтУТЕЦГЕ СИГнала Ге)эеосд. из дгп)ного рлгт)5 да.Прн рабвтЕ С ЧИСПЛ ПГ) трэттста)3 ЛЕНЦЬЬ)И В,ФЬ)эОНЯЧтп 1 ЕВОИ" С,гн т 3.С: гЧИСЛЕШя ЛО ГттЧЕСКЛЯцр)тсутотпуЕТ Гта тгев 51 гт г тг ) 0) у гэ 1) н - 1 Г 51 г:Н 1 ахБ ДЯЦ 01 СттЧгд СУ 51 гТОР 1 лтнОЛНЯЕТ алгоритм слоэкенця1,(э.) + т(.)с( +1)г, (э -2),Слс.цовдты 1 О нг Обхо)5 мь с 1 гпял суммь данного разряда, сигналы Гере- НОСЯ. В ( т.) "йт ( 2) й Р) З 151 ДЫ) СИГ нальт переноса пз (3.- ) -к), (+2) - го разитдов стмматора.5 С СЧоЭ 3; РССЭГ Ет ОСЧ тР т СЗГССгц 51 Ч)ц СЭ.-В "ТОй СтСТО.Е СПЦС;С.ЦЦ 5,БЯЛнттИЕ Д 3 Х С Ит"тдло;ЕРЕЦгтсд В ;ъЦтГй 1 Й Э)ЗР 5 тг ЕЯЯТО)Д. Ц)СПП"т1)лт необходимо св фсэ р Пр оь 3 д.3115 ттз цэ; СИРНЯЛЯ гтЛ 51 утЯСТИЯ В С 3-СОСЕТ 1 Т т: СИГ- нала переноса из дл 1 Н 010 .-го разряда Зто можно пояснить табл.2,1. а б л ия 2)эХОТцЕ СИГНа 5 тьт ПЕрЕтОгс лООО1 ,)О 1РЯССМСЭТ 1 ЭИИ т)ДЭОТУ Г М)т)тСРЯ Сучетом изложенного, На входы переноСО 3 ИЗ (1-1)-Го. (т.+2)-ГО Постуца 10 Гсигналы, элементы И э и 27 заперты,цогическим путем ця трет)ей упрятв-"3 яютгей ттцьця Сгтгнатт ге 3 ога цз 7883.э 6(1.-1)-го разряда.т)охо;,я через элее 1 тт И 11 28, т.гос тутаст тл вход гу,ттл.тора 8 по МОГулю двя, гле учить:ваетС: С СНГНЯЛОМ цнт;.ЕгОг;Я цэ ,1.2)-тоОЛЗтнтгта т 35 хппгоц С И тлЛ. 1 ОЛУТЯЕ,ьтйв соот 3 с тствци со стопб 1 том 8 тябт 1. 2без цзменепя поступает через сумматор 29 1 о модулю два, элемент ИЛИ 5ца счетцый вход триггера. Сигнал переноса из (:г)-го разряда подаетсяс гыходя элеме-:та ИЛИ 28 на входыэлементов );)И 30 ц 32 л сигнал перецоЯ из (:г+2 о рдэряцл. - на вхотыэтементов 1 Ц 1 И 1 и 32 которьй в со 130 супнОс. П с э 1 сьг.я И 2 тт 33 с 0)эИРУЮТ г:ЦГЦДЛ 1 ЕЛ:.ОСЛ В С.ООТГ)СТСТ"- Уни с.0 стоттбпом 1 т;бГ.2.Сц ця;: суммы );цНого ргз.ядд сЬ.ХотгЯ) - рь 11 Зрд ц)ЭС;утаст тгд ВЭОтт элемента И 35, цодключспцого к второй уп)эа 13 Г)тэще 1 )5 Пе, логическая 1 ЦЯ КОТОРОЙ РЯЗРЕЬ)ЯЕ ВЫДаЧУ СУМЫданно 10 э. го Р л,з 1)ЯДЯ сУ 1 мг 1 ОР Я,Сигнал переноса с выхода элемецта 7 задержки ГОдается на вход элементов Ии 3 э 5; далее поступае 1соответствуюи: разряды сумма.101 эд.Прц работе сумматора с числамц,ПРЕТ)СТЯ 33 ЕЦ)ЫЬЬ В 11 ПЦ)МД.ГЬ НОЙ СЦСТЕ 3 Ое счцслциг осуеств 11 яется я:110 ритм пэестлг 3331 ць 1 соо цс);с гз гс.с)В этом слуттл,е логическая т)1) подается на вторую и третью уттратзтяоЕ ЩтпЬ 1, тгто ЦРлноттт 1 К Ута,1 Ю В СУММИРгЭВаШП СИГНЯЛОГ, ПСРЕЦОСЯ В э -и (-, -;) ) -)т- 3 ) - й эОтэядь, с)т 1- НЯлов пе 1 эепосд. Нэ э -)30, (3 Ь 2) - ГО, т Л ) " Т 0 Р 1 ЗР)т,)ал)1-, С)0 Э.Ц 1 ЭОВ,З ЦЦО С-тм 3МЫ Д Ячт)ОГО т)г ЗРттЯН;лцч 3 лог)оссотоэ О" т второйО 1 ОЯРГГС)Ь)ГГЗт .Пс ГтЭ)13;)5 т Р1 ОЭ;гго:1 Я ныхо.з э)и 0 тов И 26 33 тРЕгЕрцгтС я .,.т -., СЛЕт;рнд ГЕ;гьЦО, Г УМЭЗДТО) ПГЭ;КтдтЕЦ .", ГЬ)10 Я: 1 ЭЕрецоса из ь" го -2)1 о, (э.+3) -го1 эаз 1 эядов и к выходам в Э.-ц (3-2) -й(1"3) й р 113 1 эядытакже к выходу эО суммы данного э.л го разряда суьЯтора. По предлагаеэОму способу сложе"ния сложение дву.: единичных разрядов слагаемых пгэиводт к по 5 г 51 ешпс)единичной сумы данного э.".го разряда. 5 Б силу особеНости 1 редставления чиСЕЛ В МИНИМДЛВНОй СИСТЕМЕ СЧИС)1 т ЦИЯлСИГНЯ;тЫ ПЕРЕНОСЯ В с Д 2)-., (3.-.5)-йразряды поступают в разряды, заве домо сод рэсацтп цо), Это ис;ктгючаетпорождение промежуточных сумм и дополнительных переносав и приводит к повышению быстродействия сумматора.Рассмотрим процесс сложения при поступлении на вход единичных разрядов слагаемых при условии, что сигналы переноса в данный разряд сумматора заведомо равны нулю, При этом формируются сигнал суммы, равный нулю, и сигнал переноса, равный единице. Сигнал переноса подается на вход данного разряда по шине переноса с выхода на вход разряда,. переводит триггер в единичное состояние Рассмотрим образование из сигналов переноса сигнала, участвующего в сложении, и сигнала переноса из данного в соседние разряды. При поступлении на вход сигналов переноса из -го, (+2)-го, (д+3)-го разрядов сумматоры 8 и 29 по модулю два формируют сигнал, участвующий в сложении, в соответствии со столбцом Бтабл.1, Этот сигнал и поступает на вход элемента ИЛИ 5. Кроме того,сигналы переноса поступают на входы элементов ИЛИ 30-32, которые в совокупности с элементами И 2 и 33 формируют сигнал переноса в соответствии со столбцом Р табл.1,Формула изобретения Накапливающий сумматор, содержащий в каждом х-м разряде (з.=1 и, и - разрядность операндов),триггер, первый и второй элементы ИЛИ, первый второй и третий элементы И, первый сумматор по модулю два,элемент задержки, причем -е разряды первого и второго операндов сумматора соединены соответственно с первыми и вторыми входами первого элемента ИЛИ, соответственно выход которого подключен к счетному входутриггера и к первому входу первогоэлемента И, нулевой вход триггерасоединен с входом сброса сумматора,а прямой выход триггера - с вторым входом первого элемента И, выход которого соединен с первым входом второго элемента ИЛИ, выход которого через элемент задержки соединен с первым входом второго элемента И, выход которого соединен с выходом переноса в (-2)-й разряд сумматора, второй вход второго элемента ИЛИ 5 10 15 20 25 30 35 40 45 50 55 соединен с выходом третьего элемента И, первый вход первого сумматора по модулю два соединен с входом переноса из (+2) -го разряда сумматора, о т л и ч а ю щ и й с я тем, что, с целью расширения функциональных возможностей за счет суммирования чисел, представленных в минимальной системе счисления при сохранении функции суммирования в "Фибоначчиевой" и традиционной системах счисления в каждый д-и разряд сумматора введены второй сумматор по модулю два, третий, четвертый, пятый и шестой элементы ИЛИ, четвертый, пятый, шестой, седьмой, восьмой, девятый, десятый и одиннадцатый элементы И, причем вход разрешения суммирования в традиционной и "фибоначчиевой" системах счисления сумматора соединен с первыми входами четвертого, пятого и шестого элементов И, вход разрешения суммирования в минимальной системе счисления сумматора соединен с первыми входами седьмого, восьмого, девятого и десятого элементов И, второй вход четвертого элемента И соединен с входом переноса из (д)-го разряда сумматора, выход четвертого элемента - с первым входом третьего элемента ИЛИ, второй вход которого соединен с выходом седьмого элемента И, второй вход которого соединен с входом переноса из -го разряда сумматора, вход переноса из (+3)-го разряда сумматора соединен с вторым входом восьмого элемента И, выход которого соединен с первыми входами второго сумматора по модулю два, четвертого и пятого элементов ИЛИ, второй вход четвертого элемента ИЛИ соединен с первым входом шестого элемента ИЛИ, с выходом третьего элемента ИЛИ и вторым входом первого сумматора по модулю 1два, первый вход которого соединен с вторыми входами пятого и шестого элементов ИЛИ, выходы четвертого и пятого элементов ИЛИ соединены соответственно с первым и вторым входами одиннадцатого элемента И, выход которого соединен с первым входом третьего элемента И, второй вход которого соединен с выходом шестого элемента И, выход первого сумматора по модулю два соединен с вторым входом второго сумматора по модулю два, выход которого соединен с третьим70 7 б Составитель М. ЕсенинаТехред З.Кадар Корректор М, Шароши Редактор Л. Гратилло Заказ б 839/47 Тираж 671 Подписное БНИИПИ Государственного комитета СССР по делам изобретений и открытий 113035, Москва., Ж, Раушская наб д, 4/5Производственно-полиграФическое предприятие, г. Ужгород, ул. Проектная,4 9 127883510входом первого элемента ИЛИ, прямой входом десятого элемента И и первым выход триггера соединен с вторыми входом второго элемента И, второй входами пятого и девятого элементов И, вход которого соединен с входом развыходы которых являштся выходами ре- решения суммирования в минимальной зультата сумматора, выход переноса 5 и "Фибоначчиевой" системах счисления в (+1)-й разряд сумматора соединен сумматора, выход десятого элемента И с выходом шестого элемента И, второй соединен с выходами переноса в -й чход которого соединен с вторым и (-3)-й разряды сумматора.