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

 

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

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

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

Недостатком сумматора является невозможность выполнения сложения по модулю 2ⁿ+1.

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

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

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

При n = 4 устройство содержит сумматор 3 по модулю 2⁴ + 1 = 17, n + 1 = 5 одноразрядных двоичных сумматоров 1₁...1₅, n - 1 = 3 элементов ИЛИ 2₁... 2₅, n + 1 = =5 входов 4₁...4₅, n + 1 = 5 первого операнда входов 5₁...5₅, n + 1 = 5 второго операнда входов 6₁...6₅ третьего операнда n + 1 = 5 входов 7₁...7₅ четвертого операнда, причем входы 4₁, 5₁, 6₁, 7₁ - входы старших, а входы 4₅, 5₅, 6₅, 7₅ - входы младших разрядов операндов, и n + 1 = 5 выходов 9₁...9₅ результата, причем выход 9₁ - выход старшего, а выход 9₅ - выход младшего разряда результата.

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

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

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

На входы 4₁...4₅, 5₁...5₅ и 6₁...6₅ устройства подаются соответственно четырехразрядные операнды X= 2⁴x₁+2³x₂+ +2²x₃+2x₄+ x₅, Y = 24y₁+2³y₂+ 2²y₃+2y₄+ y₅ и Z = 2⁴z₁+2³z₂+2²z₃+2z₄+z ₅, где x_i {0, 1}, y_i { 0, 1} , z_i {0, 1},i=, X=, Y= и z=. При этом н входы 4₁, 5₁, 6₁ подаются соответственно старшие x₁, y₁, z₁, а на входы 4₅, 5₅, 6₅ - соответственно младшие x₅, y₅, z₅ разряды операндов X, Y и Z. На выходах 9₁...9₅ формиpуется четырехразрядный двоичный код результата R= 2⁴r₁+2³r₂+2²r₃+2r₄+r₅ операции сложения трех чисел X, Y и Z по модулю семнадцать r_i {0,1},i= и R=, причем на выходе 9₁ реализуется старший разряд r₁, а на выходе 9₅ - младший разряд r₅ результата R.

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

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

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

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

РИСУНКИ

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