close

Вход

Забыли?

вход по аккаунту

?

Патент BY7592

код для вставкиСкачать
ОПИСАНИЕ
ИЗОБРЕТЕНИЯ
К ПАТЕНТУ
РЕСПУБЛИКА БЕЛАРУСЬ
(46) 2005.12.30
(12)
7
(51) G 06F 7/00,
НАЦИОНАЛЬНЫЙ ЦЕНТР
ИНТЕЛЛЕКТУАЛЬНОЙ
СОБСТВЕННОСТИ
(54)
BY (11) 7592
(13) C1
(19)
H 03M 7/22
УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ БИСИММЕТРИЧЕСКИХ
БУЛЕВЫХ ФУНКЦИЙ N ПЕРЕМЕННЫХ
(21) Номер заявки: a 20030435
(22) 2003.05.19
(43) 2004.06.30
(71) Заявитель: Белорусский государственный университет (BY)
(72) Авторы: Авгуль Леонид Болеславович; Супрун Валерий Павлович (BY)
(73) Патентообладатель: Белорусский государственный университет (BY)
(56) SU 1765898 A1, 1992.
BY a19990063, 2000.
BY 2119 C1, 1998.
SU 1833860 A1, 1993.
JP 5543612 A, 1980.
JP 554691 A, 1980.
BY 7592 C1 2005.12.30
(57)
Устройство для вычисления бисимметрических булевых функций n переменных, содержащее первый блок вычисления веса двоичных кодовых комбинаций, i-й ( i = 1, m ) вход
которого соединен с i-м информационным входом устройства, отличающееся тем, что
содержит второй блок вычисления веса двоичных кодовых комбинаций, элемент ИЛИ и
Фиг. 1
BY 7592 C1 2005.12.30
m + 1 группу элементов И (m = 1,2,3,…) по p элементов в каждой (p = n-m + 1, n > m, n число переменных реализуемых функций), при этом (m + j)-й информационный вход
( j = 1, n − m ) устройства соединен с j-м входом второго блока вычисления веса двоичных
кодовых комбинаций, k-й выход ( k = 1, p ) которого соединен с первым входом k-го элемента И s-й группы ( s = 1, m + 1 ), второй вход которого соединен с s-м выходом первого
блока вычисления веса двоичных кодовых комбинаций, третий вход соединен с (p(s-1)+k)-м
настроечным входом устройства, а выход соединен с (p(s-1)+k)-м входом элемента ИЛИ,
выход которого соединен с выходом устройства.
Изобретение относится к вычислительной технике и микроэлектронике и предназначено для вычисления бисимметрических булевых функций n переменных.
Известно устройство для вычисления бисимметрических булевых функций n переменных, содержащее два многовходовых одноразрядных сумматора и мультиплексор [1].
Недостатком устройства является высокая конструктивная сложность.
Наиболее близким по конструкции и функциональным возможностям техническим
решением к предлагаемому является устройство для вычисления веса двоичных кодовых
комбинаций, содержащее пороговые элементы, элементы сложения по модулю два, элементы НЕ и элементы И [2]. На выходах устройства формируются фундаментальные симметрические функции n переменных.
Недостатком известного устройства являются ограниченные функциональные возможности, так как оно не вычисляет бисимметрические булевы функции n переменных.
Изобретение направлено на решение задачи расширения функциональных возможностей устройства за счет реализации бисимметрических булевых функций n переменных.
Названный технический результат достигается путем введения в состав устройства
второго блока вычисления веса двоичных кодовых комбинаций, элемента ИЛИ и элементов И.
Устройство для вычисления бисимметрических булевых функций n переменных содержит первый блок вычисления веса двоичных кодовых комбинаций, i-й (i = 1, m ) вход
которого соединен с i-м информационным входом устройства.
В отличие от прототипа, устройство содержит второй блок вычисления веса двоичных
кодовых комбинаций, элемент ИЛИ и m + 1 группу элементов И (m = 1,2,3,...) по p элементов в каждой (p = n-m + 1, n > m, n - число переменных реализуемых функций). При
этом (m + j)-й информационный вход (j = 1, n − m ) устройства соединен с j-м входом второго блока вычисления веса двоичных кодовых комбинаций, k-й выход (k = 1, p ) которого
соединен с первым входом k-го элемента И s-й группы (s = 1, m + 1 ). Второй вход k-го элемента И s-й группы соединен c s-м выходом первого блока вычисления веса двоичных кодовых комбинаций. Третий вход k-го элемента И s-й группы соединен с (p(s-1) + k)-м настроечным входом устройства. Выход k-го элемента И s-й группы соединен с (p(s-1) + k)-м
входом элемента ИЛИ, выход которого соединен с выходом устройства.
На фиг. 1 представлена схема устройства для вычисления бисимметрических булевых
функций n переменных. Устройство содержит два блока вычисления веса двоичных кодовых комбинаций 1 и 2, L = (m + 1)(n-m + 1) элементов И 31...3L (p элементов И первой группы 31…3p, p элементов И второй группы 3р+1...32р,..., p элементов И s-й группы 3L-p+1...3L),
элемент ИЛИ 4, n информационных входов 51...5n, L настроечных входов 61...6L, выход 7.
Поясним принцип работы устройства для вычисления бисимметрических булевых
функций n переменных.
Обозначим: G sh = (h,h,...,h) - некоторый кортеж длины s, содержащий только элементы
h ∈ {0,1} и G 0h ≡ ∅.
2
BY 7592 C1 2005.12.30
Булева функция F = F(X), X = (х1,х2,...,хn) называется симметрической (с.б.ф.), если
она симметрична относительно любой пары переменных из X. С.б.ф. F однозначно определяется своим локальным кодом π(F) = (π0,π1,...,πn), где πi = F( G1i , G 0n −1 ), 0 ≤ i ≤ n.
С.б.ф. Fni = Fni (X), 0 ≤ i ≤ n, называется фундаментальной (ф.с.б.ф.), если в ее локальном коде π( Fni ) только один элемент πi = 1 (все остальные элементы πj = 0, 0 ≤ j ≤ n, j ≠ i):
1, если x1 + x 2 + ... + x n = i;
F ni = F ni ( x1, x 2 ,..., x n ) =
0, если x1 + x 2 + ... + x n ≠ i; 0 ≤ i ≤ n.
Булева функция f = f(X) называется бисимметрической (б.с.б.ф.), если вектор ее переменных X допускает разбиение на два кортежа Х1 и X2, и при этом f симметрична относительно любой пары переменных, принадлежащих одному и тому же кортежу X1 и X2.
Для определенности полагаем: X1 = (x1,x2,...,xm), X2 = (xm+l,xm+2,...,xn), 1 ≤ m < n.
При X1 = m, X2 = n-m будем говорить, что б.с.б.ф. f от n переменных принадлежит классу (m, n-m).
Б.с.б.ф. f = f(X) = f(X1,X2), принадлежащая классу (m, n-m), однозначно определяется
своим локальным кодом С(f), который представляет собой булев вектор длины
L = (m + 1)(n-m + 1) бит:
C(f) = (C00,C01,…,C0,n-m,C10,C11,…,C1,n-m,…,Cm0,Cm1,…,Cm,n-m),
(1)
0
1
0
1
где Сij = f( G i , G m −i , G j , G n − m − j , 0 ≤ i ≤ т, 0 ≤ j ≤ n-m.
Число б.с.б.ф. класса (m, n-m) равно 2L. При этом любая б.ф.ч.с. класса (m, n-m) может
быть представлена в виде:
m n −m
f = f ( X 1, X 2 ) = ∨ ∨ F mi ( X 1 ) ⋅ F nj−m ( X 2 ) ⋅ C ij ,
i =0 j=0
(2)
где Fmi (X1), Fnj−m (X2), i = 0, m , j = 0, n − m - ф.с.б.ф.;
Cij - элементы локального кода (1).
Устройство для вычисления б.с.б.ф. n переменных построено в соответствии с выражением (2).
На входы первого блока вычисления веса двоичных кодовых комбинаций подаются
переменные X1 = (х1,х2,...,хm), на входы второго блока - переменные X2 = (xm+1,xm+2,…,xn).
Входы первого и второго блоков вычисления веса двоичных кодовых комбинаций являются информационными входами устройства.
На выходах первого блока вычисления веса двоичных кодовых комбинаций реализу0
ются ф.с.б.ф. Fm0 (X1), Fm1 (X1),..., Fmm (X1), на выходах второго блока - ф.с.б.ф. Fn−
m ( X 2 ),
Fn1−m (X 2 ),..., Fnn−−mm (X 2 ) .
Вектором настройки U = (u0, u1,..., uL-1) устройства на реализацию конкретной б.с.б.ф.
f является ее локальный код C(f), т.е. U = C(f). Сигнал настройки Cij (0 ≤ i ≤ m, 0 ≤ j ≤ n-m)
подается на вход элемента И, у которого другие входы соединены с выходами первого и
второго блоков вычисления веса двоичных кодовых комбинаций, на которых реализуются
ф.с.б.ф. Fmi (X1) и Fnj−m (X2) соответственно.
Устройство для вычисления б.с.б.ф. n переменных работает следующим образом.
На информационные входы 51-5m поступают переменные х1-хm первого кортежа Х1, на
входы 5m+1-5n - переменные хm+1-xn второго кортежа X2, на настроечные входы 61-6L - сигналы настройки u0-uL-1 соответственно. На выходе 7 реализуется б.с.б.ф. f = f(X1,X2), определяемая вектором настройки U = (u0, u1,...,uL-1).
Рассмотрим следующий пример. При n = 5 и m = 2 предлагаемое устройство реализует
12
2 б.с.б.ф. f = f(X1,X2), Х1 = (х1, x2), X2 = (x3, x4, х5) класса (2, 3). В этом случае устройство
(фиг. 2) содержит два блока вычисления веса двоичных кодовых комбинаций (FSM2 и
FSM3), L = (m + 1)(n-m + 1) = 12 элементов И и элемент ИЛИ. Переменные из Х1 и X2 по-
3
BY 7592 C1 2005.12.30
даются на входы блоков FSM2 и FSM3 соответственно. Число настроечных входов устройства равно L = 12.
Найдем вектор настройки U устройства (фиг. 2) на реализацию б.с.б.ф. f класса (2, 3):
f x 1 , x 5 = x 1 x 2 ∨ ( x 1 x 2 ∨ x 1 x 2 ) ⋅ x 3 x 4 x 5 ∨ x 1 x 2 ( x 3 x 4 x 5 ∨ x 3 x 4 x 5 ∨ x 3 x 4 x 5 ∨ x 3 x 4 x 5 ).
Очевидно, локальный код заданной б.с.б.ф. имеет вид:
C(f) = (C00,C01,С02,С03,С10,С11,С12,С13,С20,С21,С22,С23) = (0,0,1,1,1,0,0,0,1,1,1,1).
Поскольку U = C(f), то
u0 = u1 = u5 = u6 = u7 = 0; u2 = u3 = u4 = u8 = u9 = u10 = u11 = 1.
Устройство реализует также и все симметрические булевы функции от n переменных.
На входы первого и второго блоков вычисления веса двоичных кодовых комбинаций (в
произвольном порядке) переменные X = (х1,х2,...,хn) реализуемой с.б.ф. F = F(X). Сигналы
настройки Сij устройства на реализацию конкретной с.б.ф. находятся из ее локального кода π(F) по правилу:
Сij = πw, где w = i + j, 0 ≤ i ≤ m, 0 ≤ j ≤ n-m.
Достоинствами устройства для вычисления бисимметрических булевых функций являются простая конструкция и высокое быстродействие.
(
)
Источники информации:
1. Патент РБ 5171, МПК G 06F 7/00, 2003.
2. А.с. СССР 1765898, МПК H 03M 7/22, 1992 (прототип).
Фиг. 2
Национальный центр интеллектуальной собственности.
220034, г. Минск, ул. Козлова, 20.
Документ
Категория
Без категории
Просмотров
0
Размер файла
140 Кб
Теги
by7592, патент
1/--страниц
Пожаловаться на содержимое документа