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

Описание патента на изобретение RU2045771C1

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

На чертеже представлена схема устройства для формирования остатка по модулю пять при разрядности входного двоичного слова, равной 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= Ф41

1∨ Ф91
1 (6)
p2= Ф21
1∨ Ф31
1∨ Ф71
1∨ Ф81
1 (7)
p3= Ф31
1∨ Ф81
1∨ Ф11
1∨ Ф61
1∨ Ф1111
(8)
S1= F21
0∨ F71
0 (9)
S2= F11
0∨ F41
0∨ F61
0∨ F91
0 (10)
S3= F41
0∨ F91
0∨ F31
0∨ F81
0 (11)
V1= Q41
0∨ Q91
0 (12)
V2= Q21
0∨ Q31
0∨ Q71
0∨ Q81
0 (13)
V3= Q31
0∨ Q81
0∨ Q11
0∨ Q61
0 (14)
W1= Z21
0∨ Z71
0 (15)
W2= Z71
0∨ Z41
0∨ Z61
0∨ Z91
0 (16)
W3= Z41
0∨ Z91
0∨ Z31
0∨ Z81
0 (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 соответственно быстродействие блока вычисления фундаментальных симметрических булевых функций, элемента ИЛИ, сумматора по модулю пять, вычитателя по модулю пять.

Похожие патенты RU2045771C1

название год авторы номер документа
УСТРОЙСТВО ДЛЯ ФОРМИРОВАНИЯ ОСТАТКА ПО МОДУЛЮ ТРИ 1992
  • Авгуль Леонид Болеславович[By]
  • Терешко Сергей Михайлович[By]
  • Курносенко Сергей Васильевич[By]
RU2045770C1
УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ СИММЕТРИЧЕСКИХ БУЛЕВЫХ ФУНКЦИЙ 1992
  • Авгуль Леонид Болеславович[By]
  • Костеневич Валерий Иванович[By]
  • Торбунов Владимир Васильевич[By]
RU2047893C1
УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ СИММЕТРИЧЕСКИХ БУЛЕВЫХ ФУНКЦИЙ 1992
  • Авгуль Леонид Болеславович[By]
  • Супрун Валерий Павлович[By]
RU2047894C1
УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ СИММЕТРИЧЕСКИХ БУЛЕВЫХ ФУНКЦИЙ 1992
  • Авгуль Леонид Болеславович[By]
  • Костеневич Валерий Иванович[By]
  • Торбунов Владимир Васильевич[By]
  • Курносенко Сергей Васильевич[By]
RU2047892C1
МНОГОВХОДОВЫЙ ОДНОРАЗРЯДНЫЙ СУММАТОР 1992
  • Авгуль Леонид Болеславович[By]
  • Курносенко Сергей Васильевич[By]
  • Супрун Валерий Павлович[By]
RU2047216C1
Устройство для вычисления веса двоичных кодовых комбинаций 1990
  • Авгуль Леонид Болеславович
  • Супрун Валерий Павлович
SU1765898A1
УСТРОЙСТВО ДЛЯ СЛОЖЕНИЯ И ВЫЧИТАНИЯ N ЧИСЕЛ ПО МОДУЛЮ 2-1 1992
  • Авгуль Леонид Болеславович[By]
  • Курносенко Сергей Васильевич[By]
RU2047897C1
МНОГОФУНКЦИОНАЛЬНЫЙ ЛОГИЧЕСКИЙ МОДУЛЬ 1991
  • Авгуль Леонид Болеславович[By]
  • Супрун Валерий Павлович[By]
RU2045769C1
Программируемое устройство 1991
  • Авгуль Леонид Болеславович
  • Супрун Валерий Павлович
SU1789979A1
СУММАТОР ПО МОДУЛЮ СЕМЬ 1992
  • Авгуль Леонид Болеславович[By]
RU2028660C1

Иллюстрации к изобретению RU 2 045 771 C1

Реферат патента 1995 года УСТРОЙСТВО ДЛЯ ФОРМИРОВАНИЯ ОСТАТКА ПО МОДУЛЮ ПЯТЬ

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

Формула изобретения RU 2 045 771 C1

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

Документы, цитированные в отчете о поиске Патент 1995 года RU2045771C1

Сумматор по модулю пять 1988
  • Музыченко Олег Николаевич
SU1566342A1
Приспособление для точного наложения листов бумаги при снятии оттисков 1922
  • Асафов Н.И.
SU6A1

RU 2 045 771 C1

Авторы

Авгуль Леонид Болеславович[By]

Даты

1995-10-10Публикация

1992-05-18Подача