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

 

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

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

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

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

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

Недостатком сумматора является невозможность сложения N > 2 операндов по модулю пять.

На чертеже представлена схема предлагаемого устройство для сложения N числа по модулю пять при N = 11.

Устройство содержит три блока 1, 2 и 3 вычисления фундаментальных симметрических булевых функций, десять элементов ИЛИ 4-13, три одноразрядных двоичных сумматора 14, 15 и 16, сумматор 17 по модулю пять, N = 11 входов 18₁. . . 18₁₁ старших разрядов операндов, N = 11 входов 19₁...19₁₁ средних разрядов операндов, N = 11 входов 20₁...20₁₁ младших разрядов операндов и три выхода 21, 22 и 23.

В устройстве j-й (j=) вход i-го (i=) блока вычисления фундаментальных симметрических булевых функций соединен с входом i-го разряда j-го операнда. Входы i-го элемента ИЛИ соединены с выходами первого блока 1 вычисления фундаментальных симметрических булевых функций, на котором реализуется фундаментальная симметрическая булева функция с порогом А (А находится из условия А = j при a_i = 1 и (4j)mod5 = 4a₁ + 2a₂ + a₃, a_i ∈ 0,1}. Входы (i+3)-го элемента ИЛИ соединены с выходами второго блока 2 вычисления фундаментальных симметрических булевых функций, на котором реализуется фундаментальная симметрическая булевая функция с порогом В (В находится из условия B = j при b_i = 1 и (2j)mod5 = 4b₁+ 2b₂ + b₃, b_i ∈ {0,1}. Входы (i+6)-го элемента ИЛИ соединены с выходами третьего блока 3 вычисления фундаментальных симметрических булевых функций, на котором реализуется фундаментальная симметрическая булева функция с порогом С (С находится из условия C = j при c_i = 1 и jmod5 = 4c₁ + 2c₂ + c₃, c_i ∈ {0,1}. В k-м (k =(k= )) одноразрядном двоичном сумматоре i-й вход соединен с выходом (i+3k-3)-го элемента ИЛИ. Выход суммы k-го одноразрядного двоичного сумматора соединен с первым входом k-го разряда сумматора 17 по модулю пять.

Выход переноса первого одноразрядного двоичного сумматора 14 соединен с вторым входом третьего разряда сумматора 17 по модулю пять и первым входом десятого элемента ИЛИ 13, второй вход которого соединен с выходом переноса третьего одноразрядного двоичного сумматора 16. Выход десятого элемента ИЛИ 13 соединен с вторым входом второго разряда сумматора 17 по модулю пять, второй вход первого разряда которого соединен с выходом переноса второго одноразрядного двоичного сумматора 15. Выход i-го разряда сумматора по модулю пять соединен с выходом i-го разряда устройства.

Устройство для сложения N чисел по модулю пять при N = 11 работает следующим образом.

На входы 18₁...18₁₁ устройства поступают старшие разряды х_1,1...х_11,1, на входы 19₁...19₁₁ - средние разряды х_1,2...х_11,2, на входы 20₁...20₁₁ - младшие разряды х_1,3...х_11,3 входных слов Х₁...Х₁₁. При этом Х_l = 4x_l,1 + 2x_l,2 + x_l,3,l=. На выходах 21, 22 и 23 формируется трехразрядный двоичный код результата R = 4r₁ + 2r₂ + r₃сложения по модулю пять входных слов X_l, r_i ∈ {0,1}, i = i= и R ∈ {0, 1, 2, 3, 4}, причем на выходе 21 реализуется старший разряд r₁, на выходе 22 - средний разряд r₂, на выходе 23 - младший разряд r₃результата R.

Принцип работы предлагаемого устройства для сложения N чисел по модулю пять.

Пусть X_j = 4x_j,1 + 2x_j,2 + x_j,z,j= - входные двоичные слова и Х ∈ { 0,1, ...,7}, x_i ∈ {0,1},i=. Тогда результат сложения по модулю пять входных слов можно представить в виде R= X_jmod5= 4r₁+2r₂+r₃= ((4P)mod5+(2S)mod5+Vmod5)mod5, (1) где P= X_j,1, S=X_j,2, V=X_j,3 .

Обозначим (4P)mod5 = 4p₁ + 2p₂ + p₃, (2S)mod5 = 4s₁ + 2s₂ + s₃, Vmod5 = 4v₁ + 2v₂ + +v₃, p_i ∈ {0,1}, s_i ∈ {0,1}, v_i ∈ [0,1},i=. Тогда P_i= Ф^A_N; (2) S_i= F^B_N; (3) V_i= Q^C_N; (4) где фундаментальные симметрические булевы функции Ф_N^A, F_N^B и Q_N^Cравны Ф^A_N = F^B_N = V^C_N = Пороги фундаментальных симметрических булевых функций в формулах (2) - (4) определяются следующим образом.

Порог А находится из условия A = j при ai = 1 и (4j)mod = 4a₁ + 2a₂+ a₃, a_i ∈ {0,1},j=, i=..

Порог В находится из условия B = j при b_i = 1 и (2j)mod5 = 4b₁ + 2b₂ + b₃, b_i ∈{0,1},j=, i=.

Порог С находится из условия C = j при c_i = 1 и jmod5 = 4c₁ + 2c₂ + c₃, c_i ∈ {0,1},j=, i=.

Так, при N = 11 на выходах элементов ИЛИ 4-12 реализуются соответственно функции p_i, s_i и v_i,i=: P₁=Ф¹₁₁∨ Ф⁶₁₁∨ Ф¹¹₁₁;
P₂=Ф²₁₁∨ Ф³₁₁∨ Ф⁷₁₁∨ Ф⁸₁₁;
P₃=Ф²₁₁∨ Ф⁴₁₁∨ Ф⁷₁₁∨ Ф⁹₁₁;
S₁=F²₁₁∨ F⁷₁₁;
S₂=F¹₁₁∨ F⁴₁₁∨ F⁶₁₁∨ F⁹₁₁∨ F¹¹₁₁;
S₃=F³₁₁∨ F⁴₁₁∨ F⁸₁₁∨ F⁹₁₁;
V₁=Q⁴₁₁∨ Q⁹₁₁;
V₂=Q²₁₁∨ Q³₁₁∨ Q⁷₁₁∨ Q⁸₁₁;
V₃=Q¹₁₁∨ Q³₁₁∨ Q⁶₁₁∨ Q⁸₁₁∨ Q¹¹₁₁.

В предлагаемом устройстве фундаментальные симметрические булевы функций Ф_N^A, F_N^B и Q_N^C вычисляются соответственно первым 1, вторым 2 и третьим 3 блоками вычисления фундаментальных симметрических булевых функций. На выходах элементов ИЛИ 4-12 реализуются функции p_i, s_i и v_iсогласно выражениям (2) - (4). Сумма по модулю пять N входных слов формируется в соответствии с выражением (1) блоком сложения трех приведенных операндов: (4P)mod5 = 4p₁ + 2p₂ + p₃, (2S)mod5 = 4s1 + +2s₂+ s₃ и Vmod5 = 4v₁ + 2v₂ + v₃. Этот блок включает в себя три одноразрядных двоичных сумматора 14, 15 и 16, элемент ИЛИ 13 и сумматор 17 двух чисел по модулю пять. Рассмотрим работу устройства на примере сложения по модулю пять N = 11 чисел X_l = 4x_l,1 + 2x_l,2 + x_l,3,l=:
Х₁ = 100, Х₂ = 110, Х₃ = 111, Х₄ = 011,
Х₅ = 101, Х₆ = 010, Х₇ = 110, Х₈ = 001,
Х₉ = 011, Х₁₀ = 101, Х₁₁ = 110.

Очевидно, на входы первого блока 1 вычисления фундаментальных симметрических булевых функций поступает вектор двоичных переменных (х_1,1, х_2,1.. . х_11,1) = (11101010011), на входы второго блока 2 вычисления фундаментальных симметрических булевых функций - вектор двоичных переменных (х_1,2, х_2,2. ..х_11,2) = (01110110101), на входы третьего блока 3 вычисления фундаментальных симметрических булевых функций - вектор двоичных переменных (х_1,3, х_2,3...х_11,3) = (00111001110).

Веса двоичных векторов равны соответственно
P = X_l,1= 7, S =X_l,2= 7, V =X_l,3= 6. Следовательно, на выходе блока 1 формируется фундаментальная симметрическая булева функция Ф₁₁⁷ = 1 (остальные функции равны нулю), на выходе блока 2 - функция F₁₁⁷ = 1 (остальные функции равны нулю), на выходе блока 3 - функция Q₁₁⁶ = 1 (остальные функции равны нулю).

Структуры блоков для вычисления фундаментальных симметрических булевых функций известны. Например, в устройстве по авт.св. СССР N 1589400, кл. H 03 M 7/22, 1988, реализация всех n+1 фундаментальных симметрических булевых функций n переменных осуществляется схемой, глубина которой равна 2t, где t - задержка на вентиль.

Работа блоков 1, 2 и 3 описывается таблицей.

Как следует из выражений (5) - (13), на выходах элементов ИЛИ 4-12 сигналы принимают значения
p₁ = 0, p₂ = 1, p₃ = 1, s₁ = 1, s₂ = 0, s₃ = 0, v₁ = 0, v₂ = 0, v₃= 1.

Таким образом, на входы блока сложения трех приведенных операндов поступают числа (4P)mod5 = 4p₁ + 2p₂ + p₃ = 011, (2S)mod5 = 4s₁ + 2s₂ + s₃ = 100 и Vmod5 = =4v₁ + 2v₂ + v₃ = 001.

На выходах блока, которые соединены соответственно с выходами устройства, формируется сумма трех операндов
((4P)mod5 + (2S)mod5 + Vmod5) mod5 = (011 + 100 + 001)mod5 = 011, которая и является результатом сложения N = 11 чисел по модулю пять.

Таким образом
R = (X₁ + X₂ +...+ X₁₁)mod5 = (100 + 110 +
+111 + 011 + 101 + 010 + 110 + 001 + 011+
+101 + 100)mod5 = 011.

Отметим, что сумматор 17 выполняет сложение по модулю пять двух полных операндов.

Достоинством заявляемого устройства является высокое быстродействие, определяемое малой глубиной схемы. Быстродействие предлагаемого устройства для сложения N чисел по модулю пять может быть рассчитано по формуле
T = t_FSM + 2t_ИЛИ + t_ОДС + t_SM5, где t_FSM, t_ИЛИ, t_ОДС, t_SM5 - соответственно быстродействие блока вычисления фундаментальных симметрических булевых функций, элемента ИЛИ, одноразрядного двоичного сумматора и сумматора по модулю пять.

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

УСТРОЙСТВО ДЛЯ СЛОЖЕНИЯ N ЧИСЕЛ ПО МОДУЛЮ ПЯТЬ, содержащее сумматор по модулю пять, выход i-го (i=) разряда которого соединен с выходом i-го разряда устройства, отличающееся тем, что содержит десять элементов ИЛИ, три одноразрядных двоичных сумматора и три блока вычисления фундаментальных симметрических булевых функций, j-й (j=) вход i-го из которых соединен с входом i-го разряда j-го операнда, входы i-го элемента ИЛИ соединены с выходами первого блока вычисления фундаментальных симметрических булевых функций, на котором реализуется фундаментальная симметрическая булевая функция с порогом A (A находится из условия: A = j при a_i = 1 и (4j) mod5 = 4 a₁+ 2a₂+ a₃, a_i∈ { 0.1} , входы (i + 3)-го элемента ИЛИ соединены с выходами второго блока вычисления фундаментальных симметрических булевых функций, на котором реализуется фундаментальная симметрическая булевая функция с порогом B (B находится из условия: B = j при b_i = 1 и (2j)mod5 = 4 b₁+ 2b₂+ b₃, b_i∈ { 0.1} ,входы (i+6)-го элемента ИЛИ соединены с выходами третьего блока вычисления фундаментальных симметричных булевых функций,на котором реализуется фундаментальная симметричная булевая функция с порогом С ( С находится из условия : C=j при с_i=1 и j mod 5 = 4c₁+2c₂+ c₃, c_i∈ {0.1}, i-й вход к-го (k= ) одноразрядного двоичного сумматора соединен с выходом (i+3k+3)-го элемента ИЛИ,выход суммы к-го одноразрядного двоичного сумматора соединен с первым входом к-го разряда сумматора по модулю пятьбвыход переноса первого одноразрядного двоичного сумматора соединен с вторым входом третьего разряда сумматора по модулю пять и первым входом десятого элемента ИЛИ, второй вход которого соединен с выходом переноса третьего одноразрядного двоичного сумматора,а выход соединен с вторым входом второго разряда сумматора по модулю пять,второй вход первого разряда которого соединен с выходом переноса второго одноразрядногодвоичного сумматора.

РИСУНКИ

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