close

Вход

Забыли?

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

?

Патент BY16553

код для вставкиСкачать
ОПИСАНИЕ
ИЗОБРЕТЕНИЯ
К ПАТЕНТУ
РЕСПУБЛИКА БЕЛАРУСЬ
(46) 2012.12.30
(12)
(51) МПК
НАЦИОНАЛЬНЫЙ ЦЕНТР
ИНТЕЛЛЕКТУАЛЬНОЙ
СОБСТВЕННОСТИ
(54)
BY (11) 16553
(13) C1
(19)
G 06F 7/00
(2006.01)
УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ ПОЛИНОМИАЛЬНЫХ
СИММЕТРИЧЕСКИХ БУЛЕВЫХ ФУНКЦИЙ ДВЕНАДЦАТИ
ПЕРЕМЕННЫХ
(21) Номер заявки: a 20110063
(22) 2011.01.17
(43) 2012.06.30
(71) Заявитель: Белорусский государственный университет (BY)
(72) Авторы: Супрун Валерий Павлович;
Городецкий Данила Андреевич
(BY)
(73) Патентообладатель: Белорусский государственный университет (BY)
(56) BY a20091501, 2010.
BY a20090336, 2009.
BY 13666 C1, 2010.
RU 2047894 C1, 1995.
SU 1559338 A1, 1990.
BY 16553 C1 2012.12.30
(57)
Устройство для вычисления полиномиальных симметрических булевых функций двенадцати переменных, характеризующееся тем, что содержит элемент СЛОЖЕНИЕ ПО
МОДУЛЮ ДВА и с первого по шестой элементы ИСКЛЮЧАЮЩЕЕ ИЛИ, выполненные
с порогами четыре, восемь, девять, десять, двенадцать и тринадцать соответственно, выход i-го из которых, где i = 1 ,2, …, 6, соединен с i-м входом элемента СЛОЖЕНИЕ ПО
МОДУЛЮ ДВА, выход которого соединен с выходом устройства, j-й информационный
BY 16553 C1 2012.12.30
вход которого, где j = 1, 2, …, 12, соединен с j-м входом i-го элемента ИСКЛЮЧАЮЩЕЕ
ИЛИ; первый настроечный вход устройства соединен с тринадцатым входом элемента
ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре, четырнадцатый и пятнадцатый входы которого соединены со вторым настроечным входом устройства, а шестнадцатый и семнадцатый
входы - с третьим настроечным входом устройства; четвертый настроечный вход устройства соединен с тринадцатым входом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом восемь, четырнадцатый и пятнадцатый входы которого соединены с пятым настроечным
входом устройства; шестой настроечный вход устройства соединен с тринадцатым и четырнадцатым входами элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом девять, пятнадцатый,
шестнадцатый, семнадцатый и восемнадцатый входы которого соединены с седьмым
настроечным входом устройства; восьмой настроечный вход устройства соединен с тринадцатым, четырнадцатым и пятнадцатым входами элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с
порогом десять; девятый настроечный вход устройства соединен с тринадцатым входом
элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом двенадцать, четырнадцатый и пятнадцатый
входы которого соединены с десятым настроечным входом устройства; одиннадцатый
настроечный вход устройства соединен с тринадцатым и четырнадцатым входами элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом тринадцать.
Изобретение относится к области вычислительной техники и микроэлектроники и
предназначено для вычисления полиномиальных симметрических булевых функций двенадцати переменных.
Известно устройство для вычисления симметрических булевых функций n переменных, которое содержит n2 + n + 1 элементов И-НЕ, n элементов НЕ, n информационных и
n + 1 настроечных входов, выход [1]. Конструктивная сложность устройства (по числу
входов логических элементов) равна 3n2 + 2n + 2, а его быстродействие, определяемое
глубиной схемы, составляет (n + 2)τ, где τ-задержка на один логический элемент. Известное устройство при n = 12 содержит 157 элементов И-НЕ и 12 элементов НЕ.
Основными недостатками известного устройства при n = 12 являются: 1) высокая конструктивная сложность, равная 458; 2) низкое быстродействие, которое составляет 14τ.
Наиболее близким по функциональным возможностям и конструкции техническим
решением к предлагаемому устройству является устройство для вычисления полиномиальных симметрических булевых функций одиннадцати переменных, содержащее элемент
ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом
пять, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом восемь, элемент ИСКЛЮЧАЮЩЕЕ
ИЛИ с порогом девять и элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом одиннадцать, элемент И и элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА [2].
Устройство-прототип, как и заявляемое устройство, содержит элемент СЛОЖЕНИЕ
ПО МОДУЛЮ ДВА, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом восемь и элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом
девять, выход каждого из которых соединен со входом элемента СЛОЖЕНИЕ ПО
МОДУЛЮ ДВА, выход которого соединен с выходом устройства.
Недостатком устройства-прототипа являются ограниченные функциональные возможности, поскольку устройство не позволяет вычислять полиномиальные симметрические булевы функции двенадцати переменных.
Изобретение направлено на решение технической задачи расширения функциональных возможностей устройства-прототипа за счет вычисления (реализации) полиномиальных симметрических булевых функций двенадцати переменных.
Устройство для вычисления полиномиальных симметрических булевых функций двенадцати переменных характеризуется тем, что содержит элемент СЛОЖЕНИЕ ПО МО-
2
BY 16553 C1 2012.12.30
ДУЛЮ ДВА и с первого по шестой элементы ИСКЛЮЧАЮЩЕЕ ИЛИ, выполненные с
порогами четыре, восемь, девять, десять, двенадцать и тринадцать соответственно.
Выход i-го элемента ИСКЛЮЧАЮЩЕЕ ИЛИ, где i = 1, 2, ..., 6, соединен с i-м входом
элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, выход которого соединен с выходом устройства, j-й информационный вход которого, где j = 1, 2, ..., 12, соединен с j-м входом i-го
элемента ИСКЛЮЧАЮЩЕЕ ИЛИ.
Первый настроечный вход устройства соединен с тринадцатым входом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре, четырнадцатый и пятнадцатый входы которого
соединены со вторым настроечным входом устройства, а шестнадцатый и семнадцатый
входы - с третьим настроечным входом устройства.
Четвертый настроечный вход устройства соединен с тринадцатым входом элемента
ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом восемь, четырнадцатый и пятнадцатый входы которого соединены с пятым настроечным входом устройства.
Шестой настроечный вход устройства соединен с тринадцатым и четырнадцатым входами элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом девять, пятнадцатый, шестнадцатый,
семнадцатый и восемнадцатый входы которого соединены с седьмым настроечным входом устройства.
Восьмой настроечный вход устройства соединен с тринадцатым, четырнадцатым и
пятнадцатым входами элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом десять.
Девятый настроечный вход устройства соединен с тринадцатым входом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом двенадцать, четырнадцатый и пятнадцатый входы которого соединены с десятым настроечным входом устройства.
Одиннадцатый настроечный вход устройства соединен с тринадцатым и четырнадцатым входами элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом тринадцать.
Основной технический результат изобретения заключается в расширении функциональных возможностей устройства за счет реализации полиномиальных симметрических
булевых функций двенадцати переменных. Названный технический эффект достигнут на
основе использования новых логических элементов (элементов ИСКЛЮЧАЮЩЕЕ ИЛИ с
порогами десять, двенадцать и тринадцать).
На фигуре представлена логическая схема устройства для вычисления полиномиальных симметрических булевых функций двенадцати переменных, а посредством таблицы
представлен способ его настройки.
Устройство для вычисления полиномиальных симметрических булевых функций двенадцати переменных содержит элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре 1, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом восемь 2, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с
порогом девять 3, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом десять 4, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом двенадцать 5, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом
тринадцать 6, элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА 7, двенадцать информационных
входов 8...19, одиннадцать настроечных входов 20...30 и выход 31.
Устройство для вычисления полиномиальных симметрических булевых функций двенадцати переменных работает следующим образом. На информационные входы устройства 8...19 поступают (в произвольном порядке) значения переменных x1, x2, ..., x12, а на
настроечные входы 20...30 - сигналы настройки u1, u2, ..., u11, значения которых принадлежат множеству {0,1}. На выходе устройства 31 реализуется полиномиальная
симметрическая булева функция F = Ek12(x1, x2, ..., x12), определяемая вектором
настройки u(F) = (u1, u2, ..., u11), где k = 1, 2, ..., 12.
Поясним принцип построения и работы устройства для вычисления полиномиальных
симметрических булевых функций двенадцати переменных.
Известно, что произвольная симметрическая булева функция n переменных
F = F(x1, x2, ..., xn) с рабочими числами a1, a2, ..., ar (0 ≤ r ≤ n + 1) принимает значение 1 на
тех и только тех наборах значений переменных X = {x1, x2, ..., xn}, которые содержат ров3
BY 16553 C1 2012.12.30
но aj(j = 1, 2, ..., r) единиц. Такая булева функция обозначается F = Fna1 , a 2 , ..., a r ( x1 , x 2 , ..., x n ) .
Если r = 1, то симметрическая булева функция F = Fna ( x1 , x 2 , ..., x n ) называется фундаментальной (или элементарной).
Симметрическая булева функция n переменных F = Fna1 ,a 2 ,...,a r (X) называется полиномиальной (или полиномиально-однородной), если ее полином Жегалкина содержит ровно
C kn (число сочетаний из n по k) различных элементарных конъюнкций ранга k, где
k = 1, 2, ..., n. Такая симметрическая булева функция обозначается через F = E kn (X) .
Устройство (фигура) синтезировано на основе применения следующих аналитических
представлений полиномиальных симметрических булевых функций двенадцати переменk
ных F = F = E12
(x1,x2,...,x12):
E112 (X) = F121 (X) ∨ F123 (X) ∨ F125 (X) ∨ F127 (X) ∨ F129 (X) ∨ F1211 (X),
2
E12
(X) = F122 (X) ∨ F123 (X) ∨ F126 (X) ∨ F127 (X) ∨ F1210 (X) ∨ F1211 (X),
3
E12
(X) = F123 (X) ∨ F127 (X) ∨ F1211 (X),
4
E12
(X) = F124 (X) ∨ F125 (X) ∨ F126 (X) ∨ F127 (X) ∨ F1212 (X),
5
E12
(X) = F125 (X) ∨ F127 (X),
6
E12
(X) = F126 (X) ∨ F127 (X),
7
E12
(X) = F127 (X),
8
E12
(X) = F128 (X) ∨ F129 (X) ∨ F1210 (X) ∨ F1211 (X) ∨ F1212 (X),
9
E12
(X) = F129 (X) ∨ F1211 (X),
10
11
E10
12 ( X ) = F12 ( X ) ∨ F12 ( X ),
11
12
E11
и E12
12 ( X ) = F12 ( X )
12 ( X ) = F12 ( X ).
Первообразная функция устройства для вычисления полиномиальных симметрических булевых функций двенадцати переменных имеет вид
F( x1 , x 2 ,..., x12 , u1 , u 2 ,..., u11 ) = F174 ( x1 , x 2 ,..., x12 , u1 , u 2 , u 2 , u 3 , u 3 ) ⊕
⊕ F178 ( x1 , x 2 ,..., x12 , u 4 , u 5 , u 5 ) ⊕
⊕ F189 ( x1 , x 2 ,..., x12 , u 6 , u 6 , u 7 , u 7 , u 7 , u 7 ) ⊕ F1510 ( x1 , x 2 ,..., x12 , u 8 , u 8 , u 8 ) ⊕
⊕ F1512 ( x1 , x 2 ,..., x12 , u 9 , u10 , u10 ) ⊕ F1413 ( x1 , x 2 ,..., x12 , u11 , u11 ).
В таблице представлена настройка устройства на реализацию полиномиальных симметрических булевых функций двенадцати переменных.
Рассмотрим пример. Допустим, что на выходе 31 устройства требуется вычислить (реализовать) полиномиальную симметрическую булеву функцию
2
E12
( x1 , x 2 ,..., x12 ) = x1x 2 ⊕ x1x 3 ⊕ x1x 4 ⊕ x1x 5 ⊕ x1x 6 ⊕ x1x 7 ⊕ x1x 8 ⊕ x1x 9 ⊕
⊕ x1x10 ⊕ x1x11 ⊕ x1x12 ⊕ x 2 x 3 ⊕ x 2 x 4 ⊕ x 2 x 5 ⊕ x 2 x 6 ⊕ x 2 x 7 ⊕ x 2 x 8 ⊕ x 2 x 9 ⊕
⊕ x 2 x10 ⊕ x 2 x11 ⊕ x 2 x12 ⊕ x 3 x 4 ⊕ x 3 x 5 ⊕ x 3 x 6 ⊕ x 3 x 7 ⊕ x 3 x 8 ⊕ x 3 x 9 ⊕ x 3 x10 ⊕
⊕ x 3 x11 ⊕ x 3 x12 ⊕ x 4 x 5 ⊕ x 4 x 6 ⊕ x 4 x 7 ⊕ x 4 x 8 ⊕ x 4 x 9 ⊕ x 4 x10 ⊕ x 4 x11 ⊕ x 4 x12 ⊕
⊕ x 5 x 6 ⊕ x 5 x 7 ⊕ x 5 x 8 ⊕ x 5 x 9 ⊕ x 5 x10 ⊕ x 5 x11 ⊕ x 5 x12 ⊕ x 6 x 7 ⊕ x 6 x 8 ⊕ x 6 x 9 ⊕
⊕ x 6 x10 ⊕ x 6 x11 ⊕ x 6 x12 ⊕ x 7 x 8 ⊕ x 7 x 9 ⊕ x 7 x10 ⊕ x 7 x11 ⊕ x 7 x12 ⊕ x 8 x 9 ⊕
⊕ x 8 x10 ⊕ x 8 x11 ⊕ x 8 x12 ⊕ x 9 x10 ⊕ x 9 x11 ⊕ x 9 x12 ⊕ x10 x11 ⊕ x10 x12 ⊕ x11x12 .
В таком случае, согласно таблице настроек (таблица), необходимо положить
u1 = u3 = u4 = u9 = 0 и u2 = u5 = u6 = u7 = u8 = u10 = u11 = 1.
4
BY 16553 C1 2012.12.30
Тогда первообразная функция устройства принимает вид
F( x1 , x 2 , ..., x12 , 0, 1, 0, 0, 1, 1, 1, 1, 0, 1, 1) = F174 ( x1 , x 2 ,..., x12 ,0,1,1,0,0) ⊕
⊕ F158 ( x1 , x 2 , ..., x12 , 0, 1, 1) ⊕ F189 ( x1 , x 2 , ..., x12 , 1, 1, 1, 1, 1, 1) ⊕
⊕ F1510 ( x1 , x 2 , ..., x12 , 1, 1, 1) ⊕ F1512 ( x1 , x 2 , ..., x12 , 0, 1, 1) ⊕ F1413 ( x1 , x 2 , ..., x12 , 1, 1) =
= F122 (X) ⊕ F126 (X) ⊕ F123 (X) ⊕ F127 (X) ⊕ ⊕ F1210 (X) ⊕ F1211 (X) =
2
= F122 (X) ∨ F126 (X) ∨ F123 (X) ∨ F127 (X) ∨ F1210 (X) ∨ F1211 (X) = E12
(X).
Основным достоинством заявляемого устройства являются широкие функциональные
возможности, поскольку его применение позволяет вычислить (реализовать) любую полиномиальную симметрическую булеву функцию двенадцати переменных.
Дополнительными достоинствами устройства являются: а) низкая конструктивная
сложность (по числу входов логических элементов), равная 100; б) небольшое число
внешних выводов, равное 24; в) высокое быстродействие, определяемое глубиной схемы и
равное 2τ.
Сигналы настройки
u5
u6
u7
u8
u9
u10
u11
Выход
F
26
27
28
29
30
31
1
1
1
1
1
1
F121
1
1
1
1
0
1
1
F122
1
0
1
1
0
0
1
1
F123
0
0
1
0
1
1
0
0
0
F124
0
0
1
1
1
1
1
1
0
1
F125
1
0
0
0
1
1
1
1
1
0
1
F126
1
1
1
1
1
0
1
1
1
0
1
F127
1
1
1
0
0
0
0
0
0
0
1
F128
1
0
0
1
0
1
1
1
1
1
1
F129
1
0
0
1
0
1
1
1
0
1
1
F1210
1
0
0
1
0
1
1
1
1
0
0
F1211
1
0
0
1
0
1
1
1
0
0
0
F1212
u1
u2
u3
u4
20
21
22
23
24
25
1
1
0
1
1
0
1
0
0
1
1
1
0
0
1
Источники информации:
1. А.с. СССР 1478208, МПК G 06F 7/00, 1989.
2. Заявка на патент РБ 20091501, МПК G 06F 7/00, 2010 (прототип).
Национальный центр интеллектуальной собственности.
220034, г. Минск, ул. Козлова, 20.
5
Документ
Категория
Без категории
Просмотров
0
Размер файла
195 Кб
Теги
by16553, патент
1/--страниц
Пожаловаться на содержимое документа