Сумматор по модулю 2n+1

 

Изобретение относится к вычислительной технике и микроэлектронике и может быть использовано при построении устройств, работающих в системе остаточных классов. Сумматор по модулю 2ⁿ+1 содержит (n+1)-разрядный двоичный сумматор, n элементов ЗАПРЕТ и 2n+1 элементов ИСКЛЮЧАЮЩЕЕ ИЛИ. На его входы потупают (n+1)-разрядные приведенные операнды X и Y, значения которых принадлежат множеству { 0, 1 ..., 2ⁿ}. На выходах формируется (n+1)-разрядный двоичный код результата операции сложения по модулю 2ⁿ+1 входных операндов R = X + Y mod (2ⁿ+1).. Достоинством сумматора по модулю 2ⁿ+1 является высокое быстродействие и простая конструкция. 1 ил.

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

Известен сумматор по модулю 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≅ Y≅16 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.

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

СУММАТОР ПО МОДУЛЮ 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-го элемента ЗАПРЕТ.

РИСУНКИ

Рисунок 1