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

(51) МПК (2009) НАЦИОНАЛЬНЫЙ ЦЕНТР ИНТЕЛЛЕКТУАЛЬНОЙ СОБСТВЕННОСТИ УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ ПОЛИНОМИАЛЬНЫХ СИММЕТРИЧЕСКИХ БУЛЕВЫХ ФУНКЦИЙ ПЯТИ ПЕРЕМЕННЫХ(71) Заявитель Белорусский государственный университет(72) Авторы Супрун Валерий Павлович Седун Андрей Максимович(73) Патентообладатель Белорусский государственный университет(57) Устройство для вычисления полиномиальных симметрических булевых функций пяти переменных, характеризующееся тем, что содержит элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, элемент И, первый и второй элементы ЗАПРЕТ, мажоритарный элемент с порогом два и мажоритарный элемент с порогом четыре, -й, где 1, 2, , 5, вход которого соединен с -м входом устройства, с -м входом мажоритарного элемента с порогом два и с -м входом элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, выход которого соединен с первым входом элемента И, с первым прямым входом первого элемента ЗАПРЕТ и с первым выходом устройства, второй выход которого соединен с выходом второго элемента ЗАПРЕТ,прямой вход которого соединен с выходом мажоритарного элемента с порогом два и со вторым прямым входом первого элемента ЗАПРЕТ, выход которого соединен с третьим выходом устройства, четвертый выход которого соединен с входами запрета первого и второго элементов ЗАПРЕТ, с выходом мажоритарного элемента с порогом четыре и со вторым входом элемента И, выход которого соединен с пятым выходом устройства. 13387 1 2010.06.30 Изобретение относится к области вычислительной техники и микроэлектроники и предназначено для вычисления полиномиальных симметрических булевых функций пяти переменных. Известно устройство для вычисления симметрических булевых функций пяти переменных, содержащее мажоритарный элемент с порогом два, мажоритарный элемент с порогом три, мажоритарный элемент с порогом четыре, мажоритарный элемент с порогом пять, мажоритарный элемент с порогом шесть, элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА,пять информационных входов, шесть настроечных входов и выход 1. Известное устройство, как и предлагаемое устройство, содержит элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА,мажоритарные элементы с порогом два и с порогом четыре. Конструктивная сложность устройства (по числу входов логических элементов) равна 36, а его быстродействие, определяемое глубиной схемы, составляет 2, где- усредненная задержка на один логический элемент. Недостатком известного устройства является большая конструктивная сложность. Наиболее близким по функциональным возможностям и конструкции техническим решением к предлагаемому устройству является устройство для вычисления симметрических булевых функций пяти переменных, которое содержит элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом два, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом шесть, мажоритарный элемент с порогом три, элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, двенадцать входов и выход 2. Конструктивная сложность устройства (по числу входов логических элементов) равна 28, а быстродействие составляет 2, где- задержка на один логический элемент. Недостатком устройства-прототипа является высокая конструктивная сложность. Как и изобретение, устройство-прототип содержит элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА. Изобретение направлено на решение технической задачи уменьшения конструктивной сложности устройства при вычислении полиномиальных симметрических булевых функций пяти переменных. Устройство для вычисления полиномиальных симметрических булевых функций пяти переменных содержит элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, элемент И, первый и второй элементы ЗАПРЕТ, мажоритарный элемент с порогом два и мажоритарный элемент с порогом четыре. При этом -й, где 1, 2, , 5, вход мажоритарного элемента с порогом четыре соединен с -м входом устройства, с -м входом мажоритарного элемента с порогом два и с -м входом элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА. Выход элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА соединен с первым входом элемента И, с первым прямым входом первого элемента ЗАПРЕТ и с первым выходом устройства. Второй выход устройства соединен с выходом второго элемента ЗАПРЕТ, прямой вход которого соединен с выходом мажоритарного элемента с порогом два и со вторым прямым входом первого элемента ЗАПРЕТ, выход которого соединен с третьим выходом устройства. Четвертый выход устройства соединен с входами запрета первого и второго элементов ЗАПРЕТ, с выходом мажоритарного элемента с порогом четыре и со вторым входом элемента И, выход которого соединен с пятым выходом устройства. Названный технический результат достигается путем использования новых логических элементов (мажоритарных элементов с порогами два и четыре, элементов ЗАПРЕТ и элемента И). На чертеже (фигура) представлена логическая схема устройства для вычисления полиномиальных симметрических булевых функций пяти переменных. Устройство для вычисления полиномиальных симметрических булевых функций пяти переменных содержит элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА 1, мажоритарный эле 2 13387 1 2010.06.30 мент с порогом четыре 2, мажоритарный элемент с порогом два 3, элемент И 4, два элемента ЗАПРЕТ 5 и 6, пять входов 711 и пять выходов 1216. Устройство для вычисления полиномиальных симметрических булевых функций пяти переменных работает следующим образом. На входы устройства 711 поступают (в произвольном порядке) значения переменных 1, 2, , 5. На выходах устройства 1216 реализуется полиномиальные симметрические булевы функции( 1,2 , ,5 ) ,5 5 соответственно, где 1, 2, , 5. Поясним принцип построения и работы устройства для вычисления полиномиальных симметрических булевых функций пяти переменных. Известно, что произвольная симметрическая булева функцияпеременных(1, 2, , ) с рабочими числами 1, 2, ,(0) принимает значение 1 на тех и только тех наборах значений переменных 1, 2, , , которые содержат ровно а (1, 2, , ) единиц. Такая булева функция обозначается через 1 , 2 ( 1,2 , ,) . Если 1, то симметрическая булева функция Симметрическая булева функцияпеременных 1 , 2 называется полиномиальной, если ее полином Жегалкина содержит только элементарные конъюнкции, ранг которых равен , где 1. Такая полиномиальная симметрическая булева функцияпеременных обозначается через. Очевидно, что полином Жегалкина функции содержит(число сочетаний изпо ) элементарных конъюнкций ранга ,где 1, 2, , . Предлагаемое устройство (фигура) синтезировано на основе применения следующих аналитических представлений полиномиальных симметрических булевых функций( 1,2 , ,5 ) , где 1, 2, , 5 5 5 1 3 5 2 2 3 1555,555,5 3 4 4 5 535,555 и 55. 5 5 Основным достоинством предлагаемого устройства для вычисления полиномиальных симметрических булевых функций пяти переменных является небольшая конструктивная сложность, которая (по числу входов логических элементов) равна 22 (сложность устройства-прототипа равна 28). Также отметим, что предлагаемое устройство (в отличие от устройства-прототипа) не имеет настроечных входов, что позволяет вычислять полиномиальные симметрические булевы функции пяти переменных одновременно. Национальный центр интеллектуальной собственности. 220034, г. Минск, ул. Козлова, 20. 3