close

Вход

Забыли?

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

?

Патент BY14564

код для вставкиСкачать
ОПИСАНИЕ
ИЗОБРЕТЕНИЯ
К ПАТЕНТУ
РЕСПУБЛИКА БЕЛАРУСЬ
(46) 2011.06.30
(12)
(51) МПК
НАЦИОНАЛЬНЫЙ ЦЕНТР
ИНТЕЛЛЕКТУАЛЬНОЙ
СОБСТВЕННОСТИ
(54)
BY (11) 14564
(13) C1
(19)
G 06F 7/00
(2006.01)
УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ
ФУНДАМЕНТАЛЬНЫХ СИММЕТРИЧЕСКИХ БУЛЕВЫХ
ФУНКЦИЙ ПЯТНАДЦАТИ ПЕРЕМЕННЫХ
(21) Номер заявки: a 20091361
(22) 2009.09.22
(43) 2010.02.28
(71) Заявитель: Белорусский государственный университет (BY)
(72) Автор: Супрун Валерий Павлович
(BY)
(73) Патентообладатель: Белорусский государственный университет (BY)
(56) BY 5174 C1, 2003.
BY 2117 C1, 1998.
SU 1789978 A1, 1993.
SU 1833860 A1, 1993.
BY 14564 C1 2011.06.30
(57)
Устройство для вычисления фундаментальных симметрических булевых функций
пятнадцати переменных, содержащее элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом семь, iй, где i = 1, 2,…, 18, вход которого соединен с i-м входом устройства, а выход - с выходом
устройства, причем девятнадцатый вход элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом
семь соединен с семнадцатым входом устройства, восемнадцатый вход которого соединен
с двадцатым, двадцать первым и двадцать вторым входами элемента ИСКЛЮЧАЮЩЕЕ
ИЛИ с порогом семь.
BY 14564 C1 2011.06.30
Изобретение относится к области вычислительной техники и микроэлектроники и
предназначено для реализации фундаментальных симметрических булевых функций пятнадцати переменных.
Известно устройство для вычисления фундаментальных симметрических булевых
функций пятнадцати переменных, содержащее мажоритарный элемент с порогом пятнадцать, мажоритарный элемент с порогом шестнадцать, элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, пятнадцать информационных и четыре настроечных входов, выход [1].
Недостатками известного устройства являются высокая конструктивная сложность и
низкое быстродействие, определяемое глубиной схемы.
Наиболее близким по функциональным возможностям и конструкции техническим
решением к предлагаемому устройству является устройство для вычисления фундаментальных симметрических булевых функций пятнадцати переменных, содержащее мажоритарный элемент с порогом семь, мажоритарный элемент с порогом восемь, элемент
СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, восемнадцать настроечных входов и выход [2].
Недостатками устройства-прототипа для вычисления фундаментальных симметрических булевых функций являются: 1) высокая конструктивная сложность (по числу входов
логических элементов), равная 46; 2) низкое быстродействие, определяемое глубиной
схемы, которое составляет 2τ, где τ - задержка на один логический элемент.
Изобретение направлено на решение следующих технических задач: понижение конструктивной сложности (по числу входов логических элементов) и повышение быстродействия устройства для вычисления фундаментальных симметрических булевых
функций пятнадцати переменных.
Устройство для вычисления фундаментальных симметрических булевых функций
пятнадцати переменных содержит элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом семь, i-й,
где i = 1, 2,…, 18, вход которого соединен с i-м входом устройства. Выход элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом семь соединен с выходом устройства. Причем девятнадцатый вход элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом семь соединен с семнадцатым
входом устройства, восемнадцатый вход которого соединен с двадцатым, двадцать первым и двадцать вторым входами элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом семь.
Названный технический результат достигается путем использования нового логического элемента (элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом семь).
На фигуре представлена схема устройства для вычисления фундаментальных симметрических булевых функций пятнадцати переменных.
Устройство для вычисления фундаментальных симметрических булевых функций содержит элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом семь 1, восемнадцать входов 2, 3,…,
19 и выход 20.
Устройство для вычисления фундаментальных симметрических булевых функций работает следующим образом. На входы устройства 2, 3,…, 19 поступают сигналы настройки u1, u2,…, u18, значения которых принадлежат множеству x1 , x1 , x 2 , x 2 ,…, x15 , x15 ,0,1 , а на
выходе реализуется фундаментальная симметрическая булева функция пятнадцати переменных F = F(x1, x2,…, x15), определяемая вектором настройки U(F) = (u1, u2,…, u18).
Известно, что произвольная симметрическая булева функция n переменных F = F(x1,
x2,…, xn) с рабочими числами a1, a2,…, ar (0 ≤ r ≤ n + 1) принимает значение 1 на тех и
только тех наборах значений переменных x1, x2,…, xn, которые содержат ровно aj (j = 1,
2,…, r) единиц. Такая симметрическая булева функция F = Fna1 ,a 2 ,…,a r (x1, x 2 ,…, x n ) задается посредством (n + 1)-разрядного двоичного (локального) кода π(F) = (π0, π1,…, πn), где
πi = 1 (0 ≤ i ≤ n) тогда и только тогда, когда i ∈ {a1, a2,…, ar}.
Если r = 1, то симметрическая булева функция F = Fna называется фундаментальной
(или элементарной), т.е.
{
2
}
BY 14564 C1 2011.06.30
1, если x1 + x 2 + … + x n = a;
Fna (x1 , x 2 ,…, x n ) = 
0 - в противном случае.
На выходе n-входового элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом а реализуется
фундаментальная симметрическая булева функция
F( x1, x 2 ,…, x n ) = Fna ( x1, x 2 ,…, x n ).
Первообразная функция устройства для вычисления фундаментальных симметрических булевых функций пятнадцати переменных имеет вид:
F15a ( x1 , x 2 ,…, x15 ) = F227 (u1 , u 2 ,…, u16 , u17 , u17 , u18 , u18 , u18 , u18 ),
где a = 0, 1,…, 15.
Посредством таблицы представлена настройка устройства на реализацию шестнадцати
фундаментальных симметрических булевых функций пятнадцати переменных.
u1 u2
2 3
x1 x2
Устройство для вычисления фундаментальных симметрических
булевых функций пятнадцати переменных
Сигналы настройки
Выход
u3 u4 u5 u6 u7 u8 u9 u10 u11 u12 u13 u14 u15 u16 u17 u18
F
4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
20
0
x3 x4 x5 x6 x7 x8 x9 x10 x11 x12 x13 x14 x15 1
1
1
F15
x1 x2 x3 x4 x5 x6 x7 x8 x9 x10 x11
x12
x13
x14
x15
0
1
1
1
F15
x1 x2 x3 x4 x5 x6 x7 x8 x9 x10 x11
x12
x13
x14
x15
1
0
1
2
F15
x1 x2 x3 x4 x5 x6 x7 x8 x9 x10 x11
x12
x13
x14
x15
0
0
1
3
F15
x1 x2 x3 x4 x5 x6 x7 x8 x9 x10 x11
x12
x13
x14
x15
1
1
0
4
F15
x1 x2 x3 x4 x5 x6 x7 x8 x9 x10 x11
x12
x13
x14
x15
0
1
0
5
F15
x1 x2 x3 x4 x5 x6 x7 x8 x9 x10 x11
x12
x13
x14
x15
1
0
0
6
F15
x1 x2 x3 x4 x5 x6 x7 x8 x9 x10 x11
x12
x13
x14
x15
0
0
0
7
F15
x1 x 2 x 3 x 4 x 5 x 6 x 7 x8 x 9 x10 x11 x12 x13
x14 x15
0
0
0
8
F15
x1 x 2 x 3 x 4 x 5 x 6 x 7 x8 x 9 x10 x11 x12 x13
x14 x15
1
0
0
9
F15
x1 x 2 x 3 x 4 x 5 x 6 x 7 x8 x 9 x10 x11 x12 x13
x14 x15
0
1
0
10
F15
x1 x 2 x 3 x 4 x 5 x 6 x 7 x8 x 9 x10 x11 x12 x13
x14 x15
1
1
0
11
F15
x1 x 2 x 3 x 4 x 5 x 6 x 7 x8 x 9 x10 x11 x12 x13
x14 x15
0
0
1
12
F15
x1 x 2 x 3 x 4 x 5 x 6 x 7 x8 x 9 x10 x11 x12 x13
x14 x15
1
0
1
13
F15
x1 x 2 x 3 x 4 x 5 x 6 x 7 x8 x 9 x10 x11 x12 x13
x14 x15
0
1
1
14
F15
x1 x 2 x 3 x 4 x 5 x 6 x 7 x8 x 9 x10 x11 x12 x13
x14 x15
1
1
1
15
F15
Пример 1
Допустим, что на выходе заявляемого устройства требуется реализовать фундаментальную симметрическую булеву функцию
F( x1, x 2 ,…, x14 , x15 ) = x1x 2 … x14 x15 ∨ x1 x 2 … x14 x15 ∨ … ∨ x1x 2 … x14 x15 ∨ x1x 2 … x14 x15 .
Так как рабочим числом заданной симметрической булевой функции является a = 14,
то согласно таблице настройки (таблица) для реализации на выходе устройства функции
3
BY 14564 C1 2011.06.30
F(x1 , x 2 ,…, x15 ) = F1514 (x1 , x 2 ,…, x15 ) необходимо на его входы подать следующие значения
настройки: u1 = x1, u 2 = x 2 ,…, u15 = x15 , u16 = 0, u17 = 1 и u18 = 1.
В таком случае первообразная функция устройства принимает вид:
F15a ( x1 , x 2 ,…, x15 ) = F227 ( x1 , x 2 ,…, x15 ,0, 1, 1, 1, 1, 1, 1) = F151 ( x1 , x 2 ,…, x15 ) = F1514 ( x1 , x 2 ,…, x15 ).
Следует отметить, что заявляемое устройство для вычисления фундаментальных симметрических булевых функций пятнадцати переменных можно обобщить на случай вычисления фундаментальных симметрических булевых функций n переменных при
условии, что n = 2m - 1, где m ≥ 2.
В общем случае устройство будет содержать единственный элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом 2m-1 - 1, а число его настроечных входов будет равно n + m - 1.
Сложность такого устройства (по числу входов логического элемента ИСКЛЮЧАЮЩЕЕ
ИЛИ) вычисляется по формуле
m −1
n +1
3n − 1
l = n + ∑ 2 j−1 = n + 2m −1 − 1 = n +
.
−1 =
2
2
j=1
Пример 2
Если n = 3, то m = 2, и устройство для вычисления фундаментальных симметрических
булевых функций трех переменных будет содержать элемент ИСКЛЮЧАЮЩЕЕ ИЛИ,
порог которого равен единице [3].
При этом устройство будет иметь n + m - 1 = 4 настроечных входов, а его сложность
3n − 1
= 4.
будет составлять l =
2
Пример 3.
Пусть n = 7, тогда m = 3, и устройство для вычисления фундаментальных симметрических булевых функций семи переменных будет содержать элемент ИСКЛЮЧАЮЩЕЕ
3n − 1
ИЛИ с порогом три, число входов которого равно l =
= 10. Такое устройство для
2
вычисления фундаментальных симметрических булевых функций семи переменных имеет
меньшую сложность по сравнению с существующим аналогом [4]. Сложность устройства
равна 10, в то время как сложность аналога составляет 14.
Основными достоинствами заявляемого устройства для вычисления фундаментальных
симметрических булевых функций пятнадцати переменных являются: 1) низкая конструктивная сложность (по числу входов логических элементов), равная 22; 2) высокое быстродействие, которое составляет τ, где τ - задержка на логический элемент.
Источники информации:
1. Патент РБ 2990, МПК G 06F 7/00, 1999.
2. Патент РБ 5174, МПК G 06F 7/00, 2003 (прототип).
3. Патент РБ 5938, МПК G 06F 7/00, 2004.
4. Патент РБ 8421, МПК G 06F 7/00, 2006.
Национальный центр интеллектуальной собственности.
220034, г. Минск, ул. Козлова, 20.
4
Документ
Категория
Без категории
Просмотров
0
Размер файла
178 Кб
Теги
by14564, патент
1/--страниц
Пожаловаться на содержимое документа