Устройство для сложения и вычитания семи чисел по модулю 2 n-1

 

Изобретение относится к вычислительной технике и микроэлектронике и может быть использовано при построении устройств, работающих в системе остаточных классов. Устройство содержит n семивходовых одноразрядных сумматоров, n одноразрядных двоичных сумматоров, сумматор двух чисел по модулю 2ⁿ-1 , входы семи операндов с первого по n-й разряд, n выходов результата. На входы поступают разряды с первого по n-й семи операндов . На выходах формируются значения n-разрядного результата R (суммы по модулю 2ⁿ-1 семи входных операндов, которые могут иметь различные знаки). При этом , R ∈ {0, 1, ..., 2ⁿ-2} , и если некоторый операнд X_j суммируется с отрицательным знаком, то на входы устройства он поступает в обратном коде. Достоинством устройства являются широкие функциональные возможности, простая конструкция, высокое быстродействие. 1 ил.

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

Известен сумматор по модулю семь, содержащий элементы сложения по модулю два, ИЛИ-НЕ, И, ИЛИ [1].

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

Наиболее близким по функциональным возможностям и конструкции техническим решением к предлагаемому является сумматор по модулю 2ⁿ-1, содержащий в каждом разряде элементы ИЛИ, И, ИЛИ-НЕ, РАВНОЗНАЧНОСТЬ и НЕРАВНОЗНАЧНОСТЬ [2].

Недостатком известного сумматора по модулю 2ⁿ-1 являются низкие функциональные возможности, поскольку он не обеспечивает сложение по модулю более двух операндов.

На чертеже представлена схема устройства для сложения и вычитания семи чисел по модулю 2ⁿ-1 при n = 5.

Устройство содержит n = 5 семивходовых одноразрядных сумматоров 1₁... 1₅, n = =5 одноразрядных двоичных сумматоров 2₁...2₅, сумматор 3 двух чисел по модулю 2ⁿ - 1 = 31, входы j-го (j=) операнда с первого по пятый (n-1) разряд соответственно 4_j..8_j, n = 5 выходов 9₁...9₅ результата.

В общем случае устройство для сложения и вычитания семи чисел по модулю 2ⁿ-1 содержит сумматор двух чисел по модулю 2ⁿ-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-го разряда сумматора двух чисел по модулю 2ⁿ-1, второй вход k-го разряда которого соединен с выходом переноса (k+1)-го одноразрядного двоичного сумматора. Выход переноса первого одноразрядного двоичного сумматора соединен с вторым входом n-го разряда сумматора двух чисел по модулю 2ⁿ-1, выход -го разряда которого соединен с выходом i-го разряда устройства.

Устройство для сложения и вычитания семи чисел по модулю 2ⁿ-1 при n = 5 работает следующим образом.

На входы 4_j. ..8_j поступают соответственно разряды с первого по пятый x_j1. ..x_j5 j-го (j=) операнда X_j = 16x_j1 + 8x_j2 + 4x_j3 + 2x_j4 + +x_j5. На выходах 9₁. ..9₅ формируются значения соответственно разрядов с первого по пятый r₁...r₅ результата R = 16r₁ + 8r₂ + 4r₃ + 2r₄ + r₅(суммы по модулю 2ⁿ - 1 = 31 семи входных операндов, которые могут иметь различные знаки). При этом R= Xmod31, и X_j ∈ {0, 1,...,31}, R ∈ {0, 1,..,30}, x_j5 ∈ {0, 1}, r_s∈ { 0, 1 },j=, s=.

Если некоторый операнд X_j суммируется с отрицательным знаком, то на входы 4_j...8_j подаются соответственно инверсные значения его разрядов: . .., т.е. на входы 4_j...8_j поступает обратный код операнда X_j.

Семивходовые одноразрядные сумматоры 1₁...1₅, входящие в состав заявляемого устройства, формируют позиционный двоичный код числа единиц, присутствующих на их входах. При подаче на входы такого сумматора двоичных переменных z₁, z₂,...,z₇ на его выходах формируются сигналы суммы f₀, младшего переноса f₁ и старшего переноса f₂. При этом z₁ + z₂ +...+ z₇ = 4f₂ + 2f₁ + f₀.

Структуры семивходовых одноразрядных сумматоров известны. Например, семивходовый одноразрядный сумматор по авт. св. СССР N 1592846, кл. G 06 F 7/50, 1988, имеет простую конструкцию и высокое быстродействие.

Сумматор 3 по модулю 2ⁿ-1 выполняет сложение двух полных операндов. В качестве такого сумматора может быть использовано устройство-прототип из [2].

Рассмотрим работу предлагаемого устройства на примере выполнения следующей операции сложения-вычитания по модулю тридцать один (n = 5) семи операндов Х₁, Х₂,..,Х₇: R= (-X₁-X₂+X₃-X₄+X₅-X₆-X₇)mod31 при Х₁ = 10010, Х₂ = 01010, Х₃ = 11111, Х₄ = =11011, Х₅ = 11101, Х₆ = 10010, Х₇ = 00100.

Следовательно, на входы 4₁, 4₂,...,4₇ поступают соответственно первые разряды операндов Х₁, Х₂,...,Х₇: (, , x₃₁, , x₅₁, , )=(0110101), на входы 5₁, 5₂,...,5₇ поступают соответственно вторые разряды операндов Х₁, Х₂,...,Х₇: (, , x₃₂, , x₅₂, , )=(1010111), на входы 6₁, 6₂,...,6₇ поступают соответственно третьи разряды операндов Х₁, Х₂,...,Х₇: (, , x₃₃, , x₅₃, , )=(1111110), на входы 7₁, 7₂,...,7₇ поступают соответственно четвертые разряды операндов Х₁, Х₂,...,Х₇: (, , x₃₄, , x₅₄, , )=(0010001), на входы 8₁, 8₂,...,8₇ поступают соответственно пятые разряды операндов Х₁, Х₂,...,Х₇: (, , x₃₅, , x₅₅, , )=(1110111).

На выходах первого семивходового одноразрядного сумматора 1₁формируются значения функций f₂ = 1, f₁ = 0, f₀ = 0, на выходах второго семивходового одноразрядного сумматора 1₂ - значения функций f₂ = 1, f₁= 0, f₀ = 1, на выходах третьего семивходового одноразрядного сумматора 1₃ - значения функций f₂ = 1, f₁ = 1, f₀ = 0, на выходах четвертого семивходового одноразрядного сумматора 1₄ - значения функций f₂ = 0, f₁= 1, f₀ = 0, на выходах пятого семивходового одноразрядного сумматора 1₅- значения функций f₂ = 1, f₁ = 1, f₀ = 0.

На выходах первого одноразрядного двоичного сумматора 2₁ сигналы переноса р = 0 и сигналы суммы s = 1, на выходах второго одноразрядного двоичного сумматора 22 сигналы переноса р = 1 и сигналы суммы s = 0, на выходах третьего одноразрядного двоичного сумматора 2₃ сигналы переноса р = 1 и сигналы суммы s = 0, на выходах четвертого одноразрядного двоичного сумматора 2₄ сигналы переноса р = 1 и сигналы суммы s = 0, на выходах пятого одноразрядного двоичного сумматора 2₅ сигналы переноса р = 0 и сигналы суммы s = =1.

Тогда на входы 10₁...10₅ сумматора 3 по модулю тридцать один поступает двоичный код 10000, на входы 11₁...11₅ - двоичный код 11101. На выходах 9₁. ..9₅ сумматора 3 формируются разряды результата r₁...r₅соответственно: (10000 + 11101) mod31 = 01110.

Таким образом, R = (-X₁ - X₂ + X₃ - X₄ + X₅ - X₆ - X₇)mod31 = =(-10010 - 01010 + 11111 - 11011 +
+ 11101 - 10010 - 00100)mod31 = 01110.

В десятичной системе счисления
R = (-X₁ - X₂ + X₃ - X₄ + X₅ - X₆ - X₇)mod31= = (-18 - 10 + 31 - 27 + 29 - 18 - 4)mod31 =
=(-17)mod31 = (31 - 17)mod31 = 14.

Достоинством предлагаемого устройства для сложения и вычитания семи чисел по модулю 2ⁿ-1 являются широкие функциональные возможности и высокое быстродействие, определяемое малой глубиной схемы.

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

УСТРОЙСТВО ДЛЯ СЛОЖЕНИЯ И ВЫЧИТАНИЯ СЕМИ ЧИСЕЛ ПО МОДУЛЮ 2ⁿ-1, содержащее сумматор двух чисел по модулю 2ⁿ - 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-го разряда сумматора двух чисел по модулю 2ⁿ - 1, второй вход k-го разряда которого соединен с выходом переноса (k + 1)-го одноразрядного двоичного сумматора, выход переноса первого одноразрядного двоичного сумматора соединен с вторым входом n-го разряда сумматора двух чисел по модулю 2ⁿ - 1.

РИСУНКИ

Рисунок 1