устройство для сложения и вычитания семи чисел по модулю 2 n-1
| Классы МПК: | G06F7/49 для вычислений, выполняемых над числами с основанием, отличным от 2, 8, 16 или 10, например с троичным отрицательным или мнимым основаниями, комплексными основаниями |
| Патентообладатель(и): | Авгуль Леонид Болеславович |
| Приоритеты: |
подача заявки:
1992-06-17 публикация патента:
30.08.1994 |
Изобретение относится к вычислительной технике и микроэлектронике и может быть использовано при построении устройств, работающих в системе остаточных классов. Устройство содержит n семивходовых одноразрядных сумматоров, n одноразрядных двоичных сумматоров, сумматор двух чисел по модулю 2n-1 , входы семи операндов с первого по n-й разряд, n выходов результата. На входы поступают разряды с первого по n-й семи операндов 
. На выходах формируются значения n-разрядного результата R (суммы по модулю 2n-1 семи входных операндов, которые могут иметь различные знаки). При этом 
, R 
{0, 1, ..., 2n-2} , и если некоторый операнд Xj суммируется с отрицательным знаком, то на входы устройства он поступает в обратном коде. Достоинством устройства являются широкие функциональные возможности, простая конструкция, высокое быстродействие. 1 ил.
Рисунок 1
. На выходах формируются значения n-разрядного результата R (суммы по модулю 2n-1 семи входных операндов, которые могут иметь различные знаки). При этом , R {0, 1, ..., 2n-2} , и если некоторый операнд Xj суммируется с отрицательным знаком, то на входы устройства он поступает в обратном коде. Достоинством устройства являются широкие функциональные возможности, простая конструкция, высокое быстродействие. 1 ил.
Формула изобретения
УСТРОЙСТВО ДЛЯ СЛОЖЕНИЯ И ВЫЧИТАНИЯ СЕМИ ЧИСЕЛ ПО МОДУЛЮ 2n-1, содержащее сумматор двух чисел по модулю 2n - 1, выход i-го (i=
) разряда которого соединен с выходом i-го разряда устройства, отличающееся тем, что содержит n одноразрядных двоичных сумматоров и n семивходовых одноразрядных сумматоров, j-й (j=
) вход i-го из которых соединен с входом i-го разряда j-го операнда, первый вход i-го одноразрядного двоичного сумматора соединен с выходом суммы i-го семивходового одноразрядного сумматора, второй вход k-го (k=
) одноразрядного двоичного сумматора соединен с выходом младшего переноса (k + 1)-го семивходового одноразрядного сумматора, третий вход l-го (l=
) одноразрядного двоичного сумматора соединен с выходом старшего переноса (l + 2)-го семивходового одноразрядного сумматора, второй вход n-го одноразрядного двоичного сумматора соединен с выходом младшего переноса первого семивходового одноразрядного сумматора, третий вход (n + h - 2)-го (h = 1, 2) одноразрядного двоичного сумматора соединен с выходом старшего переноса h-го семивходового одноразрядного сумматора, выход суммы i-го одноразрядного двоичного сумматора соединен с первым входом i-го разряда сумматора двух чисел по модулю 2n - 1, второй вход k-го разряда которого соединен с выходом переноса (k + 1)-го одноразрядного двоичного сумматора, выход переноса первого одноразрядного двоичного сумматора соединен с вторым входом n-го разряда сумматора двух чисел по модулю 2n - 1.
Описание изобретения к патенту
Изобретение относится к вычислительной технике и микроэлектронике и может быть использовано при построении устройств, работающих в системе остаточных классов. Известен сумматор по модулю семь, содержащий элементы сложения по модулю два, ИЛИ-НЕ, И, ИЛИ [1]. Недостатком сумматора являются низкие функциональные возможности, так как он не выполняет операцию сложения по различным модулям. Наиболее близким по функциональным возможностям и конструкции техническим решением к предлагаемому является сумматор по модулю 2n-1, содержащий в каждом разряде элементы ИЛИ, И, ИЛИ-НЕ, РАВНОЗНАЧНОСТЬ и НЕРАВНОЗНАЧНОСТЬ [2]. Недостатком известного сумматора по модулю 2n-1 являются низкие функциональные возможности, поскольку он не обеспечивает сложение по модулю более двух операндов. На чертеже представлена схема устройства для сложения и вычитания семи чисел по модулю 2n-1 при n = 5. Устройство содержит n = 5 семивходовых одноразрядных сумматоров 11... 15, n = =5 одноразрядных двоичных сумматоров 21...25, сумматор 3 двух чисел по модулю 2n - 1 = 31, входы j-го (j=
) операнда с первого по пятый (n-1) разряд соответственно 4j..8j, n = 5 выходов 91...95 результата. В общем случае устройство для сложения и вычитания семи чисел по модулю 2n-1 содержит сумматор двух чисел по модулю 2n-1, n одноразрядных двоичных сумматоров и n семивходовых одноразрядных сумматоров, j=й (j=
) вход i-го (i= 
) из которых соединен с входом i-го разряда j-го операнда. Первый вход i-го одноразрядного двоичного сумматора соединен с выходом суммы i-го семивходового одноразрядного сумматора, второй вход k-го (k=
) одноразрядного двоичного сумматора - с выходом младшего переноса (k+1)-го семивходового одноразрядного сумматора, третий вход l-го (l=
) одноразрядного двоичного сумматора - с выходом старшего переноса (l+2)-го семивходового одноразрядного сумматора, второй вход n-го одноразрядного двоичного сумматора - с выходом младшего переноса первого семивходового одноразрядного сумматора, третий вход (n+h-2)-го (h = 1, 2) одноразрядного двоичного сумматора - с выходом старшего переноса h-го семивходового одноразрядного сумматора, выход суммы i-го одноразрядного двоичного сумматора - с первым входом i-го разряда сумматора двух чисел по модулю 2n-1, второй вход k-го разряда которого соединен с выходом переноса (k+1)-го одноразрядного двоичного сумматора. Выход переноса первого одноразрядного двоичного сумматора соединен с вторым входом n-го разряда сумматора двух чисел по модулю 2n-1, выход -го разряда которого соединен с выходом i-го разряда устройства. Устройство для сложения и вычитания семи чисел по модулю 2n-1 при n = 5 работает следующим образом. На входы 4j. ..8j поступают соответственно разряды с первого по пятый xj1. ..xj5 j-го (j=
) операнда Xj = 16xj1 + 8xj2 + 4xj3 + 2xj4 + +xj5. На выходах 91. ..95 формируются значения соответственно разрядов с первого по пятый r1...r5 результата R = 16r1 + 8r2 + 4r3 + 2r4 + r5(суммы по модулю 2n - 1 = 31 семи входных операндов, которые могут иметь различные знаки). При этом R=
X
mod31, и Xj {0, 1,...,31}, R {0, 1,..,30}, xj5 {0, 1}, rs { 0, 1 },j=
, s=
. Если некоторый операнд Xj суммируется с отрицательным знаком, то на входы 4j...8j подаются соответственно инверсные значения его разрядов: 
. ..
, т.е. на входы 4j...8j поступает обратный код операнда Xj. Семивходовые одноразрядные сумматоры 11...15, входящие в состав заявляемого устройства, формируют позиционный двоичный код числа единиц, присутствующих на их входах. При подаче на входы такого сумматора двоичных переменных z1, z2,...,z7 на его выходах формируются сигналы суммы f0, младшего переноса f1 и старшего переноса f2. При этомz1 + z2 +...+ z7 = 4f2 + 2f1 + f0. Структуры семивходовых одноразрядных сумматоров известны. Например, семивходовый одноразрядный сумматор по авт. св. СССР N 1592846, кл. G 06 F 7/50, 1988, имеет простую конструкцию и высокое быстродействие. Сумматор 3 по модулю 2n-1 выполняет сложение двух полных операндов. В качестве такого сумматора может быть использовано устройство-прототип из [2]. Рассмотрим работу предлагаемого устройства на примере выполнения следующей операции сложения-вычитания по модулю тридцать один (n = 5) семи операндов Х1, Х2,..,Х7:
R= (-X1-X2+X3-X4+X5-X6-X7)mod31 при Х1 = 10010, Х2 = 01010, Х3 = 11111, Х4 = =11011, Х5 = 11101, Х6 = 10010, Х7 = 00100. Следовательно, на входы 41, 42,...,47 поступают соответственно первые разряды операндов Х1, Х2,...,Х7:
(
, 
, x31, 
, x51, 
, 
)=(0110101), на входы 51, 52,...,57 поступают соответственно вторые разряды операндов Х1, Х2,...,Х7:(
, 
, x32, 
, x52, 
, 
)=(1010111), на входы 61, 62,...,67 поступают соответственно третьи разряды операндов Х1, Х2,...,Х7:(
, 
, x33, 
, x53, 
, 
)=(1111110), на входы 71, 72,...,77 поступают соответственно четвертые разряды операндов Х1, Х2,...,Х7:(
, 
, x34, 
, x54, 
, 
)=(0010001), на входы 81, 82,...,87 поступают соответственно пятые разряды операндов Х1, Х2,...,Х7:(
, 
, x35, 
, x55, 
, 
)=(1110111). На выходах первого семивходового одноразрядного сумматора 11формируются значения функций f2 = 1, f1 = 0, f0 = 0, на выходах второго семивходового одноразрядного сумматора 12 - значения функций f2 = 1, f1= 0, f0 = 1, на выходах третьего семивходового одноразрядного сумматора 13 - значения функций f2 = 1, f1 = 1, f0 = 0, на выходах четвертого семивходового одноразрядного сумматора 14 - значения функций f2 = 0, f1= 1, f0 = 0, на выходах пятого семивходового одноразрядного сумматора 15- значения функций f2 = 1, f1 = 1, f0 = 0. На выходах первого одноразрядного двоичного сумматора 21 сигналы переноса р = 0 и сигналы суммы s = 1, на выходах второго одноразрядного двоичного сумматора 22 сигналы переноса р = 1 и сигналы суммы s = 0, на выходах третьего одноразрядного двоичного сумматора 23 сигналы переноса р = 1 и сигналы суммы s = 0, на выходах четвертого одноразрядного двоичного сумматора 24 сигналы переноса р = 1 и сигналы суммы s = 0, на выходах пятого одноразрядного двоичного сумматора 25 сигналы переноса р = 0 и сигналы суммы s = =1. Тогда на входы 101...105 сумматора 3 по модулю тридцать один поступает двоичный код 10000, на входы 111...115 - двоичный код 11101. На выходах 91. ..95 сумматора 3 формируются разряды результата r1...r5соответственно:(10000 + 11101) mod31 = 01110. Таким образом,
R = (-X1 - X2 + X3 - X4 + X5 - X6 - X7)mod31 = =(-10010 - 01010 + 11111 - 11011 +
+ 11101 - 10010 - 00100)mod31 = 01110. В десятичной системе счисления
R = (-X1 - X2 + X3 - X4 + X5 - X6 - X7)mod31= = (-18 - 10 + 31 - 27 + 29 - 18 - 4)mod31 =
=(-17)mod31 = (31 - 17)mod31 = 14. Достоинством предлагаемого устройства для сложения и вычитания семи чисел по модулю 2n-1 являются широкие функциональные возможности и высокое быстродействие, определяемое малой глубиной схемы.
Класс G06F7/49 для вычислений, выполняемых над числами с основанием, отличным от 2, 8, 16 или 10, например с троичным отрицательным или мнимым основаниями, комплексными основаниями
+1) "дополнительный код" с применением арифметических аксиом троичной системы счисления f(+1,0,-1) (варианты русской логики) - патент 2429523