close

Вход

Забыли?

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

?

Патент BY10219

код для вставкиСкачать
ОПИСАНИЕ
ИЗОБРЕТЕНИЯ
К ПАТЕНТУ
РЕСПУБЛИКА БЕЛАРУСЬ
(46) 2008.02.28
(12)
(51) МПК (2006)
НАЦИОНАЛЬНЫЙ ЦЕНТР
ИНТЕЛЛЕКТУАЛЬНОЙ
СОБСТВЕННОСТИ
(54)
BY (11) 10219
(13) C1
(19)
G 06F 7/00
УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ СИММЕТРИЧЕСКИХ
БУЛЕВЫХ ФУНКЦИЙ
(21) Номер заявки: a 20060388
(22) 2006.04.24
(43) 2006.10.30
(71) Заявитель: Белорусский государственный университет (BY)
(72) Автор: Супрун Валерий Павлович
(BY)
(73) Патентообладатель: Белорусский государственный университет (BY)
(56) BY a 20030644, 2004.
BY 1587 C1, 1997.
BY 5838 C1, 2003.
SU 1681302 A1, 1991.
BY 10219 C1 2008.02.28
(57)
Устройство для вычисления симметрических булевых функций, содержащее элемент
СЛОЖЕНИЕ ПО МОДУЛЮ ДВА и элемент ИСКЛЮЧАЮЩЕЕ ИЛИ, i-й, где i = 1, 2, 3, 4,
вход которого соединен с i-м входом устройства, выход устройства соединен с выходом
элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, первый вход которого соединен с выходом
элемента ИСКЛЮЧАЮЩЕЕ ИЛИ, а второй вход соединен с пятым входом устройства,
отличающееся тем, что содержит элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре,
выход которого соединен с третьим входом элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, а
i-й вход соединен с i-м входом устройства, шестой вход которого соединен с пятым входом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре, шестой и седьмой входы которого соединены с седьмым входом устройства, восьмой и девятый входы устройства соединены, соответственно, с пятым и шестым входами элемента ИСКЛЮЧАЮЩЕЕ ИЛИ.
BY 10219 C1 2008.02.28
Изобретение относится к области вычислительной техники и микроэлектроники и
предназначено для реализации симметрических булевых функций четырех переменных.
Известно устройство для вычисления симметрических булевых функций четырех переменных, содержащее элемент ИЛИ, элемент И, мажоритарный элемент с порогом два,
мажоритарный элемент с порогом пять, элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, четыре информационных входа, пять настроечных входов и выход [1].
Недостатком устройства является высокая конструктивная сложность по числу входов
логических элементов.
Наиболее близким по функциональным возможностям и конструкции техническим
решением к предлагаемому является устройство для вычисления симметрических булевых
функций четырех переменных, содержащее элемент ИЛИ, элемент ИСКЛЮЧАЮЩЕЕ
ИЛИ, мажоритарный элемент с порогом два, элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА,
тринадцать входов и один выход [2]. Конструктивная сложность устройства (по числу
входов логических элементов) равна 16, а его быстродействие, определяемое глубиной
схемы, составляет 2τ, где τ - усредненная задержка на один логический элемент.
Недостатком известного устройства для вычисления симметрических булевых функций четырех переменных является большое число внешних выводов (число входов и выход), равное 14.
Изобретение направлено на решение следующей технической задачи: уменьшение
числа внешних выводов устройства для вычисления симметрических булевых функций
четырех переменных.
Устройство для вычисления симметрических булевых функций содержит элемент
СЛОЖЕНИЕ ПО МОДУЛЮ ДВА и элемент ИСКЛЮЧАЮЩЕЕ ИЛИ, i-й (i = 1, 2, 3, 4),
вход которого соединен с i-м входом устройства. Выход устройства соединен с выходом
элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, первый вход которого соединен с выходом
элемента ИСКЛЮЧАЮЩЕЕ ИЛИ, а второй вход соединен с пятым входом устройства. В
отличие от прототипа в устройство дополнительно введен элемент ИСКЛЮЧАЮЩЕЕ
ИЛИ с порогом четыре, выход которого соединен с третьим входом элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, а i-й вход соединен с i-м входом устройства. Шестой вход устройства соединен с пятым входом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре,
шестой и седьмой входы которого соединены с седьмым входом устройства. Восьмой и
девятый входы устройства соединены, соответственно, с пятым и шестым входами элемента ИСКЛЮЧАЮЩЕЕ ИЛИ.
Названный технический результат достигается путем использования нового логического элемента (элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре) с последующим
удалением четырех входов устройства.
На чертеже (фигура) представлена логическая схема устройства для вычисления симметрических булевых функций четырех переменных.
Устройство для вычисления симметрических булевых функций содержит элемент
ИСКЛЮЧАЮЩЕЕ ИЛИ 1, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре 2, элемент
СЛОЖЕНИЕ ПО МОДУЛЮ ДВА 3, девять входов 4, 5,…, 12 и выход 13.
Устройство для вычисления симметрических булевых функций четырех переменных
работает следующим образом. На входы устройства 4, 5,…, 12 поступают сигналы настройки u1, u2,…, u9, значения которых принадлежат множеству {0, 1, х1, x1 , х2, x 2 , х3,
x 3 , х4, x 4 }. На выходе 13 реализуется симметрическая булева функция четырех переменных F = F(x1, x2, x3, x4), определяемая вектором настройки U = (u1, u2,…, u9).
2
BY 10219 C1 2008.02.28
Известно, что произвольная симметрическая булева функция n переменных F = F{x1,
x2,…, xn) с рабочими числами al, 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 + l)-разрядного двоичного кода π(F) = (π0, π1,…, πn), где πi = 1 (0 ≤ i ≤ n) тогда и только тогда, когда i ∈{а1, а2,…, аr}.
Первообразная устройства для вычисления симметрических булевых функций четырех переменных имеет вид
F(ul, u2,…, u9) = F61(ul, u2, u3, u4, u5, u6)⊕F74(u3, u4, u5, u6, u7, u8, u8)⊕u9,
1, если u1 + u 2 + u 3 + u 4 + u 5 + u 6 = 1;
где F61 (u1 , u 2 , u 3 , u 4 , u 5 , u 6 ) = 
0 − в противном случае
1, если u 3 + u 4 + u 5 + u 6 + u 7 + 2u 8 = 4;
и F74 (u 3 , u 4 , u 5 , u 6 , u 7 , u 8 , u 8 ) = 
0 − в противном случае.
В таблице представлен способ настройки устройства на реализацию произвольных
симметрических булевых функций четырех переменных. В данной таблице симметрическая булева функция F = F(x1, x2, x3, x4), реализуемая на выходе устройства, представлена
в виде своего двоичного кода π(F) = (π0, π1, π2, π3, π4).
Рассмотрим пример настройки устройства (фигура) на реализацию (вычисление) симметрической булевой функции четырех переменных. Допустим, что на выходе 13 устройства требуется реализовать симметрическую булеву функцию F(x1, x2, x3,
x4) = x1 x 2 x 3 x 4 ∨ х1 х2 ∨ х1 х3 ∨ х1 х4 ∨ х2 х3 ∨ х2 х4 ∨ х3 х4.
Так как рабочими числами функции F являются 0, 2, 3 и 4, то ее двоичный код π(F) равен (1, 0, 1, 1, 1). Тогда из таблицы настройки следует, что для реализации функции F на
выходе 13 устройства необходимо на входы 4, 5,…, 12 подать значения 1, 1, х1, х2, х3, х4, 1,
1, 1 соответственно.
Основным достоинством устройства для вычисления симметрических булевых функций четырех переменных является небольшое число внешних выводов (устройство имеет
на четыре входа меньше, чем устройство - прототип). При этом конструктивная сложность
(по числу входов логических элементов) и быстродействие предлагаемого устройства и
устройства-прототипа совпадают.
Источники информации:
1. Патент РБ 2119, МПК G 06F 7/00, 1998.
2. Патент РБ 7947, МПК G 06F 7/00, 2006 (прототип).
3
BY 10219 C1 2008.02.28
u3
6
x1
x1
x1
Сигналы настройки
u4
u5
u6
7
8
9
х2
х3
х4
x2
х3
х4
х2
х3
х4
x3
x2
x4
х2
х3
х4
x3
x2
x4
u1
4
0
1
1
0
1
0
u2
5
0
1
1
1
1
1
0
0
1
0
0
0
0
0
0
1
0
1
1
0
0
1
0
1
1
1
x1
x1
x1
x1
x1
x1
x1
x1
х1
x2
х2
х2
х2
х2
х2
х2
х2
х2
x1
x2
1
0
0
0
0
0
0
1
0
0
1
1
1
0
1
0
0
1
1
0
x1
x1
x1
x1
x1
x1
x1
x1
x1
x2
х2
х2
х2
х2
х2
х2
х2
х2
x1
x2
0
1
0
1
1
0
1
1
1
1
1
0
x1
x1
x2
х2
x1
x1
x1
х1
x2
х2
х2
х2
x1
x1
x1
x3
х3
х3
х3
х3
х3
х3
х3
х3
x3
x4
х4
х4
х4
х4
х4
х4
х4
х4
x3
х3
х3
х3
х3
х3
х3
х3
х3
x3
x4
х4
х4
х4
х4
х4
х4
х4
х4
x3
х3
x3
х3
х3
х3
x4
х4
x4
x4
x4
х4
х4
х4
u7
10
1
0
1
1
0
0
u8
11
1
0
0
1
1
1
u9
12
0
0
0
0
0
0
Выход
π(F)
13
00000
00001
00010
00011
00100
00101
0
1
1
0
1
0
0
1
0
0
1
1
1
0
0
1
1
0
0
0
0
1
0
0
0
1
0
1
1
1
00110
00111
01000
01001
01010
01011
01100
01101
01110
01111
0
0
1
0
0
1
0
1
1
0
0
0
0
1
1
0
0
1
1
1
0
0
0
1
0
1
1
1
0
1
10000
10001
10010
10011
10100
10101
10110
10111
11000
11001
0
0
1
1
0
1
1
1
1
0
0
1
1
1
1
1
1
1
11010
11011
11100
11101
11110
11111
Национальный центр интеллектуальной собственности.
220034, г. Минск, ул. Козлова, 20.
4
Документ
Категория
Без категории
Просмотров
0
Размер файла
103 Кб
Теги
by10219, патент
1/--страниц
Пожаловаться на содержимое документа