Накапливающий сумматор Советский патент 1986 года по МПК G06F7/49 

Изобретение относится к области вычислительной техники и может быть использовано для параллельного суммирования многоразрядных двоичных чисел.

Цель изобретения - расширение функциональных возможностей накапливающего сумматора за счет способности суммирования двоичных чисел, представленньк в минимальной системе счисления при сохранении функции суммирования двоичных чисел в традиционной и Фибоначчиевой системах счисления.

На чертеже представлена функциональная схема, сумматора.

Сумматор содержит триггер 1 со счетным входом, элементы И 2-4, элементы И 5 и 6, элемент 7 задержки, первый сумматор 8 по модулю два, выходы i-ых разрядов первого и второго операндов 9 и 10, вход 11 переноса из (i-l.)-ro разряда, вход 12 переноса из (i+2)-ro разряда выход 13 в (1+1)-й разряд, выход 14 переноса в (1-3)-й разряд, вьгхо,ц 15 переноса в (1-2)-й разряд, вход 16 сброса сумматора, вход 17 разрешения суммирования в минимальной и Фибоначчиевой системах счисления, выход 18 переноса в i-й разряд, выходы 19 и 20 результата, вход 21 разрешения суммирования в традиционной

ния, вход 22 разрешения суммирования в минимальной системе счисления, вход 23 переноса из i-ro разряда, выход 24 переноса из (i+3)-ro разряда, элементы И 25-27, элемент ИЛИ 28, второй сумматор 29 по модулю два, элементы ИЛИ 30-32, элементы И 33-37.

Любое натуральное число А в нимальной системе счисления пр ставляетса в вхеде многочлена:

А a;Cf(i);

1 1

где, ,l }

qKi)

0,при i О

1,при Ci(i-2) +V(i-3), при ,

Значение ; (п+1) является мощностью п-разрядного минимального кода, предлагаемый способ сложения основан на соотношении

(f(i) +v(i) V(i) +ф(1-2) +

+ ФС1-з),

(2)

вытекающем из реккуррентного соотношения (1),, следовательно, правило сложения представляется выражением

.

(3)

5

0

5

0

0

5

Из сказанного вытекает алгоритм сложения чисел, представленных в минимальной системе счисления. Поступление единичных разрядов слагаемых на вход данного разряда сумматора приводит к выдаче суммы данного i-ro разряда и сигналов переноса в i-й, (i-2)-й, (i-3)-й разряды сумматора. Промежуточные суммы не возникают.

Особенностью предлагаемого способа слолсения является поступление переносов в разряд сумматора из 5 i-ro, (i+2)-ro, (i+3)-ro разрядов , при использовании накапливающего типа суммирования и формирования из сигналов переноса сигнала, участвующего в сложении наравне со слагае- мьми данного разряда, и сигнала переноса из данного разряда.

При поступлении двух нулевых и одного единичного сигналов переноса в данный разряд сумматора сигнал, участвующий в сложении, равен 1, а сигнал переноса равен 0.

При поступлении одного нулевого и двух единичных сигналов переноса сигнал, участвующий в сложении,равен О, а сигнал переноса равен 1.

При трех единичных сигналах сигнал, участвующий в сложении, и сигнал переноса равны 1, что наглядно представлено в табл. 1.

Т а б л и

Ц а

Примечание. S- сигнал, участвующий в сложении наравне со слагаемыми данного i-ro разряда Р сигнал переноса.

(4)

31

Использование соотношения (2) для сложения чисел приводит к определенным особенностям, обусловлен} ым тем, что формирование суммы данного разряда осуществляется по правилу 0+1 1 1 + 1 1

Этой особенностью и вызвана необходимость в шине переноса в i-й разряд, т.е, на вход данного i-ro разряда сумматора, дающая возможность сумматору выполнять возложенные на него задачи.

Триггер со входом предназначен для сложения поступающих на его вход слагаемых и вьщачи результата сложения и его запоминания.

Элемент ИЛИ 5 служит для формирования сигнала, поступающего на счет- ньй вход триггера из слагаемых данного разряда, и сигналов переноса, поступающих из соседних разрядов.

Элемент И 3 формирует сигнал переноса, возникающий в данном разряде сумматора.

Элемент ИЛИ 6 формирует сигнал переноса с учетом сигнала, сформированного из сигналов переноса.

Элемент 7 задержки предназначен для задержки сигналов переноса из данного разряда на величину времени, необходимую для перехода триггеров в устойчивое состояние.

Элементы И 35 и 36 разрешают прохождение сигналов суммы данного разряда и переноса в (1+1)-й разряд при работе сумматора в традиционной и Фибоначчиевой системах счисления.

Элемент И 4 предназначен для прохождения сигнала переноса в (1-2)й разряд при суммировании чисел в Фибоначчиевой и минимальной системах счисления.

Элементы И 25-27, элемент ИЛИ 28 представляют собой электронньш ключ, производящий коммутацию шин сигналов переноса в зависимости от того, в какой системе счисления представлены суммирующие числа. Элементы И 25 и 26, элемент ШМ 28 в зависимости от сигналов на управляющих шинах 21 и 22 производят коммутацию входов данного разряда суг-матора с шинами переноса либо из (i-1)-ro, либо из i-ro разрядов сумматора при работе соответственно в традиционной, Фи

54

боначчиевой Ш1И минимальной системах счисления.

Элемент И 27 производит подключение шины переноса из (i+3)ro раз- ряда суммирования чисел, представленных в минимальной системе счисления.

Сумматоры 8 и 29 по модулю два формируют из сигналов переноса сигнал, участвующий в сложении в соот- ветствии со столбцом S табл,1.

Элементы ИЛ1-1 30-32, элементы И 2 и 23 формируют из сигналов переноса сигнал переноса из данного разряда в соседние в соответствии со столб- цом Р табл.1

.Устройство работает следующиь5 образом.

При сложении чисел, представленных в традиционной системе счисле- НИЛ, логическая 1 подается лишь на вторую управляющую шину, на первой и третьей управляющих шинах присутствует ноль. При этих условиях сумматор осуществляет алгоритм сло

женил

if(i) + (i) 9()

Следовательно, имеют смысл сигнал данного i-ro разряда, сигнал переиоса в старший разряд (i+1)-и,сиг- кал переноса из (i-l)-ro разряда в данный разряд сумматора.

Процесс сложения разрядов первого и второго слагаемых без учета

сигнала переноса является очевидным: триггер со счетным входом формирует сигнал суммы данного i-ro разряда, поступаюцщй на вход элемента И 35, разрешающего его выдачу. Сигнал переноса вырабатывается следующей цепочкой: элемент И 3, элемент ИЛИ 6, элемент 7 задержки, элемент И 36 разрешает его выдачу в (i+1)-й разряд. Сигнал переноса из (i-l)-ro разряда

поступает на элемент И 25, далее - на вход элемента ИЛИ 28, после - на вход су шатора по модулю два, кото- рьш без измененрш выдает его на вход элемента ИЛИ 5, подключенного к счетному входу триггера и cyм шpyeтcя со значением данного разряда,

На входах элементов И 26 и 27 постоянно присутствует логический О, так как они подключены к третьей управляющей шине, на шине переноса из (1-2)-го разряда тахоке присутствует логическт О, обусловлен- ньш тем, что элемент И 4 (i-2)-ro

разряда5 подключ еннын кпервом

равляющей П.ИИР. этого ггера;-,пяда, ла

выходе имеет логический О Иаличи ем на 1иине переноса из

ряда нуля объясляется работа сумматора 8 ло модулю д«а з,)1еме}1та ИЛИ, а. посгояяиая подача с выхода элемента И 2 нулевого сигнала на вход элемента ИЛИ 6 объяспяется теьц что на входы элемента ИЛИ 31 подается два нуле.в1йх сигнала.

При суммировании в традиционной системе счи.слеиия сигнал переноса из (i- l)-ro разряда участвует лишь в сложенл-ит,, не влияя на получение сигнала переноса из данного разряда.

При работе с числами,: пред,ставлен- ныыи Е. Фибоначчиевой системе счисления , логическая

на первой и второй управляющих шинах, В да1п-юм случа.е cyr.n-saTop с.ыполняет алгоритм слолгения

(,Ki) -I- wCi) (.fd-n} (f (i.--2),

Следовате:аьно , необходимы сигнал суммы данног о разряда, сигналы переноса 3 (г1-1)-Й5 (i-2)-i-i разряды,сигналы переноса, из (i-1);ro, (:L-i-2)- To разрядов сумматора.

Рассмо7 рим особенность е:ложепия чисопл в этой системе счисления „Наличие двух сигнало. переноса в ;,аннын разряд сумматора прецполагает необходимость формирования из них сигнала для участия з сложении JL сиг-нала nepejioca из данлого i-ro разряда Это можно пояс1П-1ть табл,2,

Т а б л и I г а 2

Входные сигналы переноса

О 1

О 1

Рассмотрш работу суммап ора с

учетом изложенного. На входы пёрено- jS силу особенности представления сов на ()rOj (i-f-2)-ro поступают

сел в минимальной си.стеме счислен сигналы переноса в (1-2)-йз {1-3) разряда поступают в разр.яды, заве домо содержащие iicj.ib Это исключа

сигналы элемеи-пэ PI 26 и 2/ заперты .погИ -iecKj-iM путем на третьей управ- л.я:щщей шине,. Сигнал переноса из

12788356

(i-1)ro разряда, ароходя через эле;- t SeiiT ИЛИ 2.85, поступает на вход сум- матера 8 по модулю д.ва, г де учитывается с сигпало переноса из (i-i-2)-i o

разряда, выходной сигнал,, получае -шй в, соответствир5. со столбдом S табл. 25 без изменения поступает через сумматор 29 по doд,yлю зва, элемент ИЛИ 5 на счетный вход триггера. Сигнал переноса из (:1-1)Го разряда подается с выхода элемента ИЛИ 28 на входы элементов И ТИ 30 и 32. а. сигнал переноса из (i+2)--ro разряда -- на входы элементов ИЛИ 31 и 32, которьвд в со- зокунности с элементами И 2 и 33 формируют сигнал nepcjHoca в соответст-- апи со сто.ттбдом Р

Сиг нал суммы данного разряда с выхода триггера поступает на вход элемепта И 35., под.ключенного к второй управляющей шнне, логическая 1 на которой разрешает, выдачу данног о i-ro ра.зряда суглматора.

Сигнал переноса с вьпсода злемеп- та 7 задержки подается на вход эле ментов И 4 и 36 li далее поступает в соответствутэшд1е разряды сумматора,

При работе сумматора с числами, .представле;И1Ыми Б М1н-1имальной системе счислени.л, осуществляется алг о- ригм, представленный соои нокением (2) „

В этом случае логическая 1 по- дается на вторую и третью управляю- п..ие шины, что приводит к учас1 ию в суммировании сри налов переноса в ,, ()-iV, (5.-3.)--й разряды, сигналов переноса, иг i.-roj (i-i-2)--ro, i-i-3)-го разрядов, формировз.пию суммы данного разря.да.

.Нали:ч1-1е логичг-.ского 0 на. второй управляющей шине приводит к тому что па выходе зл;гме51тов И 26р 35 и 36 генерируется HOJH-:, Следовательно 3 сумматор по5.1,;слючеп тс выходам переноса .из (i- -2)-ro5 ()-ro разрядов и к выа-содам в 1--й, (1--2)-й, (1--3)-й разряды, а также к выходу суммы данного i-ro разряда сумматора. По предла аемому способу сложения сложение дву/с единичных разрядов слагаемых Г риводит к появлению единичной суммы дашюго i.-ro разряда.

чи силу особенности представления

сел в минимальной си.стеме счисления сигналы переноса в (1-2)-йз {1-3)-й разряда поступают в разр.яды, заведомо содержащие iicj.ib Это исключает

71

порождение промежуточных сумм и дополнительных переносок н приводит к повышению быстродействия сумматора. Рассмотрим процесс сложения при поступлении на вход единичных разрядов слагаемых при условии, что сигналы переноса в данный разряд тора заведомо равны нулю. При этом формируются сигнал суммы, равньм нулю, и сигнал переноса, равный единице. Сигнал переноса подается на вход данного разряда по шине переноса с выхода на вход разряда, переводит триггер в единичное состояние,

Рассмотрим образование из сигналов переноса сигнала, участвующего в сложении, и сигнала переноса из данного в соседние разряды. При поступлении на вход сигналов переноса из i-ro, (i+2)-ro, (i+3)-ro разрядов сумматоры 8 и 29 по модулю два формируют сигнал, участвующий в сложении, в соответствии со столбцом S табл,1. Этот сигнал и поступает на вход элемента ИЛИ 5, Кроме того,сигналы переноса поступают на входы элементов ИЛИ 30-32, которые в совокупности с элементами И 2 и 33 формируют сигнал переноса в соответствии со столбцом Р табл,1.

Формула изобретения

Накапливающий сумматор, содержащий в каждом i-M разряде (,,,,, п, п - разрядность операндов),триггер, первый и второй элементы ИЛ1-1, первый второй и третий элементы И, первый сумматор по модулю два,элемент задерж1 си, причем i-e разряды первого и второго операндов сумматора соединены соответственно с первыми и вторыми входами первого элемента ИЛИ, соответственно выход ко- торого подключен к счетному входу триггера и к первому входу первого элемента И, нулевой вход триггера соединен с входом сброса сумматора, а прямой выход триггера - с вторым входом первого элемента И, выход которого соединен с первым входом второго элемента ИЛИ, выход которого через элемент задержки соединен с первым входом второго элемента И, ,выход которого соединен с выходом переноса в (1-2)-й разряд сумматора, второй вход второго элемента ИЛИ

788358

соединен с выходом третьего элемента И, первый вход первого сумматора по модулю два соединен с входом переноса из (i+2)-ro разряда сумматора,

2 отличающийся тем, что, с целью расширения функциональных возможностей за счет суммирования чисел, представленных в минимальной системе счисления при сохранении

fO функции суммирования в Фибоначчие- вой и традиционной системах счисления в каждый i-й разряд сумматора введены второй сумматор по модулю два, третий, четвертый, пятый и шесJ5 той элементы ИШ1, четвертый, пятый, шестой, седьмой, восьмой, девятый, десятый и одиннадцатьм элементы И, причем вход разрешения суммирования в традиционной и Фибоначчиевой

20 системах счисления сумматора соединен с первыми входами четвертого, пятого и шестого элементов И, вход разрешения суммирования в минимальной системе счисления сумматора сое25

динен с первыми входами седьмого, восьмого, девятого и десятого элементов И, второй вход четвертого элемента И соединен с входом переноса из (i-l)-ro разряда сумматора, выход 30 четвертого элемента - с первым вхо- дом третьего элемента ИЛИ, второй вход которого соединен с выходом седьмого элемента И, второй вход которого соединен с входом переноса из

35 i-ro разряда сумматора, ёход перено- I са из (i+3)-ro разряда сумматора

соединен с вторым входом восьмого элемента И, выход которого соединен с первыми входами второго сумматора по модулю два, четвертого и пятого элементов ИЛИ, второй вход четвертого элемента ИЛИ соединен с первым входом шестого элемента ИЛИ, с выходом третьего элемента ИЛИ и вторым

45

50

55

входом первого сумматора по модулю

два, первый вход которого соединен с вторыми входами пятого и шестого элементов ИЛИ, выходы четвертого и пятого элементов I-fflH соединены .соответственно с первым и вторым входами одиннадцатого элемента И, выход ко- . торого соединен с первым входом третьего элемента И, второй вход ко- торого соединен с выходом шестого

элемента И, выход первоЬо сумматора по модулю два соединен с вторым входом второго сумматора по модулю два, выход которого соединен с третьим

входом первого элемента ИЛИ, прямой выход триггера соединен с вторыми входами пятого и девятого элементов И, выходы которых являются выходами результата сумматора, выход переноса в (1+1)-й разряд сумматора соединен с выходом шестого элемента И, второй чход которого соединен с вторым

входом десятого элемента И и первым входом второго элемента И, в.торой вход которого соединен с входом разрешения суммирования в минимальной и Фибоначчиевой системах счисления сумматора, выход десятого элемента И соединен с выходами переноса в i-й и (1-3)-й разряды сумматора.

Изобретение относится к области вычислительной техники и может быть использовано для параллельного суммирования многоразрядных двоичных чисел. Цель изобретения - расширение функциональных возможностей за счет cyм шpoвaния двоичных чисел, представленных в минимальной системе счисления при сохранении функции суммирования двоичных чисел в традиционной и Фибоначчиевой системах счисления. Сумматор содержит шесть элементов ИЛИ, одиннадцать элементов И, два с умматора по модулю два, элемент задержки. Время сложе1шя Б двоичной минимальной системе счисления в отличие от других известньк двоичных позиционных систем счисления составляет один такт. Это позволяет значительно уменьшить время выполнения арифметических операций в вычислительных устройствах или, что аналогично, сократить число процессов в мультипроцессорных системах при -сохранении одинакового времени решения задач. 1 ИЛ. (явиЬ го - 00

Редактор JL Гратилло

Составитель М. Есенина

Техред В.Кадар Корректор М. Шароши

Заказ 6839/47Тираж 671 Подписное

ВНШШИ Государственного комитета СССР

по делам изобретений и открытий 113035, Москва, , Раушская наб., д. 4/5

Производственно-полиграфическое предприятие, г. Ужгород, ул. Проектная, J