close

Вход

Забыли?

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

?

Патент BY13969

код для вставкиСкачать
ОПИСАНИЕ
ИЗОБРЕТЕНИЯ
К ПАТЕНТУ
РЕСПУБЛИКА БЕЛАРУСЬ
(46) 2011.02.28
(12)
(51) МПК (2009)
НАЦИОНАЛЬНЫЙ ЦЕНТР
ИНТЕЛЛЕКТУАЛЬНОЙ
СОБСТВЕННОСТИ
(54)
BY (11) 13969
(13) C1
(19)
G 06F 7/00
УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ ПОЛИНОМИАЛЬНЫХ
СИММЕТРИЧЕСКИХ БУЛЕВЫХ ФУНКЦИЙ
(21) Номер заявки: a 20090336
(22) 2009.03.10
(43) 2009.08.30
(71) Заявитель: Белорусский государственный университет (BY)
(72) Авторы: Супрун Валерий Павлович;
Городецкий Данила Андреевич (BY)
(73) Патентообладатель: Белорусский государственный университет (BY)
(56) BY 1587 C1, 1997.
BY 3031 C1, 1999.
BY 11024 C1, 2007.
BY 11028 C1, 2007.
BY 13969 C1 2011.02.28
(57)
Устройство для вычисления полиномиальных симметрических булевых функций десяти переменных, содержащее элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом пять,
BY 13969 C1 2011.02.28
элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом восемь, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с
порогом девять и элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом одиннадцать, выход которого соединен с первым входом элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, второй вход
которого соединен с выходом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом девять, третий
вход - с выходом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом восемь, четвертый вход - c
выходом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом пять и пятый вход - с выходом
элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре, а выход - с выходом устройства, i-й,
где i = 1, 2,…,10, информационный вход которого соединен с i-м входом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом одиннадцать, с i-м входом элемента ИСКЛЮЧАЮЩЕЕ
ИЛИ с порогом девять, с i-м входом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом восемь,
с i-м входом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом пять и с i-м входом элемента
ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре, одиннадцатый вход которого соединен с первым настроечным входом устройства, второй настроечный вход которого соединен с двенадцатым и тринадцатым входами элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре,
третий настроечный вход устройства соединен с одиннадцатым и двенадцатым входами
элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом пять, четвертый настроечный вход устройства соединен с одиннадцатым входом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом восемь, двенадцатый и тринадцатый входы которого соединены с пятым настроечным
входом устройства, шестой настроечный вход которого соединен с одиннадцатым и двенадцатым входами элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом девять, седьмой и восьмой настроечные входы устройства соединены с одиннадцатым и двенадцатым входами
элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом одиннадцать.
Изобретение относится к области вычислительной техники и микроэлектроники и
предназначено для вычисления полиномиальных симметрических булевых функций десяти переменных.
Известно устройство для вычисления симметрических булевых функций n переменных, которое при n = 10 содержит десять элементов НЕ и сто одиннадцать элементов
И-НЕ [1].
Недостатками известного устройства являются высокая конструктивная сложность (по
числу входов логических элементов), а также низкое быстродействие, определяемое глубиной схемы.
Наиболее близким по функциональным возможностям и конструкции техническим
решением к предлагаемому является устройство для вычисления фундаментальных симметрических булевых функций n переменных, содержащее при n = 10 три элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, элемент И, мажоритарный элемент с порогом восемь и
мажоритарный элемент с порогом десять [2].
Устройство-прототип, как и заявляемое устройство, содержит элемент СЛОЖЕНИЕ
ПО МОДУЛЮ ДВА.
Недостатком устройства-прототипа являются ограниченные функциональные возможности, поскольку устройство не позволяет вычислять полиномиальные симметрические булевы функции десяти переменных.
Изобретение направлено на решение технической задачи расширения функциональных возможностей устройства для вычисления фундаментальных симметрических функций за счет вычисления (реализации) полиномиальных симметрических булевых функций
десяти переменных.
Устройство для вычисления полиномиальных симметрических булевых функций содержит элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с
порогом четыре, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом пять, элемент ИСКЛЮЧА2
BY 13969 C1 2011.02.28
ЮЩЕЕ ИЛИ с порогом восемь, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом девять и элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом одиннадцать.
Выход элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом одиннадцать соединен с первым
входом элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА.
Второй вход элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА соединен с выходом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом девять.
Третий вход элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА соединен с выходом элемента
ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом восемь.
Четвертый вход элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА соединен с выходом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом пять.
Пятый вход элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА соединен с выходом элемента
ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре.
Выход элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА соединен с выходом устройства,
i-й, где i = 1, 2,...,10, информационный вход которого соединен с i-м входом элемента
ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом одиннадцать, с i-м входом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом девять, с i-м входом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом
восемь, с i-м входом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом пять и с i-м входом
элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре.
Одиннадцатый вход элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре соединен с
первым настроечным входом устройства.
Второй настроечный вход устройства соединен с двенадцатым и тринадцатым входами элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре.
Третий настроечный вход устройства соединен с одиннадцатым и двенадцатым входами элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом пять.
Четвертый настроечный вход устройства соединен с одиннадцатым входом элемента
ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом восемь.
Двенадцатый и тринадцатый входы элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом восемь соединены с пятым настроечным входом устройства.
Шестой настроечный вход устройства соединен с одиннадцатым и двенадцатым входами элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом девять.
Седьмой и восьмой настроечные входы устройства соединены с одиннадцатым и двенадцатым входами элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом одиннадцать.
На чертеже (фигура) представлена логическая схема устройства для вычисления полиномиальных симметрических булевых функций десяти переменных.
Устройство для вычисления полиномиальных симметрических булевых функций десяти переменных содержит элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре 1, элемент
ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом пять 2, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом
восемь 3, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом девять 4, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом одиннадцать 5, элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА 6, десять
информационных входов 7...16, восемь настроечных входов 17...24 и один выход 25.
Устройство для вычисления полиномиальных симметрических булевых функций работает следующим образом. На информационные входы устройства 7...16 поступают (в
произвольном порядке) значения переменных x1, x2,..., x10, а на настроечные входы 17...24 сигналы настройки u0, u1,..., u7, значения которых принадлежат множеству {0,1}. На выхоk
де устройства 25 реализуется полиномиальная симметрическая булева функция E10
=
k
E10
(x1, x2,..., x10), определяемая вектором настройки u(F) = (u0, u1,..., u7), где k = 1, 2,...,10.
Поясним принцип построения и работы устройства для вычисления полиномиальных
симметрических булевых функций десяти переменных.
Известно, что произвольная симметрическая булева функция n переменных
F = (x1, x2,..., xn) с рабочими числами a1, a2,..., ar (0 ≤ r ≤ n) принимает значение 1 на тех и
3
BY 13969 C1 2011.02.28
только тех наборах значений переменных X = {x1, x2,..., xn}, которые содержат ровно
aj (j = 1, 2,..., r) единиц. Такая булева функция обозначается F = Fna1 ,a 2 ,...,a r (X) . Если r = 1,
то симметрическая булева функция F = Fna (x1, x2,..., xn) называется фундаментальной (или
элементарной).
Симметрическая булева функция n переменных F = Fna1 ,a 2 ,..., a r (X) называется полиномиальной, если ее полином Жегалкина содержит только элементарные конъюнкции, ранг
которых равен k (1 ≤ k ≤ n). Такая полиномиальная симметрическая булева функция n переменных обозначается F = E kn (X). Очевидно, что полином Жегалкина функции F = E kn (X)
содержит Ckn ("число сочетаний из n по k") элементарных конъюнкций ранга k, где
k = 1, 2,..., n.
Устройство синтезировано на основании применения следующих аналитических
представлений полиномиальных симметрических булевых функций десяти переменных
k
k
E10
(X) = E10
(x1, x2,..., x10):
E110 (X) = F101 (X) ∨ F103 (X) ∨ F105 (X) ∨ F107 (X) ∨ F109 (X),
2
E10
(X) = F102 (X) ∨ F103 (X) ∨ F106 (X) ∨ F107 (X) ∨ F1010 (X),
3
E10
(X) = F103 (X) ∨ F107 (X),
4
E10
(X) = F104 (X) ∨ F105 (X) ∨ F106 (X) ∨ F107 (X),
5
6
E10
(X) = F105 (X) ∨ F107 (X), E10
(X) = F106 (X) ∨ F107 (X),
7
8
E10
(X) = F107 (X), E10
(X) = F108 (X) ∨ F109 (X) ∨ F1010 (X),
9
10
E10
(X) = F109 (X), E10
10 (X) = F10 (X).
В таблице представлена настройка устройства на вычисление (реализацию) полиномиальных симметрических булевых функций десяти переменных.
Устройство для вычисления полиномиальных симметрических булевых функций
Сигналы настройки
Выход
u0
u1
u2
u3
u4
u5
u6
u7
F
17
18
19
20
21
22
23
24
25
E110
1
1
1
1
1
1
1
1
0
1
1
0
1
1
0
1
2
E10
1
0
0
1
1
1
0
0
3
E10
0
0
0
0
1
1
0
0
4
E10
1
0
1
1
1
1
0
0
5
E10
1
0
1
0
1
1
0
0
6
E10
1
0
1
1
0
0
1
1
7
E10
1
0
1
0
0
0
0
1
8
E10
1
0
1
1
0
1
1
1
9
E10
1
0
1
1
0
1
0
1
E10
10
Первообразная функция заявляемого устройства для вычисления полиномиальных
симметрических булевых функций имеет вид
F(x1, x2,…, x10, u0, u1,…, u7) = F134 (x1, x2,…, x10, u0, u1, u1) ⊕
4
BY 13969 C1 2011.02.28
⊕ F125 (x1, x2,..., x10, u2, u2) ⊕ F138 (x1, x2,..., x10, u3, u4, u4) ⊕
⊕ F129 (x1, x2,…, x10, u5, u5) ⊕ F1211 (x1, x2,…, x10, u6, u7).
Рассмотрим пример. Допустим, что на выходе устройства требуется вычислить (реализовать) полиномиальную симметрическую булеву функцию
2
E10
(x1, x2,…, x10)=x1x2 ⊕ x1x3 ⊕ x1x4 ⊕ x1x5 ⊕ x1x6 ⊕ x1x7 ⊕ x1x8 ⊕
⊕ x1x9 ⊕ x1x10 ⊕ x2x3 ⊕ x2x4 ⊕ x2x5 ⊕ x2x6 ⊕ x2x7 ⊕ x2x8 ⊕ x2x9 ⊕
⊕ x2x10 ⊕ x3x4 ⊕ x3x5 ⊕ x3x6 ⊕ x3x7 ⊕ x3x8 ⊕ x3x9 ⊕ x3x10 ⊕ x4x5 ⊕
⊕ x4x6 ⊕ x4x7 ⊕ x4x8 ⊕ x4x9 ⊕ x4x10 ⊕ x5x6 ⊕ x5x7 ⊕ x5x8 ⊕ x5x9 ⊕
⊕ x5x10 ⊕ x6x7 ⊕ x6x8 ⊕ x6x9 ⊕ x6x10 ⊕ x7x8 ⊕ x7x9 ⊕ x7x10 ⊕
⊕ x8x9 ⊕ x8x10 ⊕ x9x10.
В таком случае, согласно таблице настроек, необходимо положить u0 = u3 = u6 = 0 и
u1 = u2 = u4 = u5 = u7 = 1. Тогда первообразная функция устройства принимает вид
F(x1, x2,…, x10, 0, 1, 1, 0, 1, 1, 0, 1) = F134 (x1, x2,…, x10, 0, 1, 1) ⊕
⊕ F125 (x1, x2,..., x10, 1, 1) ⊕ F138 (x1, x2,..., x10, 0, 1, 1) ⊕
⊕ F129 (x1, x2,..., x10, 1, 1) ⊕ F1211 (x1, x2,..., x10, 0, 1) =
= F102 (x1, x2,..., x10) ⊕ F103 (x1, x2,..., x10) ⊕ F106 (x1, x2,..., x10) ⊕
⊕ F107 (x1, x2,..., x10) ⊕ F1010 (x1, x2,..., x10) =
2
= F102 (X) ∨ F103 (X) ∨ F106 (X) ∨ F107 (X) ∨ F1010 (X) = E10
(X).
Дополнительными достоинствами устройства для вычисления полиномиальных симметрических булевых функций десяти переменных являются: а) низкая конструктивная
сложность (по числу входов логических элементов), равная 67; б) небольшое число внешних выводов, равное 19; в) высокое быстродействие, определяемое глубиной схемы и равное 2τ, где τ -задержка на логический элемент.
Источники информации:
1. А.с. СССР 1478208, МПК G 06F 7/00, 1989.
2. Патент РБ 2117, МПК G 06F 7/00, 1998 (прототип).
Национальный центр интеллектуальной собственности.
220034, г. Минск, ул. Козлова, 20.
5
Документ
Категория
Без категории
Просмотров
0
Размер файла
255 Кб
Теги
by13969, патент
1/--страниц
Пожаловаться на содержимое документа