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

(Л

С

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

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

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

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

А 2 aiЧЧО, где ai E{0, 1}

I 1

О, при i 0

4(i) I 1, при 1 0(1) xP(i-1) + W(i-2), .

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

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

Веса разрядов Ґ(0 55 34 21 1385321 1 Форма представления числа 851 0 1 0 100010

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

ЧЧО + ЧЧО- 4(i + 1) + 44i - 2)(2)

00

о о ел

4

Ч (i)+ 4(i-1) ЧЧ14-1)(3)

Следовательно, правило сложения имеет вид:

00 01 00 10 00 10 10Пунктиром обведены анализируемые

+ + + + + + +разряды слагаемых. В данном случае код

00 00 01 00 10 01 К)суммы получился в нормализованной фор00 01 01 10 10 100 1001ме, В ряде других случаев он может быть

5получен в ненормализованной форме, наТаким образом, в предлагаемомпример при сложении чисел А

способе сложения, в отличие от извест- 01001010010 и 6 01000001001

ного, анализируются два разряда слагаемого-10 V0 89 55 34 21 13 8 5 3 2 1 1

Допустим, нужно сложить числа А п п Г.1 01000010010 и В 01000001000, тогда А °«1 °| ,1 °, ° ,1 °,

+ м i i

В О И 000 0| |0 1i 0 0 11 V® 89 55 34 21 13 8 5 3 2 1 1 15I -- ---U---i--I

г---, i- - -i S 10011100100 А 0 7 0 0 0 0 1 0 | 0 1 0 | . - --- -1--

4

В ОМ 0,0 О О О 1|OiO 0 Как в первом, так и во втором случае -25

Особенностью предлагаемого спо-сумматоре кодов Фибоначчи формирусоба сложения является поступлениеет с я частично нормализованный

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

при наличии единицы в i-м разряде 30Рассмотрим сложение этих же чи- первого слагаемого и (i - 1)-м разрядесел в прототипе предлагаемого сумма- второго слагаемого, в результате чего втора:

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

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

Сущность изобретения состоите реализации выражений (2) и (3). Функциональная схема i-ro разряда (i 1 -j-n) сумматора представлена на чертеже.

Сумматор i-ro разряда (i 1 -j-n) содержит триггер 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-ro разряда сумматора 13, выходы переносов в (1+1)-й 15 и в (-2)-й разряды сумматора, шина 16 сброса, управляющая шина 26 разрешения суммирования в фибоначчиевой системе счисления.

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

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

- 2)-й разряд сумматора 14, выход элемента И 19 подключен к четвертому входу элемента ИЛИ 5 и к входу элемента задержки 22, выход которого соединен со вторым входом элемента ИЛИ 23, выход которого является

выходом переноса в (i + 1)-й разряд сумматора 15, единичный выход триггера 1 со счетным входом является выходом суммы данного i-ro разряда 13. Назначение элементов.

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

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

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

сигналов переноса.

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

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

Сумматор по модулю два 8 формирует

из сигналов переноса сигнал, участвующий в сложении.

Элемент И 2 формирует из сигналов переноса сигнал переноса в соседние разряды.

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

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

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

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

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

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

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

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

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

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

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

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

0 единичном состоянии. Сформированный импульс является импульсом переноса в (i + 1)-й разряд и одновременно переводит триггер данного разряда в нулевое состояние. Если же триггер находился в нулевом

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

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

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

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

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

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