close

Вход

Забыли?

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

?

Патент BY13666

код для вставкиСкачать
ОПИСАНИЕ
ИЗОБРЕТЕНИЯ
К ПАТЕНТУ
РЕСПУБЛИКА БЕЛАРУСЬ
(46) 2010.10.30
(12)
(51) МПК (2009)
НАЦИОНАЛЬНЫЙ ЦЕНТР
ИНТЕЛЛЕКТУАЛЬНОЙ
СОБСТВЕННОСТИ
(54)
BY (11) 13666
(13) C1
(19)
G 06F 7/00
УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ ПОЛИНОМИАЛЬНЫХ
СИММЕТРИЧЕСКИХ БУЛЕВЫХ ФУНКЦИЙ
(21) Номер заявки: a 20090175
(22) 2009.02.09
(43) 2009.08.30
(71) Заявитель: Белорусский государственный университет (BY)
(72) Автор: Супрун Валерий Павлович
(BY)
(73) Патентообладатель: Белорусский государственный университет (BY)
(56) BY a 20071232, 2008.
BY 11028 C1, 2008.
BY 10219 C1, 2008.
SU 1444743 A1, 1988.
SU 1559337 A1, 1990.
BY 13666 C1 2010.10.30
(57)
Устройство для вычисления полиномиальных симметрических булевых функций восьми переменных, содержащее элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом пять,
элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом шесть и элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с
BY 13666 C1 2010.10.30
порогом восемь, i-й, где i = 1,2,…,8, вход которого соединен с i-м входом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре, с i-м входом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с
порогом пять, с i-м входом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом шесть и с i-м информационным входом устройства, выход которого соединен с выходом элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, входы которого с первого по четвертый соединены
соответственно с выходами элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре, элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом пять, элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом
шесть и элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом восемь, причем первый настроечный вход устройства соединен с девятым входом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре, десятый и одиннадцатый входы которого соединены со вторым
настроечным входом устройства, третий настроечный вход которого соединен с двенадцатым и тринадцатым входами элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре, четвертый настроечный вход устройства соединен с девятым и десятым входами элемента
ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом пять, пятый настроечный вход устройства соединен с
девятым входом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом шесть, шестой настроечный
вход устройства соединен с девятым входом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом
восемь, отличающееся тем, что устройство выполнено с шестью настроечными входами,
а элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом шесть - с девятью входами.
Изобретение относится к области вычислительной техники и микроэлектроники и
предназначено для вычисления полиномиальных симметрических булевых функций восьми переменных.
Известно устройство для вычисления полиномиальных симметрических булевых
функций восьми переменных, содержащее элемент ИСКЛЮЧАЮЩЕЕ ИЛИ, элемент
ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом два, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом три,
элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с
порогом пять, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом шесть, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом семь, элемент И, шесть элементов ИЛИ, восемь входов и восемь
выходов [1].
Основным недостатком известного устройства является высокая конструктивная
сложность, которая по числу входов логических элементов равна 82.
Известное устройство, как и предлагаемое устройство, содержит элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом пять и
элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом шесть.
Наиболее близким по функциональным возможностям и конструкции техническим
решением к предлагаемому является устройство, содержащее элемент ИСКЛЮЧАЮЩЕЕ
ИЛИ с порогом четыре, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом пять, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом шесть, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом восемь, элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, восемь информационных входов, семь
настроечных входов и выход [2].
Недостатком устройства является большое число внешних выводов, равное 16 (информационных входов - 8, настроечных входов -7 и выход).
Устройство-прототип, как и предлагаемое устройство, содержит элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом пять, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом шесть, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с
порогом восемь и элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА.
Изобретение направлено на решение следующей технической задачи: уменьшение
числа внешних выводов (уменьшение числа настроечных входов) устройства для вычисления полиномиальных симметрических булевых функций восьми переменных.
2
BY 13666 C1 2010.10.30
Устройство для вычисления полиномиальных симметрических булевых функций
восьми переменных содержит элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом
пять, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом шесть и элемент ИСКЛЮЧАЮЩЕЕ
ИЛИ с порогом восемь, i-й, где i = 1,2,...,8, вход которого соединен с i-м входом элемента
ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре, с i-м входом элемента ИСКЛЮЧАЮЩЕЕ
ИЛИ с порогом пять, с i-м входом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом шесть и с
i-м информационным входом устройства, выход которого соединен с выходом элемента
СЛОЖЕНИЕ ПО МОДУЛЮ ДВА.
Входы элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА с первого по четвертый соединены
соответственно с выходами элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре, элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом пять, элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом
шесть и элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом восемь.
Первый настроечный вход устройства соединен с девятым входом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре, десятый и одиннадцатый входы которого соединены
со вторым настроечным входом устройства, третий настроечный вход которого соединен
с двенадцатым и тринадцатым входами элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре.
Четвертый настроечный вход устройства соединен с девятым и десятым входами элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом пять, пятый настроечный вход устройства соединен с девятым входом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом шесть, шестой
настроечный вход устройства соединен с девятым входом элемента ИСКЛЮЧАЮЩЕЕ
ИЛИ с порогом восемь.
В отличие от прототипа устройство выполнено с шестью настроечными входами, а
элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом шесть - с девятью входами.
Основной технический результат изобретения заключается в уменьшении числа
внешних выводов устройства (уменьшения числа настроечных входов) за счет изменения
способа его настройки на реализацию (вычисление) полиномиальных симметрических булевых функций восьми переменных.
На чертеже (фигура) представлена логическая схема устройства для вычисления полиномиальных симметрических булевых функций восьми переменных.
Устройство для вычисления полиномиальных симметрических булевых функций содержит элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре 1, элемент ИСКЛЮЧАЮЩЕЕ
ИЛИ с порогом пять 2, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом шесть 3, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом восемь 4, элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА 5,
восемь информационных входов 6... 13, шесть настроечных входов 14... 19 и выход 20.
Устройство для вычисления полиномиальных симметрических булевых функций
восьми переменных работает следующим образом. На информационные входы устройства
6...13 поступают (в произвольном порядке) значения переменных x1,x2,...,x8; на настроечные входы 14...19 - сигналы настройки u1, u2,...,u6 соответственно; на выходе 20 реализуется (вычисляется) полиномиальная симметрическая булева функция восьми переменных
Е8k = Е8k(x1,x2,...,x8), определяемая вектором настройки U = (u1,u2,...,u6), где k = 1,2,...,8.
Поясним принцип построения и работы устройства для вычисления полиномиальных
симметрических булевых функций восьми переменных.
Известно, что произвольная симметрическая булева функция n переменных
F = F(x1,x2,...,xn) с рабочими числами a1,a2,...,ar (0 ≤ r ≤ n) принимает значение 1 на тех и
только тех наборах значений переменных X = {x1,x2,...,xn}, которые содержат ровно aj
(j = 1,2,...,r) единиц. Такая булева функция обозначается через F = Fna1 ,a 2 ,...,a r ( x1, x 2 ,..., x n ) .
Если r = 1, то симметрическая булева функция F = Fna(x1,x2,...,xn) называется фундаментальной (или элементарной).
3
BY 13666 C1 2010.10.30
Симметрическая булева функция n переменных F = Fna1 ,a 2 ,...,a r (X) называется полиномиальной, если ее полином Жегалкина содержит Cnk ("число сочетаний из n по k") различных элементарных конъюнкций ранга k, где k = 1,2,...,n. Такая полиномиальная
симметрическая булева функция обозначается через F = Enk(X).
Предлагаемое устройство (фигура) синтезировано на основе применения следующих
аналитических представлений полиномиальных симметрических булевых функций
Е8k(X) = Е8k(х1,х2,...,х8), зависящих от восьми переменных:
Е81(Х) = F8l(x) ∨ F83(X) ∨ F85(x) ∨ F7(X),
E82(X) = F82(X) ∨ F83(X) ∨ F86(X) ∨ F87(X),
E83(X) = F83(X) ∨ F7(X), E84(X) = F84(X) ∨ F85(X) ∨ F86(X) ∨ F87(X),
E85(X) = F85(X) ∨ F87(X), E86(X) = F86(X) ∨ F87(X),
E87(X) = F87(X) и E88(X) = F88(X).
В таблице представлена настройка устройства на реализацию полиномиальных симметрических булевых функций восьми переменных.
Первообразная функция предлагаемого устройства для вычисления полиномиальных
симметрических булевых функций восьми переменных
Е8k(X) = E8k(x1,x2,...,x8) имеет вид
F(x1,x2,...,x8,u1,u2,...,u6) = Fl34(x1,x2,...,x8,u1,u2,u2,u3,u3)⊕
⊕F105(x1,x2,...,х8,u4,u4) ⊕ F96(x1,x2,…,x8,u5) ⊕ F98(x1,x2,...,x8, u6),
где
1, если x1 + x 2 + ... + x 8 + u1 + 2u 2 + 2u 3 = 4,
4
F13
( x1, x 2 ,..., x 8 , u1, u 2 , u 2 , u 3 , u 3 ) = 
0 − в противном случае,
1, если x1 + x 2 + ... + x 8 + 2u 4 = 5,
5
F10
( x1, x 2 ,..., x 8 , u 4 , u 4 ) = 
0 − в противном случае,
1, если x1 + x 2 + ... + x 8 + u 5 = 6,
F96 ( x1, x 2 ,..., x 8 , u 5 ) = 
0 − в противном случае,
1, если x1 + x 2 + ... + x 8 + u 6 = 8,
F98 ( x1, x 2 ,..., x 8 , u 6 ) = 
0 − в противном случае,
Пример
Допустим, на выходе устройства требуется вычислить полиномиальную симметрическую булеву функцию восьми переменных
E83(x1,x2,…,x8)=x1x2x3⊕x1x2x4⊕x1x2x5⊕x1x2x6⊕x1x2x7⊕x1x2x8⊕
⊕x1x3x4⊕x1x3x5⊕x1x3x6⊕x1x3x7⊕x1x3x8⊕x1x4x5⊕x1x4x6⊕x1x4x7⊕
⊕x1x4x8⊕x1x5x6⊕x1x5x7⊕x1x5x8⊕x1x6x7⊕x1x6x8⊕x1x7x8⊕x2x3x4⊕
⊕x2x3x5⊕x2x3x6⊕x2x3x7⊕x2x3x8⊕x2x4x5⊕x2x4x6⊕x2x4x7⊕x2x4x8⊕
⊕x2x5x6⊕x2x5x7⊕x2x5x8⊕x2x6x7⊕x2x6x8⊕x2x7x8⊕x3x4x5⊕x3x4x6⊕
⊕x3x4x7⊕x3x4x8⊕x3x5x6⊕x2x5x7⊕x3x5x8⊕x3x6x7⊕x3x6x8⊕x3x7x8⊕
⊕x4x5x6⊕x4x5x7⊕x4x5x8⊕x4x6x7⊕x4x6x8⊕x4x7x8⊕
⊕x5x6x7⊕x5x6x8⊕x5x7x8⊕x6x7x8.
В таком случае, согласно таблице настроек (таблица), необходимо на настроечные
входы устройства подать u2 = u3 = u4 = 0 и u1 = u5 = u6 = 1.
В таком случае первообразная функция устройства принимает вид
F(x1,x2,...,x8,1,0,0,0,1,1) = Fl34(x1,x2,...,x8,1,0,0,0,0)⊕
⊕F105(x1,x2,...,x8,0,0)⊕F96(x1,x2,...,х8,1)⊕F98(x1,x2,...,x8,1) =
3
= F8 (x1,x2,...,x8)⊕F85(x1,x2,...,x8)⊕F85(x1,x2,...,x8) ⊕F87(x1,x2,...,x8) =
= F83(x1,x2,…,x8)⊕F87(x1,x2,…,x8) =
4
BY 13666 C1 2010.10.30
= F83(x1,x2,...,x8)∨F87(x1,x2,...,x8) = E83(x1,x2,...,x8).
Дополнительным достоинством предлагаемого устройства для вычисления полиномиальных симметрических булевых функций восьми переменных является небольшая конструктивная сложность, которая (по числу входов логических элементов) равна 45.
Источники информации:
1. Патент РБ 11024, МПК G 06F 7/00, 2008.
2. Патент РБ 11785, МПК G 06F 7/00, 2009 (прототип).
Устройство для вычисления полиномиальных симметрических булевых функций
Сигналы настройки
Выход
u1
u2
u3
u4
u5
u6
F
14
15
16
17
18
19
20
1
1
0
1
1
1
E81
0
1
0
1
0
1
E82
1
0
0
0
1
1
E83
0
0
0
0
0
1
E84
1
0
0
1
1
1
E85
1
0
0
1
0
1
E86
1
1
1
0
1
1
E87
1
1
1
0
1
0
E88
Национальный центр интеллектуальной собственности.
220034, г. Минск, ул. Козлова, 20.
5
Документ
Категория
Без категории
Просмотров
0
Размер файла
187 Кб
Теги
by13666, патент
1/--страниц
Пожаловаться на содержимое документа