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

 

Изобретение относится к вычислительной технике и может быть использовано для параллельного суммирования многоразрядных двоичных чисел. Цель изобретения - расширение области применения за счет суммирования двоичных чисел, представленных в пакетной системе счисления, при сохранении возможности суммирования двоичных чисел в традиционной и "фибоначчиевой" системах счисления. Накапливающий сумматор содержит в каждом разряде триггер 1, сумматор 2 по модулю два, элементы И 3-9, элементы ИЛИ 10-13 и элемент 14 задержки с соответствующими связями. Сумматор может быть использован для построения специализированного устройства, работающего в режиме сквозного контроля информации и исправления возникающих ошибок, что позволит этому специализированному устройству длительно функционировать с высоким быстродействием. 1 ил., 5 табл.

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСА ЛИК ц11 4 6 06 F 7/49.

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

17

79

21

22

Зд

7В

ГОСУДАРСТВЕННЫЙ КОМИТЕТ

ПО ИЗОБРЕТЕНИЯМ И ОЧНРЫТИЯМ

ПРИ ГННТ СССР

1 (2l ) 4419431/24-24 (22) 03.05,88 (46) 30.12.89. Бюл. М 48 (71) Ленинградский кораблестроительный институт (72) Н.Н.Шапошников, А.В.Ткаченко и О.П.Гриб (53) 681.325.5(088.8) (56) Авторское свидетельство СССР

У 1319023, кл. С 06 F 7/49, 1985, Авторское свидетельство СССР

У 1278835, кл. G 06 F 7/49, 1985. (54) НАКАПЛИВАЮЩИЙ СУММАТОР (57) Изобретение относится к вычислительной технике и может быть использовано для параллельного суммирования многоразрядных двоичных чисел. Цель изобретения — расширение

„,SU„„1532916 А1

2 области применения за счет суммирования двоичных чисел, представленных в пакетной системе счисления, при сохранении возможности суммирования двоичных чисел в традиционной и "фи-. боначчиевой" системах счисления„ Накапливающий сумматор содержит в каждом разряде триггер 1, сумматор 2 ,по модулю два, элементы И 3-9, элементы ИЛИ 10-13 и элемент 14 задержки с соответствующими связями. Сумматор может быть использован для по.строения специализированного устройства, работающего в режиме сквозного контроля информации и исправления возникающих ошибок, что позволит этоб му специализированному устройству длительно функционировать с высоким быстродействием. 1 ил., 5 табл.

1532916

ici;

t «(i <2t;

2t i < 3 ; (1) О

g(i-.t)+ у,(&е-3) фь (х-с-|с!

Ь = Ф- 2 при при при при у (j) а

o3t

f g(i)+ 3 (i+1)+e + gg(i+t-2)+ ф,6+ -l) gg(i+3t-3); (3) 2 g<(i)+2 У,(х+1)+...+2 g<(i+t-2)+2 %e(i+t-1) g(i)+ f+(i+1}+...+ .+ ф a(i+t 2)+ gg(i+t-1)+ gg(i+3t-Ç). (4) Этот алгоритм вытекает иэ реккур-рентного соотношения (1). Для пакетного 2-кода (t 2) выражения (3) и (4) преобразуются к виду: 55

g (i)+, (+1) g (i+3); (5)

2 У, (з.)+2 y((i+1) g((i)+ У((л.+1)+ ф!)(3.+3). (6) Изобретение относится к вычислительной технике и может быть использовано для параллельного суммирования многоразрядных двоичных чисел.

Цель изобретения — расширение области применения sa счет суииирования двоичных чисел, представленных в пакетной системе счисления при сохранении воэможности ауимирования двоичных чисел в традиционной и фибоначчиевой системах счисления.

На чертеже представлена схема

i-ro разряда накапливающего суииато" ра (для t 2).

i-й разряд сумиатора содержит триггер 1, сумматор 2 по модулю два, второй 3, седьмой 4,- первый 5, четвертый 6, пятый 7, шестой 8 и третий 9 элементы И, с первого по чет° вертый элементы ИЛИ 10"13, элемент

14 задержки, входы 15 и 16 переноса где t — натуральное число, задающее номер пакетной t-системы счисления; — разрядность кода.

Любое натуральное число А в.пакетном t-коде представляется в следую" щем виде:

А! I...IOO...Î...I ..ДОО...Oil...! (z) Из (2) для любого натурального числа А в пакетном t-коде видно,что Ф

20 иэ (i-3)-ro и (i-1)-го разрядов сумматора, входы 17 и 18 переноса иэ

{i+2)-ro н (i-1)-го разрядов сумма тора, входы 19 и 20 i-х разрядов первого и второго слагаемых в пакетной систеие счисления сумматора, входы

2) и 22 i-x разрядов первого и второго слагаемых в традиционной и фибоначчиевой системах счисления сумматора, выход 23 i-го разряда суммы сумматора, выходы 24-26 переноса в (i+1)-й, (i-2)-й и (i+3)-й разряды сумматора, вход 27 задания традиционной и фибоначчиевой систем счисления сумматора, вход 28 задания пакетной системы счисления суиматора, вход 29 задания фибоначчиевой системы счисления сумматора, вход 30 сброса сумматора.

Вес двоичных разрядов g (i) па" кетных t-кодов задается следующим реккуррентным соотношением: для него характерно наличие пакетов из t единиц, а также не менее (2t-2) нулей между пакетаии из и единиц.

Сложение слагаемых, в которых пакеты из единиц стоят в различных разрядах, выполняется согласно выражению (3), а при нахождении пакетов иэ единиц в одних и тех же разрядахсогласно (4).

Накапливающий сумматор позволяет осуществлять сложение по следующему алгоритму:

Сложение любых двух чисел, представленных в пакетном 2-коде, осуще-. : ствляется согласно выражениям (5) и (6). Если прй сложении слагаемых окажется, что пакеты иэ единиц,.находящиеся в слагаемых, стоят в различных разрядах, то их сложение производится путем переноса единиц иэ ъ-го

5 153 и (i+1)"ro разрядов первого слагаемого в (i+3)-й разряд суммы, а пакет единиц второго слагаемого переносится также в (i+3)-й разряд суммы, ио относительно своей i-й позиции. При сложении i-м считается тот разряд в пакете, у которого наименьшая позиция 1 °

Если пакеты из единиц, находящиеся в слагаемых, стоят в одних и тех же разрядах, то сложение производится по правилу: пакет единиц первого. слагаемого переносится из i-го .и (i+1)-го разрядов в (i+3)-й разряд суммы, а пакет единиц второго слагаемого переходит в сумму без изменения.

При нахождении пакета из единиц в одном из слагаемых происходит перенос единиц из i-го и (i+1)-го разрядов этого слагаемого в (i+3)-й разряд суммы.

Сложение чисел, представленных в пакетной системе счисления, осущест вляется за один такт беэ образования промежуточных сумм, что являет,ся .существенным преимуществом этой системы счисления с ранее известными.

Сумматор работает следующим образом.

При сложении чисел, представленных в традиционной системе счисления, пР подается лишь на вход 27. На входах .

28, 29 присутствует "0". При этих условиях сумматор осуществляет алгоритм сложения

y (i) +4(i) = М.(i+1) Следовательно, имеют значение сигнал данного i-го разряда, сигнал. переноса в старший разряд (х+1)-й, сигнал переноса из (i-1)-го разряда в данный разряд сумматора.

Пример 1. Сложить числа 12

0001100 и 28 = 0011100.(табл.l)..

Процесс сложения разрядов первого и второго слагаемых без учета сигнала переноса .состоит в следующем. триггер 1 со счетным входом формирует сигнал суммы данного i-ro yasряда, поступающий на вход элемента

И 6, разрешающего его выдачу. Сигнал переноса в {i+1)-й разряд сумматора вырабатывается элементами И 5

ИЛИ ll и элементом 14 задержки. Сигнал переноса из (i-1)-ro разряда поступает на вход сумматора 2 по моду2916 6 лю два, который без изменения выдает его на вход элемента ИЛИ 10, подключенного к счетному входу триггера, и суммирует со значением данного разряда.

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

При работе с числами, представленными в фибоначчиевой системе счисления, "1" присутствует на входах 27 и 29. В данном случае сумматор выполняет алгоритм сложения

9 (i)+ ц7 (i) * 4(i+1)+ Ц (з-2).

Следовательно, необходимы сигнал

20 суммы данного разряда, сигналы переноса в (i+1)-й, (i-2)-й разряды, сигналы переноса из (i-1)-го разряда сумматора и (1+2)-.го разряда.

Рассмотрим особенность сложения

25 чисел в этой системе счисления. На- личие двух сигналов переноса в данный i-.é разряд сумматора предполагает необходимость формирования из них сигнала для участия в сложении и сиг-.

30 нала переноса из данного i-ro разряда.

Пример 2. Сложить числа 33 =

;= 010101010 и 28 = 010010100 (табл.2 .

Рассмотрим работу сумматора с учетом изложенного. При наличии лишь од35 ного сигнала переноса в любом разряде на выходе сумматора 2 по модулю два формируется единичный сигнал, который через элемент ИЛИ 10 поступает на счетный .вход триггера 1, где учитывается с поступающим сигналом в данный разряд сумматора.

При наличии одновременно двух сиг налов переноса в любом разряде на 5 капливающего сумматора на выходе сумматора 2 по модулю два формируется нулевой сигнал, который не изменяет состояние триггера, но при этом элементом И 3 формируется единичный сиг-.

50 нал переноса из данного разряда.

Сигнал суммы данного разряда с выхода триггера 1 поступает на вход элемента И 6, подключенного K входу

27, "1" на котором разрешает выдачу суммы данного >-го разряда сумматора.

Сигнал переноса с выхода элемента

ИЛИ 11 через элемент 14 задержки поступает в соответствующие разряды сумматора.

1532916

При работе сумматора с числами, 1 редставленными в пакетной системе счисления, осуществляется алгоритм, представленный соотношениями (5) и (6), этом случае "1" подается на вход

l28 что приводит к работе элементов 1 7 и 8, которые разрешают прохожде ние сигналов переноса в i-.é, (i+1)-й и (i+3)-й разряды, а также подключатся входы 15 и 16 переносов из (i3)-го и (i-1)-го разрядов сумматора соответственно.

Наличие "0" йа входах 27 и 29 приводит к тому, что на выходе эле" ментов И 6 и 9 генерируется "0". Следовательно, сумматор подключен к выходам переносов из (i-3)-го и (i-1)го разрядов и выходам переносов в (i+1)-й и (i+3)-й разряды сумматора, а также к выходу суммы данного i-го

1разряда сумматора. Слагаемые подаются на вход сумматора поочередно, по две единицы (так как t 2) на входы элемента И 4, причем i-м считается тот разряд в пакете из t единиц, у которого наименЪшая позиция

В силу особенности представления чисел в пакетной системе счисления сигналы переноса в (i+1)-й, (i+3)-й разряды поступают в разряды, заведо мо. содержащие "0". Это исключает порождение промежуточных сумм и дополнительных переносов, что приводит к повышению быстродействия сумматора.

П р и и е р 3. Сложить числа 0

000000000000 и 7=000011000000 (табл.3).

При поступлении на вход сумматора слагаемых, в которых пакет из единиц находится только в одном иэ них, на выходе элемента И 4 формируется единичный сигнал, который через элемент ИЛИ 10 поступает на счетный вход триггера 1, переводя его в единичное состояние. Единичный сигнал с выхода триггера 1 поступает на вход элемента И 8, который разрешает прохождение сигналов переноса в (i+3)-й разряд сумматора.

Пример 4. Сложить числа 5 =

=000001100000 и 7 000011000000 (табл, 4).

При поступлении на вход сумматора слагаемых, в которых пакеты из единиц стоят в различных разрядах, на выходе элемента И 4 после каждого поступления пакета из слагаемых поочередно формируются единичные сиг5 калы, которые через элемент ИЛИ 10 переводят триггер 1 в единичные состояния и формируют переносы в (i +

+3)-й разряды сумматора. Перенос в

i-й и (i+1)-й разряды сумматора не производится, так как 1-е разряды в пакетах слагаемых не совпадают, а перед поступлением на вход каждого

i-ro разряда слагаемого на вход 30 сброса подается сигнал, по которому триггеры 1 всех разрядов устанавливаются в нулевое состояние.

Пример 5. Сложить числа 7

=000011000000 и 7 = 000011000000 (табл.5) °

При поступлении на вход сумматора". слагаемых, в которых пакеты из единиц стоят в одних и тех же разрядах, на выходе элемента И 4 после каждого поступления пакета из слагаемых по25 очередно формируются два единичных сигнала, которые через элемент ИЛИ

10 поступают на счетный вход триггера 1. Первый единичный сигнал переводит триггер 1 в единичное состояние. Единичный сигнал с выхода триг- гера 1 поступает на элемент И 8, который разрешает перенос в (i+3)-й разряд сумматора. Второй единичный сигнал переводит триггер 1 в нулевое

35 состояние, но при этом 1срабатывает элемент И 5. Единичный сигнал с выхода элемента И 5 через элемент ИЛИ

11 поступает на вход элемента 14 задержки, с его выхода — на вход элемента И 7 и через элемент ИЛИ 13 в

i-й разряд сумматора, а также одновременно на выход переноса в (i+1)-й разряд.

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

Накапливающий сумматор, содержащий в i-м разряде триггер, сумматор по модулю два, с первого по седьмой элементы И, с первого по четвертый элементы ИЛИ и элемент задержки, при" чем входы i-õ разрядов первого и второго слагаемых в традиционной и фибоначчиевой системах счисления сумматора (i=1...n, n — разрядность слагаемых) соединены соответственно с первым и вторым входами первого элемента ИЛИ i-го разряда сумматора, выход которого соединен со счетным

1532916

Таблица 1

О

0 0

0 0

0 0

0 1 1

1 1 1 о о о о о о о о о

1 0 1 0

0

О.

0 Сумма входом триггера и с первым входом первого элемента И i-го разряда сумматора, вход сброса сумматора соединен с входами установки в "0". триг5 геров разрядов сумматора, прямой выход триггера i-го разряда сумматора соединен с вторым входом первого эле" мента И i-ro разряда сумматора, выходы первого и второro элементов И

i-го разряда сумматора соединены соответственно с первым и вторым входами второго элемента ИЛИ i-ro разряда сумматора, выход сумматора по модулю два i-го разряда сумматора,: соединен с третьим входом первого элемента ИЛИ i-ro разряда сумматора, выход второго элемента,ИЛИ i-го раз-, ряда сумматора через элемент задержки соединен с первым входом третьего элемента И i-го разряда сумматора, второй вход которого соединен с входом задания "фибоначчиевой" системы счисления сумматора, вход задания традиционной и "фибоначчиевой" 25 систем счисления сумматора соединен с первым входом четвертого элемента

И i-го разряда сумматора, выход коI торого соединен с первым входом третьего элемента HJIH i-ro разряда сумматора, выходы третьего элемента

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

1-го разряда сумматора, выход элемента задержки i-го разряда сумматора соединен с вторым входом пятого элемента И i-го разряда сумматора, прямой выход триггера i-го разряда сумматора соединен с вторым вход0м четвертого элемента И 1. го разряда сумматора, входы i-x разрядов с первого по t-e слагаемых {t — параметр пакетной системы) в пакетной системе счисления сумматора соединены с соответствующими входами седьмого элемента H i-ro разряда сумматора, выход которого соединен с четвертым входом первого элемента ИЛИ i-ro разряда сумматора, выход четвертого элемента ИЛИ i-ro разряда сумматора является выходом х-го разряда суммы сумматора, выход элемента задержкиi-го разряда сумматора соединен с первыми входами сумматора по модулю два и второго элемента И (i+1)-ão разряда сумматора, выход третьего элемента И i-го разряда сумматора соединен с вторыми входами сумматора по модулю два и второго элемента

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

ИЛИ i-ro разряда сумматора соедине- . ны соответственно с выходами элементов задержки с (i-1)-го по (i-t+1)-й разрядов сумматора, (t+1)-й вход третьего элемента ИЛИ k-го разряда сумматора соединен с выходом шестого. элемента И (i-Зй-3)-го разряда сумматора.

0 Первое слагаемое

0 Второе слагаемое

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

1532916

Таблица 2

Вес разрядов

1 II

Примечание

34 21 13 8 5 3 2 1 1

Первое слагаемое

Второе слагаемое

1 О l.

О 1 О

О 1 0

О 1 0

О 1

О 0 0

1 О 1

1. 0 О

О 1

I 0

1 0 1

1 О 1 1 О 1 Сумма

Вес: pas рядов

12 9 7 5, 4 3 2 2 1 I 1 О

О О О О О О О 0 О Первое слагаемое

О О О . 0 О О Второе. слагаемое

0 О О

0 О

1 Сигналы переноса

О О О О О О О, Сумма

i+1

О О

i+3

О 0 1

Вес разрядов

12 9 7 5 4 3 2 2 1 1 1 О . +3 1+! i Сигнал переноса

6 Ъ Т 1

0 0 О О .1 1 0 0 О О О О Второе слагаемое

i+l i Сигналы переноса

1 О О О 0 0 О 0 О Сумма

i+3

0 0 1

1 О 1

1 О 1

1 О 1

О 1 О

1 0 0

1 О ! I О

Таблица 3

Примечание

Таблица 4

Примечание

13!

1532916

Вес разрядов

I i t t ) т 1

Таблица5

Примечание

i+1 i

i+3

1 1

Сигналы переноса

0 Сумма

0 0 0 0 0

0 0 1

Составитель А.Клк ев

Редактор Л.Пчолинская Техред.Jf.Îëèéíûê Корректор В.Кабаций

Заказ 8100/53 Тираж 668 Подписное

ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР

f13035, Москва, Ж-35,,Раушская наб., д. 4/5

Производственно-издательский комбинат "Патент" ° г.ужгород, ул. Гагарина, 101

0 0 О 0

0 0 0 0

1 I

i+1

1 1

0 0 0 0 0

0 0 0 0 0

Сигналы переноса

0 Первое слагаемое

0 Второе слагаемое