сумматор по модулю 2ⁿ+1

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

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

Описание изобретения к патенту

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

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

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

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

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

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

При n = 4 сумматор по модулю 2⁴ + 1 = =17 содержит пятиразрядный двоичный сумматор 1, n = 4 элементов ЗАПРЕТ 2₁...2₄, 2ⁿ+1 = 9 элементов ИСКЛЮЧАЮЩЕЕ ИЛИ 3₁. . .3₉, n = 5 входов первого операнда 4₁...4₅, n = 5 входов второго операнда 5₁...5₅, n = 5 выходов 6₁...6₅.

В общем случае сумматор по модулю 2ⁿ+1 содержит n элементов ЗАПРЕТ, 2ⁿ+1 элементов ИСКЛЮЧАЮЩЕЕ ИЛИ и (n+1)-разрядный двоичный сумматор, i-й (i = 1, 2) вход j-го (j= разряда которого соединен с j-м разрядом i-го операнда. Выход переноса (n+1)-разрядного двоичного сумматора соединен с первым входом первого элемента ИСКЛЮЧАЮЩЕЕ ИЛИ, второй вход которого соединен с выходом первого элемента ЗАПРЕТ и первым выходом сумматора по модулю 2ⁿ+1. Выход первого элемента ЗАПРЕТ соединен с первым входом (k+1)-го (k= элемента ИСКЛЮЧАЮЩЕЕ ИЛИ, выход которого соединен с (k+1)-м выходом сумматора по модулю 2ⁿ+1, а второй вход - с выходом (n + k + 1)-го элемента ИСКЛЮЧАЮЩЕЕ ИЛИ. Первый вход (n + l + +1)-го (l= элемента ИСКЛЮЧАЮЩЕЕ ИЛИ соединен с выходом (l+1)-го элемента ЗАПРЕТ. Выход первого разряда суммы (n+1)-разрядного двоичного сумматора соединен с прямым входом k-го элемента ЗАПРЕТ и первым входом (2ⁿ+1)-го элемента ИСКЛЮЧАЮЩЕЕ ИЛИ. Выход (k+1)-го разряда суммы (n+1)-го разрядного двоичного сумматора соединен с вторым входом (n + k + 1)-го элемента ИСКЛЮЧАЮЩЕЕ ИЛИ и (k - s + 1)-м входом запрета (s= s-го элемента ЗАПРЕТ.

Сумматор по модулю 2ⁿ+1 работает следующим образом.

На входы (n+1)-разрядного двоичного сумматора поступают (n+1)-разрядные операнды X = 2ⁿx₁ + 2^n-1x₂ +...+x_n+1 и Y = 2ⁿy₁ + 2^n-1y₂+...+Y_n+1, значения которых принадлежат множеству {0, 1,...,2}, X_j {0, 1}, Y_j {0, 1}, j = . На выходе (n+1)-разрядного двоичного сумматора вычисляется сумма S = X + Y = 2ⁿ⁺¹ CR + 2ⁿs₁ + 2^n-1s₂ +...+ s_n+1. Причем CR {0, 1} - сигнал переноса и S {0, 1,...,2ⁿ⁺¹}, s_j {0, 1},j= .

Двоичные разряды результата операции сложения по модулю 2ⁿ+1 входных операндов R = X + Y mod (2ⁿ+1) = 2ⁿr₁ + 2^n-1r₂ +...+ r_n+1формируются комбинационной схемой из сигнала CR и S_j согласно следующим соотношениям:

(1) где z = r₁ CR

Так, при n = 4 на входы 4₁...4₅ и 5₁...5₅ пятиразрядного двоичного сумматора 1 поступают пятиразрядные операнды X = =16x₁ + 8x₂ + 4x₃ + 2x₄+ x₅ и Y = 16y₁ + 8y₂ + +4y₃ + 2y₄ + y₅ соответственно. При этом 0 Х 16, 0 Y16 x_t {0, 1}, Y_t {0, 1},t=. На выходе двоичного сумматора 1 вычисляется сумма S = X + Y = 32CR + 16s₁ + + 8s₂ + 4s₃ + 2s₄ + s₅. Причем 0 S 32, CR {0, 1}, s_t {0, 1},t=.

Как следует из соотношений (1), двоичные разряды результата операции сложения по модулю семнадцать R = X + Y mod 17= = 16r₁ + 8r₂ + 4r₃ + 2r₄ + r₅ формируются комбинационной схемой из сигналов CR и s_tсогласно следующим соотношениям:

r₁= s₁,;

r₂= z s₂ s;

r₃= z s₃ s;

r₄=z s₄ s;

r₅= z s₅ s₁, где z = r₁ CR.

Достоинством предлагаемого сумматора по модулю 2ⁿ+1 является высокое быстродействие и простая конструкция.

Быстродействие заявляемого сумматора по модулю 2ⁿ+1 не зависит от величины модуля и определяется выражением

T = t_sм + 3t, где t_sм - быстродействие (n+1)-разрядного двоичного сумматора;

t - задержка на вентиль.

Сигнал переноса CR в (n+1)-разрядном двоичном сумматоре может быть сформирован двухвходовым элементом И согласно соотношению CR = x₁y₁, поскольку X 2ⁿ и Y 2ⁿ. Кроме того, при использовании инверсного значения первого разряда суммы (n+1)-разрядного двоичного сумматора элементы ЗАПРЕТ могут быть однозначно заменены элементами ИЛИ-НЕ без изменения связей в предлагаемом сумматоре по модулю 2ⁿ+1.