close

Вход

Забыли?

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

?

Патент BY13248

код для вставкиСкачать
ОПИСАНИЕ
ИЗОБРЕТЕНИЯ
К ПАТЕНТУ
РЕСПУБЛИКА БЕЛАРУСЬ
(46) 2010.06.30
(12)
(51) МПК (2009)
НАЦИОНАЛЬНЫЙ ЦЕНТР
ИНТЕЛЛЕКТУАЛЬНОЙ
СОБСТВЕННОСТИ
(54)
BY (11) 13248
(13) C1
(19)
G 06F 7/00
УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ ПОЛИНОМИАЛЬНЫХ
СИММЕТРИЧЕСКИХ БУЛЕВЫХ ФУНКЦИЙ
(21) Номер заявки: a 20081526
(22) 2008.12.02
(43) 2009.06.30
(71) Заявитель: Белорусский государственный университет (BY)
(72) Автор: Супрун Валерий Павлович
(BY)
(73) Патентообладатель: Белорусский государственный университет (BY)
(56) BY 11028 C1, 2008.
BY 11024 C1, 2008.
BY 11027 C1, 2008.
BY 10219 C1, 2008.
RU 2047892 C1, 1995.
SU 1765818 A1, 1992.
BY 13248 C1 2010.06.30
(57)
Устройство для вычисления полиномиальных симметрических булевых функций, содержащее элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с
порогом четыре и элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом пять, i-й (i = 1, 2,…,6) вход
которого соединен с i-м информационным входом устройства и с i-м входом элемента
ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре, выход которого соединен с первым входом
элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, выход которого соединен с выходом устройства, а второй вход соединен с выходом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом
BY 13248 C1 2010.06.30
пять, седьмой и восьмой входы которого соединены с первым настроечным входом устройства, второй настроечный вход которого соединен с седьмым входом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре, восьмой и девятый входы которого соединены с
третьим настроечным входом устройства, отличающееся тем, что содержит элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом восемь и элемент И, j-й (j = 1, 2,…,7) вход которого соединен с j-м информационным входом устройства и с j-м входом элемента
ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом восемь, восьмой вход которого соединен с четвертым
настроечным входом устройства, пятый настроечный вход которого соединен с девятым и
десятым входами элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом восемь, выход которого
соединен с третьим входом элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, четвертый вход
которого соединен с выходом элемента И, а седьмой информационный вход устройства
соединен с десятым входом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре и с девятым входом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом пять.
Изобретение относится к области вычислительной техники и микроэлектроники и
предназначено для вычисления полиномиальных симметрических булевых функций семи
переменных.
Известно устройство для вычисления фундаментальных симметрических булевых
функций семи переменных, содержащее элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом три,
девять настроечных входов и выход [1].
Конструктивная сложность устройства (по числу входов логических элементов) равна
10, а его быстродействие, определяемое глубиной схемы, составляет τ, где τ - усредненная
задержка на один логический элемент.
Недостатком известного устройства являются низкие функциональные возможности,
поскольку устройство не позволяет вычислять полиномиальные симметрические булевы
функции семи переменных. Устройство, предназначенное для вычисления фундаментальных симметрических булевых функций семи переменных, как и предлагаемое устройство,
содержит элемент ИСКЛЮЧАЮЩЕЕ ИЛИ, только выполненное с порогом три.
Наиболее близким по функциональным возможностям и конструкции техническим
решением к предлагаемому является устройство для вычисления полиномиальных симметрических булевых функций шести переменных, которое содержит элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом пять,
элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом шесть, элемент СЛОЖЕНИЕ ПО МОДУЛЮ
ДВА, шесть информационных входов, четыре настроечных входа и выход [2]. Конструктивная сложность устройства (по числу входов логических элементов) равна 27, а быстродействие составляет 2τ, где τ - задержка на один логический элемент.
Недостатком устройства-прототипа являются низкие функциональные возможности,
так как это устройство не позволяет вычислять полиномиальные симметрические булевы
функции семи переменных. Как и предлагаемое изобретение, устройство-прототип содержит элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре, элемент ИСКЛЮЧАЮЩЕЕ
ИЛИ с порогом пять и элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, выход которого соединен с выходом устройства.
Изобретение направлено на решение технической задачи расширения функциональных возможностей устройства за счет реализации (вычисления) полиномиальных симметрических булевых функций семи переменных.
Устройство для вычисления полиномиальных симметрических булевых функций содержит элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с
порогом четыре и элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом пять, i-й (i = 1, 2,..., 6) вход
2
BY 13248 C1 2010.06.30
которого соединен с i-м информационным входом устройства и с i-м входом элемента
ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре.
Выход элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре соединен с первым входом элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, выход которого соединен с выходом устройства, а второй вход соединен с выходом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом
пять, седьмой и восьмой входы которого соединены с первым настроечным входом устройства.
Второй настроечный вход устройства соединен с седьмым входом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре, восьмой и девятый входы которого соединены с
третьим настроечным входом устройства.
В отличие от прототипа устройство содержит элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом восемь и элемент И, j-й (j = 1, 2,..., 7) вход которого соединен с j-м информационным входом устройства и с j-м входом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом
восемь.
Восьмой вход элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом восемь соединен с четвертым настроечным входом устройства, пятый настроечный вход которого соединен с девятым и десятым входами элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом восемь, выход
которого соединен с третьим входом элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, четвертый вход которого соединен с выходом элемента И.
Седьмой информационный вход устройства соединен с десятым входом элемента
ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре и с девятым входом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом пять.
Названный технический результат достигается путем использования новых логических элементов (элемента И и элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом восемь).
На чертеже (фигура) представлена логическая схема устройства для вычисления полиномиальных симметрических булевых функций семи переменных.
Устройство для вычисления полиномиальных симметрических булевых функций содержит элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре 1, элемент ИСКЛЮЧАЮЩЕЕ
ИЛИ с порогом пять 2, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом восемь 3, элемент И 4,
элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА 5, семь информационных входов 6…12, пять
настроечных входов 13…17 и выход 18.
Устройство для вычисления полиномиальных симметрических булевых функций семи
переменных работает следующим образом. На информационные входы устройства 6…12
поступают (в произвольном порядке) значения переменных xl, x2,…, x7, а на настроечные
входы 13…17 - сигналы настройки u1, u2,..., u5. На выходе устройства 18 реализуется (вычисляется) полиномиальная симметрическая булева функция E 7k = E 7k ( x1, x 2 ,K, x 7 ) , определяемая вектором настройки U = (u1, u2, …, u5), где = 1, 2, …, 7.
Поясним принцип построения и работы устройства для вычисления полиномиальных
симметрических булевых функций семи переменных.
Известно, что произвольная симметрическая булева функция n переменных F = F(xl,
x2, …, xn) с рабочими числами al, a2, …, ar (0 ≤ r ≤ n) принимает значение 1 на тех и только
тех наборах значений переменных Х = {х1, х2, …, xn}, которые содержат ровно аj (j = 1, 2,
a , a 2 ,K, a r
…, r) единиц. Такая булева функция обозначается через F = Fn 1
( x1, x 2 ,K, x n ) . Если
r = 1, то симметрическая булева функция F = Fna ( x1, x 2 ,K, x n ) называется фундаментальной (или элементарной).
a , a ,K, a
r
Симметрическая булева функция n переменных F = Fn 1 2
(X) называется полиномиальной, если ее полином Жегалкина содержит только всевозможные элементарные
конъюнкции, ранг которых равен k, где k = 1, 2,…, n. Такая полиномиальная симметриче-
3
BY 13248 C1 2010.06.30
ская булева функция n переменных обозначается через F = E kn (X) . Очевидно, что полином
Жегалкина функции F = E kn (X) содержит C kn ("число сочетаний из n по k") элементарных
конъюнкций ранга k, где k = 1, 2,..., n.
Предлагаемое устройство (фигура) синтезировано на основе применения следующих
аналитических представлений полиномиальных симметрических булевых функций семи
переменных:
E17 (X) = F71 (X) ∨ F73 (X) ∨ F75 (X) ∨ F77 (X),
E 72 (X) = F72 (X) ∨ F73 (X) ∨ F76 (X) ∨ F77 (X),
E 37 (X) = F73 (X) ∨ F77 (X), E 74 (X) = F74 (X) ∨ F75 (X) ∨ F76 (X) ∨ F77 (X),
E 57 (X) = F75 (X) ∨ F77 (X), E 67 (X) = F76 (X) ∨ F77 (X), E 77 (X) = F77 (X).
Отметим, что в приведенных выше формулах логическую операцию "дизъюнкция"
можно заменить логической операцией "сложение по модулю два".
Первообразная функция устройства имеет вид
4
F( x1, x 2 ,K, x 7 , u1, u 2 ,K, u 5 ) = F10
( x1, x 2 ,K, x 7 , u1, u 2 , u 2 ) ⊕
8
⊕ F95 ( x1, x 2 ,K, x 7 , u 3 , u 3 ) ⊕ F10
( x1, x 2 ,K, x 7 , u 4 , u 5 , u 5 ) ⊕ F77 ( x1, x 2 ,K, x 7 ).
В таблице приведен способ настройки устройства на вычисление полиномиальной
симметрической булевой функции E 7k (X) = E 7k ( x1, x 2 ,K, x 7 ) , где k = 1, 2,…, 7.
Рассмотрим пример. Допустим, на выходе 18 устройства требуется реализовать полиномиальную симметрическую булеву функцию E 37 (X) = E37 ( x1, x 2 ,K, x 7 ) . Тогда, согласно
таблице настроек (таблица), необходимо на настроечные входы 13…17 подать значения
1,0,0,1,1 соответственно. В таком случае первообразная функция устройства принимает
вид
F( x1 , x 2 ,K, x 7 , 1,0,0,1,1) = F104 ( x1 , x 2 ,K, x 7 , 1,0,0) ⊕
⊕ F95 ( x1 , x 2 ,K, x 7 , 0,0) ⊕ F108 ( x1 , x 2 ,K, x 7 , 1,1,1) ⊕ F77 ( x1 , x 2 ,K, x 7 ) =
= F73 ( x1 , x 2 ,K, x 7 ) ⊕ F75 ( x1 , x 2 ,K, x 7 ) ⊕ F75 ( x1 , x 2 ,K, x 7 ) ⊕ F77 ( x1 , x 2 ,K, x 7 ) =
= F73 ( x1 , x 2 ,K, x 7 ) ⊕ F77 ( x1 , x 2 ,K, x 7 ) = E 37 ( x1 , x 2 ,K, x 7 ).
Дополнительными достоинствами устройства для вычисления полиномиальных симметрических булевых функций семи переменных являются: 1) небольшая конструктивная
сложность, которая (по числу входов логических элементов) равна 40; 2) высокое быстродействие, которое составляет 2τ, где τ - задержка на логический элемент; 3) небольшое
число внешних выводов (7 информационных и 5 настроечных входов, а также один выход).
Источники информации:
1. Патент РБ 10549, МПК G 06F 7/00, 2008.
2. Патент РБ 11028, МПК G 06F 7/00, 2008 (прототип).
4
BY 13248 C1 2010.06.30
u1
13
1
Сигналы настройки
u2
u3
u4
14
15
16
1
1
1
u5
17
1
0
1
1
0
1
E 72
1
0
0
1
1
E37
0
0
0
0
1
E 74
1
0
1
1
1
E57
1
0
1
0
1
E 67
1
0
1
0
0
E 77
Национальный центр интеллектуальной собственности.
220034, г. Минск, ул. Козлова, 20.
5
Реализуемая функция
F
18
E17
Документ
Категория
Без категории
Просмотров
0
Размер файла
225 Кб
Теги
by13248, патент
1/--страниц
Пожаловаться на содержимое документа