close

Вход

Забыли?

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

?

Патент BY5171

код для вставкиСкачать
ОПИСАНИЕ
ИЗОБРЕТЕНИЯ
К ПАТЕНТУ
РЕСПУБЛИКА БЕЛАРУСЬ
BY (11) 5171
(13) C1
(19)
7
(51) G 06F 7/00
(12)
НАЦИОНАЛЬНЫЙ ЦЕНТР
ИНТЕЛЛЕКТУАЛЬНОЙ
СОБСТВЕННОСТИ
(54)
УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ БИСИММЕТРИЧЕСКИХ
БУЛЕВЫХ ФУНКЦИЙ N ПЕРЕМЕННЫХ
(21) Номер заявки: a 19990063
(22) 1999.01.26
(46) 2003.06.30
(71) Заявитель: Белорусский государственный университет (BY)
(72) Авторы: Авгуль Леонид Болеславович;
Супрун Валерий Павлович (BY)
(73) Патентообладатель: Белорусский государственный университет (BY)
(57)
Устройство для вычисления бисимметрических булевых функций n переменных, содержащее первый многовходовый одноразрядный сумматор и мультиплексор, выход которого
соединен с выходом устройства, i-й (i = 1, 2,..., n + 1) настроечный вход которого соединен с iм входом данных мультиплексора, a j-й (j = 1, 2,..., m; 1≤m<n) информационный вход соединен с j-м входом первого многовходового одноразрядного сумматора, t-й (t = 1, 2,..., p;
p = ]log2(m + 1)[) выход которого соединен с t-м адресным входом мультиплексора, отличающееся тем, что дополнительно содержит второй многовходовый одноразрядный сумматор, g-й (g = 1, 2,..., n-m) вход которого соединен с (m + g)-м информационным входом
устройства, а s-й (s = 1, 2,..., r; r = ]log2(n-m + 1)[) выход соединен (p + s)-м адресным входом
мультиплексора, (v + n + 1)-й (v = 1, 2,..., L-n-1; L = (m + 1)(n - m + 1)) вход данных которого
соединен с (v + n + 1)-м настроечным входом устройства.
BY 5171 C1
(56)
SU 1833860 A1, 1993.
BY 2119 C1, 1995.
RU 2047892 C1, 1995.
Фиг. 1
BY 5171 C1
SU 1767495 A1, 1992.
SU 1765818 A1, 1992.
JP 55004691 A, 1980.
JP 55043612 A, 1980.
US 4417305 A, 1983.
Изобретение относится к вычислительной технике и микроэлектронике и предназначено для вычисления бисимметрических булевых функций n переменных.
Известно устройство для вычисления произвольных булевых функций n переменных
(универсальный логический модуль), содержащее n элементов НЕ и n + 1 группу элементов И и ИЛИ [1]. Устройство работает также в режиме 2n-канального мультиплексора.
Недостатком устройства является высокая конструктивная сложность.
Наиболее близким по конструкции и функциональным возможностям техническим
решением к предлагаемому является устройство для вычисления симметрических булевых
функций n переменных, содержащее много-входовый одноразрядный сумматор и мультиплексор [2].
Недостатком известного устройства являются ограниченные функциональные возможности, так как оно не вычисляет бисимметрические булевы функции n переменных.
Изобретение направлено на решение задачи расширения функциональных возможностей устройства.
Названный технический результат достигается путем введения в состав устройства
дополнительно второго многовходового одноразрядного сумматора, а также изменением
связей между элементами устройства.
Устройство для вычисления бисимметрических булевых функций содержит первый
многовходовый одноразрядный сумматор и мультиплексор. Выход мультиплексора соединен с выходом устройства, i-и (i = 1, 2,..., n + 1) настроечный вход которого соединен с
i-м входом данных мультиплексора. В устройстве j-й (j = 1,2,..., m; 1≤m<n) информационный вход соединен с j-м входом первого многовходового одноразрядного сумматора, t-й
(t = 1,2,...,p; р = ]log2(m + 1)[) выход которого соединен с t-м адресным входом мультиплексора.
В отличие от прототипа, в устройство дополнительно введен второй многовходовый
одноразрядный сумматор, g-й (g = 1, 2,..., n-m) вход которого соединен с (m + g)-м информационным входом устройства. При этом s-й (s = I, 2,..., r; r = ]log2(n-m + 1)[) выход второго многовходового одноразрядного сумматора соединен (р+s)-м адресным входом
мультиплексора, (v + n + 1)-й (v = 1, 2,..., L-n-1; L = (m + 1)(n-m + 1)) вход данных которого соединен с (v + n + 1)-м настроечным входом устройства.
На фиг. 1 представлена схема устройства для вычисления бисимметрических булевых
функций. Устройство содержит два многовходовых одноразрядных сумматора 1 и 2, мультиплексор 3, n информационных входов 41-4n, L настроечных входов 515L, и один выход 6.
Поясним принцип работы устройства для вычисления бисимметрических булевых функций.
Обозначим: G sh = (h,h,...,h) - некоторый кортеж длины s, содержащий только элементы h∈{0,1}, и G oh ≡ ∅.
Булева функция F = F(X), X = (x1, x2,..., xn) называется симметрической (с.б.ф.), если
она симметрична относительно любой пары переменных из X. С.б.ф. F однозначно определяется своим локальным кодом π(F) = (π0, π1,...,πn), где πl = F( G1i , G 0n −i ), 0≤i≤n.
Булева функция f = f(X), Х = (х1, х2,..., хn) называется бисимметрической (б.с.б.ф.), если вектор ее переменных X допускает разбиение на два кортежа X1 и Х2, и при этом f
2
BY 5171 C1
симметрична относительно любой пары переменных, принадлежащих одному и тому же
кортежу Х1 и Х2.
Для определенности полагаем: X1 = (x1, x2,..., хm), Х2 = (хm+1 + 1, хm + 2,..., хn, 1≤m<n.
При |Х1| = m, |Х2| -n-m будем говорить, что б.с.б.ф. f от n переменных принадлежит
классу (m, n-m).
Б.с.б.ф. f = f(X) = f(X1,X2), принадлежащая классу (m, n-m), однозначно определяется
своим локальным кодом С(f), который представляет собой булев вектор длины
L = (m + l)(n-m + l) бит:
С(f) = (С00, С01,…, С0, n-m, С10, С11,..., С1, n-m,..., Сm0, Cml,..., Cm, n-m),
где Cij = F( G1i , G 0m − i , G1j , G 0n − m − j ), 0≤i≤m, 0≤j≤n-m.
Число б.с.б.ф. класса (m, n-m) равно 2L.
В общем случае многовходовый одноразрядный сумматор (МОС) имеет n входов и
k = ]log2(n + 1)[ выходов. На входы МОС подаются двоичные переменные X = (x1, x2,...,
xn), на выходах МОС реализуются с.б.ф. ϕ0(X), ϕl(X),..., ϕk-l(X), значения которых составляют позиционный двоичный код, содержащихся в векторе входных переменных X.
Пусть x1 + х2 + ... + хn = i, 0≤i<n. Тогда, очевидно, что
i = ϕ0( G1i , G 0n −i ) + 2ϕ1( G1i , G 0n −i ) + ... + 2k-1 ϕk-1( G1i , G 0n −i ).
Устройство для вычисления б.с.б.ф. содержит два МОС (m-входовый и (n-m)входовый) и 2M-канальный мультиплексор, где
М = p + r, p = ]log2(m + 1)[, r = ]log2(n-m + 1)[.
На входы первого (m-входового) МОС подаются переменные X1 = (x1, х2,…, xm), на
входы второго ((n-m)-входового) МОС - переменные Х2 = (хm+1, xm+2,…, xn).
Выходы первого МОС, на которых реализуются с.б.ф, ϕ0(Х1), ϕ1(Х1),..., ϕp-1(X1) соединяются соответственно с адресными входами мультиплексора, имеющими веса 2М-p, 2М-p + 1,..., 2M-1.
Выходы второго МОС, на которых реализуются с.б.ф. ϕ0(X2), ϕl(X2),..., ϕr-l(X2), соединяются соответственно с адресными входами мультиплексора, имеющими веса 20, 21,…,
2М-р-1. Входы первого и второго МОС являются информационными входами устройства.
Вектором настройки U = (u0, u1,..., uL-1) устройства на реализацию конкретной б.с.б.ф.
f является ее локальный код C(f), т.е. U = С(f).
При этом вход настройки устройства, на который подается сигнал настройки Cij,
0≤i≤m, 0≤j≤n-m, соединяется с входом данных мультиплексора, имеющим номер:
N = i⋅2r + j, r = ]lоg2(n-m + 1)[.
Отметим, что длина L вектора настройки U не превышает число 2M входов данных
мультиплексора (с нулевого по (2М-1)-й). Поэтому, в общем случае, 2М-L входов данных
мультиплексора являются неиспользуемыми.
Устройство для вычисления бисимметрических булевых функций работает следующим образом.
На входы 41-4m поступают переменные x1-xm, первого кортежа X1, на входы 4m+1-4n переменные xm+1-хn второго кортежа X2, на настроечные входы 51-5L - компоненты вектора настройки u0 – uL-1 соответственно. На выходе 6 реализуется значение бисимметрической булевой функции f = f(X1,X2), определяемое вектором настройки U = (u0, u1,..., uL-1).
Рассмотрим следующий пример. При n = 8 и m = 3 предлагаемое устройство реализует
24
2 б.с.б.ф. f = f(X1,Х2), X1 = (х1х2,х3), Х2 = (х4,х5,х6,х7,х8) класса (3, 5).
В этом случае устройство (фиг. 2) содержит трехвходовый одноразрядный сумматор
SM3, пятивходовый одноразрядный сумматор SM5 и мультиплексор MS. Переменные из
X1 и Х2 подаются на входы сумматоров SM3 и SM5 соответственно. Число настроечных
входов устройства равно L = 24.
При этом сигналы настройки u0-u5 подаются на входы данных мультиплексора с нулевого по пятый соответственно, сигналы настройки u6-u11 - на входы данных мультиплексора с восьмого по тринадцатый соответственно, сигналы настройки u12-u17 - на входы
3
BY 5171 C1
данных мультиплексора с шестнадцатого по двадцать первый соответственно, сигналы
настройки uis-uh - на входы данных мультиплексора с двадцать четвертого по двадцать
девятый соответственно.
Найдем вектор настройки U устройства (фиг. 2) на реализацию б.с.б.ф.f класса (3, 5):
f( x1,x8 ) = х1 х2 х3 ∨ (x1х2 х3 ∨ x1 х2 х3 ∨ х1 х2х3) х4 x5 х6 х7 x8 ∨
∨ x1x2x3(x4x5x6x7 ∨ x4x5x6x8 ∨ х4х5х7х8 ∨ x4x6x7x8 ∨ x5x6x7x8).
Очевидно, локальный код заданной б.с.б.ф. имеет вид:
C(f) = (C00, С01 С02, C03, C04, C05, С10, С11, С12, С13, С14, С15,
С20, С21, C22, С23, С24, С25, С30, С31, С32, С33, С34, С35) =
= (1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1).
Поскольку U = С(f), то u0 = u1 = u2 = u3 = u4 = = u5 = u12 = u22 = u23 = 1;
u6 = u7 = u8 = u9 = u10 = u11 = u13 = u14 = u15 = u16 = u17 = u18 = u19 = u20 = u21 = 0.
Устройство реализует также и все симметрические булевы функции от n переменных.
На входы первого и второго МОС подаются (в произвольном порядке) переменные
X = (x1, x2,..., xn) реализуемой с.б.ф. F = F(X). локального кода π(F) по правилу:
Cij = πw, где w = i + j, 0≤i≤m, 0≤j≤n-m.
Достоинствами устройства для вычисления бисимметрических булевых функций являются простая конструкция и высокое быстродействие.
Фиг. 2
Национальный центр интеллектуальной собственности.
220034, г. Минск, ул. Козлова, 20.
4
Документ
Категория
Без категории
Просмотров
0
Размер файла
135 Кб
Теги
by5171, патент
1/--страниц
Пожаловаться на содержимое документа