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

(51) МПК (2009) НАЦИОНАЛЬНЫЙ ЦЕНТР ИНТЕЛЛЕКТУАЛЬНОЙ СОБСТВЕННОСТИ УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ ПОЛИНОМИАЛЬНЫХ СИММЕТРИЧЕСКИХ БУЛЕВЫХ ФУНКЦИЙ(71) Заявитель Белорусский государственный университет(72) Автор Супрун Валерий Павлович(73) Патентообладатель Белорусский государственный университет(57) Устройство для вычисления полиномиальных симметрических булевых функций, содержащее элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре и элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом пять, -й (1, 26) вход которого соединен с -м информационным входом устройства и с -м входом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре, выход которого соединен с первым входом элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, выход которого соединен с выходом устройства, а второй вход соединен с выходом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом 13248 1 2010.06.30 пять, седьмой и восьмой входы которого соединены с первым настроечным входом устройства, второй настроечный вход которого соединен с седьмым входом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре, восьмой и девятый входы которого соединены с третьим настроечным входом устройства, отличающееся тем, что содержит элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом восемь и элемент И, -й (1, 27) вход которого соединен с -м информационным входом устройства и с -м входом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом восемь, восьмой вход которого соединен с четвертым настроечным входом устройства, пятый настроечный вход которого соединен с девятым и десятым входами элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом восемь, выход которого соединен с третьим входом элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, четвертый вход которого соединен с выходом элемента И, а седьмой информационный вход устройства соединен с десятым входом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре и с девятым входом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом пять. Изобретение относится к области вычислительной техники и микроэлектроники и предназначено для вычисления полиномиальных симметрических булевых функций семи переменных. Известно устройство для вычисления фундаментальных симметрических булевых функций семи переменных, содержащее элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом три,девять настроечных входов и выход 1. Конструктивная сложность устройства (по числу входов логических элементов) равна 10, а его быстродействие, определяемое глубиной схемы, составляет , где- усредненная задержка на один логический элемент. Недостатком известного устройства являются низкие функциональные возможности,поскольку устройство не позволяет вычислять полиномиальные симметрические булевы функции семи переменных. Устройство, предназначенное для вычисления фундаментальных симметрических булевых функций семи переменных, как и предлагаемое устройство,содержит элемент ИСКЛЮЧАЮЩЕЕ ИЛИ, только выполненное с порогом три. Наиболее близким по функциональным возможностям и конструкции техническим решением к предлагаемому является устройство для вычисления полиномиальных симметрических булевых функций шести переменных, которое содержит элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом пять,элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом шесть, элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, шесть информационных входов, четыре настроечных входа и выход 2. Конструктивная сложность устройства (по числу входов логических элементов) равна 27, а быстродействие составляет 2, где- задержка на один логический элемент. Недостатком устройства-прототипа являются низкие функциональные возможности,так как это устройство не позволяет вычислять полиномиальные симметрические булевы функции семи переменных. Как и предлагаемое изобретение, устройство-прототип содержит элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом пять и элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, выход которого соединен с выходом устройства. Изобретение направлено на решение технической задачи расширения функциональных возможностей устройства за счет реализации (вычисления) полиномиальных симметрических булевых функций семи переменных. Устройство для вычисления полиномиальных симметрических булевых функций содержит элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре и элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом пять, -й (1, 2 6) вход 13248 1 2010.06.30 которого соединен с -м информационным входом устройства и с -м входом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре. Выход элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре соединен с первым входом элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, выход которого соединен с выходом устройства, а второй вход соединен с выходом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом пять, седьмой и восьмой входы которого соединены с первым настроечным входом устройства. Второй настроечный вход устройства соединен с седьмым входом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре, восьмой и девятый входы которого соединены с третьим настроечным входом устройства. В отличие от прототипа устройство содержит элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом восемь и элемент И, -й (1, 2 7) вход которого соединен с -м информационным входом устройства и с -м входом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом восемь. Восьмой вход элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом восемь соединен с четвертым настроечным входом устройства, пятый настроечный вход которого соединен с девятым и десятым входами элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом восемь, выход которого соединен с третьим входом элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, четвертый вход которого соединен с выходом элемента И. Седьмой информационный вход устройства соединен с десятым входом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре и с девятым входом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом пять. Названный технический результат достигается путем использования новых логических элементов (элемента И и элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом восемь). На чертеже (фигура) представлена логическая схема устройства для вычисления полиномиальных симметрических булевых функций семи переменных. Устройство для вычисления полиномиальных симметрических булевых функций содержит элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре 1, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом пять 2, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом восемь 3, элемент И 4,элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА 5, семь информационных входов 612, пять настроечных входов 1317 и выход 18. Устройство для вычисления полиномиальных симметрических булевых функций семи переменных работает следующим образом. На информационные входы устройства 612 поступают (в произвольном порядке) значения переменных , 2 7, а на настроечные входы 1317 - сигналы настройки 1, 2 5. На выходе устройства 18 реализуется (вы числяется) полиномиальная симметрическая булева функция 77 ( 1,2 7 ) , определяемая вектором настройки(1, 2, , 5), где 1, 2, , 7. Поясним принцип построения и работы устройства для вычисления полиномиальных симметрических булевых функций семи переменных. Известно, что произвольная симметрическая булева функцияпеременных(,2, , ) с рабочими числами , 2, ,(0) принимает значение 1 на тех и только тех наборах значений переменных Хх 1, х 2, , , которые содержат ровно а (1, 2, ,2, ) единиц. Такая булева функция обозначается через 1 1, то симметрическая булева функция( 1,2 ) называется фундаментальной (или элементарной).,Симметрическая булева функцияпеременных 1 2 называется полиномиальной, если ее полином Жегалкина содержит только всевозможные элементарные конъюнкции, ранг которых равен , где 1, 2 . Такая полиномиальная симметриче 3 13248 1 2010.06.30 ская булева функцияпеременных обозначается через. Очевидно, что полином конъюнкций ранга , где 1, 2 . Предлагаемое устройство (фигура) синтезировано на основе применения следующих аналитических представлений полиномиальных симметрических булевых функций семи переменных 1 17737577 ,7 2772737677 ,437377 ,774757677 ,7 57577 ,67677 ,777 . 7 7 7 Отметим, что в приведенных выше формулах логическую операцию дизъюнкция можно заменить логической операцией сложение по модулю два. Первообразная функция устройства имеет вид 4( 1,2 7 , 1,2 5 )10 ( 1,2 7 , 1,2 ,2 )5 8 79 ( 1,2 7 ,3 ,3 )10 ( 1,2 7 ,4 ,5 ,5 )7 ( 1,2 7 ). В таблице приведен способ настройки устройства на вычисление полиномиальной симметрической булевой функции 77 ( 1,2 7 ) , где 1, 2 7. Рассмотрим пример. Допустим, на выходе 18 устройства требуется реализовать полиномиальную симметрическую булеву функцию 33 ( 1,2 7 ) . Тогда, согласно 7 7 таблице настроек (таблица), необходимо на настроечные входы 1317 подать значения 1,0,0,1,1 соответственно. В таком случае первообразная функция устройства принимает вид 4 73 ( 1 ,2 7 )75 ( 1 ,2 7 )75 ( 1 ,2 7 )77 ( 1 ,2 7 )73 ( 1 ,2 7 )77 ( 1 ,2 7 )3 ( 1 ,2 7 ). 7 Дополнительными достоинствами устройства для вычисления полиномиальных симметрических булевых функций семи переменных являются 1) небольшая конструктивная сложность, которая (по числу входов логических элементов) равна 40 2) высокое быстродействие, которое составляет 2, где- задержка на логический элемент 3) небольшое число внешних выводов (7 информационных и 5 настроечных входов, а также один выход). Источники информации Национальный центр интеллектуальной собственности. 220034, г. Минск, ул. Козлова, 20.