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

 

Изобретение относится к вычислительной технике и микроэлектронике и может быть использовано для построения средств аппаратурного контроля и цифровых устройств, работающих в системе остаточных классов. Устройство содержит сумматор двух чисел по модулю 2ⁿ-1 (n=2, 3, ...), n одноразрядных двоичных сумматоров и n полусумматоров. На его входы подаются n-разрядные полные операнды X, Y и Z. На выходах формируется n-разрядный двоичный код результата R = ( X Y Z) mod (2ⁿ-1). . Выполняемая операция определяется путем соответствующей коммутации прямых и обратных кодов операндов на входах устройства. 2 табл., 1 ил.

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

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

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

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

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

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

Устройство содержит n = 4 одноразрядных двоичных сумматоров 1₁...1₄, n = 4 полусумматоров 2₁...2₄, сумматор 3 по модулю 2⁴ - 1 = 15, входы первого 4₁...4₄, второго 5₁...5₄ и третьего 6₁...6₄ операндов, причем входы 4₁, 5₁, 6₁ - входы старших, а входы 4₄, 5₄, 6₄ - входы младших разрядов операндов, выходы 9₁. ..9₄ результата, причем выход 9₁ - выход старшего, а выход 9₄ - выход младшего разряда результата.

В общем случае устройство для сложения и вычитания трех чисел по модулю 2ⁿ-1 содержит сумматор по модулю 2ⁿ-1, i-й (i = выход которого соединен с i-м выходом устройства. В i-м одноразрядном двоичном сумматоре j-й (j = 1, 2, 3) вход соединен с входом i-го разряда j-го операнда. Выход суммы i-го одноразрядного двоичного сумматора соединен с первым входом i-го полусумматора, выход суммы которого соединен с входом i-го разряда первого операнда сумматора по модулю 2ⁿ-1. Выход переноса первого одноразрядного двоичного сумматора соединен с вторым входом n-го полусумматора, выход переноса (k+1)-го (k = одноразрядного двоичного сумматора - с вторым входом k-го полусумматора. Выход переноса первого полусумматора соединен с входом n-го разряда второго операнда сумматора по модулю 2ⁿ-1, выход переноса (k+1)-го полусумматора - с входом k-го разряда второго операнда сумматора по модулю 2ⁿ-1.

При n = 4 входы первого одноразрядного двоичного сумматора 1₁соединены соответственно с входами 4₁, 5₁, 6₁, входы второго одноразрядного двоичного сумматора 1₂ - соответственно с входами 4₂, 5₂, 6₂, входы третьего одноразрядного двоичного сумматора 1₃ - соответственно с входами 4₃, 5₃, 6_3, входы четвертого одноразрядного двоичного сумматора 1₄ - соответственно с входами 4₄, 5₄, 6₄. Выход переноса первого одноразрядного двоичного сумматора 1₁ соединен с вторым входом четвертого полусумматора 2₄, первый вход которого соединен с выходом суммы четвертого одноразрядного двоичного сумматора 1₄. Выход переноса последнего соединен с вторым входом третьего полусумматора 2₃, первый вход которого соединен с выходом суммы третьего одноразрядного двоичного сумматора 1₃. Выход переноса сумматора 1₃ соединен с вторым входом второго полусумматора 2₂, первый вход которого соединен с выходом суммы второго одноразрядного двоичного сумматора 1₂. Выход переноса сумматора 1₂ соединен с вторым входом первого полусумматора 2₁, первый вход которого соединен с выходом суммы первого одноразрядного двоичного сумматора 1₁. Выход переноса первого полусумматора 2₁ соединен с входом 8₄ четвертого разряда второго операнда сумматора 3 по модулю пятнадцать, вход 7₄ четвертого разряда первого операнда которого соединен с выходом суммы четвертого полусумматора 2₄. Выход переноса полусумматора 2₄соединен с входом 8₃ третьего разряда второго операнда сумматора 3 по модулю пятнадцать, вход 7₃ третьего разряда первого операнда которого соединен с выходом суммы третьего полусумматора 2₃. Выход переноса полусумматора 2₃ соединен с входом 8₂ второго разряда второго операнда сумматора 3 по модулю пятнадцать, вход 7₂ второго разряда первого операнда которого соединен с выходом суммы второго полусумматора 2₂. Выход переноса полусумматора 2₂ соединен с входом 8₁ первого разряда второго операнда сумматора 3 по модулю пятнадцать, вход 7₁ первого разряда первого операнда которого соединен с выходом суммы первого полусумматора 2₁. Выходы первого, второго, третьего и четвертого разрядов сумматора 3 по модулю пятнадцать соединены с выходами первого 9₁, второго 9₂, третьего 9₃ и четвертого 9₄ разрядов результата соответственно.

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

На входы 4₁...4₄, 5₁...5₄, 6₁...6₄ подаются соответственно четырехразрядные полные операнды Х = 2³х₁ + 2²х₂ + 2х₃ + х₃, Y = 2³y₁ + 2²y₂ + 2y₃ + y₄ и Z = 2³z₁ + 2²z₂ + 2z₃ + z₄, где x_i {0,1}, y_i {0,1},z_i {0,1}, i = , X =, Y = и z = .

На выходах 9₁...9₄ формируется четырехразрядный двоичный код результата R = =2³r₁ + 2²r₂ + 2r₃ + r₄ операций сложения и вычитания трех чисел X, Y и Z по модулю пятнадцать, r_i {0,1}, i = и R = . Причем на выходе 9₁ реализуется старший разряд r₁, а на выходе 9₄ - младший разряд r₄ результата R.

Предлагаемое устройство реализует восемь операций сложения и вычитания вида R = ( XYX) mod (2ⁿ-1) Выполняемая операция определяется путем соответствующей коммутации прямых и обратных кодов операндов на входах устройства, как это указано в табл. 1 для n = 4.

Устройство для сложения и вычитания трех чисел по модулю 2ⁿ-1 построено с использованием следующего соотношения: (-X) mod (2ⁿ-1) = mod (2ⁿ-1) ,, где X =2^n-ix_i.

Отметим, что в качестве сумматора 3, входящего в состав заявляемого устройства, может быть использован сумматор, выполняющий сложение по модулю 2ⁿ-1 двух приведенных операндов, значения которых меньше значения модуля. Работа такого сумматора при n = 4 описывается табл.2.

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

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

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

РИСУНКИ

Рисунок 1, Рисунок 2, Рисунок 3, Рисунок 4