close

Вход

Забыли?

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

?

Патент BY16552

код для вставкиСкачать
ОПИСАНИЕ
ИЗОБРЕТЕНИЯ
К ПАТЕНТУ
РЕСПУБЛИКА БЕЛАРУСЬ
(46) 2012.12.30
(12)
(51) МПК
НАЦИОНАЛЬНЫЙ ЦЕНТР
ИНТЕЛЛЕКТУАЛЬНОЙ
СОБСТВЕННОСТИ
(54)
G 06F 7/00
(2006.01)
УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ ПОЛИНОМИАЛЬНЫХ
СИММЕТРИЧЕСКИХ БУЛЕВЫХ ФУНКЦИЙ ВОСЬМИ
ПЕРЕМЕННЫХ
(21) Номер заявки: a 20110037
(22) 2011.01.10
(43) 2012.06.30
(71) Заявитель: Белорусский государственный университет (BY)
(72) Автор: Супрун Валерий Павлович
(BY)
BY 16552 C1 2012.12.30
BY (11) 16552
(13) C1
(19)
(73) Патентообладатель: Белорусский государственный университет (BY)
(56) BY 13666 C1, 2010.
BY a20090336, 2009.
BY 13248 C1, 2010.
BY 13818 C1, 2010.
BY 11028 C1, 2008.
(57)
Устройство для вычисления полиномиальных симметрических булевых функций
восьми переменных, характеризующееся тем, что содержит элемент СЛОЖЕНИЕ ПО
МОДУЛЮ ДВА и первый, второй, третий и четвертый элементы ИСКЛЮЧАЮЩЕЕ
ИЛИ, выполненные с порогами четыре, пять, восемь и девять соответственно, выход i-го
из которых, где i = 1, 2, 3, 4, соединен с i-м входом элемента СЛОЖЕНИЕ ПО МОДУЛЮ
ДВА, выход которого соединен с выходом устройства, j-й информационный вход которого, где j = 1, 2, …, 8, соединен с j-м входом i-го элемента ИСКЛЮЧАЮЩЕЕ ИЛИ; первый
настроечный вход устройства соединен с девятым входом элемента ИСКЛЮЧАЮЩЕЕ
ИЛИ с порогом четыре, десятый и одиннадцатый входы которого соединены со вторым
настроечным входом устройства, третий настроечный вход которого соединен с девятым
и десятым входами элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом пять; четвертый настроечный вход устройства соединен с девятым входом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с
BY 16552 C1 2012.12.30
порогом восемь, десятый и одиннадцатый входы которого соединены с пятым настроечным входом устройства и с девятым и десятым входами элемента ИСКЛЮЧАЮЩЕЕ
ИЛИ с порогом девять.
Изобретение относится к области вычислительной техники и микроэлектроники и
предназначено для вычисления полиномиальных симметрических булевых функций восьми переменных.
Известно устройство для вычисления полиномиальных симметрических булевых
функций восьми переменных, которое содержит элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом пять, элемент ИСКЛЮЧАЮЩЕЕ
ИЛИ с порогом шесть, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом восемь, элемент
СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, восемь информационных и семь настроечных входов,
выход [1]. Сложность устройства (по числу входов логических элементов) равна 46, а
быстродействие, определяемое глубиной логической схемы, составляет 2τ, где τ - задержка на один логический элемент.
Недостатком известного устройства является большое число внешних выводов, равное
16 (информационных входов - 8, настроечных входов - 7 и выход).
Известное устройство, как и предлагаемое устройство, содержит элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом пять, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом восемь и элемент СЛОЖЕНИЕ ПО МОДУЛЮ
ДВА, входы которого соединены с выходами элементов ИСКЛЮЧАЮЩЕЕ ИЛИ с порогами четыре, пять и восемь, а выход - с выходом устройства.
Наиболее близким по функциональным возможностям и конструкции техническим
решением к заявляемому устройству является устройство, содержащее элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом пять, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом шесть, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с
порогом восемь, элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, восемь информационных и
шесть настроечных входов, выход [2].
Недостатком устройства является большое число внешних выводов, равное 15 (информационных входов - 8, настроечных входов - 6 и выход).
Устройство-прототип, как и заявляемое устройство, содержит элемент СЛОЖЕНИЕ
ПО МОДУЛЮ ДВА и три элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогами четыре, пять и
восемь, причем выходы элементов ИСКЛЮЧАЮЩЕЕ ИЛИ соединены со входами элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, выход которого соединен с выходом устройства.
Изобретение направлено на решение следующей технической задачи: уменьшение
числа внешних выводов устройства для вычисления полиномиальных симметрических
булевых функций восьми переменных.
Устройство для вычисления полиномиальных симметрических булевых функций
восьми переменных характеризуется тем, что содержит элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА и первый, второй, третий и четвертый элементы ИСКЛЮЧАЮЩЕЕ ИЛИ, выполненные с порогами четыре, пять, восемь и девять соответственно.
Выход i-го элемента ИСКЛЮЧАЮЩЕЕ ИЛИ, где i = 1, 2, 3, 4, соединен с i-м входом
элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, выход которого соединен с выходом устройства, j-й информационный вход которого, где j = 1, 2, …, 8, соединен с j-м входом i-го
элемента ИСКЛЮЧАЮЩЕЕ ИЛИ.
Первый настроечный вход устройства соединен с девятым входом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре, десятый и одиннадцатый входы которого соединены
со вторым настроечным входом устройства, третий настроечный вход которого соединен
с девятым и десятым входами элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом пять.
2
BY 16552 C1 2012.12.30
Четвертый настроечный вход устройства соединен с девятым входом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом восемь, десятый и одиннадцатый входы которого соединены с пятым настроечным входом устройства и с девятым и десятым входами элемента
ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом девять.
Основной технический результат изобретения заключается в уменьшении числа
внешних выводов устройства (в уменьшении числа настроечных входов) за счет использования элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом девять, а также посредством изменения способа его настройки на реализацию (вычисление) полиномиальных
симметрических булевых функций восьми переменных.
На фигуре представлена логическая схема устройства для вычисления полиномиальных симметрических булевых функций восьми переменных.
Устройство для вычисления полиномиальных симметрических булевых функций восьми
переменных содержит элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре 1, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом пять 2, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом восемь 3,
элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом девять 4, элемент СЛОЖЕНИЕ ПО МОДУЛЮ
ДВА 5, восемь информационных входов 6…13, пять настроечных входов 14…18 и выход 19.
Устройство для вычисления полиномиальных симметрических булевых функций восьми
переменных работает следующим образом. На информационные входы устройства 6…13
поступают (в произвольном порядке) значения переменных x1, x2, …, x8, на настроечные
входы 14…18 - сигналы настройки u1, u2, …, u5 соответственно, принимающие значения
из множества {0,1}, на выходе устройства 19 реализуется (вычисляется) полиномиальная
симметрическая булева функция восьми переменных F = E 8k ( x1 , x 2 , K , x 8 ) , определяемая
двоичным вектором настройки u(F) = (u1, u2, …, u5), где k = 1, 2, …, 8.
Поясним принцип построения и работы устройства для вычисления полиномиальных
симметрических булевых функций восьми переменных.
Известно, что произвольная симметрическая булева функция n переменных
F = F(x1, x2, …, xn) с рабочими числами a1, a2, …, ar (0 ≤ r ≤n+1) принимает значение 1
на тех и только тех наборах значений переменных X = {x1, x2, …, xn}, которые содержат ровно аj (j = 1, 2, …, r) единиц. Такая булева функция обозначается через
F = Fna1 , a 2 , K, a r ( x 1 , x 2 , K , x n ) . Если r = 1, то симметрическая булева функция
F = Fna ( x1 , x 2 , K , x n ) называется фундаментальной (или элементарной).
Симметрическая булева функция n переменных F = Fna1 , a 2 , K, a r (X) называется полиномиальной (или полиномиально-однородной), если ее полином Жегалкина содержит ровно
С kn (число сочетаний из n по k) различных элементарных конъюнкций ранга k, где
k = 1, 2, …, n. Такая симметрическая булева функция обозначается через F = E kn (X) .
Заявляемое устройство (фигура) синтезировано на основе применения следующих
аналитических представлений полиномиальных симметрических булевых функций
F = E 8k ( x1 , x 2 , K , x n ) восьми переменных:
E18 (X) = F81 (X) ∨ F83 (X) ∨ F85 (X) ∨ F87 (X) ,
E 82 (X) = F82 (X) ∨ F83 (X) ∨ F86 (X) ∨ F87 (X) ,
E 83 (X) = F83 (X) ∨ F87 (X) , E 84 (X) = F84 (X) ∨ F85 (X) ∨ F86 (X) ∨ F87 (X) ,
E 85 (X) = F85 (X) ∨ F87 (X) , E 86 (X) = F86 (X) ∨ F87 (X) ,
E 87 (X) = F87 (X) и E 88 (X) = F88 (X) .
Посредством таблицы представлен способ настройки устройства на реализацию полиномиальных симметрических булевых функций восьми переменных.
3
BY 16552 C1 2012.12.30
Первообразная функция устройства для вычисления полиномиальных симметрических булевых функций F(X) = E 8k ( x 1 , x 2 ,K, x 8 ) имеет вид
F = ( x 1 , x 2 ,K, x 8 , u 1 , u 2 ,K, u 5 ) = F114 ( x 1 , x 2 ,K, x 8 , u 1 , u 2 , u 2 ) ⊕
⊕ F105 ( x 1 , x 2 ,K, x 8 , u 3 , u 3 ) ⊕ F118 ( x 1 , x 2 ,K, x 8 , u 4 , u 5 , u 5 ) ⊕ F109 ( x 1 , x 2 ,K, x 8 , u 5 , u 5 ),
где
1, если x 1 + x 2 + K x 8 + u1 + 2u 2 = 4,
F114 ( x 1 , x 2 , K , x 8 , u 1 , u 2 , u 2 ) = 
0 − в противном случае,
1, если x1 + x 2 + K x 8 + 2u 3 = 5,
F105 ( x1 , x 2 , K , x 8 , u 3 , u 3 ) = 
0 − в противном случае,
1, если x 1 + x 2 + K x 8 + u 4 + 2u 5 = 8,
F118 ( x1 , x 2 , K , x 8 , u 4 , u 5 , u 5 ) = 
0 − в противном случае,
1, если x1 + x 2 + K x 8 + 2u 5 = 9,
F109 ( x1 , x 2 , K , x 8 , u 5 , u 5 ) = 
0 − в противном случае.
Рассмотрим пример вычисления (реализации) на выходе устройства полиномиальной
симметрической булевой функции восьми переменных.
Пример.
Допустим, на выходе 19 устройства требуется вычислить полиномиальную симметрическую булеву функцию восьми переменных
E 83 ( x 1 , x 2 , K , x 8 ) = x 1x 2 x 3 ⊕ x 1x 2 x 4 ⊕ x1x 2 x 5 ⊕ x1x 2 x 6 ⊕ x 1x 2 x 7 ⊕ x 1x 2 x 8 ⊕
⊕ x1x 3 x 4 ⊕ x1x 3x 5 ⊕ ⊕ x1x 3 x 6 ⊕ x1x 3x 7 ⊕ x1x 3 x 8 ⊕ x1x 4 x 5 ⊕ x1x 4 x 6 ⊕ x1x 4 x 7 ⊕
⊕ x1x 4 x 8 ⊕ x1x 5 x 6 ⊕ x1x 5 x 7 ⊕ x1x 5 x 8 ⊕ x1x 6 x 7 ⊕ x1 x 6 x 8 ⊕ x1x 7 x 8 ⊕ x 2 x 3 x 4 ⊕
⊕ x 2 x 3x 5 ⊕ x 2 x 3x 6 ⊕ x 2 x 3x 7 ⊕ x 2 x 3x8 ⊕ x 2 x 4 x 5 ⊕ x 2 x 4 x 6 ⊕ x 2 x 4 x 7 ⊕ x 2 x 4 x8 ⊕
⊕ x 2 x5x 6 ⊕ x 2 x 5x 7 ⊕ x 2x 5x8 ⊕ x 2x 6x 7 ⊕ x 2x 6x8 ⊕ x 2x 7 x8 ⊕ x3x 4x 5 ⊕ x 3x 4x 6 ⊕
⊕ x 3x 4 x 7 ⊕ x 3x 4 x8 ⊕ x 3x 5x 6 ⊕ x 3x 5x 7 ⊕ x 3x 5x8 ⊕ x 3x 6 x 7 ⊕ x 3x 6 x 8 ⊕ x 3x 7 x8 ⊕
⊕ x 4x 5x 6 ⊕ x 3x5x 7 ⊕ x 4 x 5x8 ⊕ x 4x 6 x 7 ⊕ x 4 x 6 x8 ⊕ x 4x 7 x8 ⊕
⊕ x 5x 6x 7 ⊕ x5x 6 x8 ⊕ x 5x 7 x8 ⊕ x 6x 7 x8.
Для вычисления на выходе устройства функции F = E 83 ( x 1 , x 2 ,K, x 8 ) , согласно таблице
настроек (таблица), необходимо на настроечные входы устройства подать u2 = u3 = 0 и
u1 = u4 = u5=1.
В таком случае первообразная функция устройства принимает вид
F( x 1 , x 2 , K , x 8 , 1, 0, 0, 1, 1) = F114 ( x1 , x 2 , K , x 8 , 1, 0, 0) ⊕
⊕ F105 ( x 1 , x 2 , K , x 8 , 0, 0) ⊕ F118 ( x1 , x 2 , K , x 8 , 1, 1, 1) ⊕ F109 ( x 1 , x 2 , K , x 8 , 1, 1) =
= F83 ( x1 , x 2 , K , x 8 ) ⊕ F85 ( x1 , x 2 , K , x 8 ) ⊕ F85 ( x 1 , x 2 , K , x 8 ) ⊕
⊕ F87 ( x 1 , x 2 , K , x 8 ) = F83 ( x 1 , x 2 , K , x 8 ) ⊕ F87 ( x 1 , x 2 , K , x 8 ) =
= F83 ( x 1 , x 2 , K , x 8 ) ∨ F87 ( x1 , x 2 , K , x 8 ) = F83 ( x1 , x 2 , K , x 8 ).
Основным достоинством заявляемого устройства для вычисления полиномиальных
симметрических булевых функций восьми переменных является относительно небольшое
число внешних выводов, которое равно 14 (восемь информационных и пять настроечных
входов, выход). Число внешних выводов устройства-прототипа равно 15.
При этом устройство имеет небольшую конструктивную сложность, равную 48 (сложность устройства-прототипа равна 45). Следует отметить, что быстродействие устройства
совпадает с быстродействием устройства-прототипа.
4
BY 16552 C1 2012.12.30
u1
14
1
u2
15
1
Сигналы настройки
u3
16
1
u4
17
1
u5
18
1
Выход
F
19
E18
0
1
1
0
1
E 82
1
0
0
1
1
E 83
0
0
0
0
1
E 84
1
0
1
1
1
E 85
1
0
1
0
1
E 86
1
0
1
1
0
E 87
1
0
1
0
0
E 88
Источники информации:
1. Патент РБ 11785, МПК G 06 F 7/00, 2009.
2. Патент РБ 13666, МПК G 06 F 7/00, 2010 (прототип).
Национальный центр интеллектуальной собственности.
220034, г. Минск, ул. Козлова, 20.
5
Документ
Категория
Без категории
Просмотров
0
Размер файла
96 Кб
Теги
by16552, патент
1/--страниц
Пожаловаться на содержимое документа