НАКАПЛИВАЮЩИЙ СУММАТОР Российский патент 1995 года по МПК G06F7/49 

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

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

Наиболее близким к изобретению является накапливающий сумматор (2), содержащий в каждом i-ом (i , где n разрядность операндов) разряде триггер, восемь элементов И, шесть элементов ИЛИ, элемент задеpжки и два сумматора по модулю два, причем первый и второй входы первого элемента ИЛИ соединены соответственно с входами первого и второго слагаемых данного разряда сумматора, вход разрешения сложения в минимальной системе счисления сумматора соединен с первыми входами первого и второго элементов И, выход первого элемента И соединен с первыми входами первого сумматора по модулю два, второго и третьего элементов ИЛИ, выход второго элемента И соединен с первым входом четвертого элемента ИЛИ, выходы которого соединены с выходами второго сумматора по модулю два и пятого элемента ИЛИ и вторым входом третьего элемента ИЛИ, выход которого соединен с первым входом третьего элемента И, второй вход которого соединен с выходом второго элемента ИЛИ, второй вход которого соединен с вторым входом пятого элемента ИЛИ, выход которого соединен с первым входом четвертого элемента И, второй вход которого соединен с выходом пятого элемента ИЛИ, выход второго сумматора по модулю два соединен с вторым входом первого сумматора по модулю два, выход которого соединен с третьим входом первого элемента ИЛИ, выход которого соединен со счетным входом триггера и первым входом пятого элемента И, второй вход которого соединен с выходом триггера, выход пятого элемента И соединен с первым входом шестого элемента ИЛИ, второй вход которого соединен с выходом четвертого элемента И, выход шестого элемента ИЛИ через элемент задержки соединен с первыми входами шестого и седьмого элементов И, второй вход седьмого элемента И соединен с входом разрешения сложения в минимальной системе счисления сумматора, вход разрешения сложения в Фибоначчиевой системе счисления сумматора соединен с вторым входом шестого элемента И и первым входом восьмого элемента И, выход которого соединен с вторым входом четвертого элемента ИЛИ, выход седьмого элемента И соединен с выходом переноса в (i-3)-й разряд сумматора, вход сброса триггера соединен с входом сброса сумматора, отличающийся тем, что с целью упрощения сумматора, вход переноса из (i-1)-го разряда сумматора соединен с вторыми входами второго сумматора по модулю два и вторым входом второго элемента ИЛИ, входы переносов из (i+5)-го, (i+3)-го, (i+2)-го разрядов сумматора соединены соответственно с вторыми входами первого, второго и восьмого элементов И, выход триггера соединен с выходом суммы данного разряда сумматора, первый вход седьмого элемента И и выход шестого элемента И соединены соответственно с выходами переноса в (i+1)-й, (i=5)-й и (i-2)-й разряды сумматора.

Недостаток этого устройства низкое быстродействие.

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

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

Любое натуральное число А в двоичной минимальной системе счисления представляется в виде многочлена:
A(i)Ψ(i) где α(c)∈{0,1}
Ψ(i) ,1 (1)
Значение ϕ (n+1) определяет мощность минимального n-разрядногоо кода.

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

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

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

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

Допустим, нужно сложить числа А(112) 010000100001000000 и В(104) 010000010000000100, тогда

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

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


Для сложения чисел А и В в прототипе предлагаемого сумматора потребовалось 10 тактов, а в данном сумматоре необходимо 5 тактов, т.е. в два раза меньше.

Таким образом, среднее время быстродействия предлагаемого сумматора выше.

Из сказанного вытекает алгоритм сложения:
1)образование промежуточной суммы и сигналов переноса;
2) суммирование промежуточной суммы и сигналов переноса;
3) повторение п.1,2 до тех пор, пока промежуточная сумма не станет эквивалентна окончательной, о чем свидетельствует нулевой сигнал переноса.

Сущность изобретения состоит в реализации выражений (2), (3), (4).

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

Одноразрядный накапливающий сумматор содержит: триггер со счетным входом 1, элементы И 16-23, 35, элементы ИЛИ 24-27, элементы задержки 28-31, сумматор по модулю два 32, элементы ЗАПРЕТ 33, 36, элемент И с прямыми и инверсным входами 34, входные шины первого 2 и второго 3 слагаемых данного разряда, входные шины первого слагаемого из (i+4)-го разряда 10 и из (i+1)-го разряда 11, входные шины второго слагаемого из (i-1)-го разряда 5 и из (i-4)-го разряда 6, входные шины переносов из (i-2)-го разряда 8, из (i-1)-го разряда 37 и из (i+5)-разряда 9, выход суммы 12, выходы переносов в (i-5)-й 13, (i+2)-й 14, (i-1)-й 15 разряды, шина сброса 7, управляющая шина разрешения суммирования в минимальной системе счисления 4.

Первое слагаемое i-го разряда подается с входа 2 на третий вход элемента ИЛИ 24, первый вход которого подключен к выходу сумматора по модулю два 32, а выход к счетному входу триггера 1, нулевой вход которого подключен к шине сброса 7, а единичный выход является выходом суммы 12 данного разряда и подключен к первому входу элемента И 22, выход элемента И 20 подключен к первому входу элемента ИЛИ 26, выход которого через первый элемент задержки 28 подключен к первому входу элемента И 23, выход которого является выходом переноса в (i-5)-разряд 13, а второй вход подключен к вторым входам элемента И 17 и элемента И 18, выход которого подключен к второму входу элемента ИЛИ 25, первый вход которого соединен с выходом элемента И 19, второе слагаемое i-го разряда подается с входа 3 на прямой вход элемента ЗАПРЕТ 33, инверсный вход которого подключен к выходу элемента задержки 31, а выход подключен к второму входу элемента ИЛИ 24, четвертый и пятый вход которого подключены соответственно к выходам элементов И 22, 21, которые подключены соответственно через элементы задержки 30, 29, к выходу переноса в (i+1)-й разряд 15 и к второму входу элемента ИЛИ 27, выход которого подключен к второму входу элемента И 35, первый вход которого соединен с управляющей шиной 4 и инверсным входом элемента ЗАПРЕТ 36, связанного выходом с выходом переноса в (i+1)-й разряд 15 и прямым входом с первыми входами элементов ИЛИ 27 и И 23, а выход элемента И 35 является выходом переноса в (i+2)-й разряд 14, выход элемента ИЛИ 24 подключен к первому входу элемента И 34 с прямыми и инверсным входами, инверсный вход которого соединен с выходом элемента ИЛИ 25, выход соединен с вторым входом элемента ИЛИ 26, а второй вход соединен с первыми входами элементов И 21, 22, вторые входы которых подключены соответственно к выходам элементов И 18, 19, первые входы которых подключены соответственно к входам сигналов из (i-1)-го 5 и (i-4)-го 6 разрядов второго слагаемого, сигналы из (i+4)-го и (i+1)-го разрядов первого слагаемого с входов 10, 11 подаются соответственно на первые входы элементов И 16, 17, выходы которых подключены к входу элемента задержки 31, а вторые входы соединены с вторым входом элемента И 19 и с управляющей шиной 4, сигнал переноса из (i-2)-го разряда с входа 8 подается на первые входы элемента И 20 и сумматора по модулю два 32, а перенос из (i+5)-го или из (i-1)-го разрядов соответственно с входов 9, 37 подается на вторые входы этих же элементов.

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

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

Элементы И 21, 22, И 34, ИЛИ 25, 27 формируют сигнал переноса, возникающий в данном разряде сумматора.

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

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

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

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

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

Элементы И 16-19, 23, 35 разрешают прохождение слагаемых из соседних разрядов при суммировании чисел в минимальной системе счисления.

Элемент ЗАПРЕТ 36 предназначен для формирования сигнала переноса при суммировании в традиционной двоичной системе счисления.

Введенные элементы обеспечивают достижение положительного эффекта, так как обладают признаком "существенные отличия".

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

При сложении чисел в минимальной системе счисления на шину управления 4 подается сигнал, разрешающий прохождение слагаемых из соседних разрядов и сигналов переноса через элементы И 16-19, 23.

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

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

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

При наличии второго слагаемого в (i-4)-м разряде оно поступает через элементы И 19, ИЛИ 25 на инверсный вход элемента И 34, что запрещает прохождение импульса переноса в (i-5)-й разряд и на элемент И 22, который формирует единичный импульс только тогда, когда триггер находится в единичном состоянии. Сформированный импульс является импульсом переноса в (i+1)-й разряд и одновременно переводит триггер данного разряда в нулевое состояние.

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

При сложении чисел, представленных в традиционной двоичной системе счисления, на управляющую шину 4 поступает сигнал, которым запрещается прохождение в данный разряд слагаемых из соседних разрядов через элементы И 16-19 и прохождение импульсов переноса в младшие разряды через элементы И 23, 35.

Изобретение относится к автоматике и вычислительной технике и может быть использовано для параллельного суммирования многоразрядных двоичных чисел. Изобретение предназначено для повышения быстродействия сумматора за счет получения частично разрешенного значения суммы при сложении чисел, представленных в двоичной избыточной минимальной системе счисления. Одноразрядный накапливающий сумматор содерит триггер со счетным входом 1, элементы И 16-23, 35, элементы ИЛИ 24-27, элементы задержки 28-31, сумматор по модулю два 32, элементы ЗАПРЕТ 33, 36, элементы И с прямыми и инверсным входами 34. Техническое решение поставленной задачи достигается введением трех элементов задержки 29-31, двух элементов ЗАПРЕТ 33, 36, элемента И 35, элемента И 34 с прямыми и инвесным входами. На выходе сумматора формируется код частично разрешенной суммы в соответствии с выражениями, приведенными в тексте описания. 1 ил.

НАКАПЛИВАЮЩИЙ СУММАТОР, каждый i-й разряд которого (), где n - разрядность сумматора) содержит триггер со счетным входом, первого по восьмой элементы И, четыре элемента ИЛИ, сумматор по модулю два и первый элемент задержки, причем вход первого слагаемого i-го разряда сумматора подключен к третьему входу первого элемента ИЛИ, первый вход которого подключен к выходу сумматора по модулю два, а выход- к счетному входу триггера, вход установки в "0" которого подключен к шине сброса сумматора, выход триггера является выходом суммы данного раязряда сумматора и подключен к первому входу седьмого элемента И, выход пятого элемента И подключен к первому входу третьего элемента ИЛИ, выход которого через первый элемент задержки подключен к первому входу восьмого элемента И, выход которого является выходом переноса в (i -5-й) разряд сумматора, а второй вход подключен к вторым входам второго и третьего элементов И, выход которого подключен к второму входу второго элемента ИЛИ, первый вход которого соединен с выходом четвертого элемента И, отличающийся тем, что в каждый разряд накапливающего сумматора введены второй, третий и четвертый элементы задержки, первый и второй элементы ЗАПРЕТ, элемент И с прямыми и инверсным входами, девятый элемент И, причем вход второго слагаемого i-го разряда сумматора подключен к прямому входу первого элемента ЗАПРЕТ, инверсный вход которого подключен к выходу четвертого элемента задержки, а выход подключен к второму входу первого элемента ИЛИ, четвертый и пятый входы которого подключены соответственно к выходам седьмого и шестого элементов И, выходы которых подключены соответственно, через третий и второй элементы задержки к выходу переноса в (i + 1-й) разряд сумматора и к второму входу четвертого элемента ИЛИ, выход которого подключен к второму входу девятого элемента И, первый вход которого соединен с управляющей шиной сумматора и инверсным входом второго элемента ЗАПРЕТ, связанного выходом с выходом переноса в (i+ 1-й) разряд сумматора, прямой вход второго элемента запрета подключен к первым входам четвертого элемента ИЛИ и восьмого элемента И, выход девятого элемента И является выходом переноса в (i + 2-й)-разряд сумматора, выход первого элемента ИЛИ подключен к первому прямому входу элемента И с прямыми и инверсным входами, инверсный вход которого соединен с выходом второго элемента ИЛИ, выход элемента И с прямыми и инверсным входами соединен с вторым входом третьего элемента ИЛИ, второй прямой вход которого соединен с первыми входами шестого и седьмого элементов И, вторые входы которых поключены соответственно, к выходам третьего и четвертого элементов И, первые входы которых подключены соответственно к входам (i-1-го) и (i+4-го) разрядов второго слагаемого сумматора, входы (i+4-го) и (i+1-го) разрядов первого слагаемого сумматора подключены соответственно к первым входам первого и второго элементов И, выходы которых подключены к входу четвертого элемента задержки, а вторые входы первого и второго элементов И соединены с вторым входом четвертого элемента И и управляющий шиной сумматора, сигнал переноса из (i-2-го) разряда сумматора подключен к первым входам пятого элемента И и сумматора по модулю два, вторые входы которых подключены к входам сигналов переноса из (i+5-го) и (i-1-го) разрядов сумматора через МОНТАЖНОЕ ИЛИ.