close

Вход

Забыли?

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

?

Патент BY11756

код для вставкиСкачать
ОПИСАНИЕ
ИЗОБРЕТЕНИЯ
К ПАТЕНТУ
РЕСПУБЛИКА БЕЛАРУСЬ
(46) 2009.04.30
(12)
(51) МПК (2006)
НАЦИОНАЛЬНЫЙ ЦЕНТР
ИНТЕЛЛЕКТУАЛЬНОЙ
СОБСТВЕННОСТИ
(54)
BY (11) 11756
(13) C1
(19)
G 06F 7/00
УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ ЧАСТИЧНО
СИММЕТРИЧЕСКИХ БУЛЕВЫХ ФУНКЦИЙ n ПЕРЕМЕННЫХ
(21) Номер заявки: a 20060919
(22) 2006.09.20
(43) 2007.10.30
(71) Заявитель: Общество с ограниченной
ответственностью "Научно-технический центр "ДЭЛС" (BY)
(72) Автор: Авгуль Леонид Болеславович
(BY)
(73) Патентообладатель: Общество с ограниченной ответственностью "Научнотехнический центр "ДЭЛС" (BY)
(56) BY 7592 C1, 2005.
BY 3300 C1, 2000.
BY 11756 C1 2009.04.30
(57)
Устройство для вычисления частично симметрических булевых функций n переменных,
характеризующееся тем, что содержит первый многофункциональный логический модуль,
BY 11756 C1 2009.04.30
выход которого соединен с выходом устройства, a jl-й, где jl = 1, k l , где kl = 1, 2, 3,…,
информационный вход соединен с jl-м входом первой группы информационных входов
устройства, N − 1, где N = 2, 3, 4,…, линейку многофункциональных логических модулей,
i-я из которых, где i = 1, N − 1 , содержит pi групп по ki + 1 модулей в каждой группе, где
p i = ∏ (k t −1 + 1) ; k0 = 0; ki + l = 1, 2, 3,…; n = ∑ k q - количество переменных частично симi
N
t =1
q =1
метрических булевых функций, при этом ji + 1-й, где ji+1 = 1, k i+1 , информационный вход liго, где l i = 1, k i + 1 , модуля si-й, где si = 1, pi , группы i-й линейки соединен с ji + 1-м входом
(i + 1)-й группы информационных входов устройства, g-й, где g = 1, k 1 + 1 , настроечный
вход первого модуля соединен с выходом g-го модуля первой линейки, hν-й, где
h ν = 1, k ν +1 + 1 , настроечный вход lν-го модуля sν-й группы ν-й линейки, где ν = 1, N − 2 ,
соединен с выходом hν-го модуля ((s ν − 1)(k ν + 1) + l ν ) -й группы (ν + 1)-й линейки, hN-1-й,
где h N−1 = 1, k N + 1 , настроечный вход lN-1-го модуля sN-1-й группы (N-1)-й линейки соединен с (((s N −1 − 1)(k N −1 + 1) + l N−1 − 1)(k N + 1) + h N−1 ) -м настроечным входом устройства.
Изобретение относится к вычислительной технике и микроэлектронике и может быть
использовано для построения широкого класса цифровых устройств.
Известно устройство для вычисления бисимметрических булевых функций n переменных, содержащее два многовходовых одноразрядных сумматора и мультиплексор [1].
Недостатком известного устройства являются ограниченные функциональные возможности, поскольку оно реализует частично симметрические булевы функции, зависящие только от двух кортежей попарно симметрических переменных.
Наиболее близким по конструкции и функциональным возможностям техническим
решением к предлагаемому является устройство для вычисления бисимметрических булевых функций n переменных, содержащее два блока вычисления веса двоичных кодовых
комбинаций, группу элементов И и элемент ИЛИ [2].
Недостатком известного устройства также являются ограниченные функциональные
возможности, так как оно не реализует частично симметрические булевы функции, зависящие от трех и более кортежей попарно симметрических переменных.
Изобретение направлено на решение задачи расширения функциональных возможностей устройства за счет вычисления частично симметрических булевых функций, зависящих от произвольного числа кортежей попарно симметрических переменных.
Названный технический результат достигается путем использования для построения
устройства многофункциональных логических модулей (устройств для вычисления симметрических булевых функций) с ограниченным числом информационных входов, соединенных между собой по специальной схеме.
Устройство для вычисления частично симметрических булевых функций n переменных содержит первый многофункциональный логический модуль, выход которого соединен с выходом устройства, а j1-й, где j1 = 1, k1 , где k1 = 1, 2, 3,…, информационный вход
соединен с j1-м входом первой группы информационных входов устройства.
Кроме того, устройство содержит N − 1, где N = 2, 3, 4,…, линейку многофункциональных логических модулей, i-я из которых, где i = 1, N − 1 , содержит рi групп по ki + 1
i
N
t =1
q =1
модулей в каждой группе, где p i = ∏ (k t −1 + 1) ; k0 = 0; ki+l = 1, 2, 3,…; n = ∑ k q - количество переменных частично симметрических булевых функций.
2
BY 11756 C1 2009.04.30
При этом ji+1-й, где ji +1 = 1, k i +1 , информационный вход li-го, где li = 1, k i + 1 , модуля si-й,
где s i = 1, pi , группы i-й линейки соединен с ji+1-м входом (i + 1)-й группы информационных входов устройства, g-й, где g = 1, k1 + 1 , настроечный вход первого модуля соединен
с выходом g-го модуля первой линейки, hν -й , где h ν = 1, k ν +1 + 1 , настроечный вход
lν-го модуля sν-й группы ν-й линейки, где ν = 1, N − 2 , соединен с выходом hν-го модуля
((sν - 1)(kν + 1) + lν)-й группы (ν + 1)-й линейки, hN-1-й, где h N −1 = 1, k N + 1 , настроечный
вход lN-1 -го модуля s N-1 -й группы (N − 1)-й линейки соединен с (((s N−1 - 1)(kN−1 + 1) +
+ lN-1 – 1)(kN + 1) + hN-1)-м настроечным входом устройства.
На фигуре представлена схема устройства для вычисления частично симметрических
булевых функций n переменных при n = 7 и k1 = 2, k2 = 2, k3 = 3 (N = 3).
Устройство содержит первый многофункциональный логический модуль 1 с k1 = 2
информационными входами, N − 1 = 2 линейки многофункциональных логических модулей (p1 = k0 + 1 = 1 одну группу из k1 + 1 = 3 модулей 2, 3 и 4 с k2 = 2 информационными
входами первой линейки; р2 = (k0 + l)(k1 + 1) = 3 группы по k2 + 1 = 3 модуля в каждой с
k3 = 3 информационными входами второй линейки - модули первой группы 5, 6 и 7, модули второй группы 8, 9 и 10, модули третьей группы 11, 12 и 13), k1 = 2 входа 14 и 15 первой группы информационных входов устройства, k2 = 2 входа 16 и 17 второй группы
информационных входов устройства, k3 = 3 входа 18, 19 и 20 третьей группы информационных входов устройства, (k1 + 1)(k2 + 1)(k3 + 1) = 36 настроечных входов 21-56 устройства и один выход 57 устройства.
Устройство (фигура) реализует 2( k 1 +1)( k 2 +1)( k 3 +1) = 236 частично симметрических булевых функций n = 7 переменных (включая функции все 2n+1 = 28 симметрические булевы
функции n = 7 переменных) при настройке сигналами из множества {0,1}.
Поясним принцип построения и работы устройства для вычисления частично симметрических булевых функций n переменных.
Обозначим G sh = (h , h , L , h ) - некоторый кортеж длины s, содержащий только элементы h ∈ {0,1} и G 0h ≡ ∅.
Булева функция F = F(X), X = (х1, х2,…, хn), называется симметрической (с.б.ф.), если
она симметрична относительно любой пары переменных из X.
С.б.ф. F=F(X) однозначно определяется своим локальным кодом π(F) = (π0, π1,…, πn),
где πi = F(G1i , G 0n − i ) , i = 0, n .
С.б.ф. Fni = Fni (X) , 0 ≤ i ≤ n, называется фундаментальной (ф.с.б.ф.), если
1, если x1 + x 2 + L + x n = i;
Fni = Fni (X) =
0, если x1 + x 2 + L + x n ≠ i; 0 ≤ i ≤ n.
Очевидно, что в локальном коде π(Fni ) ф.с.б.ф. Fni только один элемент πi = 1 (все остальные элементы πj = 0, 0 ≤ j ≤ n, j ≠ 1).
Очевидно, что произвольная с.б.ф. F = F(X) от n переменных может быть однозначно
представлена посредством ф.с.б.ф в виде
n
F = F(X) = ∨ πi ⋅ Fni (X) .
i=0
(1)
Определение. Первообразной функцией многофункционального логического модуля
называется логическое (булево) выражение, устанавливающее связь между реализуемой
на выходе модуля булевой функцией и элементами вектора входных переменных и вектора настройки.
3
BY 11756 C1 2009.04.30
Известны многофункциональные логические модули (универсальные в классе с.б.ф.),
имеющие n информационных входов (на них подаются двоичные переменные х1, х2,…, хn)
и n + 1 настроечных входов, на которые подаются сигналы настройки π0, π1,…, πn, определяющие реализуемую на единственном выходе модуля с.б.ф. F = F(X), заданную своим
локальным кодом π(F) = (π0, π1,…, πn).
Многофункциональные логические модули, вектором настройки которых на реализацию конкретной с.б.ф. F = F(X) является ее локальный код π(F), назовем модулями π-типа.
Обозначим Sn(Х, π(F)) = Sn(Х, π0, π1,…, πn) - первообразная функция модуля π-типа,
реализующего все с.б.ф. n переменных.
При описании модулей π-типа как "черных ящиков" в качестве первообразной функции Sn(X, π(F)) может выступать выражение (1), т.е.
n
Sn (X, π(F) = Sn (X, π0 , π1, L , πn ) = ∨ πi ⋅ Fni (X) .
(2)
i =0
Первообразные функции всех модулей π-типа, независимо от их конкретной структуры (схемотехнической реализации), путем тождественных преобразований могут быть
сведены к виду (2), поскольку с.б.ф. F = F(X) однозначно определяется вектором π(F).
Нетривиальная частичная симметрия индуцирует разбиение вектора переменных
Х = (х1, x2,…, хn) частично симметрической булевой функции (ч.с.б.ф.) f = f(X) на N кортежей Х1, Х2,…, XN, 1 < N < n. При этом f симметрична относительно любой пары переменных, принадлежащих одному и тому же кортежу Xi, 1 ≤ i ≤ N.
Пусть X = (Х1, Х2, …, XN) и X i = ( x1i , x i2 ,L, x ik i ) , 1 ≤ ki < n,
N
∑ k i = n , 1 ≤ i ≤ N.
i =1
Тогда число классов эквивалентности ч.с.б.ф. f определяется выражением
N
p = ∏ (k i + 1) .
(3)
i =1
Каждый класс эквивалентности характеризуется вектором
A = (al, a2,…, aN), аi ∈ {0, 1,…, ki,}, 1 ≤ i ≤ N.
Локальный код С(f) ч.с.б.ф. f есть двоичный вектор длины p, каждая компонента которого равна значению f на соответствующем классе эквивалентности наборов значений ее
аргументов.
Упорядочивая векторы А, представим С(f) в виде:
C(f ) = (C00L0 , C 00L1 ,L, C00Lk N ,L, C01L0 , C01L1 ,L, C01Lk N ,L, C 0k 2 L0 , C0 k 2 L1 , L,
C0 k 2 Lk N , L, C10L0 , C10L1 ,L, C10Lk N ,L, C11L0 , C11L1 ,L, C11Lk N , L, C1k 2 L0 , C1k 2 L1 ,
L, C1k 2 Lk N ,L, C k 1 0L0 , C k 1 0L1 ,L, C k 1 0Lk N ,L, C k 1 1L0 , C k 1 1L1 ,L, C k 1 1Lk N ,L, C k1 k 2 L0 ,
C k 1k 2 L1 ,L, C k 1 k 2 Lk N ),
(4)
где булева константа Ca1a 2 La N равна значению ч.с.б.ф. f на наборах переменных из Xi,
удовлетворяющих условию:
ki
∑ x il = a i , 1 ≤ i ≤ N .
l =1
(5)
Пример 1.
Пусть f = f(X), X = (х1, х2, х3, х4, х5, х6, х7), - некоторая ч.с.б.ф. n = 7 переменных и
X = (X1, Х2, Х3), Xl = (xl, x2), Х2 = (х3, х4), Х3 = (х5, х6, х7) (k1 = 2, k2 = 2, k3 = 3, N = 3):
4
BY 11756 C1 2009.04.30
f = f ( X ) = x 1x 2 x 3 x 4 x 5 x 6 x 7 ∨ x 1 x 2 x 3 x 4 ∨ x 1 x 2 x 3 x 4 ∨ x 3 x 4 x 5 ∨ x 3 x 4 x 6 ∨ x 3 x 4 x 7 .
Принимая во внимание (4) и (5), построим локальный код ч.с.б.ф. f:
C(f) = (C000, C001, C002, C003, C010, C011, C012, C013, C020, C021, C022, C023, C100, C101, C102,
C103, C110, C111, C112, C113, C120, C121, C122, C123, C200, C201, C202, C203, C210, C211, C212, C213, C220,
C221, C222, C223) = (0,0,0,1,0,0,0,0,1,1,1,0,1,1,1,1,0,0,0,0,1,1,1,0,0,0,0,0,0,0,0,0,1,1,1,0). Любая
ч.с.б.ф. f = f(X) = (X}, Х2,…, XN) может быть представлена посредством ф.с.б.ф., зависящих от переменных кортежей Xi, i = 1, N , в виде
k1
k2
kN
f = ∨ ∨ L ∨ Fkj11 (X1 ) ⋅ Fkj22 (X 2 ) ⋅ ... ⋅ FkjNN (X N ) ⋅ C j1 j2 L jN ,
ji = 0 j2 = 0
(6)
jN = 0
где C j1 j2L jN - элементы локального кода (4), ji = 0, k i , i = 1, N .
Преобразуем выражение (6) к виду
k1
 k2
  k N −1
 kN
f = ∨ Fkj11 (X1 ) ⋅  ∨ Fkj 22 (X 2 ) ⋅ L  ∨ Fkj NN−−11 (X N −1 ) ⋅  ∨ Fkj NN (X N ) ⋅ C j1 j 2 L j N

 j2 = 0
j1 = 0
 jN =0
  j N−1 = 0

   
  L .
   
(7)
Декомпозиционное разложение (7) по кортежам Хi, i = 1, N , попарно симметрических
переменных определяет N-уровневую каскадную структуру устройства для вычисления
частично симметрических функций n переменных, i-й уровень которой содержит многофункциональные логические модули π-типа с первообразной функцией вида (2). При этом на
информационные входы модулей i-го уровня поступают переменные только кортежа Xi.
Предлагаемое устройство построено в соответствии с разложением (7) и реализует 2p
ч.с.б.ф. n переменных, где p - длина локального кода ч.с.б.ф., определяемая формулой (3).
Вектором настройки устройства на реализацию конкретной ч.с.б.ф. f является ее локальный код С(f).
Пример 2.
Получим выражение для первообразной функции устройства при n = 7 и k1 = 2, k2 = 2,
k3 = 3 (N = 3) через первообразные модулей π-типа. Тогда (7) примет вид:
2
 2
 3
 2
f = f (X) = ∨ F2j1 (X1 ) ⋅  ∨ F2j2 (X 2 ) ⋅  ∨ F3j3 (X3 ) ⋅ C j1 j2 j3   = ∨ F2j1 (X1 ) ⋅
j1 = 0
 j3 = 0
  j1 = 0
 j2 = 0

 2
⋅  ∨ F2j2 (X 2 ) ⋅ (F30 (X3 ) ⋅ C j1 j2 0 ∨ F31 (X3 ) ⋅ C j1 j2 1 ∨ F32 (X3 ) ⋅ C j1 j2 2 ∨ F33 (X3 ) ⋅ C j1 j2 3 ) =
j
0
=

2
2
 2

= ∨ F2j1 (X1 ) ⋅  ∨ F2j2 (X 2 ) ⋅ S3 (X3 , C j1 j2 0 , C j1 j2 1, C j1 j2 2 , C j1 j2 3 ) =
j1 = 0
 j2 = 0

2

 2
= ∨ F2j1 (X1 ) ⋅  ∨ F2j2 (X 2 ) ⋅ S3 (X3 , C j1 j2 ),
j1 = 0

 j2 = 0
(8)
где C j1 j2 = (C j1 j2 0 , C j1 j2 1, C j1 j2 2 , C j1 j2 3 ) ; j1 = 0, 1, 2; j2 = 0, 1, 2;
S3 (X 3 , C j1 j2 ) - первообразная функция модуля π-типа с тремя информационными и четырьмя настроечными входами.
Проведем дальнейшие преобразования выражения (8):
5
BY 11756 C1 2009.04.30
f = ∨ F2j1 (X1 ) ⋅ (F20 (X 2 ) ⋅ S3 (X 3 , C j1 0 ) ∨ F21 (X 2 ) ⋅ S3 (X 3 , C j1 1 ) ∨ F22 (X 2 ) ⋅ S3 (X 3 , C j1 2 )) =
2
j1 = 0
= ∨ F2j1 (X1 ) ⋅ (S2 (X 2 , S3 (X 3 , C j1 0 ), S3 (X 3 , C j1 1 ), S3 (X 3 , C j1 2 ))) =
2
j1 = 0
= S2 (S2 (X 2 , S3 (X 3 , C00 ), S3 (X 3 , C01 ), S3 (X 3 , C 02 ))),
S2 (X 2 , S3 (X 3 , C10 ), S3 (X 3 , C11 ), S3 (X 3 , C12 )),
S2 (X 2 , S3 (X 3 , C 20 ), S3 (X 3 , C 21 ), S3 (X 3 , C 22 )).
(9)
Устройство для вычисления частично симметрических булевых функций семи переменных при k1 = 2, k2 = 2, k3 = 3 (фигура) построено согласно первообразной функции (9).
Устройство для вычисления частично симметрических булевых функций при n = 7
(фигура) работает следующим образом.
На информационные входы 14 и 15 первой группы подаются двоичные переменные х1
и х2 кортежа Х1 (в произвольном порядке), на информационные входы 16 и 17 второй
группы - двоичные переменные х3 и х4 кортежа Х2 (в произвольном порядке), на информационные входы 18, 19 и 20 третьей группы - двоичные переменные х5, х6 и х7 кортежа
Х3 (в произвольном порядке), на настроечные входы 21, 22,…, 56 - соответственно компоненты С000, С001,…, С223 локального кода С(f) ч.с.б.ф. f = f(X) = (Х1, Х2, Х3), значения которой реализуются на выходе 57 устройства.
Пример 3.
Определим сигналы настройки устройства (фигура) на реализацию заданной своим
локальным кодом С(f) ч.с.б.ф. f = f(X) = (Х1, Х2, Х3) из примера 1:
С(f) = (0,0,0,1,0,0,0,0,1,1,1,0,1,1,1,1,0,0,0,0,1,1,1,0,0,0,0,0,0,0,0,0,1,1,1,0).
Поскольку вектор настройки устройства совпадает с локальным кодом С(f) реализуемой функции f, то на настроечные входы 21-24 подаются соответственно компоненты кортежа С00 = (C000, С001, С002, С003) = (0,0,0,1), на настроечные входы 25-28 - соответственно
компоненты кортежа С01 = (C010, С011, С012, С013) = (0,0,0,0), на настроечные входы 29-32 соответственно компоненты кортежа С02 = (C020, С021, С022, С023) = (1,1,1,0), на настроечные
входы 33-36 - соответственно компоненты кортежа С10 = (C100, С101, С102, С103) = (1,1,1,1),
на настроечные входы 37-40 - соответственно компоненты кортежа С11 = (C110,С111, С112,
С113) = (0,0,0,0), на настроечные входы 41-44 - соответственно компоненты кортежа
С12 = (С120,С121,С122,С123) = (1,1,1,0), на настроечные входы 45-48 - соответственно компоненты кортежа С20 = (C200, С201, С202, С203) = (0,0,0,0), на настроечные входы 49-52 - соответственно компоненты кортежа С21 = (C210,С211, С212, С213) = (0,0,0,0), на настроечные
входы 53-56 - соответственно компоненты кортежа С22 = (С220,С221,С222,С223) = (1,1,1,0).
Тогда, в соответствии с (1) и (2), на выходах модулей второй линейки реализуются
симметрические булевы функции:
на выходе модуля 5 - ψ0 = ψ0(X3) = F33(X3) = x5х6х7;
на выходе модуля 6 - ψ1 = ψ1(Х3) ≡ 0;
на выходе модуля 7 - ψ 2 = ψ 2 (X3 ) = F30 (X 3 ) ∨ F31 (X 3 ) ∨ F32 (X3 ) = x 5 ∨ x 6 ∨ x 7 ;
на выходе модуля 8 - ψ3 = ψ3(Х3) ≡ 1;
на выходе модуля 9 - ψ4 = ψ4(Х3) ≡ 0;
на выходе модуля 10 - ψ 5 = ψ 5 (X3 ) = ψ 2 (X 3 ) = x 5 ∨ x 6 ∨ x 7 ;
на выходе модуля 11 - ψ6 = ψ6(Х3) ≡ 0,
на выходе модуля 12 - ψ7 = ψ7(X3) ≡ 0;
на выходе модуля 13 - ψ8 = ψ 8 (X 3 ) = ψ 2 (X 3 ) = ψ 5 (X 3 ) = x 5 ∨ x 6 ∨ x 7 .
6
BY 11756 C1 2009.04.30
На выходах модулей первой линейки реализуются частично симметрические булевы
функции:
на выходе модуля 2 - ϕ0 = ϕ0 (X 2 , X3 ) = ψ 0F20 (X 2 ) ∨ ψ1F21 (X 2 ) ∨ ψ 2F22 (X 2 ) =
= x 5 x 6 x 7 ⋅ F20 (X 2 ) ∨ ( x 5 ∨ x 6 ∨ x 7 ) ⋅ F22 (X 2 ) = x 3x 4 x 5 x 6 x 7 ∨ x 3x 4 ( x 5 ∨ x 6 ∨ x 7 );
на выходе модуля 3 - ϕ1 = ϕ1 (X 2 , X3 ) = ψ 3F20 (X 2 ) ∨ ψ 4F21 (X 2 ) ∨ ψ5F22 (X 2 ) =
= F20 (X 2 ) ∨ ( x 5 ∨ x 6 ∨ x 7 ) ⋅ F22 (X 2 ) = x 3x 4 ∨ x 3x 4 ( x 5 ∨ x 6 ∨ x 7 );
на выходе модуля 4 - ϕ2 = ϕ2 (X 2 , X3 ) = ψ 6F20 (X 2 ) ∨ ψ 7 F21 (X 2 ) ∨ ψ8F22 (X 2 ) =
= ( x 5 ∨ x 6 ∨ x 7 ) ⋅ F22 (X 2 ) = x 3 x 4 ( x 5 ∨ x 6 ∨ x 7 ) .
На выходе модуля 1 (выходе 57 устройства) реализуется заданная частично симметрическая булева функция
f = f (X) = f (X1 , X 2 , X 3 ) = ϕ0 F20 (X1 ) ∨ ϕ1F21 (X1 ) ∨ ϕ2 F22 (X1 ) =
= F20 (X1 ) ⋅ ( x 3 x 4 x 5 x 6 x 7 ∨ x 3 x 4 ( x 5 ∨ x 6 ∨ x 7 )) ∨ F21 (X1 ) ⋅ ( x 3 x 4 ∨ x 3 x 4 ( x 5 ∨ x 6 ∨ x 7 )) ∨
∨ F22 (X1 ) ⋅ ( x 3 x 4 ( x 5 ∨ x 6 ∨ x 7 )) = x1x 2 ( x 3 x 4 x 5 x 6 x 7 ∨ x 3 x 4 ( x 5 ∨ x 6 ∨ x 7 )) ∨
∨ ( x1x 2 ∨ x1x 2 )( x 3 x 4 ∨ x 3 x 4 ( x 5 ∨ x 6 ∨ x 7 )) ∨ x1x 2 x 3 x 4 ( x 5 ∨ x 6 ∨ x 7 ) =
= x 1x 2 x 3 x 4 x 5 x 6 x 7 ∨ x 1x 2 x 3 x 4 ( x 5 ∨ x 6 ∨ x 7 ) ∨ x 1 x 2 x 3 x 4 ∨ x 1 x 2 x 3 x 4 ∨
∨ ( x1x 2 ∨ x1x 2 )( x 3 x 4 ( x 5 ∨ x 6 ∨ x 7 )) ∨ x1x 2 x 3 x 4 ( x 5 ∨ x 6 ∨ x 7 ) =
= x1x 2 x 3 x 4 x 5 x 6 x 7 ∨ x1x 2 x 3 x 4 ∨ x1x 2 x 3 x 4 ∨ ( x1x 2 ∨ x1x 2 ∨ x1x 2 ∨ x1x 2 )( x 3 x 4 ( x 5 ∨ x 6 ∨ x 7 )) =
14444
4244444
3
≡1
= x 1x 2 x 3 x 4 x 5 x 6 x 7 ∨ x 1x 2 x 3 x 4 ∨ x 1 x 2 x 3 x 4 ∨ x 3 x 4 x 5 ∨ x 3 x 4 x 6 ∨ x 3 x 4 x 7 .
Следует отметить, что устройство реализует и все 2n+1 симметрические булевы функции n
переменных. В этом случае сигналы настройки находятся из локального кода π(F) = (π0,
πl,…, πn) с.б.ф. F = F(X) по правилу:
C j1 j2 L jN = π j1 + j2 +L+ jN , ji = 0, k i , i = 1, N.
(10)
Это означает, что на настроечный вход устройства, на который подается элемент
C
j1 j2L jN
локального кода С(f) ч.с.б.ф. f = f(X), должен быть подан элемент π j1 + j2 +L+ jN ло-
кального кода π(F) с.б.ф. F = F(X). При этом на информационные входы устройства переменные X = (х1, х2,…, хn) реализуемой с.б.ф. F = F(X) подаются в произвольном порядке
(без учета групп информационных входов).
Пример 4.
Определим вектор настройки устройства (фигура) на реализацию заданной своим локальным кодом π(F) = (π0, π1,…,π7) некоторой с.б.ф. F = F(X) семи переменных.
Из соотношения (10) непосредственно следует, что вектор настройки примет вид:
C(f) = (C000, C001, C002, C003, C010, C011, C012, C013, C020, C021, C022, C023, C100, C101, C102, C103,
110
C , C111, C112, C113, C120, C121, C122, C123, C200, C201, C202, C203, C210, C211, C212, C213, C220, C221,
C222, C223)=(π0, π1, π2, π3, π1, π2, π3, π4, π2, π3, π4, π5,
π1, π2, π3, π4, π2, π3, π4, π5, π3, π4, π5, π6,
π2, π3, π4, π5, π3, π4, π5, π6, π4, π5, π6, π7).
7
BY 11756 C1 2009.04.30
Достоинствами устройства являются простая конструкция и возможность вычисления
частично симметрических булевых функций произвольного числа n переменных. При
этом для построения устройства используются многофункциональные логические модули
с ограниченным числом информационных входов.
Источники информации:
1. Патент РБ 5171, МПК G 06F 7/00, 2003.
2. Патент РБ 7592, МПК G 06F 7/00, Н 03М 7/22, 2005 (прототип).
Национальный центр интеллектуальной собственности.
220034, г. Минск, ул. Козлова, 20.
8
Документ
Категория
Без категории
Просмотров
0
Размер файла
285 Кб
Теги
by11756, патент
1/--страниц
Пожаловаться на содержимое документа