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

Изобретение относится к области вычисдительной техники и может быть использовано для параллельного суммирования многоразрядных двоичных .чисел. Известны параллельные накапливающие сумматоры, представляющие собой цепочку последбвательно связанных одноразрядных суммирующих ckeM, количество которых равно числу разрядов суммируемых чисел. Разрядные сумматоры связаны между собой цепями переноса из младших разрядов в ст шие. Одноразрядная суммирующая схема соде жит триггеры со счетным входом, элементы И, ИЛИ и линии задержки. К числу, хра няшемуся в запоминающем устройстве, прибавляется слагаемое, подающееся на вход накапливающего сумматора. Полученная в результате сумма заменяет хранившееся ранее число 1, 2 . Наиболее близким аналогом может служить накапливающий сумматор, каждый ; -ый разряд которого ( i 1 и) содержит триггер со счетным входом, элементы И, ИЛИ и элемент задержки, причем входные шины соответствующих разрядов первого и второго слагаемых соединены с первым и вторым входами первого элемента ИЛИ данного разряда, выход которого подключён к счетному входу триггера, яулевой вход которого подключен к шине сброса, а единичный выход - к первому входу первого элемента И, выход которого подключен к первому входу второго элемента ИЛИ, второй вхоа которого подключен к выходу второго элемента И 3j . Недостатком этого сумматора является невозможность суммирования многоразрядных чисел, представленных в двоичной фибо. наччиевой позиционной системе счисления. Целью изобретения является расширение функциональных возможностей накапливающего сумматора, заключающееся в выполнении дополнительной функции суммирования чисел, представленных в фибоначчиевой системе счисления. Это достигается тем, что в каждый раз р$щ накапливающего сумматора введен элемент сложения по модулю 2, выход которого подключен к третьему входу первого элемента ИЛИ, выход которого соединен со вт рым входом первого элемента И, первый и второй входы элемента сложения по модулю 2 соединены соответственно с первым и вторым входами переноса . в данный разряд сумматора и с первым и вторым входа ми вторюго элемента И, выход второго элемента ИЛИ подключен к входу элемента задержки, выход которого, являющийся выходом переноса в ({ +1)-ый разряд сумматора, подключен к первому входу третьего элемента И, второй вход которого соединен с управляющей шиной, а выход является выходом переноса в ( j -2)-ой разр$щ сумматора, единичный выход триггера со счетным входом является выходом суммы данного ( -го разряда. На чертеже показана функциональная схе ма { -го накапливающего сумматора, В ее состав входят триггер со счетным входом 1, элементы И 2,3,4, элементы ИЛИ 5,6, элемент задержки 7, элемент сло жения по модулю 2j входные шины i -ых разрядов первого . и второго 1О слагаемых., входы переноса из( 1)го и ( +2) го разрядов сумматора 1Г, 12, выход сум мы 1-го разряда сумматора 13, выходы .п реноса в ( j +1)-ый и { -2)--ой разряды сумматора 14, 15, шина сброса 16, управляющая шина 17, Входные шины i ых разридов первого 9 и вторО1 О 1О слагаемых подключены к первому и второму-входам элемента ИЛИ 5 третий вход которого соединен с выходом элемента сложения по модулю 2 входы которого подключены к входам переносов из ,{ |, -1)-го и ( L +2)-го разрядов сумматора 11 и 12, которые подключены также к вкоцац элемента И 2, выход которого соединен с входом элемента ИЛИ 6, другой вход которого соединен с выходом элемента И 3, а Выход - с входом элемента задержки 7, выход которого подключен к вых переноса в ( +1)-ый разряд сумматора 14 и к первому входу элемента И 4, другой вход которого подключен к управляющей шине 17, а выход - к выходу переноса в ( V. -2)-ой разряд сумматора 15. Выход элемента ИЛИ 5 подключен к счетному вхо ду триггера 1 и к входу элемента И 3. Ед нинный выход триггера 1 подключен к дру,гому входу элемента И 3 и к выходу суммы данного + -го разряда сумматора 13, К нулевому входу триггера 1 подключена ши на сброса 16 В фибоначчиевой системе счисления любое натуральное число представляется в виде многочлена ,(,p((j.vf«-)-...а(о), (I) (Опри i .0 f(0-|iпри ( 0 (2) LV(-l)-i-Ч(-2) при i О, Представление (Ij называется нормальной формой представления, если оно получено путем разложения Ji{ и всех возникающих в прюцессе такого разложения остатков j по формуле ,, N If (4-I)f r-j где (f (3 +1) и ( (i) задаются соотношением (2). Для нормальной формы представления чисел в фибоначчиевой системе счисления, хапактерно наличие не менее одного нуля после каждой единицы. Например, нормальная форма числа 83 имеет вид Веса разрядов 55 34 21 13 853211 ,Нормаль- ная форма числа 83 1 О 1 О О 1 О 1 О О Сложение двух цифр одноименных разрядов в двоичной фибоначчиевой системе счисления выполняется согласно следующей таблице О + О О 0+ 1 1 о 1 1 + . Если в , данном разряде слагаемых имеются две единицы, то в фибоначчиевой двоичной системе счисления, наряду с переносом в следующий старший разряд, имеется еще перенос в младщий разряд, i отстоящий от данного на два разряда, что вы-Лкает из рекуррентного соотношения . t((iKtp(0-t(ihV {M}+t (l-2) )+f(li-2).; Отсюда следует, чтопри сложении двух мне горазрядных двоичных чисел, представленных в нормальной форме, возможна ситуация, когда в один разряд происходит два переноса: один со стороны предьщушего младшего разряда слагаемых, другой со стороны старшего, отстоящего от данного на два разряда. Поступление одного переноса в разряд приводит к изменению состояния разряда на инверсное. Два переноса в один разряд не изменяют состояния разряда, но вызывают перенос из данного разряда в следующий старший разряд .и в младший, отстоящий от данного на два разряда. Переносы из одного разряда в другой поступают с некоторой задержкой по отношению к моменту из возникновения в данном разряде. npHfvfep сложения двух чисел представ- , фибоначчиевой системе счислеЛ&ЯНЫХ - вi-Mfli /i /iJ,C4-I Т,ЛСОиЛ приведен в таОлице.

О

1-е слагаемое

О 2-е спагаемое

Промежуточные суммы

О

о о

О

О

О

О

о о о

1

L

о

о 1

о

о

о

1

о

О

Сумма и таблице стрелками показаны переносы Работает накапливающий сумматор следующим образом. На щину сброса 16 подается сигнал, по которому триггеры 1 всех разрядов устанавливаются в нулевое состояние. Слагаемы подаются на параллельные входы разрядов сумматора последовательно во времени. При чем временной интервал между поступлением двух чисел должен быть достаточный для формирования сигнала переноса в разрядах сумматор)а и его передачи через элементы задержки 7. Время задесжки t элемента задержки 7 должно превышать длительность импульса записи слагаемого и максимальную задержку переключения разрядного триггера вместе взятые. При сложении чисел, представленных в фибоначчиевой системе счисления, по управляющей шине 17 поступает сигнал, который разрешает прохождение импульсов переноса через элементы И 4. При наличии лишь одного переноса в любой .1 разряд на выходе элемента сложения по модулю 2 формируется единичный сигнал, который через элемент ИЛИ 5 поступает на счетный вход триггера 1. При этом состояние триггера 1 изменяется на инверс ное. При одновременном поступлении двух вхо ных сигналов переноса в любо1ь разряд нака ливающего сумматор на выходе элемента сложения по модулю 2 формируется нуле вой сигнал, который не изменяет состояния триггера 1, но при этом элементом И 2

О

О формируется сигнал переноса из данного разоаца. При сложении чисеп, представленных в традиционной двоичной системе счисления, на управляющую шину 17 поступает сигнал, которым запрещается прохождение импульсов переноса в сторону младших разрядов через элементы И 4, Введение новых элементов и связей позволяет расширить функциональные возможности накапливающего сумматора, а именно выполнять операцию суммирования.двоичных чисел, пред став/1 енных в фибонач- чиевой системе счисления. Эта снсчема счисления обладает ошибкообнаруживающей способностью при передаче, хранении чпсел и выполнении над ними арифметических операций. Формула изобретения Накапливающий сумматор, каждьпг t, -ыи разряд ( i ,-«) которого содержит триггер со счетным входом, элементы И, ИЛИ и элемент задержки, причем входные шины соответствующих разрядов первого и второгослагаемых соединены с первым и вторым входами первого элемента ИЛИ данного разр)я- да, выход которого подключен к счетному входу триггера, нулевой вход которого подключен к шипе сброса, а единичный выход к первому входу первого элемента 1-f, выход которого подключен к первому входу второго элемента ИЛИ, второй BXOZI которого подключен к выходу второго элемента И, о т л и ч а ю щ и и с я тем, что, с целью расширения функционалbHj ix,возможное тей сумматора, в каждый разряд его введен элемент сложения по модулю 2, выход которого подключен к третьему входу первого элемента ИЛИ, выход которого соединен со вторым входом первого элемента И, первый в второй входы элемента сложения по модулю 2 соединены соответственно с первым и вторым входами переноса в данный разршд сумматора и с первым и вторым входами второго элемента И, выход второго эле мента ИЛИ подключенк входу элемента задержки, выход которого, являющийся ВЫХОдом переноса в ( jx +1)-ый разряд сумматор подключен к первому входу третьего элемен/2

13

/ та И, второй вход KOTOJXJTO соединен с управляющей шиной, а выход является выходом переноса в ( J. -2)-ой разряд сумматора, единичный выход триггера со счетным входом является выходом суммы данного t -го разряда. Источники информации, принятые во внимание при экспертизе: 1.Авторское свидетельство СССР № 455340, кл. Q 06 Р 7/50, 1974. 2.Букреев И. Н. и др,Микроэлектронные схемы цифровых устройств, М. , Сов. радио , 1975, с. 330. рис. 8.8. 3.Каган Б. М. и др.Цифровые вычислительные машины и системы, М. , Энергия, 1970, с. 222. рис. 4-2.