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

 

Изобретение относится к автоматике и вычислительной технике и может использоваться для параллельного суммирования многоразрядных двоичных чисел. Цель изобретения - повышение быстродействия за счет получения частично нормализованной суммы. Поставленная цель достигается введением в каждый разряд накапливающего сумматора трех элементов И, двух элементов задержки, элемента ИЛИ, элемента ЗАПРЕТ , Сумматор содержит также триггер со счетным входом, три элемента И, два элемента ИЛИ, сумматор по модулю два. Предлагаемый сумматор может быть использован для построения вычислительных системе высоким быстродействием и помехоустойчивостью , 1 ил.

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

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

РЕСПУБЛИК (s»>s G 06 F 7/49

ГОСУДАРСТВЕННОЕ ПАТЕНТНОЕ

ВЕДОМСТВО СССР (ГОСПАТЕ НТ СССР)

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

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

О

О

3 (Я

Ф.

А= Х a1V(i), гдеai Е(0,1)

1=1 (3) (21) 4936451/24 (22) 14.05.91 (46) 07.03.93. Бюл. М 9 (72) А.B.Òêà÷åíêo, Д.В.Харламов и А.С,Шарафутдинов (56) 1. Авторское свидетельство СССР

¹ 840891, кл. G 07 F 7/49, 1978.

2. Авторское свидетельство СССР

N- 455340, кл. G 06 F 7/50, 1971.

3. Авторское свидетельство СССР

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

Цель данного изобретения — повышение быстродействия сумматора за счет получения частично нормализованной суммы.

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

О,приi<0

V(i)= 1, при i =0 (1)

V(i — 1) + V(i - 2), при > 1.,, 42,„, 1800454 А1 ваться для параллельного суммирования многоразрядных двоичных чисел. Цель изобретения — повышение быстродействия за счет получения частично нормализованной суммы. Поставленная цель достигается введением в каждый разряд накапливающего сумматора трех элементов И, двух элементов задержки, элемента ИЛИ, элемента ЗАПРЕТ. Сумматор содержит также триггер со счетным входом, три элемента И, два элемента ИЛИ, сумматор по модулю два.

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

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

Например, число 85 можно представить в следующем виде:

Веса разрядов V(i) 55 34 21 13 8 5 3 2 1 1

Форма представлениячисла85 1 0 1 0 100010

Исходя из рекуррентного соотношения (1) предлагаемый способ сложения имеет вид:

V(i) + V(i) = V(i + 1) + V (i - 2) (2)

V(i)+ V(i — 1) = Ч (+1) Следовательно, правило сложения имеет вид:

1800454

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

=01001010010 и В = 01000001001

00 01 00 10 00 10 10

+ + + + + + +

00 00 01 00 10 01 10

00 01 01 10 10 100 1001

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

10 фО1 89 55 34 21

А О 1 010

В 011 О!О

13 8 5 3 2 1 1

Допустим, нужно сложить числа А =

=01000010010 и В = 01000001000, тогда

О 10 11 ф01 89553421 13 8 5 3 2 1 1

S 1 О О 1 1 О О 1 ΠΠ— — Ю Ф .— —..!

О 0,1 0,0,1 О!

0 О О 110 !О 01 !

О, 1 О! О

Ф

В 011 О О

Как в первом, так и во втором случае

20 сложение происходит в один такт, Но чаще для суммирования требуется несколько тактов. Рассмотрим сложение чисел А =

0100100010 и В = 0101010101:

S 1 О О 1 О 1 О О О 1 О

3 2 1

Г

О lo !1 ! ! 1

О 1 iOi

13 8 !

О 11, О!

1 о!

1 !

55 34 21

О

О .J

В

Первая п ромежуточная О

О О, 1

О О О

О О сумма

Рц+1

Возникшие переносы

Рц-2

Вторая промежуточная 1 О О 1 О О О О О О сумма

Рц+1

Возникшие переносы

1 Pi i 2

1 О О

1 О

Код суммы 1 О

Особенностью предлагаемого способа сложения является поступление сигнала переноса в (i + 1)-й разряд при наличии единицы в i-м разряде первого слагаемого и (i — 1)-м разряде второго слагаемого, в результате чего в сумматоре кодов Фибоначчи формируется частич но нормализованный код суммы.

30 Рассмотрим сложение этих же чисел в прототипе предлагаемого сумматора:

1 1

1 01

1

11 О1

11 0111 О

11 I

I ,О 01 !О 1 I

1S00<54

55 34 21 13 8

О 1

О 1

О 1

О 1

Первая промежуточная О 0 сумма

О 1

Возникшие переносы

Pi,i-2

Вторая промежуточная 1 О О 0 сумма

1 О

Возникшие переносы

1 О 1 0

1 1

О О переносы

Четвертая промежуточ- 1 ная сумма

Возникшие

О 1 О О О О 0 1

Pi,н1

Р,-z переносы

Пятая промежуточная 1 О 1 1 О сумма

О О О

Pi,i+1

Возникшие переносы

Шестая промежуточная 1 О 1 1 О сумма

О 0

Возникшие переносы

1 Pi,i-2

Код суммы 1 О 1

1 О

О 1

Третья промежуточная сумма

Возникшие

О О 1

О 1 О

5 3 2 1 1

О 0 О 1 О

1800454

Таким образом, для суммирования чисел А и В посредством известного сумматора необходимы семь тактов суммирования и два такта нормализации. В данном сумматоре необходимы три такта суммирования и два — нормализации. В результате среднее быстродействие сумматора возрастает.

Из сказанного выше вытекает алгоритм сложения;

1. Образование промежуточной суммы и сигналов переноса.

2. Суммирование промежуточной суммы и сигнала переноса.

3. Повторение пп.1 и 2 до тех пор, пока промежуточная сумма не станет эквивалентна окончательной, о чем свидетельствует нулевой сигнал переноса, Сущность изобретения состоит. в реализации выражений (2) и (3). Функциональная схема i-го разряда (i = 1 —:и) сумматора представлена на чертеже.

Сумматор i-ro разряда (i = 1+и) содержит триггер 1 со счетным входом, элементы

И 2, 4, 17, 18 и 19, элемент И 3 с двумя прямыми и инверсным входами, элементы

ИЛИ 5, 6, 23, элементы задержки 7, 21, 22 элемент ЗАПРЕТ 20, сумматор 8 по модулю два, входные шины первого 9 и второго 10 слагаемых данного разряда, входные шины

24 и 25 первого слагаемого из (i + 1)-го разряда и второго слагэемого из (i -1)-го разряда 25 сумматора, входные шины переносов из (i+ 2)-го рэзряда 11 и из (i — 1)-го разряда

12, выход суммы данного i-го разряда сумматора 13, выходы переносов в (1+1)-й 15 и в (i — 2)-й разряды сумматора. шина 16 сброса, управляющая шина 26 разрешения суммирования в "фибоначчиевой" системе счисления.

Входная шина 24 первого слагаемого из (i+ 1)-го разряда подключена к первому входу элемента И 17, второй вход которого подключен к управляющей шине 26, а выход — x входу элемента задержки 21, выход которого подключен к инверсному входу элемента

ЗАПРЕТ 20, другой вход которого соединен с входной шиной второго слагаемого денного разряда 10, а выход — с первым входом элемента ИЛИ 5, второй вход которого соединен со входной шиной первого слагаемого данного разряда 9, а третий — с выходом сумматора 8 по модулю два, входы которого подключены к входным шинам переносов из (i+ 2)-го 11 и (i -1)-го 12 разрядов сумматора, которые подключены также к входам элемента И 2, выход которого соединен с первым входом элементв ИJlÈ 6, выход элемента ИЛИ 5 подключен к первому входу элемента ИЗсдвумя прямымииинверсным

55 входами и к счетному входу триггера 1, нулевой вход которого соединен с шиной сброса 16, а единичный выход — с первым входом элемента И 19 и вторым входом элемента И 3 с двумя прямыми и инверсным входами, инверсный вход которого соединен с входом элемента И 19 и выходом элемента И 18, первый вход которого подключен к входной шине 25 второго слагаемого из (i -1)-ro разряда, а второй вход— к управляющей шине 26, выход элемента И с двумя прямыми и инверсным входами 3 подключен ко второму входу элемента ИЛИ

6, выход которого соединен с входом элемента задержки 7; выход которого подключен к первому входу элемента ИЛИ 23 и к первому входу элемента И 4, другой вход которого подключен к управляющей шине

26, а выход является выходом переноса в (I

- 2)-й разряд сумматора 14, выход элемента

И 19 подключен к четвертому входу элемента ИЛИ 5 и к входу элемента задержки 22, выход которого соединен со вторым входом элемента ИЛИ 23, выход которого является выходом переноса в (i + 1)-й разряд сумматора 15, единичный выход триггера 1 со счетным входом является выходом суммы данного i-го разряда 13.

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

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

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

Элементы И 3, И 19, ИЛИ 23 формируют сигнал переноса, возникающий в данном разряде сумматора, Элементы задержки 7, 22 предназначены для задержки сигналов переноса из данного разряда на величину времени, необходимую для перехода триггеров в устойчивое состояние.

Сумматор по модулю два 8 формирует из сигналов переноса сигнал, участвующий в сложении, Элемент И 2 формирует из сигналов переноса сигнал переноса в соседние разряды.

Элемент задержки 21 предназначен для согласования времени поступления на элемент ЗАПРЕТ второго слагаемого данного разряда и первого слагаемого из (i + 1)-го разряда.

1800454

Элемент ЗАПРЕТ 20 разрешает прохождение второго слагаемого данного разряда при отсутствии первого слагаемого в (i

+ 1)-м разряде.

Элементы И 4, И 17, И 18 разрешают прохождение слагаемых из соседних разрядов и сигнала переноса в (i — 2)-й разряд при суммировании чисел в "фибоначчиевой" системе счисления.

Введенные новые элементы и связи составляют существенные отличия предлагаемого сумматора от прототипа и ведут к повышению быстродействия.

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

На шину сброса 16 подается сигнал, устанавливающий триггеры 1 всех разрядов в нулевое состояние. Слагаемые подаются на параллельные входы разрядов сумматора последовательно во времени, причем временной интервал между поступлением двух чисел достаточен для формирования сигналов переноса и их передачи через элементы задержки 7, 22. Время задержки элементов

7, 22 должно превышать время переключения триггера и длительность импульса записи, вместе взятые. Время задержки элемента 20 задержки должно быть равно временному интервалу между поступлениями на вход сумматора первого и второго слагаемых.

При сложении чисел в "фибоначчиевой" системе счисления на шину 26 управления подается сигнал, разрешающий прохождение слагаемых из соседних разрядов и сигнала переноса через элементы И 17, И 18, И

Слагаемые данного разряда поступают через элемент ИЛИ 5 на счетный вход триггера 1, причем второе слагаемое проходит только в том случае, если отсутствует первое слагаемое в(! +1)-м разряде сумматора. При его наличии сигнал из (i+ 1)-го разряда проходит через элемент задержки 21 и запирает элемент ЗАПРЕТ 20 для прохождения второго слагаемого данного разряда, так как, согласно соотношению (3),. оно будет использовано для формирования сигнала переноса в (! + 1)-м разряде сумматора.

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

55 формирует сигнал переноса из данного разряда сумматора.

При наличии второго слагаемого в (i1)-м разряде оно поступает через элемент И

18 на инверсный вход элемента И 3, что запрещает прохождение импульса переноса в (i - 2)-й разряд и на элемент И 19, который формирует единичный импульс только тогда, когда триггер находится в единичном состоянии. Сформированный импульс является импульсом переноса в (i + 1)-й разряд и одновременно переводит триггер данного разряда в нулевое состояние, Если же триггер находился в нулевом состоянии, т.е. первое слагаемого данного разряда отсутствовало и сигнал переноса в данный разряд не поступал, то второе слагаемое из (i - 1)-го разряда не учитывается в

i-м разряде.

При сложении чисел, представленных в традиционной двоичной системе счисления, на управляющую шину 26 поступает сигнал, которым запрещается прохождение в данный разряд слагаемых из соседних разрядов через элементы И 17; И 18 и прохождение импульсов переноса в младшие разряды через элемент И 4.

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

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

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

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

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

И

Составитель А. Ткаченко

Редактор С. Кулакова Техред M. Моргентал Корректор Т. Вашкович

Заказ 1165 Тираж Подписное

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

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

Производственно-издательский комбинат "Патент", г. Ужгород, ул.Гагарина, 1,01 дом второго элемента ИЛИ, о т л и ч а ю щ и йс я тем, что, с целью увеличения быстродействия за счет получения частично нормализованной суммы, в каждый разряд накапливающего сумматора введены четвертый, пятый, шестой элементы И, второй и третий элементы задержки, третий элемент ИЛИ, элемент ЗАПРЕТ, причем первое слагаемое из (i + 1)-го разряда сумматора подается на первый вход четвертого элемента И, на второй вход которого подается сигнал разрешения суммирования в "фибоначчиевой" системе счисления, выход четвертого элемента И через второй элемент задержки подключен к инверсному входу элемента ЗАПРЕТ, второй вход которого подключен к входной шине второго слагаемого данного I-го разряда, а выход элемента ЗАПРЕТ подключен к третьему входу первого элемента

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

"фибоначчиевой" системе счисления, а выход пятого элемента И подключен к инверсному входу второго элемента И к первому входу шестого элемента И, второй вход ко10 торого соединен с единичным выходом триггера со счетным входом, а выход шестого элемента И подключен к четвертому входу первого элемента ИЛИ и через третий элемент задержки — к первому входу треть15 его элемента WIN, второй вход которого соединен с выходом первого элемента задержки, а выход третьего элемента ИЛИ является выходом переноса в (i + 1)-й разряд сумматора.