УСТРОЙСТВО ДЛЯ ФОРМИРОВАНИЯ ОСТАТКА ПО МОДУЛЮ ПЯТЬ Российский патент 1995 года по МПК G06F11/00 

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

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

Устройство содержит четыре блока вычисления фундаментальных симметрических булевых функций 1, 2, 3 и 4, двенадцать элементов ИЛИ 5-16, два сумматора по модулю пять 17 и 18, вычитатель по модулю пять 19, n 41 входов 20-60 и три выхода 61, 62 и 63.

В общем случае устройство для формирования остатка по модулю пять содержит два сумматора по модулю пять, вычитатель по модулю пять, двенадцать элементов ИЛИ и четыре блока вычисления фундаментальных симметрических булевых функций. При этом i-й вход (i an/2[/2[, n-разрядность входного двоичного слова) первого блока вычисления фундаментальных симметрических булевых функций является входом (4i=3)-го разряда (начиная с младших разрядов) входного слова устройства, j-й вход (j b []n/2[/2]) второго блока вычисления фундаментальных симметрических булевых функций является входом (4j-2)-го разряда входного слова устройства, k-й вход (k c[n/2]/2[) третьего блока вычисления фундаментальных симметрических булевых функций является входом (4k-1)-го разряда входного слова устройства, l-й вход (l d [[n/2] /2] ) четвертого блока вычисления фундаментальных симметрических булевых функций является входом 41-го разряда входного слова устройства. Входы m-го (m 1,3) элемента ИЛИ соединены с выходами функций с порогом A первого блока вычисления фундаментальных симметрических булевых функций (A i при l_m 1 и i mod 5 4l₁ + 2l₂ + l₃, l_m(-{0,1}). Входы (m+3)-го элемента ИЛИ соединены с выходами функций с порогом В второго блока вычисления фундаментальных симметрических булевых функций (B j при I_m 1 и (2j) mod 5 4I₁ + 2I₂ + I₃, I_m(-{ 0,1} ). Входы (m+6)-го элемента ИЛИ соединены с выходами функций с порогом С третьего блока вычисления фундаментальных симметрических булевых функций (С k при K_m 1 и k mod 5= 4K₁ + 2K₂ + K₃, K_m(-{0,1}). Входы (m+9)-го элемента ИЛИ соединены с выходами функций с порогом D четвертого блока вычисления фундаментальных симметрических булевых функций (D 1) при l_m 1 и (2l) mod 5= 4L₁ + 2L₂ + L₃, L_m(-{0,1}). Выход (m+3t-3)-го элемента ИЛИ (t 1,2) соединен с t-м входом m-го разряда первого сумматора по модулю пять. Выход (m+3t+3)-го элемента ИЛИ соединен с t-м входом m-го разряда второго сумматора по модулю пять. Выход m-го разряда t-го сумматора по модулю пять соединен с t-м входом m-го разряда вычитателя по модулю пять, выход m-го разряда которого является выходом m-го разряда устройства.

Устройство для формирования остатка по модулю пять при n 41 работает следующим образом.

На входы 20.60 устройства поступают соответственно разряды Х₁.Х₄₁ входного двоичного слова Х х₄₁х₄₀х₃₉.х₁, причем х₁ младший разряд. На выходах 61, 62 и 63 формируется трехразрядный двоичный код результата R 4r₁ + 2r₂ + r₃ свертки по модулю пять входного слова Х, r_m(-{0,1}), m и R(-{0,1,2,3,4} ). Причем на выходе 61 реализуется старший разряд r₁, на выходе 62 средний разряд r₂, на выходе 63 младший разряд r₃ результата R.

Поясним принцип работы устройства для формирования остатка по модулю пять.

Пусть Х х_nx_n-1х_n-2..x₁ разрядное двоичное слово и х1 младший разряд. Тогда результат свертки по модулю пять входного слова можно представить в виде
R X mod 5 4r₁ + 2r₂ + r₃ ((P mod 5 + (2S) mod 5) (V mod 5 +
+(2W) mod 5)) mod 5, (1) где PX, SX, VX, WX
an/2[/2[,b [][n/2[/2]), c[n/2]/2[), d [[n/2]/2]).

Обозначим: P mod 5 4_p1 + 2_P2 + p₃, (2S) mod 5 4s₁ + 2s₂ + S₃, V mod 5 4_V1 + +2_V2 + V₃, (2W) mod 5 4_W1 + 2_W2 + W₃, P_m(-{0,1}), +S_m(-{0,1}), V_m(-{ 0,1}), W_m(-{0,1}), m 1,3
P_m= VФA1

(2)
S_m= VFBb (3)
V_m= VQcc (4)
W_m= VZDd (5) где фундаментальные симметрические булевы функции Ф_a^A, F_b^B, Q_c^C и Z_d^Dопределяются следующим образом
ФAa
FBb
QCc
ZDd
Пороги фундаментальных симметрических булевых функций в формулах (2)-(5) определяются следующим образом.

Порог A находится из условия:
A i при l_m 1 и i mod 5 4l₁ + 2l₂ + l₃,
I_m (-{0,1}), i
Порог В находится из условия:
B j при I_m 1 и (2j) mod 5 4I₁ + 2I₂ + I₃,
I_m(-{0,1}), j
Порог С находится из условия:
C при K_m 1 и k mod 5 4K₁ + 2K₂ + K₃,
K_m(-{0,1}), k
Порог D находится из условия:
D l при L_m 1 и (2l) mod 5 4L₁ + 2L₂ + L₃,
L_m(-{0,1}), l
Фундаментальные симметрические булевы функции Ф_a^A, F_b^B, Q_c^C и Z_d^Dвычисляются соответственно первым 1, вторым 2, третьим 3 и четвертым 4 блоками вычисления фундаментальных симметрических булевых функций. На выходах элементов И 5-16 реализуются функции p_m, S_m, V_m и W_m согласно выражениям (2)-(5). Результат свертки по модулю пять входного слова формируется в соответствии с (1) сумматорами по модулю пять 17 и 18 и вычитателем по модулю пять 19.

Так, при n 41 на входы 19, 23, 59 первого блока вычисления фундаментальных симметрических булевых функций 1 поступают переменные х₄₁, х₃₇, х₁; на входы 20, 24, 56 второго блока вычисления фундаментальных симметрических булевых функций 2 поступают переменные х₃₈, х₃₄, х₂; на входы 21, 25, 57 третьего блока вычисления фундаментальных симметрических булевых функций 3 поступают переменные х₃₉, х₃₈, х₃; на входы 22, 26, 58 четвертого блока вычисления фундаментальных симметрических булевых функций 4 поступают переменные х₄₀, х₃₆, х₄.

При этом a /2/2 11, b /2/2) 10, c /2/2) 10, d /2/2) 10 и на выходах элементов ИЛИ 5-16 реализуются соответственно функции p_m, s_m, v_m и w_m, m :
p₁= Ф41

₁∨ Ф91₁ (6)
p₂= Ф21₁∨ Ф31₁∨ Ф71₁∨ Ф81₁ (7)
p₃= Ф31₁∨ Ф81₁∨ Ф11₁∨ Ф61₁∨ Ф1111 (8)
S₁= F21₀∨ F71₀ (9)
S₂= F11₀∨ F41₀∨ F61₀∨ F91₀ (10)
S₃= F41₀∨ F91₀∨ F31₀∨ F81₀ (11)
V₁= Q41₀∨ Q91₀ (12)
V₂= Q21₀∨ Q31₀∨ Q71₀∨ Q81₀ (13)
V₃= Q31₀∨ Q81₀∨ Q11₀∨ Q61₀ (14)
W₁= Z21₀∨ Z71₀ (15)
W₂= Z71₀∨ Z41₀∨ Z61₀∨ Z91₀ (16)
W₃= Z41₀∨ Z91₀∨ Z31₀∨ Z81₀ (17)
На выходах 61, 62 и 63 вычитателя по модулю пять 19 формируется результат свертки по модулю пять 41-разрядного входного слова.

Рассмотрим работу устройства на примере формирования остатка по модулю пять при n 41 для входного слова
Х=10100001111011001101101101000011100010110.

Очевидно, на входы первого блока вычисления фундаментальных симметрических булевых функций 1 поступает вектор двоичных переменных Х₁= х₄₁х₃₇.х₁ 10111100110, на входы второго блока вычисления фундаментальных симметрических булевых функций 2 вектор двоичных переменных Х₂ х₃₈х₃₄.х₂ 0100110101, на входы третьего блока вычисления фундаментальных симметрических булевых функций 3 вектор двоичных переменных Х₃ х₃₉х₃₈.х₃ 1010010101, на входы четвертого блока вычисления фундаментальных симметрических булевых функций 4 вектор двоичных переменных Х₄ х₄₀х₃₆.х₄ 0011101000.

Веса двоичных векторов Х₁, Х₂, Х₃ и Х₄ равны соответственно
P X= 7; SX= 5; VX= 5; WX= 4 следовательно, на выходе блока 1 формируется фундаментальная симметрическая булева функция Ф₁₁⁷ 1 (остальные функции равны нулю), на выходе блока 4 функция Z₁₀⁴ 1 (остальные функции равны нулю). На всех выходах блоков 2 и 3 сигналы равны нулю, поскольку эти блоки не реализуют функций F₁₀⁵ и Q₁₀⁵, принимающих единичные значения соответственно при s 5 и v 5.

Тогда, как следует из (6)-(17), на выходах элементов ИЛИ 5-16 сигналы принимают значения:
p₁ 0; p₂ 1; p₃ 0; s₁ 0; s₂ 0; s₃ 0;
v₁ 0; v₂ 0; v₃ 0; w₁ 0; w₂ 1; w₃ 1.

Таким образом, на входы первого сумматора по модулю пять 17 поступают двоичные коды 010 и 000. На выходах сумматора 17 формируется код 010 (010 + 000) mod 5.

На входы второго сумматора по модулю пять 18 поступают двоичные коды 000 и 011. На выходах сумматора 18 формируется код 011 (000 + 011) mod 5.

На первых входах вычитателя по модулю пять 19 действует двоичный код 010, а на вторых входах двоичный код 011. На выходах вычитателя 19 формируется результат свертки по модулю пять входного слова 100 (010 011) mod 5.

Таким образом, X mod 5(10100001111011001101101101000011100010110) mod 5= 100.

Достоинством устройства для формирования остатка по модулю пять является высокое быстродействие, определяемое малой глубиной схемы.

Быстродействие устройства может быть рассчитано по формуле
Т t_FSM + t_ИЛИ + t_SM + t_SUB, где t_FSM, t_ИЛИ, t_SM, t_SUB соответственно быстродействие блока вычисления фундаментальных симметрических булевых функций, элемента ИЛИ, сумматора по модулю пять, вычитателя по модулю пять.

Изобретение относится к вычислительной технике и микроэлектронике и может быть использовано для построения средств аппаратурного контроля и цифровых устройств, работающих в системе остаточных классов. Устройство содержит четыре блока вычисления фундаментальных симметрических булевых функций, двенадцать элементов ИЛИ, два сумматора по модулю пять, вычитатель по модулю пять, n-входов и три выхода. На входы устройства поступают разряды входного n-разрядного двоичного слова X. На выходах формируется трехразрядный двоичный код результата R = 4r₁+2r₉+r_s свертки по модулю пять входного слова и R ( 0, 1, 2, 3, 4 1 ил. 4 табл.

УСТРОЙСТВО ДЛЯ ФОРМИРОВАНИЯ ОСТАТКА ПО МОДУЛЮ ПЯТЬ, содержащее первый сумматор по модулю пять, отличающееся тем, что оно содержит второй сумматор по модулю пять, вычитатель по модулю пять, двенадцать элементов ИЛИ и четыре блока вычисления фундаментальных симметрических булевых функций, i-й вход (i a; an/2 [/2[, n разрядность входного двоичного слова) первого из которых соединен с входом (4i 3)-го разряда (начиная с младших разрядов) входного слова, j-й вход второго блока вычисления фундаментальных симметрических булевых функций соединен с входом (4j 2)-го разряда входного слова устройства, k-й вход третьего блока вычисления фундаментальных симметрических булевых функций является входом (4K 1)-го разряда входного слова устройства, l-й вход четвертого блока вычисления фундаментальных симметрических булевый функций соединен с входом 4l-го разряда входного слова устройства, входы m-го элемента ИЛИ соединены с выходами функций с порогом A (где A i при l_m 1 и i mod 5 = 4l₁+2l₂+l₃, l_m({0,1}) первого блока вычисления фундаментальных симметрических булевых функций, входы (m + 3)-го элемента ИЛИ соединены с выходами функции с порогом B (где B j при J_m 1 и (2j) mod 5 = 4J₁+2J₂+J₃, I_m(-{0,1}) второго блока вычисления фундаментальных симметрических булевых функций, входы (m + 6)-го элемента ИЛИ соединены с выходами функции с порогом C (где C k при k_m 1 и k mod 5 = 4k₁+2k₂+k₃, k_m(-{0,1}) третьего блока вычисления фундаментальных симметрических булевых функций, входы (m + 9)-го элемента ИЛИ соединены с выходами функции с порогом D (где D l при l_m 1 и (2l)mod 5 = 4l₁+2l₂+l₃, l_m(-{0,1}) четвертого блока вычисления фундаментальных симметрических булевых функций, выход (m + 3t 3)-го элемента ИЛИ (t 1,2) соединен с t-м входом m-го разряда первого сумматора по модулю пять, выход (m + 3t + 3)-го элемента ИЛИ соединен с t-м входом m-го разряда второго сумматора по модулю пять, выход m-го разряда t-го сумматора по модулю пять с t-м входом m-го разряда вычитателя по модулю пять, выход m-го разряда которого является выходом m-го разряда устройства.