Главная страница  |  Описание сайта  |  Контакты
УСТРОЙСТВО ДЛЯ ФОРМИРОВАНИЯ ОСТАТКА ПО МОДУЛЮ ПЯТЬ
УСТРОЙСТВО ДЛЯ ФОРМИРОВАНИЯ ОСТАТКА ПО МОДУЛЮ ПЯТЬ

УСТРОЙСТВО ДЛЯ ФОРМИРОВАНИЯ ОСТАТКА ПО МОДУЛЮ ПЯТЬ

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

1. С помощью поисковых систем

   С помощью Google:    

   С помощью Яндекс:  

2. Экспресс-поиск по номеру патента


введите номер патента (7 цифр)

3. По номеру патента и году публикации

2000000 ... 2099999   (1994-1997 гг.)

2100000 ... 2199999   (1997-2003 гг.)
Номер патента: 2045771
Класс(ы) патента: G06F11/00
Номер заявки: 5042478/24
Дата подачи заявки: 18.05.1992
Дата публикации: 10.10.1995
Заявитель(и): Авгуль Леонид Болеславович[BY]
Автор(ы): Авгуль Леонид Болеславович[BY]
Патентообладатель(и): Авгуль Леонид Болеславович[BY]
Описание изобретения: Изобретение относится к вычислительной технике и микроэлектронике и может быть использовано для построения средств аппаратурного контроля и цифровых устройств, работающих в системе остаточных классов.
На чертеже представлена схема устройства для формирования остатка по модулю пять при разрядности входного двоичного слова, равной 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 при lm 1 и i mod 5 4l1 + 2l2 + l3, lm(-{0,1}). Входы (m+3)-го элемента ИЛИ соединены с выходами функций с порогом В второго блока вычисления фундаментальных симметрических булевых функций (B j при Im 1 и (2j) mod 5 4I1 + 2I2 + I3, Im(-{ 0,1} ). Входы (m+6)-го элемента ИЛИ соединены с выходами функций с порогом С третьего блока вычисления фундаментальных симметрических булевых функций (С k при Km 1 и k mod 5= 4K1 + 2K2 + K3, Km(-{0,1}). Входы (m+9)-го элемента ИЛИ соединены с выходами функций с порогом D четвертого блока вычисления фундаментальных симметрических булевых функций (D 1) при lm 1 и (2l) mod 5= 4L1 + 2L2 + L3, Lm(-{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 устройства поступают соответственно разряды Х141 входного двоичного слова Х х41х40х391, причем х1 младший разряд. На выходах 61, 62 и 63 формируется трехразрядный двоичный код результата R 4r1 + 2r2 + r3 свертки по модулю пять входного слова Х, rm(-{0,1}), m и R(-{0,1,2,3,4} ). Причем на выходе 61 реализуется старший разряд r1, на выходе 62 средний разряд r2, на выходе 63 младший разряд r3 результата R.
Поясним принцип работы устройства для формирования остатка по модулю пять.
Пусть Х хnxn-1хn-2..x1 разрядное двоичное слово и х1 младший разряд. Тогда результат свертки по модулю пять входного слова можно представить в виде
R X mod 5 4r1 + 2r2 + r3 ((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 4p1 + 2P2 + p3, (2S) mod 5 4s1 + 2s2 + S3, V mod 5 4V1 + +2V2 + V3, (2W) mod 5 4W1 + 2W2 + W3, Pm(-{0,1}), +Sm(-{0,1}), Vm(-{ 0,1}), Wm(-{0,1}), m 1,3
Pm= VФA1 (2)
Sm= VFBb (3)
Vm= VQcc (4)
Wm= VZDd (5) где фундаментальные симметрические булевы функции ФaA, FbB, QcC и ZdDопределяются следующим образом
ФAa
FBb
QCc
ZDd
Пороги фундаментальных симметрических булевых функций в формулах (2)-(5) определяются следующим образом.
Порог A находится из условия:
A i при lm 1 и i mod 5 4l1 + 2l2 + l3,
Im (-{0,1}), i
Порог В находится из условия:
B j при Im 1 и (2j) mod 5 4I1 + 2I2 + I3,
Im(-{0,1}), j
Порог С находится из условия:
C при Km 1 и k mod 5 4K1 + 2K2 + K3,
Km(-{0,1}), k
Порог D находится из условия:
D l при Lm 1 и (2l) mod 5 4L1 + 2L2 + L3,
Lm(-{0,1}), l
Фундаментальные симметрические булевы функции ФaA, FbB, QcC и ZdDвычисляются соответственно первым 1, вторым 2, третьим 3 и четвертым 4 блоками вычисления фундаментальных симметрических булевых функций. На выходах элементов И 5-16 реализуются функции pm, Sm, Vm и Wm согласно выражениям (2)-(5). Результат свертки по модулю пять входного слова формируется в соответствии с (1) сумматорами по модулю пять 17 и 18 и вычитателем по модулю пять 19.
Так, при n 41 на входы 19, 23, 59 первого блока вычисления фундаментальных симметрических булевых функций 1 поступают переменные х41, х37, х1; на входы 20, 24, 56 второго блока вычисления фундаментальных симметрических булевых функций 2 поступают переменные х38, х34, х2; на входы 21, 25, 57 третьего блока вычисления фундаментальных симметрических булевых функций 3 поступают переменные х39, х38, х3; на входы 22, 26, 58 четвертого блока вычисления фундаментальных симметрических булевых функций 4 поступают переменные х40, х36, х4.
При этом a /2/2 11, b /2/2) 10, c /2/2) 10, d /2/2) 10 и на выходах элементов ИЛИ 5-16 реализуются соответственно функции pm, sm, vm и wm, m :
p1= Ф411∨ Ф911 (6)
p2= Ф211∨ Ф311∨ Ф711∨ Ф811 (7)
p3= Ф311∨ Ф811∨ Ф111∨ Ф611∨ Ф1111 (8)
S1= F210∨ F710 (9)
S2= F110∨ F410∨ F610∨ F910 (10)
S3= F410∨ F910∨ F310∨ F810 (11)
V1= Q410∨ Q910 (12)
V2= Q210∨ Q310∨ Q710∨ Q810 (13)
V3= Q310∨ Q810∨ Q110∨ Q610 (14)
W1= Z210∨ Z710 (15)
W2= Z710∨ Z410∨ Z610∨ Z910 (16)
W3= Z410∨ Z910∨ Z310∨ Z810 (17)
На выходах 61, 62 и 63 вычитателя по модулю пять 19 формируется результат свертки по модулю пять 41-разрядного входного слова.
Рассмотрим работу устройства на примере формирования остатка по модулю пять при n 41 для входного слова
Х=10100001111011001101101101000011100010110.
Очевидно, на входы первого блока вычисления фундаментальных симметрических булевых функций 1 поступает вектор двоичных переменных Х1= х41х371 10111100110, на входы второго блока вычисления фундаментальных симметрических булевых функций 2 вектор двоичных переменных Х2 х38х342 0100110101, на входы третьего блока вычисления фундаментальных симметрических булевых функций 3 вектор двоичных переменных Х3 х39х383 1010010101, на входы четвертого блока вычисления фундаментальных симметрических булевых функций 4 вектор двоичных переменных Х4 х40х364 0011101000.
Веса двоичных векторов Х1, Х2, Х3 и Х4 равны соответственно
P X= 7; SX= 5; VX= 5; WX= 4 следовательно, на выходе блока 1 формируется фундаментальная симметрическая булева функция Ф117 1 (остальные функции равны нулю), на выходе блока 4 функция Z104 1 (остальные функции равны нулю). На всех выходах блоков 2 и 3 сигналы равны нулю, поскольку эти блоки не реализуют функций F105 и Q105, принимающих единичные значения соответственно при s 5 и v 5.
Тогда, как следует из (6)-(17), на выходах элементов ИЛИ 5-16 сигналы принимают значения:
p1 0; p2 1; p3 0; s1 0; s2 0; s3 0;
v1 0; v2 0; v3 0; w1 0; w2 1; w3 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.
Достоинством устройства для формирования остатка по модулю пять является высокое быстродействие, определяемое малой глубиной схемы.
Быстродействие устройства может быть рассчитано по формуле
Т tFSM + tИЛИ + tSM + tSUB, где tFSM, tИЛИ, tSM, tSUB соответственно быстродействие блока вычисления фундаментальных симметрических булевых функций, элемента ИЛИ, сумматора по модулю пять, вычитателя по модулю пять.
Формула изобретения: УСТРОЙСТВО ДЛЯ ФОРМИРОВАНИЯ ОСТАТКА ПО МОДУЛЮ ПЯТЬ, содержащее первый сумматор по модулю пять, отличающееся тем, что оно содержит второй сумматор по модулю пять, вычитатель по модулю пять, двенадцать элементов ИЛИ и четыре блока вычисления фундаментальных симметрических булевых функций, i-й вход (i a; an/2 [/2[, n разрядность входного двоичного слова) первого из которых соединен с входом (4i 3)-го разряда (начиная с младших разрядов) входного слова, j-й вход второго блока вычисления фундаментальных симметрических булевых функций соединен с входом (4j 2)-го разряда входного слова устройства, k-й вход третьего блока вычисления фундаментальных симметрических булевых функций является входом (4K 1)-го разряда входного слова устройства, l-й вход четвертого блока вычисления фундаментальных симметрических булевый функций соединен с входом 4l-го разряда входного слова устройства, входы m-го элемента ИЛИ соединены с выходами функций с порогом A (где A i при lm 1 и i mod 5 = 4l1+2l2+l3, lm({0,1}) первого блока вычисления фундаментальных симметрических булевых функций, входы (m + 3)-го элемента ИЛИ соединены с выходами функции с порогом B (где B j при Jm 1 и (2j) mod 5 = 4J1+2J2+J3, Im(-{0,1}) второго блока вычисления фундаментальных симметрических булевых функций, входы (m + 6)-го элемента ИЛИ соединены с выходами функции с порогом C (где C k при km 1 и k mod 5 = 4k1+2k2+k3, km(-{0,1}) третьего блока вычисления фундаментальных симметрических булевых функций, входы (m + 9)-го элемента ИЛИ соединены с выходами функции с порогом D (где D l при lm 1 и (2l)mod 5 = 4l1+2l2+l3, lm(-{0,1}) четвертого блока вычисления фундаментальных симметрических булевых функций, выход (m + 3t 3)-го элемента ИЛИ (t 1,2) соединен с t-м входом m-го разряда первого сумматора по модулю пять, выход (m + 3t + 3)-го элемента ИЛИ соединен с t-м входом m-го разряда второго сумматора по модулю пять, выход m-го разряда t-го сумматора по модулю пять с t-м входом m-го разряда вычитателя по модулю пять, выход m-го разряда которого является выходом m-го разряда устройства.