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

(51) МПК НАЦИОНАЛЬНЫЙ ЦЕНТР ИНТЕЛЛЕКТУАЛЬНОЙ СОБСТВЕННОСТИ УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ ПОЛИНОМИАЛЬНЫХ СИММЕТРИЧЕСКИХ БУЛЕВЫХ ФУНКЦИЙ ОДИННАДЦАТИ ПЕРЕМЕННЫХ(71) Заявитель Белорусский государственный университет(72) Авторы Городецкий Данила Андреевич Седун Андрей Максимович Супрун Валерий Павлович(73) Патентообладатель Белорусский государственный университет(57) Устройство для вычисления полиномиальных симметрических булевых функций одиннадцати переменных, содержащее элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, элемент И, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом пять, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом восемь, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом девять и элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом одиннадцать, выход которого соединен с первым входом элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, второй вход которого соединен с выходом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом девять, третий вход - с выходом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом восемь, четвертый вход - с выходом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом пять, пятый вход - с выходом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре и шестой вход - с выходом элемента И, а выход - с выходом устройства, -й, где 1, 2 11,14625 1 2011.08.30 информационный вход которого соединен с -м входом элемента И, с -м входом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом одиннадцать, с -м входом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом девять, с -м входом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом восемь, с -м входом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом пять и с -м входом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре, двенадцатый вход которого соединен с первым настроечным входом устройства, второй настроечный вход которого соединен с тринадцатым и четырнадцатым входами элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре, третий настроечный вход - с двенадцатым и тринадцатым входами элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом пять, четвертый настроечный вход - с двенадцатым входом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом восемь, тринадцатый и четырнадцатый входы которого соединены с пятым настроечным входом устройства, шестой настроечный вход которого соединен с двенадцатым и тринадцатым входами элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом девять, седьмой настроечный вход - с двенадцатым входом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом одиннадцать, тринадцатый и четырнадцатый входы которого соединены с восьмым настроечным входом устройства, девятый настроечный вход которого соединен с двенадцатым входом элемента И. Изобретение относится к области вычислительной техники и микроэлектроники и предназначено для вычисления полиномиальных симметрических булевых функций одиннадцати переменных. Известно устройство для вычисления симметрических булевых функцийпеременных, которое содержит 21 элементов И-НЕ,элементов НЕ,информационных и 1 настроечных входов, выход 1. Конструктивная сложность устройства (по числу входов логических элементов) равна 3222, а его быстродействие, определяемое глубиной схемы, составляет (2), где- задержка на один логический элемент. Известное устройство (при 11) содержит 133 элемента И-НЕ и 11 элементов НЕ. Основными недостатками известного устройства являются 1) высокая конструктивная сложность, равная 387 2) низкое быстродействие, которое составляет 13. Наиболее близким по функциональным возможностям и конструкции техническим решением к предлагаемому является устройство для вычисления фундаментальных симметрических булевых функцийпеременных, содержащее при 11 три элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, элемент И, мажоритарный элемент с порогом восемь и мажоритарный элемент с порогом десять 2. Устройство-прототип, как и заявляемое устройство, содержит элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА и элемент И. Недостатком устройства-прототипа являются ограниченные функциональные возможности, поскольку устройство не позволяет вычислить полиномиальные симметрические булевы функции одиннадцати переменных. Изобретение направлено на решение технической задачи расширения функциональных возможностей устройства-прототипа за счет вычисления (реализации) полиномиальных симметрических булевых функций одиннадцати переменных. Устройство для вычисления полиномиальных симметрических булевых функций одиннадцати переменных содержит элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, элемент И,элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом пять, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом восемь, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом девять и элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом одиннадцать. Выход элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом одиннадцать соединен с первым входом элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, второй вход которого соединен с вы 2 14625 1 2011.08.30 ходом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом девять, третий вход - с выходом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом восемь, четвертый вход - с выходом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом пять, пятый вход - с выходом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре и шестой вход - с выходом элемента И, а выход - с выходом устройства. Причем -й, где 1, 2 11, информационный вход устройства соединен с -м входом элемента И, с -м входом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом одиннадцать, с-м входом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом девять, с -м входом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом восемь, с -м входом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом пять и с -м входом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре. Двенадцатый вход элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре соединен с первым настроечным входом устройства, второй настроечный вход которого соединен с тринадцатым и четырнадцатым входами элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре, третий настроечный вход - с двенадцатым и тринадцатым входами элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом пять, четвертый настроечный вход - с двенадцатым входом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом восемь. Тринадцатый и четырнадцатый входы элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом восемь соединены с пятым настроечным входом устройства, шестой настроечный вход которого соединен с двенадцатым и тринадцатым входами элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом девять, седьмой настроечный вход - с двенадцатым входом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом одиннадцать. Тринадцатый и четырнадцатый входы элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом одиннадцать соединены с восьмым настроечным входом устройства, девятый настроечный вход которого соединен с двенадцатым входом элемента И. Основной технический результат изобретения заключается в расширении функциональных возможностей устройства для вычисления полиномиальных симметрических булевых функций одиннадцати переменных за счет использования новых логических элементов (элементов ИСКЛЮЧАЮЩЕЕ ИЛИ с порогами четыре, пять, восемь, девять и одиннадцать), а также изменением соединений между элементами в логической схеме устройства. На фигуре представлена логическая схема устройства для вычисления полиномиальных симметрических булевых функций одиннадцати переменных, а посредством таблицы представлена его настройка. Устройство для вычисления полиномиальных симметрических булевых функций одиннадцати переменных содержит элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре 1,элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом пять 2, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом восемь 3, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом девять 4, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом одиннадцать 5, элемент И 6, элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА 7, одиннадцать информационных входов 818, девять настроечных входов 1927 и один выход 28. Устройство для вычисления полиномиальных симметрических булевых функций одиннадцати переменных работает следующим образом. На информационные входы устройства 818 поступают (в произвольном порядке) значения переменных , 2 11,а на настроечные входы 1927 - сигналы настройки 0, 1 8, значения которых принадлежат множеству 0,1. На выходе устройства 28 реализуется полиномиальная симметрическая булева функция 11 (,2 11 ), определяемая вектором настройки(0, 1 8),где 1, 2 11. Поясним принцип построения и работы устройства для вычисления полиномиальных симметрических булевых функций одиннадцати переменных. 3 14625 1 2011.08.30 Известно, что произвольная симметрическая булева функцияпеременных(,2 ) с рабочими числами 1, 2(01) принимает значение 1 на тех и только тех наборах значений переменных 1, 2 , которые содержат ровно а единиц, где 1, 2 . Такая булева функция обозначается 1 , 2 . Если 1,то симметрическая булева функция(,2 ,,) называется фундаментальной(или элементарной). Симметрическая булева функцияпеременных 1 , 2 называется полиномиальной, если ее полином Жегалкина содержит только элементарные конъюнкции, ранг которых равен(1). Полиномиальная симметрическая булева функцияпеременных обозначается как. Очевидно, что полином Жегалкина функциисодер жит(число сочетаний изпо ) элементарных конъюнкций ранга , где 1, 2 . Логическая схема (фигура) устройства для вычисления полиномиальных симметрических булевых функций одиннадцати переменных синтезирована на основе применения следующих аналитических представлений булевых функций 1111 (,2 ,, 11 ) 1 3 5 7 9 11 11111111111111,2 2 3 6 7 10 11 11111111111111,3 3 7 11 11111111,4 4 5 6 7 1111111111,5 5 7 6 6 7 111111 , 111111,7 7 8 8 9 10 11 1111 , 1111111111,9 9 11 10 11 11 111111 , 101111 , 1111 . 11 11 Первообразная функция устройства для вычисления полиномиальных симметрических булевых функций одиннадцати переменных имеет вид 4(,2 11 ,0 ,1 8 )14 (,2 11 ,0 ,1 , 1 )5 813 (,2 11 ,2 ,2 )14 (,2 11 ,3 ,4 ,4 )9 1113 (,2 11 ,5 ,5 )14 (,2 11 ,6 ,7 ,7 )211 8 . Рассмотрим пример. Допустим, что на выходе 28 устройства требуется вычислить (реализовать) полиномиальную симметрическую булеву функцию одиннадцати переменных 2 11 (,2 ,,11 )1 21 31 41 51 61 71 81 91 101 11232425262728292102113435363738393103114546474849410411565758595105116768696106117879710711898108119109111011. В таком случае, согласно таблице настроек, необходимо положить 0370 и 1245681. Тогда первообразная функция устройства принимает вид 4(,2 11 ,0,1,1,0,1,1,1,0,1)14 (,2 11 ,0,1,1)5 813 (,2 11 ,1,1)14 (,2 11 ,0,1,1)9 1113 (,2 11 ,1,1)14 (,2 11 ,1,0,0)211 12 3 6 711 (,2 11 )11 (,2 11 )11 (,2 11 )11 (,2 11 )10 1111 (,2 11 )11 (,2 11 )2 3 6 7 10 11 211111111111111 . Дополнительными достоинствами устройства для вычисления полиномиальных симметрических булевых функций одиннадцати переменных являются а) низкая конструк 4 14625 1 2011.08.30 тивная сложность (по числу входов логических элементов), равная 86 б) небольшое число внешних выводов, равное 21 в) высокое быстродействие, определяемое глубиной схемы и равное 2. Сигналы настройки Выход 0 1 2 3 4 5 6 7 8 Национальный центр интеллектуальной собственности. 220034, г. Минск, ул. Козлова, 20.