close

Вход

Забыли?

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

?

Патент BY11275

код для вставкиСкачать
ОПИСАНИЕ
ИЗОБРЕТЕНИЯ
К ПАТЕНТУ
РЕСПУБЛИКА БЕЛАРУСЬ
(46) 2008.10.30
(12)
(51) МПК (2006)
НАЦИОНАЛЬНЫЙ ЦЕНТР
ИНТЕЛЛЕКТУАЛЬНОЙ
СОБСТВЕННОСТИ
(54)
BY (11) 11275
(13) C1
(19)
G 06F 7/00
УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ СИММЕТРИЧЕСКИХ
БУЛЕВЫХ ФУНКЦИЙ ПЯТИ ПЕРЕМЕННЫХ
(21) Номер заявки: a 20070511
(22) 2007.05.04
(43) 2007.10.30
(71) Заявитель: Белорусский государственный университет (BY)
(72) Автор: Супрун Валерий Павлович
(BY)
(73) Патентообладатель: Белорусский государственный университет (BY)
(56) BY 2793 C1, 1999.
BY 8619 C1, 2006.
SU 1716502 A1, 1992.
SU 1748149 A1, 1992.
SU 1832273 A2, 1993.
BY 11275 C1 2008.10.30
(57)
Устройство для вычисления симметрических булевых функций пяти переменных, содержащее элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА и мажоритарный элемент с порогом
три, i-й, где i = 1, …, 6, вход которого соединен с i-м входом устройства, выход которого
соединен с выходом элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, первый вход которого
соединен с выходом мажоритарного элемента с порогом три, а второй вход – с седьмым
входом устройства, отличающееся тем, что содержит элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с
порогом два и элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом шесть, j-й, где j = 1, …, 5, вход
BY 11275 C1 2008.10.30
которого соединен с j-м входом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом два и с j-м
входом устройства, восьмой вход которого соединен с седьмым и восьмым входами мажоритарного элемента с порогом три, а девятый вход – с шестым входом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом два, седьмой и восьмой входы которого соединены с
десятым входом устройства, а выход - с третьим входом элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, четвертый вход которого соединен с выходом элемента ИСКЛЮЧАЮЩЕЕ
ИЛИ с порогом шесть, шестой вход которого соединен с одиннадцатым входом устройства, двенадцатый вход которого соединен с седьмым и восьмым входами элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом шесть.
Изобретение относится к области вычислительной техники и микроэлектроники и
предназначено для реализации симметрических булевых функций пяти переменных.
Известно устройство для вычисления симметрических булевых функций пяти переменных, содержащее два элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, мажоритарный элемент с порогом два, мажоритарный элемент с порогом четыре, пять элементов И, пять
информационных входов, шесть настроечных входов и выход [1].
Недостатком устройства является высокая конструктивная сложность по числу входов
логических элементов.
Наиболее близким по функциональным возможностям и конструкции техническим
решением к предлагаемому является устройство для вычисления симметрических булевых
функций пяти переменных, содержащее мажоритарный элемент с порогом два, мажоритарный элемент с порогом три, мажоритарный элемент с порогом четыре, мажоритарный
элемент с порогом пять, мажоритарный элемент с порогом шесть, элемент СЛОЖЕНИЕ
ПО МОДУЛЮ ДВА, пять информационных входов, шесть настроечных входов и выход
[2]. Конструктивная сложность устройства (по числу входов логических элементов) равна
36, а его быстродействие, определяемое глубиной схемы, составляет 2τ, где τ усредненная задержка на один логический элемент.
Недостатком известного устройства для вычисления симметрических булевых функций пяти переменных является высокая конструктивная сложность по числу входов логических элементов.
Изобретение направлено на решение технической задачи уменьшения конструктивной
сложности устройства для вычисления симметрических булевых функций пяти переменных.
Устройство для вычисления симметрических булевых функций содержит элемент
СЛОЖЕНИЕ ПО МОДУЛЮ ДВА и мажоритарный элемент с порогом три, i-й (i = 1, 2,...,
6) вход которого соединен с i-м входом устройства.
Выход устройства соединен с выходом элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА,
первый вход которого соединен с выходом мажоритарного элемента с порогом три, а второй вход соединен с седьмым входом устройства.
В отличие от прототипа устройство дополнительно содержит элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом два и элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом шесть, j-й
(j = 1, 2,..., 5) вход которого соединен с j-м входом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с
порогом два и с j-м входом устройства.
Восьмой вход устройства соединен с седьмым и восьмым входами мажоритарного
элемента с порогом три, а девятый вход устройства соединен с шестым входом элемента
ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом два, седьмой и восьмой входы которого соединены с
десятым входом устройства.
Выход элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом два соединен с третьим входом
элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, четвертый вход которого соединен с выходом
элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом шесть.
2
BY 11275 C1 2008.10.30
Шестой вход элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом шесть соединен с одиннадцатым входом устройства, двенадцатый вход которого соединен с седьмым и восьмым
входами элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом шесть.
Названный технический результат достигается путем использования новых логических элементов (элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом два и элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом шесть).
На чертеже (фигура) представлена логическая схема устройства для вычисления симметрических булевых функций пяти переменных.
Устройство для вычисления симметрических булевых функций содержит элемент
ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом два 1, мажоритарный элемент с порогом три 2, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом шесть 3, элемент СЛОЖЕНИЕ ПО МОДУЛЮ
ДВА 4, двенадцать входов 5, 6,…, 16 и выход 17.
Устройство для вычисления симметрических булевых функций пяти переменных работает следующим образом. На входы устройства 5, 6,..., 16 поступают сигналы настройки
u1,u2,…,u12, где u1,u2,…, u7 ∈ {0,1} и u 8 , u 9 ,..., u12 ∈ {x1 , x1 , x 2 , x 2 , x 3 , x 3 , x 4 , x 4 , x 5 , x 5 }.
На выходе устройства 17 реализуется симметрическая булева функция
F = F(x1,x2,x3,x4,x5), определяемая вектором настройки U = (u1,u2,...,u12}.
Известно, что произвольная симметрическая булева функция n переменных
F = F(x1,x2,…,xn) с рабочими числами a1,a2,…,ar (0 ≤ r ≤ n) принимает значение 1 на тех и
только тех наборах значений переменных x1,x2,...,xn, которые содержат ровно аj (j = 1,2,...,
r) единиц. Такая симметрическая булева функция F = Fna 1 , a 2 ,..., a r ( x1 , x 2 ,..., x n ) задается посредством (n + 1)-разрядного двоичного кода π(F) = (π0,π1,….,πn), где πi = 1(0 ≤ i ≤ n) тогда
и только тогда, когда i ∈ {а1,а2,…,ar}.
Первообразная устройства для вычисления симметрических булевых функций пяти
переменных имеет вид
F(u1,u2,…,u12) = u1 ⊕ F82(u2,u3,u3,u8,u9,u10,u11,u12)⊕F83,4,…,8(u4,u5,u5,u8,u9,u10,u11,u12)⊕
F86(u6,u7,u7,u8,u9,u10,u11,u12),
где
1, если u 2 + 2u 3 + u 8 + u 9 + u10 + u11 + u12 = 2;
F82 (u 2 , u 3 , u 3 , u 8 , u 9 , u10 , u11 , u12 ) = 
0 − в противном случае;
1, если u 4 + 2u 5 + u 8 + u 9 + u10 + u11 + u12 ≥ 3;
F83, 4,...,8 (u 4 , u 5 , u 5 , u 8 , u 9 , u10 , u11 , u12 ) = 
0 − в противном случае;
1, если u 6 + 2u 7 + u 8 + u 9 + u10 + u11 + u12 = 6;
F86 (u 6 , u 7 , u 7 , u 8 , u 9 , u10 , u11 , u12 ) = 
0 − в противном случае.
В таблице представлен способ настройки устройства на реализацию произвольных
симметрических булевых функций пяти переменных. В данной таблице симметрическая
булева функция F = F(х1,х2,х3,х4,х5), реализуемая на выходе устройства, представлена в
виде двоичного кода π(F) = (π0,π1,π2,π3,π4,π5).
Рассмотрим пример настройки устройства на реализацию (вычисление) симметрической булевой функции пяти переменных. Допустим, что на выходе 17 устройства требуется реализовать симметрическую булеву функцию
F( x1 , x 2 , x 3 , x 4 , x 5 ) = x1 ⋅ x 2 ⋅ x 3 ⋅ x 4 ⋅ x 5 ∨ x1 ⋅ x 2 ⋅ x 3 ⋅ x 4 ⋅ x 5 .
Так как рабочими числами функции F являются 0 и 5, то ее двоичный код π(F) равен
(1,0,0,0,0,1). Тогда из таблицы настройки (таблица) следует, что для реализации функции
F на выходе 17 устройства необходимо на его входы 5,6,...,16 подать значения
1,0,1,1,1,1,0,x1,x2,x3,x4,x5 соответственно.
3
BY 11275 C1 2008.10.30
Основным достоинством предлагаемого устройства для вычисления симметрических
булевых функций пяти переменных является небольшая конструктивная сложность (по
числу входов логических элементов), равная 28. Отметим, что сложность устройствапрототипа равна 36. При этом быстродействие предлагаемого устройства и устройствапрототипа совпадают.
Устройство для вычисления симметрических булевых функций пяти переменных
u1
u2
u3
u4
u5
u6
u7
u8
u9
u10
u11
u12
π(F)
5
6
7
8
9
10
11
12
13
14
15
16
17
1
1
1
1
1
0
0
x1
x2
x3
x4
x5
000000
1
0
1
1
1
0
0
x1
х2
x3
x4
x5
100000
1
1
0
1
1
0
0
x1
x2
x3
x4
x5
010000
0
1
1
0
0
1
1
x1
x2
x3
x4
x5
110000
1
0
0
1
1
0
0
x1
x2
x3
x4
x5
001000
0
1
1
0
0
0
1
x1
x2
x3
x4
x5
101000
0
1
1
0
0
1
0
x1
x2
x3
x4
x5
011000
0
1
1
0
0
0
0
x1
x2
x3
x4
x5
111000
1
0
0
1
1
0
0
x1
x2
x3
x4
x5
000100
1
0
1
1
1
1
1
x1
x2
x3
x4
x5
100100
1
1
0
1
1
1
1
x1
x2
x3
x4
x5
010100
0
1
1
1
0
1
1
x1
x2
x3
x4
x5
110100
1
0
0
1
1
1
1
x1
x2
x3
x4
x5
001100
0
1
1
1
0
0
1
x1
x2
x3
x4
x5
101100
0
1
1
1
0
1
0
x1
x2
x3
x4
x5
011100
0
1
1
1
0
0
0
x1
x2
x3
x4
x5
111100
1
1
0
1
1
0
0
x1
x2
x3
x4
x5
000010
1
1
0
1
1
1
0
x1
x2
x3
x4
x5
100010
1
1
0
1
1
0
1
x1
x2
x3
x4
x5
010010
0
1
0
0
0
1
1
x1
x2
x3
x4
x5
110010
1
0
0
1
1
0
1
x1
x2
x3
x4
x5
001010
0
1
0
0
0
0
1
x1
x2
x3
x4
x5
101010
0
1
0
0
0
1
0
x1
x2
x3
x4
x5
011010
0
1
0
0
0
0
0
x1
x2
x3
x4
x5
111010
0
1
1
0
0
1
0
x1
x2
x3
x4
x5
000110
0
0
1
0
0
1
0
x1
x2
x3
x4
x5
100110
0
1
0
0
0
1
0
x1
x2
x3
x4
x5
010110
4
BY 11275 C1 2008.10.30
Продолжение таблицы
u11
u12
π(F)
u1
u2
u3
u4
u5
u6
u7
u8
u9
u10
5
6
7
8
9
10
11
12
13
14
15
16
17
0
0
0
1
1
1
0
x1
x2
x3
x4
x5
110110
0
1
1
1
0
1
0
x1
x2
x3
x4
x5
001110
0
1
0
1
1
1
0
x1
x2
x3
x4
x5
101110
0
0
1
1
1
1
0
x1
x2
x3
x4
x5
011110
0
1
1
1
1
1
0
x1
x2
x3
x4
x5
111110
1
1
1
1
1
1
0
x1
x2
x3
x4
x5
000001
1
0
1
1
1
1
0
x1
x2
x3
x4
x5
100001
1
1
0
1
1
1
0
x1
x2
x3
x4
x5
010001
1
1
1
1
0
1
0
x1
x2
x3
x4
x5
110001
1
0
0
1
1
1
0
x1
x2
x3
x4
x5
001001
1
1
0
0
0
1
0
x1
x2
x3
x4
x5
101001
1
0
1
0
0
1
0
x1
x2
x3
x4
x5
011001
1
1
1
0
0
1
0
x1
x2
x3
x4
x5
111001
1
1
0
0
0
0
0
x1
x2
x3
x4
x5
000101
1
1
0
0
0
1
0
x1
x2
x3
x4
x5
100101
1
1
0
0
0
0
1
x1
x2
x3
x4
x5
010101
0
0
0
1
1
0
1
x1
x2
x3
x4
x5
110101
1
1
0
0
0
1
1
x1
x2
x3
x4
x5
001101
0
1
0
1
1
0
1
x1
x2
x3
x4
x5
101101
0
1
0
1
1
1
0
x1
x2
x3
x4
x5
011101
0
1
0
1
1
0
0
x1
x2
x3
x4
x5
111101
1
1
1
1
0
0
0
x1
x2
x3
x4
x5
000011
1
1
1
1
0
1
0
x1
x2
x3
x4
x5
100011
1
1
1
1
0
0
1
x1
x2
x3
x4
x5
010011
0
0
0
1
1
1
1
x1
x2
x3
x4
x5
110011
1
1
1
1
0
1
1
x1
x2
x3
x4
x5
001011
0
1
0
1
1
1
1
x1
x2
x3
x4
x5
101011
0
0
1
1
1
1
1
x1
x2
x3
x4
x5
011011
0
0
0
1
1
0
0
x1
x2
x3
x4
x5
111011
1
1
1
0
0
0
0
x1
x2
x3
x4
x5
000111
1
1
1
0
0
1
0
x1
x2
x3
x4
x5
100111
5
BY 11275 C1 2008.10.30
Продолжение таблицы
u11
u12
π(F)
u1
u2
u3
u4
u5
u6
u7
u8
u9
u10
5
6
7
8
9
10
11
12
13
14
15
16
17
1
1
1
0
0
0
1
x1
x2
x3
x4
x5
010111
0
0
0
1
1
0
0
x1
x2
x3
x4
x5
110111
1
1
1
0
0
1
1
x1
x2
x3
x4
x5
001111
0
1
0
1
1
0
0
x1
x2
x3
x4
x5
101111
0
0
1
1
1
0
0
x1
x2
x3
x4
x5
011111
0
1
1
1
1
0
0
x1
x2
x3
x4
x5
111111
Источники информации:
1. А.с. СССР 1832273, МПК G 06F 7/00, 1993.
2. Патент РБ 2793, МПК G 06 F 7/00, 1999 (прототип).
Национальный центр интеллектуальной собственности.
220034, г. Минск, ул. Козлова, 20.
6
Документ
Категория
Без категории
Просмотров
0
Размер файла
347 Кб
Теги
by11275, патент
1/--страниц
Пожаловаться на содержимое документа