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

(51) МПК (2006) НАЦИОНАЛЬНЫЙ ЦЕНТР ИНТЕЛЛЕКТУАЛЬНОЙ СОБСТВЕННОСТИ УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ ПОЛИНОМИАЛЬНЫХ СИММЕТРИЧЕСКИХ БУЛЕВЫХ ФУНКЦИЙ(71) Заявитель Белорусский государственный университет(72) Авторы Супрун Валерий Павлович Седун Андрей Максимович(73) Патентообладатель Белорусский государственный университет(57) Устройство для вычисления полиномиальных симметрических булевых функций, содержащее элемент ИСКЛЮЧАЮЩЕЕ ИЛИ, -й, где 1, 2, , 5, вход которого соединен с -м входом устройства, отличающееся тем, что содержит элемент ИЛИ и элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре, -й, где 1, 2, , 4, вход которого соединен с-м входом устройства, -й, где 6, 7, вход которого соединен с (-1)-м входом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре, а пятый вход соединен с шестым входом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ, выход которого соединен с первым входом элемента ИЛИ, второй вход которого соединен с выходом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре, а выход соединен с выходом устройства. Изобретение относится к области вычислительной техники и микроэлектроники и предназначено для вычисления полиномиальных симметрических булевых функций четырех переменных. Известно устройство для вычисления симметрических булевых функций четырех переменных, содержащее мажоритарный элемент с порогом два, элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ и элемент ИЛИ 1. 11027 1 2008.08.30 Недостатком устройства являются большая конструктивная сложность (по числу входов логических элементов) и большое число внешних выводов. Наиболее близким по функциональным возможностям и конструкции техническим решением к предлагаемому является устройство для вычисления симметрических булевых функций четырех переменных, которое содержит элемент ИСКЛЮЧАЮЩЕЕ ИЛИ, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом два, элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА,двенадцать входов и выход 2. Недостатком устройства является большое число внешних выводов, которое равно 13. Изобретение направлено на решение технической задачи уменьшения числа внешних выводов при вычислении полиномиальных симметрических булевых функций четырех переменных. Устройство для вычисления полиномиальных симметрических булевых функций содержит элемент ИСКЛЮЧАЮЩЕЕ ИЛИ, -й (1, 2, , 5) вход которого соединен с -м входом устройства. В отличие от прототипа устройство дополнительно содержит элемент ИЛИ и элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре, -й (1, 2, , 4) вход которого соединен с -м входом устройства. Причем -й (6, 7) вход устройства соединен с(-1)-м входом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре, а пятый вход соединен с шестым входом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ. Выход элемента ИСКЛЮЧАЮЩЕЕ ИЛИ соединен с первым входом элемента ИЛИ, второй вход которого соединен с выходом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре, а выход соединен с выходом устройства. Названный технический результат достигается путем использования новых логических элементов (элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре и элемента ИЛИ). На чертеже (фигура) представлена логическая схема устройства для вычисления полиномиальных симметрических булевых функций четырех переменных. Устройство для вычисления полиномиальных симметрических булевых функций содержит элемент ИСКЛЮЧАЮЩЕЕ ИЛИ 1, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре 2, элемент ИЛИ 3, семь входов 4, 5, , 10 и один выход 11. Устройство для вычисления полиномиальных симметрических булевых функций четырех переменных работает следующим образом. На входы устройства 4, 5, , 10 поступают сигналы настройки 1, 2, , 7, значения которых принадлежат множеству 0, 1, 1 , 1 ,2 ,2 ,3 ,3 ,4 ,4 . На выходе устройства 11 реализуется полиномиальная симметрическая булева функция(, 2, 3, 4), определяемая вектором настройки(1, 2, , 7). Поясним принцип построения и работы устройства для вычисления полиномиальных симметрических булевых функций четырех переменных. Известно, что произвольная симметрическая булева функцияпеременных(,2, , ) с рабочими числами 1, 2, ,(0) принимает значение 1 на тех и только тех наборах значений переменных, 2, , , которые содержат ровно(1, 2,, ) единиц. Такая булева функция обозначается через 1 ,2 (1 ,2 ) . Если 1, то симметрическая булева функция(1 ,2 ) называется фундаментальной (или элементарной). Симметрическая булева функцияпеременных 1 ,2 ( ) называется полиномиальной, если ее полином Жегалкина содержит только элементарные конъюнкции, ранг которых равен , где 1. Такая полиномиальная симметрическая булева функцияпеременных обозначается через( ) . Очевидно, что полином Жегалкина функции( ) содержит(число сочетаний изпо ) элементарных конъюнкций ранга , где 1, 2, , . 11027 1 2008.08.30 Предлагаемое устройство (фигура) синтезировано на основе применения следующих аналитических представлений полиномиальных симметрических булевых функций четырех переменных( )(1 ,2 ,3 ,4 )4 4 1 3 2 3 3 1 ( )4 ( )4 ( ),2 ( )4 ( )4 ( ),3 ( )4 ( ) и 4 4 4 44 ( )4 ( ) . 4 В таблице представлена настройка устройства на вычисление (реализацию) полиномиальных симметрических булевых функций четырех переменных. Достоинством устройства для вычисления полиномиальных симметрических булевых функций четырех переменных является небольшое число внешних выводов, равное 8(число внешних выводов устройства-прототипа равно 13). Также отметим высокое быстродействие устройства, которое равно 2, где- усредненная задержка на один логический элемент, и низкую конструктивную сложность по числу входов логических элементов, равную 14. Национальный центр интеллектуальной собственности. 220034, г. Минск, ул. Козлова, 20.