close

Вход

Забыли?

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

?

Патент BY5838

код для вставкиСкачать
ОПИСАНИЕ
ИЗОБРЕТЕНИЯ
К ПАТЕНТУ
РЕСПУБЛИКА БЕЛАРУСЬ
BY (11) 5838
(13) C1
(19)
7
(51) G 06F 7/00
(12)
НАЦИОНАЛЬНЫЙ ЦЕНТР
ИНТЕЛЛЕКТУАЛЬНОЙ
СОБСТВЕННОСТИ
(54)
УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ СИММЕТРИЧЕСКИХ
БУЛЕВЫХ ФУНКЦИЙ ТРЕХ ПЕРЕМЕННЫХ
(21) Номер заявки: a 20010403
(22) 2001.04.28
(46) 2003.12.30
(71) Заявитель: Белорусский государственный университет (BY)
(72) Автор: Супрун Валерий Павлович; Седун Андрей Максимович (BY)
(73) Патентообладатель: Белорусский государственный университет (BY)
(57)
Устройство для вычисления симметрических булевых функций трех переменных, содержащее элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, выход которого соединен с выходом
устройства, отличающееся тем, что содержит элемент ИСКЛЮЧАЮЩЕЕ ИЛИ и мажоритарный элемент с порогом три, i-й вход которого, где i = 1, 2, 3, соединен с i-м входом
элемента ИСКЛЮЧАЮЩЕЕ ИЛИ и i-м входом устройства, четвертый вход которого соединен с четвертым входом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ, а пятый и шестой входы
устройства соединены с четвертым и пятым входами мажоритарного элемента с порогом
три соответственно, выход которого соединен с первым входом элемента СЛОЖЕНИЕ
ПО МОДУЛЮ ДВА, второй вход которого соединен с выходом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ, а третий вход соединен с седьмым входом устройства.
BY 5838 C1
(56)
BY 2118 C1, 1998.
BY 2377 C1, 1998.
BY 2119 C1, 1998.
RU 2047892 C1, 1995.
SU 1487024 A1, 1989.
SU 1432500 A1, 1988.
US 4336468, 1982.
JP 58048153, 1983.
Фиг. 1
BY 5838 C1
Изобретение относится к области вычислительной техники и микроэлектроники и
предназначено для реализации симметрических булевых функций трех переменных.
Известно устройство для вычисления симметрических булевых функций трех переменных,
содержащее шесть элементов И, три элемента СЛОЖЕНИЕ ПО МОДУЛЮ, семь входов и выход [1].
Недостатком устройства является высокая конструктивная сложность по числу входов
логических элементов.
Наиболее близким по функциональным возможностям и конструкции техническим
решением является устройство для вычисления симметрических булевых функций трех
переменных, содержащее элемент ИЛИ, мажоритарный элемент с порогом два, элемент И,
элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, семь входов и выход [2].
Недостатком известного устройства для вычисления симметрических булевых функций является высокая конструктивная сложность, которая по числу входов логических
элементов равна 17.
Изобретение направлено на решение технической задачи понижения конструктивной
сложности устройства для вычисления симметрических булевых функций трех переменных.
Устройство для вычисления симметрических булевых функций трех переменных содержит
элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, выход которого соединен с выходом устройства. В
отличие от прототипа устройство дополнительно содержит элемент ИСКЛЮЧАЮЩЕЕ ИЛИ и
мажоритарный элемент с порогом три, i-й вход которого, где i = 1, 2, 3, соединен с i-м входом
элемента ИСКЛЮЧАЮЩЕЕ ИЛИ и i-м входом устройства. Четвертый вход устройства соединен с четвертым входом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ, а пятый и шестой входы устройства соединены с четвертым и пятым входами мажоритарного элемента с порогом три
соответственно. Выход мажоритарного элемента с порогом три соединен с первым входом
элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, второй вход которого соединен с выходом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ, а третий вход соединен с седьмым входом устройства.
Названный технический результат достигается путем использования нового логического элемента (элемента ИСКЛЮЧАЮЩЕЕ ИЛИ), а также изменением межсоединений
элементов в логической схеме устройства.
На чертеже (фиг. 1) представлена схема устройства для вычисления симметрических
булевых функций трех переменных.
Устройство для вычисления симметрических булевых функций содержит элемент
ИСКЛЮЧАЮЩЕЕ ИЛИ 1, мажоритарный элемент с порогом три 2, элемент СЛОЖЕНИЕ
ПО МОДУЛЮ ДВА 3, семь входов 4, 5,…, 10 и выход 11.
Устройство для вычисления симметрических булевых функций работает следующим
образом. На входы устройства 4, 5,…, 10 поступают сигналы настройки u1, u2,…, u7, значения которых принадлежат множеству {0,1,x1, x 1 ,x2, x 2 ,x3, x 3 }. На выходе 11 реализуется симметрическая булева функция F = F(x1,х2,х3), определяемая вектором настройки
U = (u1,u2,…,u7).
Известно, что произвольная симметрическая булева функция n переменных F = F(x1,
x2,…, xn) с рабочими числами a1, a2,…, ar (0 ≤ r ≤ n) принимает значение 1 на тех и только тех
наборах значений переменных x1, x2,…, xn, которые содержат ровно aj (j = 1, 2,…, r) единиц.
Такая симметрическая булева функция обозначается через F = Fna1 , a2 ,!, ar ( x1 , x2 ,!, xn ) и
задается посредством (n + l) - разрядного двоичного кода π(F) = (π0,π1,…,πn), где πi = 1
(0 ≤ i ≤ n) тогда и только тогда, когда i∈{a1, a2,…,ar}. Если r = 1, то симметрическая булева
функция F = Fna называется фундаментальной (или элементарной), т.е.
1, если x1 + x2 + ! + xn = a;
Fna ( x1 , x2 , ! , xn ) = 
0, в противном случае.
2
BY 5838 C1
На выходе n - входового мажоритарного элемента с порогом а реализуется монотонная симметрическая булева функция
M na ( x1 , x2 ,!, xn ) = Fna , a +1,!, n ( x1 , x2 ,!, xn ) , т.е.
1, если x1 + x2 + ! + xn ≥ a;
M na ( x1 , x2 , ! , xn ) = 
0, в противном случае.
Первообразная устройства для вычисления симметрических булевых функций трех
переменных имеет вид
F (u1 , u 2 , ! , u7 ) = F41 (u1 , u 2 , u3 , u 4 ) ⊕ M 53 (u1 , u 2 , u3 , u5 , u 6 ) ⊕ u7 .
В таблице (фиг. 2) представлена настройка устройства на реализацию симметрических
булевых функций трех переменных.
Рассмотрим пример настройки устройства (фиг. 1) на реализацию (вычисление) симметрической булевой функции трех переменных.
Допустим на выходе 11 устройства требуется реализовать симметрическую булеву функцию
F (x1 , x2 , x3 ) = x1 x2 x3 ∨ x1 x2 ∨ x1 x3 ∨ x2 x3 .
Так как рабочими числами функции F являются 0,2 и 3, то двоичный код
π(F) = (1,0,1,1) и из таблицы настройки (фиг. 2) следует, что для реализации F на входы
4,5,…,10 устройства необходимо подать x1,х2,х3,1,0,1,0 соответственно.
Достоинством устройства для вычисления симметрических булевых функций трех переменных является низкая конструктивная сложность по числу входов логических элементов равная 12, в то время как сложность прототипа равна 17.
Источники информации:
1. А.с. СССР 1689943, МПК G06 F 7/00, 1991.
2. Патент Республики Беларусь 2118, МПК G06 F 7/00, 1998 // БИ № 2 (17). - С. 143
(прототип).
Фиг. 2
Национальный центр интеллектуальной собственности.
220034, г. Минск, ул. Козлова, 20.
3
Документ
Категория
Без категории
Просмотров
0
Размер файла
166 Кб
Теги
by5838, патент
1/--страниц
Пожаловаться на содержимое документа