Устройство для формирования остатка по модулю пять

 

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

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

На чертеже представлена схема устройства для формирования остатка по модулю пять при разрядности входного двоичного слова, равной 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Ф^A₁ (2) S_m= VF^B_b (3) V_m= VQ^c_c (4) W_m= VZ^D_d (5) где фундаментальные симметрические булевы функции Ф_a^A, F_b^B, Q_c^C и Z_d^Dопределяются следующим образом Ф^A_a F^B_b
Q^C_c
Z^D_d
Пороги фундаментальных симметрических булевых функций в формулах (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₁= Ф⁴₁₁∨ Ф⁹₁₁ (6)
p₂= Ф²₁₁∨ Ф³₁₁∨ Ф⁷₁₁∨ Ф⁸₁₁ (7)
p₃= Ф³₁₁∨ Ф⁸₁₁∨ Ф¹₁₁∨ Ф⁶₁₁∨ Ф¹¹₁₁ (8)
S₁= F²₁₀∨ F⁷₁₀ (9)
S₂= F¹₁₀∨ F⁴₁₀∨ F⁶₁₀∨ F⁹₁₀ (10)
S₃= F⁴₁₀∨ F⁹₁₀∨ F³₁₀∨ F⁸₁₀ (11)
V₁= Q⁴₁₀∨ Q⁹₁₀ (12)
V₂= Q²₁₀∨ Q³₁₀∨ Q⁷₁₀∨ Q⁸₁₀ (13)
V₃= Q³₁₀∨ Q⁸₁₀∨ Q¹₁₀∨ Q⁶₁₀ (14)
W₁= Z²₁₀∨ Z⁷₁₀ (15)
W₂= Z⁷₁₀∨ Z⁴₁₀∨ Z⁶₁₀∨ Z⁹₁₀ (16)
W₃= Z⁴₁₀∨ Z⁹₁₀∨ Z³₁₀∨ Z⁸₁₀ (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 соответственно быстродействие блока вычисления фундаментальных симметрических булевых функций, элемента ИЛИ, сумматора по модулю пять, вычитателя по модулю пять.

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

УСТРОЙСТВО ДЛЯ ФОРМИРОВАНИЯ ОСТАТКА ПО МОДУЛЮ ПЯТЬ, содержащее первый сумматор по модулю пять, отличающееся тем, что оно содержит второй сумматор по модулю пять, вычитатель по модулю пять, двенадцать элементов ИЛИ и четыре блока вычисления фундаментальных симметрических булевых функций, 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-го разряда устройства.

РИСУНКИ

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