close

Вход

Забыли?

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

?

Патент BY16124

код для вставкиСкачать
ОПИСАНИЕ
ИЗОБРЕТЕНИЯ
К ПАТЕНТУ
РЕСПУБЛИКА БЕЛАРУСЬ
(46) 2012.08.30
(12)
(51) МПК
НАЦИОНАЛЬНЫЙ ЦЕНТР
ИНТЕЛЛЕКТУАЛЬНОЙ
СОБСТВЕННОСТИ
(54)
BY (11) 16124
(13) C1
(19)
G 06F 7/00
(2006.01)
УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ ПОЛУСИММЕТРИЧЕСКИХ
БУЛЕВЫХ ФУНКЦИЙ ТРЕХ ПЕРЕМЕННЫХ
(21) Номер заявки: a 20101185
(22) 2010.08.03
(43) 2011.02.28
(71) Заявитель: Белорусский государственный университет (BY)
(72) Автор: Супрун Валерий Павлович
(BY)
(73) Патентообладатель: Белорусский государственный университет (BY)
(56) BY 13182 C1, 2010.
BY a 20090335, 2009.
BY 6995 С1, 2005.
BY 2118 C1, 1998.
RU 2047894 C1, 1995.
SU 1689943 A1, 1991.
BY 16124 C1 2012.08.30
(57)
Устройство для вычисления полусимметрических булевых функций трех переменных,
содержащее элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, выход которого соединен с выходом устройства, первый настроечный вход которого соединен с первым входом элемента
СЛОЖЕНИЕ ПО МОДУЛЮ ДВА; первый, второй и третий элементы И, i-й вход первого
из которых, где i = 1, 2, соединен с (i + 1)-м настроечным входом устройства, а выход - со
вторым входом элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, третий вход которого соединен с выходом второго элемента И, первый вход которого соединен с четвертым настроечным входом устройства, информационный вход которого соединен со вторым входом
второго элемента И и с первым входом третьего элемента И, (i + 1)-й вход которого соединен с (i + 4)-м настроечным входом устройства, а выход - с четвертым входом элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА.
Изобретение относится к области вычислительной техники и микроэлектроники и
предназначено для вычисления полусимметрических булевых функций трех переменных.
Известно устройство для вычисления симметрических булевых функций трех переменных, которое содержит элемент ИСКЛЮЧАЮЩЕЕ ИЛИ, элемент РАВНОЗНАЧНОСТЬ, элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, шесть настроечных входов и один
выход [1].
BY 16124 C1 2012.08.30
Известное устройство, как и предлагаемое устройство, содержит элемент СЛОЖЕНИЕ
ПО МОДУЛЮ ДВА, выход которого соединен с выходом устройства, первый настроечный
вход которого соединен с первым входом элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА.
Недостатком известного устройства являются низкие функциональные возможности,
поскольку устройство не позволяет вычислять (реализовать) полусимметрические булевы
функции трех переменных.
Наиболее близким по функциональным возможностям и конструкции техническим
решением к предлагаемому устройству является устройство для вычисления симметрических булевых функций трех переменных, которое содержит элемент И-НЕ, элемент ИЛИНЕ, элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, два информационных и три настроечных
входов, один выход [2].
Устройство-прототип предназначено для вычисления произвольных симметрических
булевых функций трех переменных. Сложность устройства (по числу входов логических
элементов) равна 9, а быстродействие составляет 2τ, где τ - задержка на один логический
элемент.
Устройство-прототип, как и заявляемое устройство, содержит элемент СЛОЖЕНИЕ
ПО МОДУЛЮ ДВА, выход которого соединен с выходом устройства, первый настроечный вход которого соединен с первым входом элемента СЛОЖЕНИЕ ПО МОДУЛЮ
ДВА.
Недостатком устройства-прототипа являются ограниченные функциональные возможности, поскольку устройство не позволяет вычислять полусимметрические булевы
функции трех переменных.
Изобретение направлено на решение задачи расширения функциональных возможностей устройства для вычисления симметрических булевых функций трех переменных за
счет реализации полусимметрических булевых функций трех переменных.
Устройство для вычисления полусимметрических булевых функций трех переменных
содержит элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, выход которого соединен с выходом
устройства, первый настроечный вход которого соединен с первым входом элемента
СЛОЖЕНИЕ ПО МОДУЛЮ ДВА.
Устройство содержит также первый, второй и третий элементы И, i-й вход первого из
которых, где i = 1, 2, соединен с (i + 1)-м настроечным входом устройства, а выход - со
вторым входом элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА.
Третий вход элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА соединен с выходом второго
элемента И, первый вход которого соединен с четвертым настроечным входом устройства.
Информационный вход устройства соединен со вторым входом второго элемента И и
с первым входом третьего элемента И, (i + 1)-й вход которого соединен с (i + 4)-м настроечным входом устройства, а выход - с четвертым входом элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА.
Названный технический результат достигается с помощью введения в логическую
схему устройства новых элементов (элементов И) с последующим изменением соединений между логическими элементами схемы.
На фигуре представлена логическая схема устройства для вычисления полусимметрических булевых функций трех переменных.
Устройство для вычисления полусимметрических булевых функций трех переменных
содержит три элемента И 1, 2 и 3, элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА 4, информационный вход 5, шесть настроечных входов 6…11 и выход 12.
Устройство для вычисления полусимметрических булевых функций трех переменных
работает следующим образом.
На информационный вход устройства 5 поступают значения переменной x3, на
настроечные входы 6…11 - сигналы настройки u0,u1,…,u5, значения которых принадлежат
множеству {0,1, x1 , x1 , x 2 , x 2 }.
2
BY 16124 C1 2012.08.30
На выходе устройства 12 вычисляется (реализуется) полусимметрическая булева функция F = F(X1,x3), где Xl = {xl,x2}, определяемая вектором настройки u(F) = (u0,u1,…,u5).
Поясним принцип построения и работы устройства для вычисления полусимметрических булевых функций трех переменных.
Произвольная булева функций n переменных F = F(xl,x2,…,xn) называется симметрической, если она не меняет своего значения после перестановки любой пары переменных
xi и xj, где i≠j и i, j = 1,2,…,n.
Симметрическая булева функция F = F(xl,x2,…,xn) определяется множеством рабочих
чисел A(F) = {а1,а2,…,аr]. Функция F принимает единичные значения на тех и только тех
наборах значений переменных х1,х2,…,хn, которые содержат ровно ai единиц, где 0 ≤ai ≤n,
1 ≤ i≤r и 0 ≤ r ≤ n + 1.
Симметрическая булева функция F = F(xl,x2,…,xn) взаимно однозначно представляется
(n + 1)-разрядным двоичным вектором (локальным кодом) π(F) = (π0,π1,…,πn), где πi - значение функции F на (любом) наборе значений n переменных, содержащем i (0 ≤ I ≤ n) единиц, т.е. πi = 1 тогда и только тогда, когда i - рабочее число F.
Булева функция n переменных F = F(xl,x2,…,xn) называется полусимметрической, если
булевы функции F0 = F(xn = 0) = F0(X1,0) и Fl = F(xn = 1) = Fl(Xl,1) являются симметрическими, зависящими от n-1 переменных множества Х1 = {х1,х2,…,хn-1}}, где n ≥ 3. Такая булева функция обозначается через F = F(X1,xn).
Любая симметрическая булева функция n переменных F = F(X) является полусимметрической, а обратное утверждение - не всегда верно. Другими словами, симметрические
булевы функции F = F(X) являются частным случаем полусимметрических функций
F = F(X1,xn).
Для булевой функции F = F(Xl,xn) имеет место формула дизъюнктивного разложения
по переменной xn вида:
F(X1 , x n ) = x n F0 ∨ x n F1 .
(1)
Симметрические булевы функции n-1 переменных F0 = F0(X1), F1 = F1(X1) задаются
посредством n-разрядных двоичных векторов π(F0) = (f 00 ,f 10 ,…,f 0n -1 ) и π(F1) = (f 10 ,f 11 ,…,f 1n -1 )
соответственно.
Если для компонент векторов π(F0) и π(F1) выполняется условие fj0 = f 1j-1 j = 1, 2,…, n-1,
то полусимметрическая булева функция F = F(X1,xn) является симметрической, зависящей
от n переменных.
Двоичный 2n-разрядный вектор ω(F) = (π(F0), π(F1)) является локальным кодом булевой функции F = F(X1,xn).
Так как двоичный вектор ω(F) имеет 2n разрядов, то число различных функций вида
F = F(X1,xn) равно 22n = 4n (число симметрических булевых функций n переменных
F = F(X) равно 2n + 1).
Если в формуле (1) заменить x n = x n ⊕ 1 , то
F(X1 , x n ) = x n F0 ⊕ x n F1 = ( x n ⊕ 1)F0 ⊕ x n F1 = F0 ⊕ x n (F0 ⊕ F1 ) , т.е.
(2)
F(X1,xn) = G0 ⊕ xnG1,
0
1
0
0
1
где G0(X1) = F0(X1), G1(X1) = F0(X1) ⊕ F1(X1), π(G0) = (g 0 ,g 1 ,…,g n -1 ) и π(G1) = (g 0 ,g 1 ,…,g 1n -1 ).
На фигуре приведена логическая схема устройства для вычисления полусимметрических булевых функций трех переменных F = F(X1,x3). Первообразная функция логической
схемы имеет вид:
(3)
F(u0,u1,…,u5,x3) = u0 ⊕ u1u2 ⊕ x3u3 ⊕ x3u4u5.
Поясним алгоритм настройки устройства на вычисление произвольно заданной функции F = F(X1,x3).
Если n = 3, то формулы (1) и (2) принимают вид:
3
BY 16124 C1 2012.08.30
F(X1 , x 3 ) = x 3 F0 ∨ x 3 F1 ,
(4)
(5)
F(X1,x3) = G0 ⊕ x3G1,
где G0(x1,x2)=F0(x1,x2) и G1(x1,x2) = F0(x1,x2) ⊕ F1(x1,x2).
Представим функцию F = F(X1,x3) посредством формул (4), (5) и вычислим значения
векторов π(F0) = (f 00 ,f 10 ,f 02 ), π(F1) = (f 10 ,f 11 ,f 12 ), π(G0) = (g 00 ,g 10 ,g 02 ) и π(G1) = (g 10 ,g 11 ,g 12 ), где
g i0 =f i0 , g 1i =f i0 ⊕ f 1i и i = 0, 1, 2.
Посредством таблицы, применительно к вектору π(Gk) = (g 0k ,g 1k ,g k2 ), вычисляем значения вектора (u3k,u3k+1,u3k+2,), где k = 0, 1. Полученные вектора (u0,u1,u2),(u3,u4,u5) являются составными частями искомого вектора настройки u(F) = (u0,u1,…,u5).
Пример 1
Допустим, что на выходе 12 устройства (фигура) требуется вычислить полусимметрическую булеву функцию:
F(X1 , x 3 ) = x 1 x 2 ⋅ x 3 ∨ ( x 1 ∨ x 2 ) ⋅ x 3 .
Так как F0 = x1x2 и F1 = x1 ∨ x2 , то π(F0) = (0,0,1) и π(F1) = (1,1,0). Тогда π(G0) = π(F0) =
(0,0,1) и π(G1) = π(F0)⊕π(F1) = (1,1,1). Если обратиться (дважды) к таблице, то получим
(u0,u1,u2) = (0,x1,x2) и (u3,u4,u5) = (1,0,0), т.е. u(F) = (0,x1,x2,1,0,0).
Следовательно, для вычисления на выходе 12 устройства функции F = F(Xl,x3) необходимо на настроечные входы 6, 10 и 11 подать значение "0", на настроечный вход 7 значение х1, на настроечный вход 8 - значение х2 и на настроечный вход 9 - значение "1".
При этом первообразная функция (3) устройства принимает вид:
F(X1 , x 3 ) = 0 ⊕ x1x 2 ⊕ x 3 ⋅ 1 ⊕ x 3 ⋅ 0 ⋅ 0 = x1x 2 ⊕ x 3 = x1x 2 ⋅ x 3 ∨ x1x 2 ⋅ x 3 = x1x 2 ⋅ x 3 ∨ ( x1 ∨ x 2 ) ⋅ x 3 .
Пример 2
Допустим, что на выходе 12 устройства требуется вычислить симметрическую булеву
функцию:
F(X) = x 1 ⋅ x 2 ⋅ x 3 ∨ x 1 ⋅ x 2 ⋅ x 3 ∨ x 1 ⋅ x 2 ⋅ x 3 .
В таком случае F0 = x1⋅x2, F1 = x1 ⋅ x 2 ∨ x1 ⋅ x 2 , π(F0) = (0,0,1), π(F1) = (0,1,0),
π(G0) = π(F0) = (0,0,1) и π(G1) = π(F0)⊕π(F1) = (0,1,1).
С помощью таблицы получаем:
(u 0 , u1 , u 2 ) = (0, x1 , x 2 ), (u 3 , u 4 , u 5 ) = (1, x1 , x 2 ) è u (F) = (0, x1 , x 2 ,1, x1 , x 2 ).
Значит, для реализации на выходе 12 устройства заданной функции F = F(X) необходимо на настроечные входы 6…11 подать значения "0", х1, х2, "1", x1 и x2 соответственно.
Здесь первообразная функция (3) устройства принимает вид:
F( x1 , x 2 , x 3 ) = 0 ⊕ x1x 2 ⊕ x 3 ⋅ 1 ⊕ x 3 ⋅ x1 ⋅ x 2 =
= x1x 2 ⊕ x 3 ⋅ (1 ⊕ x1 ⋅ x 2 ) = x1x 2 ⊕ x 3 ⋅ ( x1 ⊕ x 2 ⊕ x1x 2 ) =
= x1x 2 ( x 3 ⊕ 1) ⊕ x 3 ⋅ ( x1 ⊕ x 2 ) = x1 ⋅ x 2 ⋅ x 3 ∨ x1 ⋅ x 2 ⋅ x 3 ∨ x1 ⋅ x 2 ⋅ x 3 .
Основным достоинством заявляемого устройства являются широкие функциональные
возможности. Устройство (при подходящей настройке) реализует любую из 64 полусимметрических булевых функций, зависящих от переменных х1, х2, х3. Сложность устройства равна 11.
В то время устройство-прототип ориентировано на вычисление только симметрических булевых функций трех переменных х1, х2, х3, число которых равно 16.
При этом заявляемое устройство и устройство-прототип имеют одинаковое быстродействие, определяемое глубиной схемы.
4
BY 16124 C1 2012.08.30
Устройство для вычисления полусимметрических булевых функций
трех переменных
Локальный двоичный код симметрической
Сигналы настройки
булевой функции Gk = Gk(x1,x2)
u3k
u3k+1
u3k+2
π(Gk) = (g 0k ,g 1k ,g k2 )
000
0
0
0
001
0
x1
x2
010
x1
x2
1
011
1
x1
x2
100
0
x1
x2
x1
101
x2
1
110
1
x1
x2
111
1
0
0
Источники информации:
1. Патент РБ 10216, МПК G 06F 7/00, 2008.
2. Патент РБ 13182, МПК G 06F 7/00, 2010 (прототип).
Национальный центр интеллектуальной собственности.
220034, г. Минск, ул. Козлова, 20.
5
Документ
Категория
Без категории
Просмотров
0
Размер файла
99 Кб
Теги
by16124, патент
1/--страниц
Пожаловаться на содержимое документа