close

Вход

Забыли?

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

?

Патент BY13973

код для вставкиСкачать
ОПИСАНИЕ
ИЗОБРЕТЕНИЯ
К ПАТЕНТУ
РЕСПУБЛИКА БЕЛАРУСЬ
(46) 2011.02.28
(12)
(51) МПК (2009)
НАЦИОНАЛЬНЫЙ ЦЕНТР
ИНТЕЛЛЕКТУАЛЬНОЙ
СОБСТВЕННОСТИ
(54)
BY (11) 13973
(13) C1
(19)
G 06F 7/00
УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ
БИСИММЕТРИЧЕСКИХ БУЛЕВЫХ ФУНКЦИЙ
(21) Номер заявки: a 20090420
(22) 2009.03.20
(43) 2009.08.30
(71) Заявитель: Белорусский государственный университет (BY)
(72) Авторы: Супрун Валерий Павлович;
Городецкий Данила Андреевич (BY)
(73) Патентообладатель: Белорусский государственный университет (BY)
(56) BY 8973 C1, 2007.
BY 8619 C1, 2006.
BY 8859 C1, 2007.
SU 1748149 A1, 1992.
BY 13973 C1 2011.02.28
(57)
Устройство для вычисления бисимметрических булевых функций пяти переменных,
содержащее мажоритарный элемент с порогом два, элементы СЛОЖЕНИЕ ПО МОДУЛЮ
ДВА с первого по пятый и элементы И с первого по седьмой, характеризующееся тем, что
выход первого элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА соединен с выходом устройства, первый вход – с первым настроечным входом устройства, i-й вход мажоритарного
элемента с порогом два, где i = 1,2,3, соединен с i-м информационным входом устройства,
с i-м входом второго элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА и с i-м входом первого
элемента И, выход которого соединен со вторым входом первого элемента СЛОЖЕНИЕ
ПО МОДУЛЮ ДВА, третий вход которого соединен с выходом второго элемента И,
BY 13973 C1 2011.02.28
первый вход которого соединен с выходом мажоритарного элемента с порогом два, а второй вход - с выходом третьего элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, первый вход
которого соединен со вторым настроечным входом устройства, а второй вход соединен с
выходом третьего элемента И, j-й, где j = 1,2, вход которого соединен с (j + 2)-м настроечным входом устройства, (j + 4)-й настроечный вход которого соединен с j-м входом четвертого элемента И, выход которого соединен с четвертым входом первого элемента
СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, пятый вход которого соединен с выходом пятого элемента И, первый вход которого соединен с выходом второго элемента СЛОЖЕНИЕ ПО
МОДУЛЮ ДВА, а второй вход соединен с выходом четвертого элемента СЛОЖЕНИЕ ПО
МОДУЛЮ ДВА, первый вход которого соединен с седьмым настроечным входом устройства, а второй вход - с выходом шестого элемента И, j-й вход которого соединен с (j + 7)-м
настроечным входом устройства, десятый настроечный вход которого соединен с первым
входом пятого элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, выход которого соединен с
четвертым входом первого элемента И, а второй вход - с выходом седьмого элемента И, jй вход которого соединен с (j + 10)-м настроечным входом устройства.
Изобретение относится к области вычислительной техники и микроэлектроники и
предназначено для вычисления бисимметрических булевых функций пяти переменных.
Известно устройство для вычисления симметрических булевых функций пяти переменных, которое содержит мажоритарные элементы с порогами два, три, четыре, пять и
шесть, элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, пять информационных и шесть настроечных входов, выход [1].
Известное устройство, как и предлагаемое устройство, содержит мажоритарный элемент с порогом два и элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, выход которого соединен с выходом устройства, первый настроечный вход которого соединен с первым входом
элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА.
Недостатком известного устройства являются низкие функциональные возможности,
поскольку устройство не позволяет вычислять (реализовать) бисимметрические булевы
функции пяти переменных.
Наиболее близким по функциональным возможностям и конструкции техническим
решением к предлагаемому устройству является устройство для вычисления бисимметрических булевых функций шести переменных, которое содержит два полных одноразрядных двоичных сумматора, пятнадцать элементов ИЛИ и элемент СЛОЖЕНИЕ ПО
МОДУЛЮ ДВА, а также имеет шесть информационных и шестнадцать настроечных входов, один выход [2].
Устройство-прототип, как и заявляемое устройство, содержит элемент СЛОЖЕНИЕ
ПО МОДУЛЮ ДВА, выход которого соединен с выходом устройства, первый настроечный вход которого соединен с первым входом элемента СЛОЖЕНИЕ ПО МОДУЛЮ
ДВА.
Недостатком устройства-прототипа является высокая конструктивная сложность, которая по числу входов логических элементов составляет 75 (при этом предполагается, что
полный одноразрядный двоичный сумматор содержит элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА и мажоритарный элемент с порогом два и его сложность равна 6).
Изобретение направлено на решение технической задачи понижения конструктивной
сложности устройства для вычисления бисимметрических булевых функций пяти переменных.
Устройство для вычисления бисимметрических булевых функций пяти переменных
содержит мажоритарный элемент с порогом два, элементы СЛОЖЕНИЕ ПО МОДУЛЮ
ДВА с первого по пятый, элементы И с первого по седьмой.
2
BY 13973 C1 2011.02.28
Выход первого элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА соединен с выходом
устройства, первый вход - с первым настроечным входом устройства, i-й вход мажоритарного элемента с порогом два, где i = 1,2,3, соединен с i-м информационным входом
устройства, с i-м входом второго элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА и с i-м входом первого элемента И.
Выход первого элемента И соединен со вторым входом первого элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, третий вход которого соединен с выходом второго элемента И,
первый вход которого соединен с выходом мажоритарного элемента с порогом два, а второй вход - с выходом третьего элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА.
Первый вход третьего элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА соединен со вторым
настроечным входом устройства, а второй вход соединен с выходом третьего элемента И,
j-й, где j = 1,2, вход которого соединен с (j + 2)-м настроечным входом устройства, (j + 4)й настроечный вход которого соединен с j-м входом четвертого элемента И.
Выход четвертого элемента И соединен с четвертым входом первого элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, пятый вход которого соединен с выходом пятого элемента
И, первый вход которого соединен с выходом второго элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, а второй вход соединен с выходом четвертого элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА.
Первый вход четвертого элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА соединен с седьмым настроечным входом устройства, а второй вход - с выходом шестого элемента И, j-й
вход которого соединен с (j + 7)-м настроечным входом устройства, десятый настроечный
вход которого соединен с первым входом пятого элемента СЛОЖЕНИЕ ПО МОДУЛЮ
ДВА.
Выход пятого элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА соединен с четвертым входом первого элемента И, а второй вход - с выходом седьмого элемента И, j-й вход которого соединен с (j + 10)-м настроечным входом устройства.
Названный технический результат достигается с помощью введения в логическую
схему устройства для вычисления бисимметрических булевых функций новых логических
элементов (мажоритарного элемента с порогом два и элементов И) с последующим изменением соединений логических элементов в схеме.
На чертеже (фигура) представлена логическая схема устройства для вычисления бисимметрических булевых функций пяти переменных.
Устройство для вычисления бисимметрических булевых функций содержит мажоритарный элемент с порогом два 1, семь элементов И 2…8, пять элементов СЛОЖЕНИЕ ПО
МОДУЛЮ ДВА 9…13, три информационных входа 14, 15 и 16, двенадцать настроечных
входов 17…28 и выход 29.
Устройство для вычисления бисимметрических булевых функций пяти переменных
работает следующим образом. На информационные входы устройства 14, 15 и 16 поступают (в произвольном порядке) значения переменных x1,x2,x3, на настроечные входы
17…28 - сигналы настройки u0,u1,…,u11, значения которых принадлежат множеству
{0,1, x 4 , x 4 , x 5 , x 5} . На выходе устройства 29 вычисляется (реализуется) бисимметрическая булева функция F = F(X1,X2), где X1 = {x1,x2,x3} и X2 = {x4,x5}, определяемая вектором настройки u(F) = (u0,u1,…,u11).
Поясним принцип построения и работы устройства для вычисления бисимметрических булевых функций пяти переменных.
Произвольная симметрическая булева функция n переменных F = F(x1,x2,…,xn) характеризуется множеством рабочих чисел A(F) = {a1,a2,…,ar}. Функция F принимает единичные значения на тех и только тех наборах значений переменных x1,x2,…,xn, которые
содержат ровно ai единиц, где 0≤ai≤n, 1≤i≤r и 0≤r≤n + l. Функция F обозначается как
F = Fna1 ,a 2 ,…,a r (X) , где X = {x1,x2,…,xn}.
3
BY 13973 C1 2011.02.28
Если r = 1, то функция F = Fna (X) называется фундаментальной (или элементарной)
симметрической булевой функцией.
Произвольная симметрическая булева функция F = F(x1,x2,…,xn) взаимно однозначно
представляется (n + 1) - разрядным (локальным кодом) двоичным вектором π(F) = (π0,
π1,…,πn), где πi - значение функции F на (любом) наборе значений n переменных, содержащем i (0≤ i ≤n) единиц. Иначе, πi = 1 тогда и только тогда, когда i - рабочее число функции F.
Если произвольная булева функция n переменных F = F(X) не меняет своего значения
после перестановки любой пары переменных xi и xj (где i ≠ j и i,j = 1,2,…,n), то функция F
является симметрической. В противном случае говорят, что булева функция F = F(X) обладает (или не обладает) свойством частичной симметрии переменных.
Известно, что отношение частичной симметрии разбивает (единственным образом)
множество переменных X = {x1,x2,…,xn} на классы симметрии X1,X2,…,Xk, где 1≤k≤n.
Если k = 1, то функция F является (полностью) симметрической; если k = 2, то F - бисимметрическая булева функция; если k = n, то функция F не обладает свойством частичной симметрии переменных.
Бисимметрическая булева функция обозначается F(X) = F(X1,X2), где X1,X2 - классы
симметрии.
Пусть n = 5 и X1 = {x1,x2,x3}, X2 = {x4,x5}. Тогда для бисимметрической булевой функции F(X) = F(X1,X2) имеет место формула
F(X1 , X 2 ) = F30 (x1 , x 2 , x 3 ) ⋅ G 0 (x 4 , x 5 ) ∨ F31 (x1 , x 2 , x 3 ) ⋅ G1 (x 4 , x 5 ) ∨
∨ F32 (x1 , x 2 , x 3 ) ⋅ G 2 (x 4 , x 5 ) ∨ F33 (x1 , x 2 , x 3 ) ⋅ G 3 (x 4 , x 5 )
или
F(X) = F30 ( X1 ) ⋅ G 0 (X 2 ) ⊕ F31 ( X1 ) ⋅ G1 (X 2 ) ⊕
⊕ F32 ( X1 ) ⋅ G 2 (X 2 ) ⊕ F33 ( X1 ) ⋅ G 3 (X 2 )
,
(1)
где
F30 (x1 , x 2 , x 3 ) = x1 ⋅ x 2 ⋅ x 3 ,
F31 (x1, x 2 , x 3 ) = x1 ⋅ x 2 ⋅ x 3 ∨ x1 ⋅ x 2 ⋅ x 3 ∨ x1 ⋅ x 2 ⋅ x 3 ,
F32 (x1 , x 2 , x 3 ) = x1 ⋅ x 2 ⋅ x 3 ∨ x1 ⋅ x 2 ⋅ x 3 ∨ x1 ⋅ x 2 ⋅ x 3 ,
F33 (x1 , x 2 , x 3 ) = x1 ⋅ x 2 ⋅ x 3
и G0 = G0(x4,x5), G1 = G1(x4,x5), G2 = G2(x4,x5), G3 = G3(x4,x5) - симметрические булевы
функции, зависящие от переменных x4 и x5.
Двоичный вектор ω(F) = (π(G0),(π(G1),(π(G2),(π(G3)) = (ω0,ω1,…, ω11) называется двоичным кодом булевой функции F = F(X1,X2).
Если в формуле (1) заменить x1 = x1 ⊕ 1, x 2 = x 2 ⊕ 1 и x 3 = x 3 ⊕ 1 , то
F(X1, X 2 ) = H 0 (X 2 ) ⊕ ( x1 ⊕ x 2 ⊕ x 3 ) ⋅ H1 (X 2 ) ⊕
⊕ (x1x 2 ⊕ x1x 3 ⊕ x 2 x 3 ) ⋅ H 2 (X 2 ) ⊕ x1 x 2 x 3 ⋅ H 3 (X 2 ) ,
где H 0 (X 2 ) = G 0 (X 2 ), H1 (X 2 ) = G 0 (X 2 ) ⊕ G1 (X 2 ) ,
H 2 (X 2 ) = G 0 (X 2 ) ⊕ G 2 (X 2 ) и
H 3 (X 2 ) = G 0 (X 2 ) ⊕ G1 (X 2 ) ⊕ G 2 (X 2 ) ⊕ G 3 (X 2 ) .
Введем в рассмотрение двоичный вектор
γ(F) = (π(H0),(π(H1),(π(H2),(π(H3)) = (γ0, γ1,…,γ11).
Компоненты двоичных векторов ω(F) и γ(F) связаны между собой следующими соотношениями:
4
BY 13973 C1 2011.02.28
γ i = ωi , γ i + 3 = ωi ⊕ ωi + 3 , γ i + 6 = ωi ⊕ ωi + 6 ,
(2)
γ i + 9 = ωi ⊕ ωi + 3 ⊕ ωi + 6 ⊕ ωi + 9 ,
где i = 0,1,2.
Поясним метод построения вектора u(F) = (u0,u1,…,u11) - вектора настройки заявляемого устройства (фигура) на вычисление заданной бисимметрической булевой функции
F = F(X1,X2).
С помощью локальных кодов π(H0) = (γ0,γ1,γ2), π(H1) = (γ3,γ4,γ5), π(H2) = (γ6,γ7,γ8),
π(H3) = (γ9,γ10,γ11) из таблицы настройки (таблица), где j = 0,1,2,3, получаем значения
фрагментов (u0,u1,u2), (u3,u4,u5), (u6,u7,u8), (u9,u10,u11) вектора настройки u(F) = (u0,u1,…,u11).
Рассмотрим пример. Предположим, что на выходе 29 устройства (фигура) требуется
реализовать бисимметрическую булеву функцию
F(X1 , X 2 ) = x1 ⋅ x 2 ⋅ x 3 ⋅(x 4 ∨ x 5 ) ∨ (x1 ⋅ x 2 ∨ x1 ⋅ x 3 ∨ x 2 ⋅ x 3 ) ⋅ x 4 ⋅ x 5 .
Так как
F(x1 , x 2 ,…, x 5 ) = x1 ⋅ x 2 ⋅ x 3 ⋅(x 4 ∨ x 5 ) ∨ (x1 ⋅ x 2 ⋅ x 3 ∨ x1 ⋅ x 2 ⋅ x 3 ∨ x1 ⋅ x 2 ⋅ x 3 ) ⋅ 0 ∨
∨ ( x1 ⋅ x 2 ⋅ x 3 ∨ x1 ⋅ x 2 ⋅ x 3 ∨ x1 ⋅ x 2 ⋅ x 3 ) ⋅ x 4 ⋅ x 5 ∨ x1 ⋅ x 2 ⋅ x 3 ⋅ x 4 ⋅ x 5 ,
то формула (1) принимает вид
F( x1 , x 2 ,…, x 5 ) = E 30 (x1 , x 2 , x 3 ) ⋅ G 0 (x 4 , x 5 ) ∨ E13 (x1 , x 2 , x 3 ) ⋅ G1 (x 4 , x 5 ) ∨
∨ E 32 (x1 , x 2 , x 3 ) ⋅ G 2 (x 4 , x 5 ) ∨ E 33 (x1 , x 2 , x 3 ) ⋅ G 3 (x 4 , x 5 ),
где π(G0) = (0,1,1), π(G1) = (0,0,0) и π(G2) = π(G3) = π(0,0,1).
Отсюда следует, что двоичный код бисимметрической булевой функции F = F(X1,X2)
равен
ω(F) = (π(G0),(π(G1),(π(G2),(π(G3)) = (0,1,1,0,0,0,0,0,1,0,0,l).
Используя формулы (2), получаем γ(F) = (0,1,1,0,1,1,0,1,0,0,1,1), т.е. π(H0) = (0,1,1),
π(H1) = (0,1,1), π(H2) = (0,1,0) и π(H3) = (0,1,1).
Принимая во внимание описанную выше процедуру построения вектора настройки
u(F) = (u0,u1,…,u11), получаем u0 = 1, u1 = x 4 , u 2 = x 5 , u3 = 1, u 4 = x 4 , u 5 = x 5 , u6 = x4,
u7 = x5, u8 = 1, u9 = 1, u10 = x 4 и u 11= x 5 .
Следовательно, для вычисления на выходе 29 устройства (фигура) функции
F(X1 , X 2 ) = x1 ⋅ x 2 ⋅ x 3 ⋅(x 4 ∨ x 5 ) ∨ (x1 ⋅ x 2 ∨ x1 ⋅ x 3 ∨ x 2 ⋅ x 3 ) ⋅ x 4 ⋅ x 5 необходимо на настроечные входы 17, 20, 25 и 26 подать значение "1", на настроечные входы 18, 21 и 27 - значение x 4 , на настроечные входы 19, 22 и 28 - значение x 5 , на настроечный вход 23 значение x4 и на настроечный вход 24 - значение x5.
Первообразная функция устройства для вычисления бисимметрических булевых
функций пяти переменных (фигура) имеет вид
F(x1 , x 2 , x 3 , u 0 , u1 ,…, u11 ) = u 0 ⊕ u1u 2 ⊕ ( x1 ⊕ x 2 ⊕ x 3 ) ⋅ (u 3 ⊕ u 4 u 5 ) ⊕
⊕ ( x1x 2 ⊕ x1x 3 ⊕ x 2 x 3 ) ⋅ (u 6 ⊕ u 7 u 8 ) ⊕ x1x 2 x 3 ⋅ (u 9 ⊕ u10 u11 ).
В качестве проверки подставим в выражение для первообразной функции устройства
значения компонент вектора настройки
u ( F ) = 1, x 4 , x 5 ,1, x 4 , x 5 , x 4 , x 5 ,1,1, x 4 , x 5 .
В таком случае первообразная функция примет вид
(
)
5
BY 13973 C1 2011.02.28
F(x , x , x , x , x ) = 1 ⊕ x ⋅ x ⊕ ( x ⊕ x ⊕ x ) ⋅ (1 ⊕ x ⋅ x ) ⊕
⊕ ( x ⋅ x ⊕ x ⋅ x ⊕ x ⋅ x ) ⋅ ( x ⊕ x ⋅ 1) ⊕ x x x ⋅ (1 ⊕ x ⋅ x ) =
1
2
1
3
2
4
5
1
3
4
2
5
3
1
4
3
2
1
5
4
2
3
5
4
5
= (1 ⊕ x1 ⊕ x 2 ⊕ x 3 ⊕ x1 ⋅ x 2 ⋅ x 3 ) ⋅ ( x 4 ⊕ x 5 ⊕ x 4 ⋅ x 5 ) ⊕
⊕ ( x1 ⋅ x 2 ⊕ x1 ⋅ x 3 ⊕ x 2 ⋅ x 3 ) ⋅ ( x 4 ⊕ x 5 ) =
(
)
= x1 ⋅ x 2 ⋅ x 3 ⊕ x1 ⋅ x 2 ⊕ x1 ⋅ x 3 ⊕ x 2 ⋅ x 3 ⋅ ( x 4 ⊕ x 5 ⊕ x 4 ⋅ x 5 ) ⊕
⊕ ( x1 ⋅ x 2 ⊕ x1 ⋅ x 3 ⊕ x 2 ⋅ x 3 ) ⋅ ( x 4 ⊕ x 5 ) =
= x1 ⋅ x 2 ⋅ x 3 ⋅ ( x 4 ⊕ x 5 ⊕ x 4 ⋅ x 5 ) ⊕ ( x1 ⋅ x 2 ⊕ x1 ⋅ x 3 ⊕ x 2 ⋅ x 3 ) ⋅ x 4 ⋅ x 5 =
= x1 ⋅ x 2 ⋅ x 3 ⋅ ( x 4 ∨ x 5 ) ∨ ( x1 ⋅ x 2 ∨ x1 ⋅ x 3 ∨ x 2 ⋅ x 3 ) ⋅ x 4 ⋅ x 5 .
Основным достоинством заявляемого устройства для вычисления бисимметрических
булевых функций пяти переменных является небольшая конструктивная сложность, равная 33. При этом сложность устройства-прототипа составляет 75.
Дополнительным достоинством устройства является небольшое число внешних выводов (три информационных и двенадцать настроечных входов, выход). Число внешних выводов устройства-прототипа равно 23 (двадцать два входа и выход).
Локальный код симметрической булевой
функции Hj = Hj(x4,x5)
π(Hj) = (γ3j,γ3j + 1,γ3j + 2)
000
001
010
Вектор настройки u(F) = (u0,u1,…,u11)
u3j
0
0
x4
u3j + 1
0
x4
x5
011
1
x4
u3j + 2
0
x5
1
x5
100
0
x4
1
1
x4
x5
x5
x4
0
1
x5
0
101
110
111
Источники информации:
1. Патент РБ 2793, МПК G 06 F 7/00, 1999.
2. Патент РБ 8973, МПК G 06 F 7/00, 2007 (прототип).
Национальный центр интеллектуальной собственности.
220034, г. Минск, ул. Козлова, 20.
6
Документ
Категория
Без категории
Просмотров
0
Размер файла
102 Кб
Теги
by13973, патент
1/--страниц
Пожаловаться на содержимое документа