close

Вход

Забыли?

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

?

Патент BY13044

код для вставкиСкачать
ОПИСАНИЕ
ИЗОБРЕТЕНИЯ
К ПАТЕНТУ
РЕСПУБЛИКА БЕЛАРУСЬ
(46) 2010.04.30
(12)
(51) МПК (2009)
НАЦИОНАЛЬНЫЙ ЦЕНТР
ИНТЕЛЛЕКТУАЛЬНОЙ
СОБСТВЕННОСТИ
(54)
BY (11) 13044
(13) C1
(19)
G 06F 7/00
УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ ЧАСТИЧНО
СИММЕТРИЧЕСКИХ БУЛЕВЫХ ФУНКЦИЙ
(21) Номер заявки: a 20071254
(22) 2007.10.16
(43) 2008.06.30
(71) Заявитель: Общество с ограниченной ответственностью "Научно-технический центр "ДЭЛС" (BY)
(72) Авторы: Авгуль Леонид Болеславович; Кряжев Виктор Иванович; Терешко Сергей Михайлович; Усов
Геннадий Иванович (BY)
(73) Патентообладатель: Общество с ограниченной ответственностью "Научнотехнический центр "ДЭЛС" (BY)
(56) BY 8859 C1, 2007.
BY 3300 C1, 2000.
BY 8973 C1, 2007.
RU 2248034 C1, 2005.
US 4163211, 1979.
BY 13044 C1 2010.04.30
(57)
Устройство для вычисления частично симметрических булевых функций, содержащее
три элемента сложения по модулю два, три элемента ИЛИ-НЕ и сорок элементов И-НЕ,
выход первого из которых соединен с выходом устройства, а i-й вход, где i = 1, 2, 3, соединен с выходом (i + 1)-го элемента И-НЕ, j-й вход которого, где j = 1, 2, 3, соединен с
BY 13044 C1 2010.04.30
выходом (3i + j + 1)-го элемента И-НЕ, k-й информационный вход устройства, где k = 1, 2,
первой группы соединен с (k + 3)-м входом четвертого элемента И-НЕ, k-м входом первого элемента ИЛИ-НЕ и k-м входом первого элемента сложения по модулю два, выход которого соединен с четвертым входом третьего элемента И-НЕ, выход первого элемента
ИЛИ-НЕ соединен с четвертым входом второго элемента И-НЕ, k-й информационный
вход устройства второй группы соединен с k-м входом (3i + 4)-го элемента И-НЕ, k-м входом второго элемента ИЛИ-НЕ и k-м входом второго элемента сложения по модулю два,
выход которого соединен с первым входом (3i + 3)-го элемента И-НЕ, выход второго элемента ИЛИ-НЕ соединен с первым входом (3i + 2)-го элемента И-НЕ, первый вход
(l + 13)-го элемента И-НЕ, где l = 1, 27 , соединен с l-м настроечным входом устройства, k-й
информационный вход третьей группы которого соединен с (k + 1)-м входом (3h + 13)
элемента И-НЕ, где h = 1, 9 , k-м входом третьего элемента ИЛИ-НЕ и k-м входом третьего
элемента сложения по модулю два, выход которого соединен со вторым входом (3h + 12)го элемента И-НЕ, выход третьего элемента ИЛИ-НЕ соединен со вторым входом
(3h + 11)-го элемента И-НЕ, (i + 1)-й вход (k + 4)-го элемента И-НЕ соединен с выходом
(3k + i + 10)-го элемента И-НЕ, (i + 2)-й вход седьмого элемента И-НЕ соединен с выходом (i + 19)-го элемента И-НЕ, (i + 1)-й вход (k + 7)-го элемента И-НЕ соединен с выходом
(3k + i + 19)-го элемента И-НЕ, (i + 2)-й вход десятого элемента И-НЕ соединен с выходом
(i + 28)-го элемента И-НЕ, (i + 1)-й вход (k + 10)-го элемента И-НЕ соединен с выходом
(3k + i + 28)-го элемента И-НЕ, (i + 2)-й вход тринадцатого элемента И-НЕ соединен с выходом (i + 37)-го элемента И-НЕ.
Изобретение относится к вычислительной технике и микроэлектронике и может быть
использовано для построения широкого класса цифровых устройств.
Известно устройство для вычисления симметрических булевых функций, содержащее n
групп элементов 2-2И-2ИЛИ, n элементов НЕ, n информационных входов, n + 1 настроечных входов и один выход [1].
Недостатком устройства являются ограниченные функциональные возможности, поскольку оно не реализует частично симметрические булевы функции.
Наиболее близким по конструкции и функциональным возможностям техническим решением к предлагаемому является устройство для вычисления частично симметрических
(бисимметрических) булевых функций четырех переменных, содержащее два элемента
ИЛИ-НЕ, два элемента сложения по модулю два и тринадцать элементов И-НЕ [2].
Недостатком известного устройства для вычисления частично симметрических булевых функций также являются ограниченные функциональные возможности, так как устройство реализует функции, зависящие только от двух кортежей попарно симметрических
переменных (бисимметрические булевы функции).
Изобретение направлено на решение задачи расширения функциональных возможностей устройства для вычисления частично симметрических булевых функций за счет реализации функций, зависящих от трех кортежей попарно симметрических переменных.
Названный технический результат достигается путем введения в состав устройства дополнительно элемента ИЛИ-НЕ, элемента сложения по модулю два и двадцати семи элементов И-НЕ.
Устройство для вычисления частично симметрических булевых функций содержит два
элемента сложения по модулю два, два элемента ИЛИ-НЕ и тринадцать элементов И-НЕ.
Выход первого элемента И-НЕ соединен с выходом устройства, а i-й вход, где i = 1,2,3,
соединен с выходом (i + 1)-го элемента И-НЕ, j-й вход которого, где j = 1,2,3, соединен с
выходом (3i + j + 1)-го элемента И-НЕ.
2
BY 13044 C1 2010.04.30
В устройстве k-й информационный вход, где k = 1,2, первой группы соединен с (k + 3)-м
входом четвертого элемента И-НЕ, k-м входом первого элемента ИЛИ-НЕ и k-м входом
первого элемента сложения по модулю два, выход которого соединен с четвертым входом
третьего элемента И-НЕ. Выход первого элемента ИЛИ-НЕ соединен с четвертым входом
второго элемента И-НЕ.
В устройстве k-й информационный вход второй группы соединен с k-м входом (3i + 4)-го
элемента И-НЕ, k-м входом второго элемента ИЛИ-НЕ и k-м входом второго элемента
сложения по модулю два, выход которого соединен с первым входом (3i + 3)-го элемента
И-НЕ. Выход второго элемента ИЛИ-НЕ соединен с первым входом (3i + 2)-го элемента
И-НЕ.
Устройство содержит третий элемент ИЛИ-НЕ, третий элемент сложения по модулю
два и элементы И-НЕ с четырнадцатого по сороковой.
Первый вход (l + 13)-го элемента И-НЕ, где l = 1,27, соединен с l-м настроечным входом устройства.
В устройстве k-й информационный вход третьей группы соединен с (k + 1)-м входом
(3h + 13) элемента И-НЕ, где h = 1,9, k-м входом третьего элемента ИЛИ-НЕ и k-м входом
третьего элемента сложения по модулю два, выход которого соединен со вторым входом
(3h + 12)-го элемента И-НЕ. Выход третьего элемента ИЛИ-НЕ соединен со вторым входом (3h + 11)-го элемента И-НЕ.
При этом (i + 1)-й вход (k + 4)-го элемента И-НЕ соединен с выходом (3k + i + 10)-го
элемента И-НЕ, (i + 2)-й вход седьмого элемента И-НЕ соединен с выходом (i + 19)-го
элемента И-НЕ, (i + 1)-й вход (k + 7)-го элемента И-НЕ соединен с выходом (3k + i + 19)-го
элемента И-НЕ, (i + 2)-й вход десятого элемента И-НЕ соединен с выходом (i + 28)-го элемента И-НЕ, (i + 1)-й вход (k + 10)-го элемента И-НЕ соединен с выходом (3k + i + 28)-го
элемента И-НЕ, (i + 2)-й вход тринадцатого элемента И-НЕ соединен с выходом (i + 37)-го
элемента И-НЕ.
На фигуре представлена схема устройства для вычисления частично симметрических
булевых функций.
Устройство содержит элементы И-НЕ с первого по сороковой 1-40, первый 41, второй
42 и третий 43 элементы ИЛИ-НЕ, первый 44, второй 45 и третий 46 элементы сложения
по модулю два, два информационных входа первой группы 47 и 48, два информационных
входа второй группы 49 и 50, два информационных входа третьей группы 51 и 52, двадцать семь настроечных входов 53-79 и выход 80.
Поясним принцип работы устройства для вычисления частично симметрических булевых функций.
Обозначим: G sh = (h , h ,..., h ) - некоторый кортеж длины s, содержащий только элементы
h ∈ {0,1}, и G 0h ≡ ∅ .
Булева функция F=F(X), X = (xl,x2,…,xn) называется симметрической (с.б.ф.), если она
симметрична относительно любой пары переменных из X. С.б.ф. F однозначно определяется своим локальным кодом π(F) = (π0,π1,…,πn), где πi = F G1i , G 0n − i 0 ≤ i ≤ n.
Нетривиальная частичная симметрия индуцирует разбиение вектора переменных
X = (x1,x2,…,xn) частично симметрической булевой функции (ч.с.б.ф.) f = f(X) на N кортежей X1,X2,…,XN, 1 < N < n. При этом f симметрична относительно любой пары переменных, принадлежащих одному и тому же кортежу Xi, 1 ≤ i ≤ N.
(
(
)
Пусть X = (Xl,X2,…,XN) и X i = x1i , x i2 ,..., x ik i , 1 ≤ ki < n,
N
)
∑ k i = n,
i −1
1 ≤ i ≤ N.
Тогда число классов эквивалентности ч.с.б.ф. f определяется выражением:
3
BY 13044 C1 2010.04.30
N
p = П (k i + 1).
(1)
i =1
Каждый класс эквивалентности характеризуется вектором
A = (al,a2,…,aN), ai ∈ {0,1,…,ki}, 1 ≤ i ≤ N.
Локальный код C(f) ч.с.б.ф. f есть двоичный вектор длины p, каждая компонента которого равна значению f на соответствующем классе эквивалентности наборов значений ее
аргументов.
Упорядочивая векторы A, представим C(f) в виде:
C(f ) = C00...0 , C00...1 ,..., C00...k N ,..., C01...0 , C01...1 ,..., C01...k N ,..., C 0 k 2 ...0 , C0 k 2 ...1 ,..., C0 k 2 ...k N ,...
(
10...0
C
C
, C10...1 ,..., C10...k N ,..., C11...0 , C11...1 ,..., C11...k N ,..., C1k 2 ...0 , C1k 2 ...1 ,..., C1k 2 ...k N ,...
k 1 0...0
,C
k 1 0...1
,..., C
k 1 0...k N
,..., C
k 1 1...0
a 1a 2 ...a N
где булева константа C
удовлетворяющих условию:
,C
k 1 1...1
,..., C
k 1 1...k N
,..., C
k 1 k 2 ...0
,C
k 1 k 2 ...1
,..., C
k 1 k 2 ...k N
),
(2)
равна значению ч.с.б.ф. f на наборах переменных из Xi,
ki
∑ x iji
ji =1
= a i , ji = 1, k i , 1 ≤ i ≤ N.
Предлагаемое устройство реализует ч.с.б.ф. f = f(X) = f(X1,X2,X3) шести переменных
при k1 = k2 = k3 = 2 (N = 3) и X1 = (x1,x2), X2 = (x3,x4), X3 = (x5,x6).
В этом случае локальный код (2) примет вид:
C(f) = (C000,C001,C002,C010, C011, C012, C020, C021, C022,
C100, C101, C102, C110, C111, C112, C120, C121, C122,
(3)
200
201
202
210
211
212
220
221
222
C , C , C , C , C , C , C , C , C ).
Вектором настройки устройства на реализацию конкретной ч.с.б.ф. является ее локальный код (3). Поскольку длина p локального кода C(f), определяемая формулой (1), равна
(k1 + 1)(k2 + 1)(k3 + 1) = 27, то предлагаемое устройство реализует 2p = 227 ч.с.б.ф. шести
переменных при настройке сигналами из множества {0,1}.
Устройство для вычисления частично симметрических булевых функций работает следующим образом.
На информационные входы 47 и 48 первой группы поступают двоичные переменные x1
и x2 (в произвольном порядке), на информационные входы 49 и 50 второй группы - двоичные переменные x3 и x4 (в произвольном порядке), на информационные входы 51 и 52
третьей группы - двоичные переменные x5 и x6 (в произвольном порядке). На настроечные
входы 53,54,…,79 подаются соответственно компоненты C000,C001,…,C222 локального кода
C(f). На выходе 80 реализуется ч.с.б.ф. f = f(X) = f(X1,X2,X3), определяемая своим локальным кодом C(f).
Найдем сигналы настройки предлагаемого устройства на реализацию ч.с.б.ф.
f = f (X ) = f (X1 , X 2 , X 3 ) = x1 x 2 x 3 x 4 x 5 x 6 ∨ x1 x 2 x 3x 4 x 5 x 6 ∨
∨ (x1 ⊕ x 2 )x 3 x 4 x 5 x 6 ∨ (x1 ⊕ x 2 )x 3x 4 (x 5 ⊕ x 6 ) ∨ x1x 2 (x 3 ⊕ x 4 )x 5 x 6 .
Очевидно, локальный код (3) рассматриваемой ч.с.б.ф. f = f(X) имеет вид:
C(f) = (1,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,1,0,0,0,0,1,0,0,0,0,0).
Следовательно, для реализации ч.с.б.ф. необходимо подать сигналы логической единицы на настроечные входы 53, 58, 64, 69 и 74; сигнал логического нуля - на настроечные
входы 54-57, 59-63, 65-68, 70-73 и 75-79.
Отметим, что устройство реализует также и все симметрические булевы функции шести переменных. В этом случае на информационные входы 47-52 устройства подаются (в
произвольном порядке) переменные X = (x1,x2,…,x6) с.б.ф. F = F(X). Сигналы настройки
C a 1a 2 a 3 , подаваемые на настроечные входы 53-79 устройства, находятся из локального
кода π(F) = (π0,π1,…,π6) реализуемой с.б.ф. по правилу:
4
BY 13044 C1 2010.04.30
C a 1a 2 a 3 = π a 1 + a 2 + a 3 ,
где a1 ∈ {0,1,2}, a2 ∈ {0,1,2}, a3 ∈ {0,1,2}.
Следовательно, вектор настройки устройства при реализации с.б.ф. F = F(X) примет
вид:
C(f ) = (π0 ,π1 , π 2 , π1 , π 2 , π3 , π 2 , π3 , π 4 , π1 , π 2 , π3 , π 2 , π3 ,
π 4 , π3 , π 4 , π 5 , π 2 , π3 , π 4 , π3 , π 4 , π5 , π 4 , π5 , π 6 ).
Достоинствами устройства для вычисления частично симметрических булевых функций являются простая конструкция, высокое быстродействие, широкие функциональные
возможности.
Источники информации:
1. А.с. СССР 1742811, МПК G 06F 7/00, 1992.
2. Патент РБ 8859, МПК G 06F 7/00, H 03K 19/20, 19/01, 2007 (прототип).
Национальный центр интеллектуальной собственности.
220034, г. Минск, ул. Козлова, 20.
5
Документ
Категория
Без категории
Просмотров
0
Размер файла
210 Кб
Теги
патент, by13044
1/--страниц
Пожаловаться на содержимое документа