накапливающий сумматор
Классы МПК: | G06F7/49 для вычислений, выполняемых над числами с основанием, отличным от 2, 8, 16 или 10, например с троичным отрицательным или мнимым основаниями, комплексными основаниями |
Автор(ы): | Ткаченко А.В., Давыдкин А.А. |
Патентообладатель(и): | Давыдкин Алексей Александрович |
Приоритеты: |
подача заявки:
1993-07-12 публикация патента:
10.09.1995 |
Изобретение относится к автоматике и вычислительной технике и может быть использовано для параллельного суммирования многоразрядных двоичных чисел. Изобретение предназначено для повышения быстродействия сумматора за счет получения частично разрешенного значения суммы при сложении чисел, представленных в двоичной избыточной минимальной системе счисления. Одноразрядный накапливающий сумматор содерит триггер со счетным входом 1, элементы И 16-23, 35, элементы ИЛИ 24-27, элементы задержки 28-31, сумматор по модулю два 32, элементы ЗАПРЕТ 33, 36, элементы И с прямыми и инверсным входами 34. Техническое решение поставленной задачи достигается введением трех элементов задержки 29-31, двух элементов ЗАПРЕТ 33, 36, элемента И 35, элемента И 34 с прямыми и инвесным входами. На выходе сумматора формируется код частично разрешенной суммы в соответствии с выражениями, приведенными в тексте описания. 1 ил.
Рисунок 1
Формула изобретения
НАКАПЛИВАЮЩИЙ СУММАТОР, каждый i-й разряд которого (![накапливающий сумматор, патент № 2043650](/images/patents/429/2043650/2043650-23t.gif)
Описание изобретения к патенту
Изобретение относится к автоматике и вычислительной технике и может быть использовано для параллельного суммирования многоразрядных двоичных чисел. Известно параллельное устройство для сложения чисел, представленных в двоичной избыточной системе счисления, представляющее собой цепочку последовательно связанных одноразрядных сумматоров, количество которых равно числу разрядов суммируемых чисел (1). Наиболее близким к изобретению является накапливающий сумматор (2), содержащий в каждом i-ом (i![накапливающий сумматор, патент № 2043650](/images/patents/429/2043650/2043650-2t.gif)
![накапливающий сумматор, патент № 2043650](/images/patents/429/2043650/2043650-3t.gif)
A
![накапливающий сумматор, патент № 2043650](/images/patents/429/2043650/2043650-4t.gif)
![накапливающий сумматор, патент № 2043650](/images/patents/429/2043187/936.gif)
![накапливающий сумматор, патент № 2043650](/images/patents/429/2043002/945.gif)
![накапливающий сумматор, патент № 2043650](/images/patents/429/2043639/8712.gif)
![накапливающий сумматор, патент № 2043650](/images/patents/429/2043187/936.gif)
![накапливающий сумматор, патент № 2043650](/images/patents/429/2043650/2043650-5t.gif)
![накапливающий сумматор, патент № 2043650](/images/patents/429/2043650/2043650-6t.gif)
![накапливающий сумматор, патент № 2043650](/images/patents/429/2043650/2043650-7t.gif)
![накапливающий сумматор, патент № 2043650](/images/patents/429/2043650/2043650-8t.gif)
Значение
![накапливающий сумматор, патент № 2043650](/images/patents/429/2043172/981.gif)
![накапливающий сумматор, патент № 2043650](/images/patents/429/2043650/2043650-9t.gif)
![накапливающий сумматор, патент № 2043650](/images/patents/429/2043650/2043650-10t.gif)
![накапливающий сумматор, патент № 2043650](/images/patents/429/2043650/2043650-11t.gif)
![накапливающий сумматор, патент № 2043650](/images/patents/429/2043650/2043650-12t.gif)
Следовательно, правило сложения имеет вид:
![накапливающий сумматор, патент № 2043650](/images/patents/429/2043650/2043650-13t.gif)
![накапливающий сумматор, патент № 2043650](/images/patents/429/2043650/2043650-14t.gif)
![накапливающий сумматор, патент № 2043650](/images/patents/429/2043650/2043650-15t.gif)
![накапливающий сумматор, патент № 2043650](/images/patents/429/2043650/2043650-16t.gif)
![накапливающий сумматор, патент № 2043650](/images/patents/429/2043650/2043650-17t.gif)
![накапливающий сумматор, патент № 2043650](/images/patents/429/2043650/2043650-18t.gif)
Таким образом, в предлагаемом способе сложения (в отличие от известного) анализируется три разряда слагаемых. Допустим, нужно сложить числа А(112) 010000100001000000 и В(104) 010000010000000100, тогда
![накапливающий сумматор, патент № 2043650](/images/patents/429/2043650/2043650-19t.gif)
Особенностью предлагаемого способа сложения является поступление сигнала переноса в (i+1)-й разряд при наличии единицы в i-м разряде первого слагаемого и (i-4)-м разряде второго слагаемого и переноса в (i+2)-й разряд при наличии единицы в i-м разряде первого слагаемого и (i-1)-м разряде второго. В результате чего в сумматоре формируется частично разрешенный код суммы. Рассмотрим сложение этих же чисел в прототипе предлагаемого сумматора:
![накапливающий сумматор, патент № 2043650](/images/patents/429/2043650/2043650-20t.gif)
![накапливающий сумматор, патент № 2043650](/images/patents/429/2043650/2043650-21t.gif)
![накапливающий сумматор, патент № 2043650](/images/patents/429/2043650/2043650-22t.gif)
Для сложения чисел А и В в прототипе предлагаемого сумматора потребовалось 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.
Класс G06F7/49 для вычислений, выполняемых над числами с основанием, отличным от 2, 8, 16 или 10, например с троичным отрицательным или мнимым основаниями, комплексными основаниями