close

Вход

Забыли?

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

?

Патент BY 16715

код для вставкиСкачать
ОПИСАНИЕ
ИЗОБРЕТЕНИЯ
К ПАТЕНТУ
РЕСПУБЛИКА БЕЛАРУСЬ
(46) 2012.12.30
(12)
(51) МПК
НАЦИОНАЛЬНЫЙ ЦЕНТР
ИНТЕЛЛЕКТУАЛЬНОЙ
СОБСТВЕННОСТИ
(54)
G 06F 7/00
(2006.01)
УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ ПОЛУСИММЕТРИЧЕСКИХ
БУЛЕВЫХ ФУНКЦИЙ ПЯТИ ПЕРЕМЕННЫХ
(21) Номер заявки: a 20110361
(22) 2011.03.23
(43) 2011.08.30
(71) Заявитель: Белорусский государственный университет (BY)
(72) Автор: Супрун Валерий Павлович
(BY)
BY 16715 C1 2012.12.30
BY (11) 16715
(13) C1
(19)
(73) Патентообладатель: Белорусский государственный университет (BY)
(56) BY a20101240, 2011.
BY a20101185, 2011.
BY 2793 C1, 1999.
RU 2047894 C1, 1995.
SU 1716502 A1, 1992.
(57)
Устройство для вычисления полусимметрических булевых функций пяти переменных,
характеризующееся тем, что содержит с первого по пятый элементы И, мажоритарный
элемент с порогом два, первый и второй элементы СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, выход первого из которых соединен с выходом устройства, первый настроечный вход которого соединен с первым входом первого элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА,
(i + 1)-й вход которого, где i = 1, 2, 3, 4, соединен с выходом i-го элемента И, первый вход
которого соединен с (i + 1)-м настроечным входом устройства, i-й информационный вход
которого соединен с i-м входом второго элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, i-м
входом мажоритарного элемента с порогом два и с i-м входом пятого элемента И, выход
которого соединен с инверсным входом второго элемента И и со вторым входом четвертого элемента И, выход мажоритарного элемента с порогом два соединен со вторым входом
второго элемента И и со вторым входом третьего элемента И, третий вход которого соединен с выходом второго элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА и со вторым входом первого элемента И.
BY 16715 C1 2012.12.30
Изобретение относится к области вычислительной техники и микроэлектроники и
предназначено для вычисления полусимметрических булевых функций пяти переменных.
Известно устройство для вычисления симметрических булевых функций пяти переменных, которое содержит элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом два, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом шесть, мажоритарный элемент с порогом три, элемент
СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, двенадцать настроечных входов и выход [1].
Известное устройство, как и изобретение, содержит элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, выход которого соединен с выходом устройства, первый настроечный вход
которого соединен с первым входом элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА.
Недостатком известного устройства являются ограниченные функциональные возможности, поскольку устройство не позволяет вычислять полусимметрические булевы
функции пяти переменных.
Наиболее близким по функциональным возможностям и конструкции техническим
решением к заявляемому устройству является устройство для вычисления полусимметрических булевых функций пяти переменных, которое содержит одиннадцать элементов И,
элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, четыре информационных и восемь настроечных входов, выход [2].
Устройство-прототип предназначено для вычисления полусимметрических булевых
функций пяти переменных F = F(X1, x5), где X1 = {x1, x2, x3, x4}. Конструктивная сложность устройства (по числу входов логических элементов) равна 47, а быстродействие составляет 2τ, где τ - задержка на один логический элемент.
Устройство-прототип, как и предлагаемое устройство, содержит с первого по четвертый элементы И и элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, выход которого соединен с
выходом устройства, а первый вход - с первым настроечным входом устройства, (i + 1)-й
настроечный вход которого, где i = 1, 2, 3, 4, соединен с первым входом i-го элемента И,
выход которого соединен с (i + 1)-м входом элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА.
Недостатком устройства-прототипа является высокая конструктивная сложность, равная 47.
Изобретение направлено на решение следующей технической задачи: уменьшение
конструктивной сложности устройства для вычисления полусимметрических булевых
функций пяти переменных.
Устройство для вычисления полусимметрических булевых функций пяти переменных
характеризуется тем, что содержит с первого по пятый элементы И, мажоритарный элемент с порогом два, первый и второй элементы СЛОЖЕНИЕ ПО МОДУЛЮ ДВА.
Выход первого элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА соединен с выходом
устройства, первый настроечный вход которого соединен с первым входом первого элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, (i + 1)-й вход которого, где i = 1, 2, 3, 4, соединен
с выходом i-го элемента И, первый вход которого соединен с (i + 1)-м настроечным входом устройства.
Причем i-й информационный вход устройства соединен с i-м входом второго элемента
СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, с i-м входом мажоритарного элемента с порогом два и
с i-м входом пятого элемента И.
Выход пятого элемента И соединен с инверсным входом второго элемента И и со вторым входом четвертого элемента И.
Выход мажоритарного элемента с порогом два соединен со вторым входом второго
элемента И и со вторым входом третьего элемента И.
Третий вход третьего элемента И соединен с выходом второго элемента СЛОЖЕНИЕ
ПО МОДУЛЮ ДВА и со вторым входом первого элемента И.
Названный технический результат достигается посредством введения в логическую
схему устройства мажоритарного элемента с порогом два и второго элемента СЛОЖЕ-
2
BY 16715 C1 2012.12.30
НИЕ ПО МОДУЛЮ ДВА с последующим изменением соединений между логическими
элементами схемы.
На фигуре представлена логическая схема устройства для вычисления полусимметрических булевых функций пяти переменных.
Устройство для вычисления полусимметрических булевых функций пяти переменных
содержит два элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА 1 и 2, мажоритарный элемент с
порогом два 3, пять элементов И 4...8, четыре информационных входа 9, 10, 11 и 12, пять
настроечных входов 13...17, выход 18.
Устройство для вычисления полусимметрических булевых функций пяти переменных
работает следующим образом. На информационные входы 9, 10, 11 и 12 устройства поступают (в произвольном порядке) значения переменных x1, x2, x3 и x4, на настроечные
входы 13...17 - сигналы настройки u0, u1, u2, u3, u4, значения которых принадлежат множеству {0, 1, x 5 , x 5 } . На выходе 18 устройства вычисляется (реализуется) полусимметрическая булева функция F= F(X1, x5), где X1 = {x1, x2, x3, x4}, определяемая вектором
настройки u(F) = (u0, u1, u2, u3, u4).
Поясним принцип построения и работы устройства для вычисления полусимметрических булевых функций пяти переменных.
Произвольная булева функция n переменных F = F(x1, x2,..., xn) называется симметрической, если она не меняет своего значения после перестановки любой пары переменных
xi и xj, где i ≠ j и i, j = 1, 2,..., n.
Симметрическая булева функция F = F(x1, x2,..., xn) определяется множеством рабочих
чисел A(F) = {a1, a2,..., ar}. Функция F принимает единичные значения на тех и только тех
наборах значений переменных xl, x2,..., xn, которые содержат ровно ai единиц, где
0 ≤ ai ≤ n, 1 ≤ i ≤ r и 0 ≤ r ≤ n + 1. Такая функция обозначается как F = Fna 1 , a 2 ,K, a r (x l , x 2 ,..., x n ) .
Если r = 1, то функция F = Fna (x1 , x 2 ,..., x n ) называется фундаментальной (элементарной) симметрической булевой функцией n переменных с рабочим числом, равным a.
Симметрическая булева функция 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(x1, x2,..., xn) называется полусимметрической, если булевы функции F0 = F(xn = 0) и F1 = F(xn = 1) являются симметрическими, зависящими
от переменных Xl = {x1, x2,..., xn-1}, где n ≥ 3. Такая булева функция обозначается как
F = F(X1, xn).
Формула дизъюнктивного разложения функции F(X) = F(X1, xn) по переменным множества X1 имеет вид
F(X1, x n ) = Fn0−1 (X1 ) ⋅ G 0 ( x n ) ∨ Fn1−1 (X1 ) ⋅ G1 ( x n ) ∨ ... ∨ Fnn−−11 (X1 ) ⋅ G n −1 ( x n ) ,
(1)
где Fni −1 = Fni −1 (X1 ) - фундаментальные симметрические булевы функции n-1 переменных, а
булевы функции Gi = Gi(xn) зависят только от одной переменной xn. Здесь i = 0, 1,..., n-1.
Двоичный 2n-разрядный вектор π(F) = (π(G0), π(G1),..., π(Gn-1)) называется локальным
кодом полусимметрической булевой функции F(X) = F(X1, xn).
Наряду с дизъюнктивным разложением (1) существует полиномиальное разложение
функции F(X) = F(X1, xn) по n-1 переменным вида
F(X1, x n ) = Fn0−1 (X1 ) ⋅ H 0 ( x n ) ⊕ E1n −1 (X1 ) ⋅ H1 ( x n ) ⊕ ... ⊕ E nn −−11 (X1 ) ⋅ H n −1 ( x n ) ,
(2)
где E in −1 = E in −1 (X1 ) - полиномиально-однородные симметрические булевы функции n-1
переменных и E 0n −1 (X1 ) = 1 , а функции Hi = Hi(xn) зависят от функций Gi = Gi(xn), где i = 0,
1,..., n-1, и вычисляются по формулам, приведенным в статье Супруна В.П. и Городецко-
3
BY 16715 C1 2012.12.30
го Д.А. Реализация бисимметрических булевых функций логическими схемами // Известия вузов. Приборостроение. - 2010. - № 5. - С. 17-25.
В частности, если n ≤ 8, то
H 0 (x n ) = G 0 (x n ), H1 (x n ) = G 0 ( x n ) ⊕ G1 ( x n ) ,
H 2 (x n ) = G 0 (x n ) ⊕ G 2 ( x n ) ,
H 3 (x n ) = G 0 (x n ) ⊕ G1 ( x n ) ⊕ G 2 ( x n ) ⊕ G 3 ( x n ) ,
H 4 (x n ) = G 0 (x n ) ⊕ G 4 ( x n ) ,
(3)
H 5 (x n ) = G 0 (x n ) ⊕ G1 ( x n ) ⊕ G 4 ( x n ) ⊕ G 5 ( x n ) ,
H 6 (x n ) = G 0 (x n ) ⊕ G 2 ( x n ) ⊕ G 4 ( x n ) ⊕ G 6 ( x n ) ,
H 7 (x n ) = G 0 (x n ) ⊕ G1 ( x n ) ⊕ G 2 ( x n ) ⊕ ... ⊕ G 7 ( x n ) .
Отметим, что локальные коды π(Hi) и π(Gi) булевых функций Hi = Нi(хn) и Gi = Gi(хn)
связаны между собой, согласно формулам (3), где i = 0, 1,..., 7.
Если n = 5, то формулы (1)-(3) принимают вид
F(X1 , x 5 ) = F40 (X1 ) ⋅ G 0 ( x 5 ) ∨ F41 (X1 ) ⋅ G1 ( x 5 ) ∨ F42 (X1 ) ⋅ G 2 ( x 5 ) ∨
∨ F43 (X1 ) ⋅ G 3 ( x 5 ) ∨ F44 (X1 ) ⋅ G 4 ( x 5 ),
F(X1 , x 5 ) = H 0 ( x 5 ) ⊕ E14 (X1 ) ⋅ H1 ( x 5 ) ⊕ E 24 (X1 ) ⋅ H 2 ( x 5 ) ⊕
(4)
⊕ E34 (X1 ) ⋅ H 3 ( x 5 ) ⊕ E 44 (X1 ) ⋅ H 4 ( x 5 ),
где π(H0) = π(G0), π(H1 ) = π(G 0 ) ⊕ π(G1 ) , π(H 2 ) = π(G 0 ) ⊕ π(G 2 ) ,
π(H3 ) = π(G 0 ) ⊕ π(G1 ) ⊕ π(G 2 ) ⊕ π(G 3 ) и π(H 4 ) = π(G 0 ) ⊕ π(G 4 ) .
Логическая схема устройства для вычисления полусимметрических булевых функций
пяти переменных, синтезированная на основе применения полиномиального разложения
(4), приведена на фигуре.
Первообразная функция устройства имеет вид
F( x1 , x 2 , x 3 , x 4 , u 0 , u1 , u 2 , u 3 , u 4 ) = u 0 ⊕ u1 ( x1 ⊕ x 2 ⊕ x 3 ⊕ x 4 ) ⊕
⊕ u 2 ( x1x 2 ⊕ x1x 3 ⊕ x1x 4 ⊕ x 2 x 3 ⊕ x 2 x 4 ⊕ x 3 x 4 ) ⊕
(5)
⊕ u 3 ( x1x 2 x 3 ⊕ x1x 2 x 4 ⊕ x1x 3 x 4 ⊕ x 2 x 3 x 4 ) ⊕ u 4 x1 x 2 x 3 x 4 .
Если обозначить π(Hi ) = (πi0 , π1i ) , то значения разрядов вектора настройки u(F) =
(u0, u1, u2, u3, u4) устройства на реализацию полусимметрической функции F(X) = F(X1, x5)
вычисляются по формуле
(6)
u i = πi0 ⋅ x 5 ∨ π1i ⋅ x 5 ,
где i = 0, 1, 2, 3, 4.
Рассмотрим пример вычисления (реализации) на выходе 18 устройства (фигура) заданной булевой функции F(X) = F(X1, x5).
Допустим, что на выходе 18 устройства требуется вычислить полусимметрическую
булеву функцию
F( x1 , x 2 , x 3 , x 4 , x 5 ) = x1 ⋅ x 2 ⋅ x 3 ⋅ x 4 ∨ x1 ⋅ x 2 ⋅ x 3 ⋅ x 4 ⋅ x 5 .
В таком случае формулы (4) принимают вид
F(X1, x 5 ) = F40 (X1 ) ⋅1 ∨ F41 (X1 ) ⋅ 0 ∨ F42 (X1 ) ⋅ 0 ∨ F43 (X1 ) ⋅ 0 ∨ F44 (X1 ) ⋅ x 5 ,
F(X1 , x 5 ) = H 0 ( x 5 ) ⊕ ( x1 ⊕ x 2 ⊕ x 3 ⊕ x 4 ) ⋅ H1 ( x 5 ) ⊕
⊕ ( x1x 2 ⊕ x1x 3 ⊕ x1x 4 ⊕ x 2 x 3 ⊕ x 2 x 4 ⊕ x 3 x 4 ) ⋅ H 2 ( x 5 ) ⊕
⊕ ( x1 x 2 x 3 ⊕ x1x 2 x 4 ⊕ x1x 3 x 4 ⊕ x 2 x 3 x 4 ) ⋅ H 3 ( x 5 ) ⊕ x1x 2 x 3 x 4 ⋅ H 4 ( x 5 )
и
4
BY 16715 C1 2012.12.30
π(G0) = (1, 1), π(G1) = π(G2) = π(G3) = (0, 0), π(G4) = (1, 0),
π(H0) = π(G0) = (1, 1), π(H1 ) = π(G 0 ) ⊕ π(G1 ) = (1, 1) ,
π(H 2 ) = π(G 0 ) ⊕ π(G 2 ) = (1,1) , π(H3 ) = π(G 0 ) ⊕ π(G1 ) ⊕ π(G 2 ) ⊕ π(G 3 ) = (1,1) ,
π(H 4 ) = π(G 0 ) ⊕ π(G 4 ) = (0,1) .
Принимая во внимание формулу (6), получаем u0 = 1, u1 = 1, u2 = 1, u3 = 1 и u4 = x5.
Следовательно, для реализации на выходе 18 заявляемого устройства полусимметрической булевой функции
F( x1 , x 2 , x 3 , x 4 , x 5 ) = x1 ⋅ x 2 ⋅ x 3 ⋅ x 4 ∨ x1 ⋅ x 2 ⋅ x 3 ⋅ x 4 ⋅ x 5
необходимо на его настроечные входы 13...17 подать значения компонент вектора
настройки u(F) = (1, 1, 1, 1, x5).
Для проверки правильности функционирования устройства подставим в выражение
(5) значения вектора u(F) = (1, 1, 1, 1, x5). Тогда
F( x1 , x 2 , x 3 , x 4 ,1, 1, 1, 1, x 5 ) = 1 ⊕ 1 ⋅ ( x1 ⊕ x 2 ⊕ x 3 ⊕ x 4 ) ⊕
⊕ 1 ⋅ ( x1x 2 ⊕ x1x 3 ⊕ x1x 4 ⊕ x 2 x 3 ⊕ x 2 x 4 ⊕ x 3 x 4 ) ⊕
⊕ 1 ⋅ ( x1x 2 x 3 ⊕ x1x 2 x 4 ⊕ x1x 3 x 4 ⊕ x 2 x 3 x 4 ) ⊕ x1x 2 x 3 x 4 x 5 =
= 1 ⊕ x1 ⊕ x 2 ⊕ x 3 ⊕ x 4 ⊕ x1x 2 ⊕ x1x 3 ⊕ x1x 4 ⊕ x 2 x 3 ⊕ x 2 x 4 ⊕ x 3 x 4 ⊕
⊕ x1x 2 x 3 ⊕ x1x 2 x 4 ⊕ x1x 3 x 4 ⊕ x 2 x 3 x 4 ⊕ x1x 2 x 3 x 4 ⊕ x1x 2 x 3 x 4 x 5 =
= x1 ⋅ x 2 ⋅ x 3 ⋅ x 4 ⊕ x1x 2 x 3 x 4 x 5 = x1 ⋅ x 2 ⋅ x 3 ⋅ x 4 ∨ x1x 2 x 3 x 4 x 5 .
Основным достоинством заявляемого устройства является низкая конструктивная
сложность, равная 27 (сложность устройства-прототипа равна 47).
Кроме того, устройство имеет всего 10 внешних выводов (четыре информационных и
пять настроечных входов, выход). Устройство-прототип имеет 13 внешних выводов (четыре информационных и восемь настроечных входов, выход).
Источники информации:
1. Патент РБ 11275, МПК G 06F 7/00, 2008.
2. Заявка на Патент РБ 20101240, МПК G 06F 7/00, 2011 (прототип).
Национальный центр интеллектуальной собственности.
220034, г. Минск, ул. Козлова, 20.
5
Документ
Категория
Без категории
Просмотров
0
Размер файла
151 Кб
Теги
16715, патент
1/--страниц
Пожаловаться на содержимое документа