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

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

Иллюстрации

Показать все

Реферат

 

Изобретение относится к области вычислительной техники и может быть использовано для параллельного суммирования многоразрядных двоичных чисел. Цель изобретения - расширение функциональных возможностей за счет 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)I(0 ))1!»«I l« !i< B) )(P! (<3)ITé Ит)И, а постоя};цап пода.та с выхода эле! (ЕНТЯ H ? )1 <731ЕВОГO СIЛГНат" а т(а ВХОД элемента ))Т)И 6 о(з(Ä(

При суммировании в тт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)-й разряды сумматора.