Устройство для вычисления симметрических булевых функций трех переменных

(12) НАЦИОНАЛЬНЫЙ ЦЕНТР ИНТЕЛЛЕКТУАЛЬНОЙ СОБСТВЕННОСТИ УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ СИММЕТРИЧЕСКИХ БУЛЕВЫХ ФУНКЦИЙ ТРЕХ ПЕРЕМЕННЫХ(71) Заявитель Белорусский государственный университет(72) Автор Супрун Валерий Павлович Седун Андрей Максимович(73) Патентообладатель Белорусский государственный университет(57) Устройство для вычисления симметрических булевых функций трех переменных, содержащее элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, выход которого соединен с выходом устройства, отличающееся тем, что содержит элемент ИСКЛЮЧАЮЩЕЕ ИЛИ и мажоритарный элемент с порогом три, -й вход которого, где 1, 2, 3, соединен с -м входом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ и -м входом устройства, четвертый вход которого соединен с четвертым входом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ, а пятый и шестой входы устройства соединены с четвертым и пятым входами мажоритарного элемента с порогом три соответственно, выход которого соединен с первым входом элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, второй вход которого соединен с выходом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ, а третий вход соединен с седьмым входом устройства. 5838 1 Изобретение относится к области вычислительной техники и микроэлектроники и предназначено для реализации симметрических булевых функций трех переменных. Известно устройство для вычисления симметрических булевых функций трех переменных,содержащее шесть элементов И, три элемента СЛОЖЕНИЕ ПО МОДУЛЮ, семь входов и выход 1. Недостатком устройства является высокая конструктивная сложность по числу входов логических элементов. Наиболее близким по функциональным возможностям и конструкции техническим решением является устройство для вычисления симметрических булевых функций трех переменных, содержащее элемент ИЛИ, мажоритарный элемент с порогом два, элемент И,элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, семь входов и выход 2. Недостатком известного устройства для вычисления симметрических булевых функций является высокая конструктивная сложность, которая по числу входов логических элементов равна 17. Изобретение направлено на решение технической задачи понижения конструктивной сложности устройства для вычисления симметрических булевых функций трех переменных. Устройство для вычисления симметрических булевых функций трех переменных содержит элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, выход которого соединен с выходом устройства. В отличие от прототипа устройство дополнительно содержит элемент ИСКЛЮЧАЮЩЕЕ ИЛИ и мажоритарный элемент с порогом три, -й вход которого, где 1, 2, 3, соединен с -м входом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ и -м входом устройства. Четвертый вход устройства соединен с четвертым входом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ, а пятый и шестой входы устройства соединены с четвертым и пятым входами мажоритарного элемента с порогом три соответственно. Выход мажоритарного элемента с порогом три соединен с первым входом элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, второй вход которого соединен с выходом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ, а третий вход соединен с седьмым входом устройства. Названный технический результат достигается путем использования нового логического элемента (элемента ИСКЛЮЧАЮЩЕЕ ИЛИ), а также изменением межсоединений элементов в логической схеме устройства. На чертеже (фиг. 1) представлена схема устройства для вычисления симметрических булевых функций трех переменных. Устройство для вычисления симметрических булевых функций содержит элемент ИСКЛЮЧАЮЩЕЕ ИЛИ 1, мажоритарный элемент с порогом три 2, элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА 3, семь входов 4, 5 10 и выход 11. Устройство для вычисления симметрических булевых функций работает следующим образом. На входы устройства 4, 5 10 поступают сигналы настройки 1, 2 7, значения которых принадлежат множеству 0,1,1,1 ,2,2 ,3,3 . На выходе 11 реализуется симметрическая булева функция(1,х 2,х 3), определяемая вектором настройки(1,27). Известно, что произвольная симметрическая булева функцияпеременных(1,2 ) с рабочими числами 1, 2(0) принимает значение 1 на тех и только тех наборах значений переменных 1, 2 , которые содержат ровно(1, 2 ) единиц. Такая симметрическая булева функция обозначается через 1 , 2 ( 1 , 2 ) и задается посредством - разрядного двоичного кода(0,1), где 1(0) тогда и только тогда, когда 1, 2. Если 1, то симметрическая булева функцияназывается фундаментальной (или элементарной), т.е. 1, если 12( 1 , 2 ,,)0, в противном случае. 2 5838 1 На выходе- входового мажоритарного элемента с порогом а реализуется монотонная симметрическая булева функция( 1 , 2 ,,)0, в противном случае. Первообразная устройства для вычисления симметрических булевых функций трех переменных имеет вид 1 3(1 ,2 ,, 7 )4 (1 ,2 , 3 ,4 )5 (1 ,2 , 3 , 5 ,6 )7 . В таблице (фиг. 2) представлена настройка устройства на реализацию симметрических булевых функций трех переменных. Рассмотрим пример настройки устройства (фиг. 1) на реализацию (вычисление) симметрической булевой функции трех переменных. Допустим на выходе 11 устройства требуется реализовать симметрическую булеву функцию(1 , 2 , 3 )1 2 31 21 32 3 . Так как рабочими числами функцииявляются 0,2 и 3, то двоичный код(1,0,1,1) и из таблицы настройки (фиг. 2) следует, что для реализациина входы 4,510 устройства необходимо подать 1,х 2,х 3,1,0,1,0 соответственно. Достоинством устройства для вычисления симметрических булевых функций трех переменных является низкая конструктивная сложность по числу входов логических элементов равная 12, в то время как сложность прототипа равна 17. Источники информации 1. А.с. СССР 1689943, МПК 067/00, 1991. 2. Патент Республики Беларусь 2118, МПК 067/00, 1998 // БИ 2 (17). - С. 143 Национальный центр интеллектуальной собственности. 220034, г. Минск, ул. Козлова, 20. 3