close

Вход

Забыли?

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

?

Патент BY16241

код для вставкиСкачать
ОПИСАНИЕ
ИЗОБРЕТЕНИЯ
К ПАТЕНТУ
РЕСПУБЛИКА БЕЛАРУСЬ
(46) 2012.08.30
(12)
(51) МПК
НАЦИОНАЛЬНЫЙ ЦЕНТР
ИНТЕЛЛЕКТУАЛЬНОЙ
СОБСТВЕННОСТИ
(54)
BY (11) 16241
(13) C1
(19)
G 06F 7/00
(2006.01)
УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ БИСИММЕТРИЧЕСКИХ
БУЛЕВЫХ ФУНКЦИЙ ПЯТИ ПЕРЕМЕННЫХ
(21) Номер заявки: a 20101148
(22) 2010.07.26
(43) 2011.02.28
(71) Заявитель: Белорусский государственный университет (BY)
(72) Автор: Супрун Валерий Павлович
(BY)
(73) Патентообладатель: Белорусский государственный университет (BY)
(56) BY a20090420, 2009.
BY a20090335, 2009.
BY 7947 C1, 2006.
BY 13240 C1, 2010.
BY 16241 C1 2012.08.30
(57)
Устройство для вычисления бисимметрических булевых функций пяти переменных,
содержащее первый, второй, третий, четвертый и пятый элементы И, первый, второй и
третий элементы СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, выход первого из которых соединен с
выходом устройства, первый настроечный вход которого соединен с первым входом первого элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, второй вход которого соединен с выходом первого элемента И, первый вход которого соединен со вторым настроечным входом
устройства, третий настроечный вход которого соединен с первым входом второго элемента И, выход которого соединен с первым входом второго элемента СЛОЖЕНИЕ ПО
МОДУЛЮ ДВА, выход которого соединен с первым входом третьего элемента И, выход
которого соединен с третьим входом первого элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА,
четвертый вход которого соединен с выходом четвертого элемента И, первый вход которого соединен с выходом третьего элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, первый
BY 16241 C1 2012.08.30
вход которого соединен с выходом пятого элемента И, первый вход которого соединен с
четвертым настроечным входом устройства, пятый и шестой настроечные входы которого
соединены со вторыми входами второго и третьего элементов СЛОЖЕНИЕ ПО МОДУЛЮ ДВА соответственно; первый, второй и третий элементы ИЛИ и четвертый элемент
СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, выход которого соединен со вторым входом третьего
элемента И, а i-й вход, где i = 1, 2, соединен с (i + 1)-м входом четвертого элемента И и с
i-м информационным входом устройства, (i + 2)-й информационный вход которого соединен с (i + 1)-м входом первого, второго и пятого элементов И и с i-м входом первого, второго и третьего элементов ИЛИ, третьи входы которых соединены соответственно с
седьмым, восьмым и девятым настроечными входами устройства.
Изобретение относится к области вычислительной техники и микроэлектроники и
предназначено для вычисления бисимметрических булевых функций пяти переменных.
Известно устройство для вычисления симметрических булевых функций пяти переменных, которое содержит элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом два, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом шесть, мажоритарный элемент с порогом три, элемент
СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, двенадцать настроечных входов и выход [1]. Известное
устройство, как и предлагаемое устройство, содержит элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, выход которого соединен с выходом устройства.
Недостатком известного устройства являются низкие функциональные возможности,
поскольку устройство не позволяет вычислять (реализовывать) бисимметрические булевы
функции пяти переменных.
Наиболее близким по функциональным возможностям и конструкции техническим
решением к предлагаемому устройству является устройство для вычисления бисимметрических булевых функций пяти переменных, которое содержит семь элементов И, пять
элементов СЛОЖЕНИЕ ПО МОДУЛЮ ДВА и мажоритарный элемент с порогом два, а
также имеет три информационных и двенадцать настроечных входов, выход [2].
Конструктивная сложность устройства (по числу входов логических элементов) равна
33, а быстродействие составляет 4τ, где τ - задержка на один логический элемент. Устройство-прототип, как и предлагаемое устройство, содержит пять элементов И и три элемента
СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, выход первого из которых соединен с выходом устройства, первый вход соединен с первым настроечным входом устройства, а второй и третий
входы - с выходами первого и второго элементов И.
Недостатком устройства-прототипа является большое число внешних выводов, равное 16.
Изобретение направлено на решение технической задачи: уменьшение числа внешних
выводов устройства для вычисления бисимметрических булевых функций пяти переменных.
Устройство для вычисления бисимметрических булевых функций пяти переменных
содержит первый, второй, третий, четвертый и пятый элементы И, первый, второй и третий элементы СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, выход первого из которых соединен с
выходом устройства.
Первый настроечный вход устройства соединен с первым входом первого элемента
СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, второй вход которого соединен с выходом первого
элемента И, первый вход которого соединен со вторым настроечным входом устройства.
Третий настроечный вход устройства соединен с первым входом второго элемента И,
выход которого соединен с первым входом второго элемента СЛОЖЕНИЕ ПО МОДУЛЮ
ДВА, выход которого соединен с первым входом третьего элемента И.
Выход третьего элемента И соединен с третьим входом первого элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, четвертый вход которого соединен с выходом четвертого элемента И, первый вход которого соединен с выходом третьего элемента СЛОЖЕНИЕ ПО
МОДУЛЮ ДВА.
2
BY 16241 C1 2012.08.30
Первый вход третьего элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА соединен с выходом пятого элемента И, первый вход которого соединен с четвертым настроечным входом
устройства, пятый и шестой настроечные входы которого соединены со вторыми входами
второго и третьего элементов СЛОЖЕНИЕ ПО МОДУЛЮ ДВА соответственно.
Устройство содержит также первый, второй, третий элементы ИЛИ и четвертый элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, выход которого соединен со вторым входом третьего элемента И, а i-й вход, где i = 1, 2, соединен с (i + 1)-м входом четвертого элемента
И и с i-м информационным входом устройства.
Причем (i + 2)-й информационный вход устройства соединен с (i + 1)-м входом первого, второго и пятого элементов И и с i-м входом первого, второго и третьего элементов
ИЛИ, третьи входы которых соединены соответственно с седьмым, восьмым и девятым
настроечными входами устройства.
Названный технический результат достигается с помощью введения в логическую
схему устройства новых логических элементов (элементов ИЛИ) и путем изменения соединений между элементами схемы.
На фигуре представлена логическая схема устройства для вычисления бисимметрических булевых функций пяти переменных.
Устройство для вычисления бисимметрических булевых функций содержит пять элементов И 1...5, три элемента ИЛИ 6, 7 и 8, четыре элемента СЛОЖЕНИЕ ПО МОДУЛЮ
ДВА 9...12, четыре информационных входа 13...16, девять настроечных входов 17...25 и
выход 26.
Устройство для вычисления бисимметрических булевых функций пяти переменных
работает следующим образом. На информационные входы устройства 13, 14, 15 и 16 поступают значения переменных x1, x2, x3, x4 соответственно, на настроечные входы 17…25 сигналы настройки u0, u1, … , u8, значения которых принадлежат множеству
0, 1, x 5 , x 5 . На выходе устройства 26 вычисляется (реализуется) бисимметрическая булева функция F = F(X1, X2), где X1 = {x1, x2} и X2 = {x3, x4, x5}, определяемая вектором
настройки u(F) = (u0, u1, … , u8).
Поясним принцип построения и работы устройства для вычисления бисимметрических булевых функций пяти переменных.
Произвольная симметрическая булева функция n переменных F = F(x1, x2, …, xn) характеризуется множеством рабочих чисел A(F) = {a1, a2, …, ar}. Функция F принимает
единичные значения на тех и только тех наборах значений переменных x1, x2, …, xn, которые содержат ровно ai единиц, где 0 ≤ ai ≤ n, 0 ≤ i ≤r и 0 ≤ r ≤n + 1. Такая функция F обозначается как F = Fna1 ,a 2 ,K,a r (X), где X = {x1, x2, … , xn}.
Если 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) разбивает (единственным образом) множество переменных 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 = {x1, x2} и X2 = {x3,
x4, x5}, имеет место формула:
F(X1 , X 2 ) = F20 (X1 ) ⋅ G 0 (X 2 ) ∨ F21 (X1 ) ⋅ G l (X 2 ) ∨ F22 (X1 ) ⋅ G 2 (X 2 ) или
{
}
3
BY 16241 C1 2012.08.30
F(X1 , X 2 ) = F20 (X1 ) ⋅ G 0 (X 2 ) ⊕ F21 (X1 ) ⋅ G l (X2 ) ⊕ F22 (X1 ) ⋅ G 2 (X2 ) ,
(1)
где F ( x1 , x 2 ) = x1 ⋅ x 2 , F ( x1 , x 2 ) = x1x 2 ∨ x1 x 2 и F ( x1 , x 2 ) = x1x 2 .
В формуле (1) булевы функции G0 = G0 (x3, x4, x5), G1 = G1 (x3, x4, x5), G2 = G2 (x3, x4,
x5) являются симметрическими, каждая из которых задается посредством четырехразрядного двоичного вектора π(G k ) = (g 0k , g1k , g k2 , g 3k ) , где k = 0, 1, 2.
0
2
1
2
2
2
Если в формуле (1) заменить x1 = x1 ⊕ 1 и x 2 = x 2 ⊕ 1 , то после несложных преобразований получим:
F(X1 , X 2 ) = H0 (X2 ) ⊕ (x1 ⊕ x 2 ) ⋅ Hl (X2 ) ⊕ x1x 2 ⋅ H2 (X2 ) ,
(2)
где симметрические булевы функции H0(X2), H1(X2) и H2(X2) вычисляются по формулам
H0(X2) = G0(X2), H1 (X 2 ) = G 0 (X 2 ) ⊕ G l (X 2 ) и H 2 (X 2 ) = G 0 (X 2 ) ⊕ G 2 (X 2 ) .
Следовательно, значения компонент двоичных векторов π(G k ) = (g 0k , g1k , g k2 , g 3k ) и
π(H k ) = (h 0k , h1k , h k2 , h 3k ) связаны между собой следующими соотношениями (k = 0, 1, 2):
h i0 = g10 , h1i = g i0 ⊕ g1i , h i2 = g i0 ⊕ gi2 ,
(3)
где i = 0, 1, 2, 3.
Поясним метод построения вектора настройки u(F) = (u0, u1, … , u8) устройства (фигура) на вычисление произвольно заданной бисимметрической булевой функции
F = F(X1, X2).
1. Первоначально воспользуемся представлением функции F = F(Xl, X2) посредством
формулы (1) и вычислим значения компонент векторов π(G k ) = (g 0k , g1k , g k2 , g 3k ) для симметрических булевых функций Gk = Gk(x3, x4, x5), где k = 0, 1, 2.
2. Затем по формулам (3) определим значения компонент двоичных векторов
π(H k ) = (h 0k , h1k , h k2 , h 3k ) для симметрических булевых функций Hk = Hk(x3, x4, x5), входящих в представление функции F = F(Xl, X2) посредством формулы (2), где k = 0, 1, 2.
3. С целью построения вектора настройки u(F) = (u0, u1, … , u8) для каждого из векторов π(H 0 ) = (h 00 , h10 , h 02 , h 30 ) , π(H1 ) = (h10 , h11 , h12 , h13 ) и π(H 2 ) = (h 02 , h12 , h 22 , h 32 ) посредством
таблицы настроек (таблица) вычислим значения векторов (u0, u1, u2), (u3, u4, u5) и (u6, u7, u8).
Первообразная функция заявляемого устройства для вычисления бисимметрических
булевых функций пяти переменных (фигура) имеет вид:
F( x1 , x 2 , x 3 , x 4 , u 0 , u1 ,K, u 8 ) = x 3 x 4 u 0 ⊕ ( x 3 ∨ x 4 ∨ u1 ) ⊕ u 2 ⊕
⊕ ( x1 ⊕ x 2 ) ⋅ ( x 3 x 4 u 3 ⊕ ( x 3 ∨ x 4 ∨ u 4 ) ⊕ u 5 ⊕
(4)
⊕ x1x 2 ⋅ ( x 3 x 4 u 6 ⊕ ( x 3 ∨ x 4 ∨ u 7 ) ⊕ u 8 ).
Рассмотрим два примера построения вектора настройки u(F) = (u0, u1, … , u8) устройства для вычисления (реализации) бисимметрических булевых функций F = F(X1, X2).
Пример 1
Предположим, что на выходе 26 устройства требуется вычислить бисимметрическую
булеву функцию
F(X1 , X 2 ) = x1 ⋅ x 2 ⋅ ( x 3 ∨ x 4 ∨ x 5 ) ∨ x1x 2 x 3 x 4 x 5 .
Так как формула (1), применительно к данной функции, принимает вид
F(X1 , X 2 ) = F20 (X1 ) ⋅ G 0 (X 2 ) ∨ F21 (X1 ) ⋅ G l (X 2 ) ∨ F22 (X1 ) ⋅ G 2 (X 2 ) =
= F20 (X1 ) ⋅ G 0 (X2 ) ⊕ F21 (X1 ) ⋅ G l (X2 ) ⊕ F22 (X1 ) ⋅ G 2 (X2 ) =
= x1 ⋅ x 2 ⋅ ( x 3 ∨ x 4 ∨ x 5 ) ⊕ ( x1 x 2 ∨ x1 x 2 ) ⋅ 0 ⊕ x1 x 2 ⋅ ( x 3 x 4 x 5 ) ,
то π(G 0 ) = (0, 1, 1, 1) , π(G1 ) = (0, 0, 0, 0) , π(G 2 ) = (0, 0, 0, 1) .
Если представить функцию F = F(X1, X2) формулой (2), то
F(X1 , X 2 ) = H 0 (X2 ) ⊕ (x1 ⊕ x 2 ) ⋅ H l (X2 ) ⊕ x1x 2 ⋅ H 2 (X2 ) ,
4
BY 16241 C1 2012.08.30
где
π(H 0 ) = π(G 0 ) = (0, 1,1, 1),
π(H1 ) = π(G 0 ) ⊕ π(G1 ) = (0, 1, 1, 1) ⊕ (0, 0, 0, 0) = (0, 1, 1, 1) и
π(H 2 ) = π(G 0 ) ⊕ π(G 2 ) = (0, 1, 1, 1) ⊕ (0, 0, 0, 1) = (0, 1, 1, 0).
Если π(H 0 ) = (0, 1, 1, 1) , π(H1 ) = (0, 1,1, 1) и π(H 2 ) = (0, 1, 1, 0) , то из таблицы настроек
(таблица) получаем u0 = 0, u1 = x5, u2 = 0, u3 = 0, u4 = x5, u5 = 0, u6 = х5, u7 = x5 и u8 = 0.
Следовательно, для вычисления на выходе 26 устройства (фигура) бисимметрической
булевой функции
F(X1 , X 2 ) = x1 ⋅ x 2 ⋅ ( x 3 ∨ x 4 ∨ x 5 ) ∨ x1x 2 x 3 x 4 x 5
необходимо на настроечные входы 17, 19, 20, 22 и 25 подать значение "0", а на настроечные входы 18, 21, 23 и 24 - значение x5.
В качестве проверки в формуле (4) положим u0 = u2 = u3 = u5 = u8 = 0 и
u1 = u4 = u6 = u7 = x5. Тогда первообразная функция (4) заявляемого устройства будет
иметь вид
F( x1 , x 2 , x 3 , x 4 , x 5 ) = x 3 x 4 ⋅ 0 ⊕ ( x 3 ∨ x 4 ∨ x 5 ) ⊕ 0 ⊕
⊕ ( x1 ⊕ x 2 ) ⋅ ( x 3x 4 ⋅ 0 ⊕ ( x 3 ∨ x 4 ∨ x 5 ) ⊕ 0) ⊕
⊕ x1x 2 ⋅ ( x 3 x 4 x 5 ⊕ ( x 3 ∨ x 4 ∨ x 5 ) ⊕ 0) =
= (1 ⊕ x1 ⊕ x 2 ⊕ x1x 2 ) ⋅ ( x 3 ∨ x 4 ∨ x 5 ) ⊕ x1x 2 x 3 x 4 x 5 =
= x1 ⋅ x 2 ⋅ ( x 3 ∨ x 4 ∨ x 5 ) ⊕ x1x 2 x 3 x 4 x 5 = x1 ⋅ x 2 ⋅ ( x 3 ∨ x 4 ∨ x 5 ) ∨ x1 x 2 x 3 x 4 x 5
Пример 2
Пусть на выходе 26 устройства требуется вычислить бисимметрическую булеву функцию F(X1 , X 2 ) = x1x 2 ⊕ x 3 x 4 x 5 .
Так как
F(X1 , X 2 ) = ( x1 ∨ x 2 ) ⋅ x 3 x 4 x 5 ∨ x1x 2 ⋅ ( x 3 ∨ x 4 ∨ x 5 ) =
= x1 ⋅ x 2 ⋅ x 3 x 4 x 5 ∨ ( x1x 2 ∨ x1 x 2 ) ⋅ x 3 x 4 x 5 ∨ x1x 2 ⋅ ( x 3 ∨ x 4 ∨ x 5 ) =
= F20 (X1 ) ⋅ G 0 (X 2 ) ⊕ F21 (X1 ) ⋅ G l (X 2 ) ⊕ F22 (X1 ) ⋅ G 2 (X 2 ),
то π(G 0 ) = (0, 0, 0, 1) , π(G1 ) = (0, 0, 0, 1) , π(G 2 ) = (1, 1, 1, 0).
Если представить функцию F = F(X1, X2) формулой (2), то
F(X1 , X 2 ) = H 0 (X2 ) ⊕ (x1 ⊕ x 2 ) ⋅ H l (X2 ) ⊕ x1x 2 ⋅ H 2 (X2 ),
где
π(H 0 ) = π(G 0 ) = (0, 0, 0, 1),
π(H1 ) = π(G 0 ) ⊕ π(G1 ) = (0, 0, 0, 1) ⊕ (0, 0, 0, 1) = (0, 0, 0, 0) и
π(H 2 ) = π(G 0 ) ⊕ π(G 2 ) = (0, 0, 0, 1) ⊕ (1, 1, 1, 0) = (1, 1, 1, 1).
Если π(H 0 ) = (0, 0, 0, 1) , π(H1 ) = (0, 0, 0, 0) и π(H 2 ) = (1, 1, 1, 1) , то из таблицы настроек
(таблица) получаем u0 = x5, u1 = 1, u2 = 1, u3 = 0, u4 = 1, u5 = 1, u6 = 0, u7 = 1 и u8 = 0.
Значит, для вычисления на выходе 26 устройства булевой функции
F(X1 , X 2 ) = x1x 2 ⊕ x 3 x 4 x 5 необходимо на настроечный вход 17 подать значение x5, на
настроечные входы 18, 19, 21, 22 и 24 - значение "1", на настроечные входы 20, 23 и 25 значение "0".
Если u0 = 5, u1 = u2 = u4 = u5 = u7 = 1 и u3 = u6 = u8 = 0, то первообразная функция (4)
принимает вид:
5
BY 16241 C1 2012.08.30
F( x1 , x 2 , x 3 , x 4 , x 5 ) = x 3 x 4 x 5 ⊕ ( x 3 ∨ x 4 ∨ 1) ⊕ 1 ⊕
⊕ ( x1 ⊕ x 2 ) ⋅ ( x 3 x 4 ⋅ 0 ⊕ ( x 3 ∨ x 4 ∨ 1) ⊕ 1) ⊕
⊕ x1x 2 ⋅ ( x 3 x 4 ⋅ 0 ⊕ ( x 3 ∨ x 4 ∨ 1) ⊕ 0) = x1x 2 ⊕ x 3 x 4 x 5 .
Основным достоинством заявляемого устройства для вычисления бисимметрических
булевых функций пяти переменных является небольшое число внешних выводов, равное
14 (четыре информационных и девять настроечных входов, выход), в то время как устройство-прототип имеет 16 внешних выводов (три информационных и двенадцать настроечных входов, выход).
Дополнительным достоинством устройства для вычисления бисимметрических булевых функций пяти переменных является относительно небольшая конструктивная сложность (по числу входов логических элементов), равная 36. При этом сложность
устройства-прототипа равна 33.
Двоичный код симметрической булевой
функции Hk = Hk(x3, x4, x5)
π(H k ) = (h 0k , h1k , h k2 , h 3k )
0000
0001
0010
Вектор настройки u(F) = (u0, u1, … , u8)
u3k
0
х5
1
u3k+1
1
1
x5
u3k+2
1
1
x5
0011
x5
x5
x5
0100
0101
0110
0111
1000
1001
1010
x5
1
х5
0
0
x5
1
0
0
х5
х5
х5
х5
0
х5
x5
0
0
1
1
x5
1011
x5
0
x5
1100
x5
x5
x5
1101
1110
1111
1
х5
0
x5
1
1
х5
0
0
Источники информации:
1. Патент РБ 11275, МПК G 06F 7/00, 2008.
2. Заявка на Патент РБ а20090420, МПК G 06F 7/00, 2009 (прототип).
Национальный центр интеллектуальной собственности.
220034, г. Минск, ул. Козлова, 20.
6
Документ
Категория
Без категории
Просмотров
0
Размер файла
112 Кб
Теги
патент, by16241
1/--страниц
Пожаловаться на содержимое документа