Накапливающий сумматор
Изобретение относится к области вычислительной техники и может быть использовано для параллельного суммирования многоразрядных двоичных чисел. Цель изобретения - расширение функциональных возможностей за счет cyм шpoвaния двоичных чисел, представленных в минимальной системе счисления при сохранении функции суммирования двоичных чисел в традиционной и Фибоначчиевой системах счисления. Сумматор содержит шесть элементов ИЛИ, одиннадцать элементов И, два с умматора по модулю два, элемент задержки. Время сложе1шя Б двоичной минимальной системе счисления в отличие от других известньк двоичных позиционных систем счисления составляет один такт. Это позволяет значительно уменьшить время выполнения арифметических операций в вычислительных устройствах или, что аналогично, сократить число процессов в мультипроцессорных системах при -сохранении одинакового времени решения задач. 1 ИЛ. (явиЬ го - 00
(51)4 С 062 74
ГОСУДАРСТВЕННЫЙ НОМИТЕТ СССР
ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 3901232/24-24 (22) 27.05.85 (46) 23.12.86. Бюл. 9 47 (72) А.Б. Ткаченко и Б.В. Дудкин (53) 681.325 (088.8) (56) Авторское свидетельство СССР
У 455340, кл. G 06 F 7/49, 1974.
Авторское свидетельство СССР
У 577528, кл. G 06 Р 7/49, 1977. (54) НАКАПЛИБА10ЩИИ СУММАТОР (57) Изобретение относится к области вычислительной техники и может быть использовано для параллельного суммирования многоразрядных двоичных чисел. Цель изобретения — расширение функциональных возможностей за счет суммирования двоичных чисел, представленных в минимальной системе счисления при сохранении функции суммирования двоичных чисел в традиционной и "Фибоначчиевой" системах счисления. Сумматор содержит шесть элементов ИЛИ, одиннадцать элементов И, два сумматора по модулю два, элемент задержки. Бремя сложения в двоичной минимальной системе счисления в отличие от других известных двоичных позиционных систем счисления составляет один такт. Это позволяет значительно уменьшить время выполнения арифметических операций в вычислительных устройствах или, что аналогично, сократить число процессов в мультипроцессорных системах при сохранении одинакового времени решения задач. 1 ил, 1 1? 78835 2
Изобретение относится к области ((1) + p (i) = (!>(з.) + (!>(i-2) + вычислительной техники и может быть + ср(ь — 3), (2) Иэ сказанного вытекает алгоритм сложения чисел, представленных в минимальной системе счисления. ПосЛюбое натуральное число А в минимальной системе счисления представляется. в виде многочлена:
Выходные сигналы пе- S Р реноса
h л= - "1 где а, Е 0, О О О О
a; q(i);
50 0
О, при 10
1, при 0<Ы1
Y(i-2) + V (1-3), при i>i
1 О
0 1
CP(i) =
1 1 1 1 1
П р и м е ч а н и е. S — сигнал, участвующий в сложении наравне со слагаемыми данного i-rî разряда; Р сигнал переноса. использовано для параллельного суммирования многоразрядных двоичных чисел.
Цель изобретения — расширение функциональных возможностей накапливающего сумматора за счет способности суммирования двоичных чисел, представленных в минимальной системе счисления при сохранении функции суммирования двоичных чисел в традиционной и "Фибоначчиевой" системах счисления.
На чертеже представлена функциональная схема- сумматора.
Сумматор содержит триггер 1 со счетным вхоцом, элементы И 2-4, элементы И 5 и б, элемент 7 задержки, первый сумматор 8 по модулю два, выходы >-ых разрядов первого и второго операндов 9 и 10, вход 11 переноса из (i-1) — ro разряда, вход 12 переноса из (i+2)-го разряда", выход 13 в (i+1)-й разряд, выход 14 переноса в (i-3) -й разряд, выход 15 переноса в (i-2)-й разряд, вход 16 сброса сумматора, вход 17 разрешения суммирования в минимальной и "Фибоначчиевой" системах счисления, выход 18 переноса в i-й разряд, выходы 19 и 20 результата, вход 21 разрешения суммирования в традиционной и "Фибоначчиевой" системах счисления, вход 22 разрешения суммирования в минимальной системе счисления, вход 23 переноса из i-го разряда, выход 24 переноса из (i+3) ãî разряда, элементы И 25-?7, элемент
ИЛИ 28, второй сумматор 29 по модулю два, элементы ИЛИ 30-32, элементы И 33-37.
Значение g (n+1) является мощностью и-разрядного минимального кода, предлагаемый способ сложения основан на соотношении вытекающем из реккуррентного соотношения (1)., следовательно, правило сложения представляется выражением
0+0=0
0+1 =1 (3)
1+0=1
0 1+1=1011 тупление единичных разрядов слагаемых на вход данного разряда сумматора приводит к выдаче суммы данного
i-го разряда и сигналов переноса в
i-й, (i-2)-й, (i-3)-й разряды сум>О матора. Промежуточные суммы не возникают.
Особенностью предлагаемого способа сложения является поступление переносов в 1-й разряд сумматора из
25 i-го, (i+2)-ro, (i+3) -ro разрядов при использовании накапливающего типа суммирования и формирования из сигналов переноса сигнала, участвующего в сложении наравне со слагаемыми данного разряда, и сигнала переноса из данного разряда.
При поступлении двух нулевых и одного единичного сигналов переноса в данный разряд сумматора сигнал, участвующий в сложении, равен 1, а сигнал переноса равен О.
При поступлении одного нулевого и двух единичных сигналов переноса сигнал, участвующий в сложении,равен О, а сигнал переноса равен 1, При трех единичных сигналах сигнал, участвующий в сложении, и сигнал переноса равны 1, что наглядно представлено в табл. 1.
45 Таблица 1
3 12
Использование соотношения (2) для сложения чисел приводит к определенным особенностям, обусловленным тем, что формирование сум.мы данного разряда осуществляется па правилу
0-.0=-0
0+1=1 (4)
1+0=1
1+1=1
Этой особенностью и вызвана необходимость в шине переноса в i-й разряд, т.е. на вход данного i-го разряда сумматора, дающая возможность сумматору выполнять возложенные на него задачи.
Триггер со счетпым входом предназначен для сложения поступающих на ега вход слагаемых и выдачи результата сложения и его запоминания.
Элемент ИЛИ 5 служит для формирования сигнала, поступающего на счетный вход три-гера из слагаемых данного разряда, и сигналов переноса, поступающих из соседних разрядов.
Элемент И 3 формирует сигнал переноса, возникающий в,цанном разряде сумматора.
Элемент ИЛИ 6 формирует сигнал переноса с учетом сигнала, сформированного из сигналов переноса.
Элемент 7 задержки предназначен для задержки сигналов переноса из данного разряда на величину времени, необходимую для перехода триггеров в устойчивое состояние.
Элементы И 35 и 36 разрешают прохождение сигналов суммы данного разряда и переноса в (1+1)-й разряд при работе сумматора в традиционной и
"Фибаначчиевой" системах счисления.
Элемент И 4 предназначен для прохождения сигнала переноса в (i-2)-й разряд при суммировании чисел в "Фибаначчиевой™ и минимальной системах счисления.
Элементы И 25-27, элемент ИЛИ 28 представляют собой электронньп - -, ключ, производящий коммутацию шин сигналов переноса в зависимости от того, в какой системе счисления представлены суммирующие числа. Элементы И 25 и
26, элемент ИЛИ 28 в зависимости ат сигналов на управляющих шинах 2 1 и
22 производят коммутацию входов данного разряда сумматора с шинами переноса либо из (1-1)-ro, либо из
i-го разрядов сумматора при работе соответственно в традиционной, "Фи78835 боначчиевай" или минимальной системах счисления.
Элемент И 27 производит подключение шины переноса из (i+3)-го разряда суммирования чисел, представленных в минимальной системе счисления.
Сумматоры 8 и 29 по модулю два формируют из сигналов переноса сигнал, участвующий в сложении в соот10 ветствии со столбцом S табл.1, Элементы ИЛИ 30-32, элементы И 2 и 23 формируют из сигналов переноса сигнал переноса из данного разряда в соседние в соответствии со столбцам Р табл.1
Устройство работает следующим образом.
При сложении чисел, представленных в традиционной системе счисле20 ния, логическая "1" подается лишь на вторую управляющую шину, на первой и третьей управляющих шинах присутствует ноль. При этих условиях сумматор осуществляет алгоритм сложения (1) + Q(i) = C (i+1)
Следовательно, имеют смысл сигнал данного i-ro разряда, сигнал переноса в старший разряд (i+1)-й,сигнал переноса из (1-1)-го разряда B данный разряд сумматора.
Процесс сложения разрядов первого и второго слагаемых без учета сигнала переноса является очевидным: триггер са счетным входом формирует сигнал суммы данного i-ro разряда, поступающий на вход элемента И 35, разрешаощего его выдачу. Сигнал пере40 носа вырабатывается следующей цепочкой: элемент И 3, элемент ИЛИ 6, элемент 7 задержки, элемент И 36 разрешает его выдачу в (i+1)-й разряд.
Сигнал переноса из (i-i)-го разряда
45 поступает на элемент И 25, далее— на вход элемента ИЛИ 28, после — на вход сумматора по модулю два, кото.рый без изменения выдает его на вход элемента ИЛИ 5, подключенного к счет50 ному входу триггера и сужжруется со значением данного разряда.
На входах элементов И 26 и 27 постоянно присутствует логический
"0", так как они подключены к третьей управляющей шине, на шине переноса из (Х-2)-ro разряда также присутствует логический "0", обусловленный тем, что элемент И 4 (i-2)-го
12
PP ЗРЯДЙ !(ОДКЛ1<3 Рат»ЛЯ(СЩЕй И.ИНЕ Этпт О ":С . ННР.; — (тта,, Ца выходе имеет логичест(ии )". )1аличи<3м н<3 пттце пеpQJIQcb!. (ii (1 "2} " 1 <) 1)аз ряДЯ нул<я 0(бьЯСНЯС т ся р}3бота < " ?f1 При суммировании в тт3адивионпой СИСТЕМЕ СЧИСЛЕНИЯ JI(Ji)((ПСРЕт!ОСЯ ИЗ (3 1 ) 1" О разряда уча((13 ) (- . (" л!»Н((1> )3 СЛОжЕЦШ(„НЕ ВЛИЯЯ Ца ПО-(tr При работе с чт(с)3<33)11,, цредставлен)) „) ° НЬ()(и !3 <))1-!301!ач <Пт". 3)ИJ" Стт)СТ(< ((3 r ..ЧИС rr.!,r т!е(тт т !Io! ттт(е, ая . ) тр)т(. ((< !. 73 < <31 ца т" е1))3г Iт (T B f Q ()О)) У < Г)) Я)» -(
Б ДЯ (! ),".Ом слУч «е (- Уьт(<(,(TOP 1 ь!1!Qfili !1 ет азы Оритм слоя ения )(J(3) + (<)(j) -- С?<() -(-!) <, (3-2). Следоват -)ть(»0, н(зо)бх)3;тп(.11)(сигцал суммь! данного разряда, сигналы переноса в (). (- I)-.é, ()-.2)-)т::;)эряды,сигI àËÜi ПЕрЕНО(а ттэ (! — ) —.). О,. ((.+2) - ГО РаЗРЯДОВ С(<М(ЛатОРа. ). а < 1)o! )3)fr<, Pc<) б) еl?!»Qc T!» < )) <3)i() н(я N () )» Г) B . "т О?<< (((С ) (),fP (<3»т )»" !C?»1(!1 Б -,." ЛИ<ЧНЕ Д(3") I; СИт-JIH 3()-.; ) (ЕР Е НО С Н Б < аННЫй 1 Й 3<13 p!I Ir су!(Iл ато})а н (30 7(в<) )) <а) ) гт НЕО()ХОДИ((ОСТН ())От);)т(1) ))»анття ИЗ )П(Х СИГНа (та НЛЯ У (QCTV H В (ЛОжн НИН т" г(ЛГ нала переноса из данного !-го разряда. Зто можно пояснить табл.2, Габлиi!а2 ВХОт)1»(,)Е СИТ наЛЬт. ПЬРЕНОг са ) 1 ;) О 1 Рассмот13ии т)а(3ат<7 ()мма) Ора с учетом изложенного, На входы перено(1-1)-f o, (3.+2)- r) 7(0(.Т-.7!(а(вт сигнапы, элементы И ?6 и 27 заперты Цо Гит<1(- С ?„JII 3(яют))ей )rifi!i(r! Сигir 3 f1 тr<3()riirr)r а 78835 6 (1-1) -го разряда „нт)охо;IJI через эле).,eI(ИЛИ 28, т)ост г(т)3ст )!;(1»ход <.у лrl.,<ггора 8 Jio мат(у!1)<3 два, где",(ить:ВастСЯ (Cifl ЦНЛО(.) П<<-< НОr.а. Н 3 (j }- ).) -т (< B Q 3»)!l r J 71 выхо и ц ой с и Г I J ä Ji, 1) <3! ) у»(ее,(ый в CQQTB
:37(е((енто)3 )»<()И 1 и 32, которьй в сэ?»ОК))ПНОС. П С Э IЕМ J! (O.if!! HÒ 2 )т 33 d!Op((1(Р; )Oт (B Blтал I.J:!:-P<1-! С(т Hp i —;.-,»ММЫ -); (ЯОГ<-) р;.- З!31) т(а вь:хопа - ригl ера поступает (а вход элем)=нта И 3 ), цодключснно -0 к втО= рой у(трат»л)зюще(1 ))))!Н(3, логическая ii I (71 I(0 l OP 0) I P Q 3 P (u(r 3Q !" ВЫдаЧУ C 3» f1<)bl данного j.-гo разряда сумматора. CH1 J(Bë переноса с вь)хода элемец25 То. 7 задержки т-одается на вход элементoB И (и 36 . Далее поступает В COOTBPTCTB Ют))3(Е P3P (Brbi C) ММатоРа. При работе сумма ора с числами, (lPe òC (а)ЗЛЕ(и)ЫМ-1 L- («!!?П!Ма.г(ЬНОЙ СИС ) ЕЗO С Pi(!MAL ПРЕД<. }"<)133)ЕНННI. СОО !;!Oi;iCШI<3М (1 < - - ) Б этом с)3 .ае логическая "1" поДаЕтСЯ На ВТОРУЮ и тРСтЬЮ УттРаВЛЯ(О1})1!Е 1ЦЬ!1!1»1, тттд НРИт,ОтттЛI К )т(ПСТ)Щ В CÓÌ)<
j -й (- -,) ) --;"т. (3 - < } --r. l B;1013Ä-,Ц(, СЬ(1 налов переттоса I(3 3- Г э, (3+2, -.ГО, ф ), 1+3) --ГQ т) Озряпоь .;;()-)»)(1)тров"-)тl)1()3 с 7м) Nbi P,а1т!!0 C РИЗРЯт а .. HP )Ц)-.;Не,-:ОГ)-,т?(ICОт 0 0 )а BТОРОИ )lпа)») )т )il!r! i юн(!с утт)! (3 ) т < (1 "3) и ()<1 3p7f Jf,bl > а также к в»)(ходу (3 суммы данного 1 -("0 разряда су:,(матора. По предлагаемому способу сложения сложение дву:: ед(лнг(нь)х разря)30B слагаемых п)3иводт!т к пот(г)лени(<) единичной сумьл()! Даш»огo 37-Го разряда. Б силу Особенности 1(реД< тант(ения чи(ец в )<())и?(ма)f(ьноd (.И(теме сч!лс)(ения СИГНа;(Ы ПЕРЕНОСа В (Ь-- . )-», (j."-з)-й разряды поступают в разряды, заве-ДО!ЛО СОД(P)i(<»DJIJ<= ЦОЛВ а ..) 1<0 И(КЛ„u -)<аЕТ 1278835 порождение промежуточных сумм и дополнительных переносюв и приводит к повышению быстродействия сумматора. Рассмотрим процесс сложения при поступлении на вход единичных разрядов слагаемых при условии, что сигналы переноса в pGHHbIH H c ììàтора заведомо равны нулю. При этом формируются сигнал суммы, равный нулю, и сигнал переноса, равный единице. Сигнал переноса подается на вход данного разряда по шине переноса с выхода на вход разряда,, переводит триггер в единичное состояние Рассмотрим образование из сигналов переноса сигнала, участвующего в сложении, и сигнала переноса из данного в соседние разряды. При поступлении на вход сигналов переноса из i-го, (i+2)-го, (i+3)-ro разрядов сумматоры 8 и 29 по модулю два формируют сигнал, участвующий в сложении, в соответствии со столбцом S табл.1, Этот сигнал и поступает на вход элемента ИЛИ 5. Кроме того,сигналы переноса поступают на входы элементов ИЛИ 30-32, которые в совокупности с элементами И 2 и 33 формируют сигнал переноса в соответствии со столбцом P табл.1. Формула изобретения Накапливающий сумматор, содержащий в каждом i-м разряде (i--1,..., и, и — разрядность операндов),триггер, первый и второй элементы ИЛИ, первый второй и третий элементы И, первый сумматор по модулю два,элемент задержки, причем i-e разряды первого и второго операндов сумматора соединены соответственно с первыми и вторыми входами первого элемента ИЛИ, соответственно выход которого подключен к счетному входу триггера и к первому входу первого элемента И, нулевой вход триггера соединен с входом сброса сумматора, а прямой выход триггера — с вторым входом первого элемента И, выход которого соединен с первым входом второго элемента ИЛИ, выход которого через элемент задержки соединен с первым входом второго элемента И, выход которого соединен с выходом переноса в (i-2)-й разряд сумматора, второй вход второго элемента ИЛИ f0 55 соединен с выходом третьего элемента И, первый вход первого сумматора по модулю два соединен с входом переноса из (i+2) -го разряда сумматора, отличающийся тем, что, с целью расширения функциональных возможностей за счет суммирования чисел, представленных в минимальной системе счисления при сохранении функции суммирования в "Фибоначчиевой" и традиционной системах счисления в каждый i-и разряд сумматора введены второй сумматор по модулю два, третий, четвертый, пятый и шестой элементы ИЛИ, четвертый, пятый, шестой, седьмой, восьмой, девятый, десятый и одиннадцатый элементы И, причем вход разрешения суммирования в традиционной и "Фибоначчиевой" системах счисления сумматора соединен с первыми входами четвертого, пятого и шестого элементов И, вход разрешения суммирования в минимальной системе счисления сумматора соединен с первыми входами седьмого, восьмого, девятого и десятого элементов И, второй вход четвертого элемента И соединен с входом переноса из (i-1)-ro разряда сумматора, выход четвертого элемента — с первым вхо дом третьего элемента ИЛИ, второй вход которого соединен с выходом седьмого элемента И, второй вход которого соединен с входом переноса из i-го разряда сумматора, вход перено1 са из (i+3)-ro разряда сумматора соединен с вторым входом восьмого элемента И, выход которого соединен с первыми входами второго сумматора по модулю два, четвертого и пятого элементов ИЛИ, второй вход четвертого элемента ИЛИ соединен с первым входом шестого элемента ИЛИ, с выходом третьего элемента ИЛИ и вторым входом первого сумматора по модулю 1 два, первый вход которого соединен с вторыми входами пятого и шестого элементов ИЛИ, выходы четвертого и пятого элементов ИЛИ соединены соответственно с первым и вторым входами одиннадцатого элемента И, выход которого соединен с первым входом третьего элемента И, второй вход которого соединен с выходом шестого элемента И, выход перво о сумматора по модулю два соединен с вторым входом второго сумматора по модулю два, выход которого соединен с третьим 7б Составитель М. Есенина Техред З.Кадар Корректор И. Шароши Редактор Л. Гратилло Заказ б839/47 Тираж 671 Подписное БНИИПИ Государственного комитета СССР по делам изобретений и открытий 1i3035, Москва., Ж-35, Раушская наб., д. 4/5 Производственно-полиграфическое предприятие, г. Ужгород, ул. Проектная,« 9 1278835 1О входом первого элемента ИЛИ, прямой входом десятого элемента И и первым выход триггера соединен с вторыми входом второго элемента И, второй входами пятого и девятого элементов И, вход которого соединен с входом развыходы которых являштся выходами ре- решения суммирования в минимальной зультата сумматора, выход переноса 5 и "Фибоначчиевой" системах счисления в (i+I) и разряд сумматора соединен сумматора, выход десятого элемента И с выходом шестого элемента И, второй соединен с выходами переноса в i-й чход которого соединен с вторым и (i-3)-й разряды сумматора.
