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

(51) МПК (2009) НАЦИОНАЛЬНЫЙ ЦЕНТР ИНТЕЛЛЕКТУАЛЬНОЙ СОБСТВЕННОСТИ УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ ПОЛИНОМИАЛЬНЫХ СИММЕТРИЧЕСКИХ БУЛЕВЫХ ФУНКЦИЙ(71) Заявитель Белорусский государственный университет(72) Авторы Супрун Валерий Павлович Городецкий Данила Андреевич(73) Патентообладатель Белорусский государственный университет(57) Устройство для вычисления полиномиальных симметрических булевых функций десяти переменных, содержащее элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом пять,13969 1 2011.02.28 элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом восемь, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом девять и элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом одиннадцать, выход которого соединен с первым входом элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, второй вход которого соединен с выходом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом девять, третий вход - с выходом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом восемь, четвертый вход -выходом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом пять и пятый вход - с выходом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре, а выход - с выходом устройства, -й,где 1, 210, информационный вход которого соединен с -м входом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом одиннадцать, с -м входом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом девять, с -м входом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом восемь,с -м входом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом пять и с -м входом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре, одиннадцатый вход которого соединен с первым настроечным входом устройства, второй настроечный вход которого соединен с двенадцатым и тринадцатым входами элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре,третий настроечный вход устройства соединен с одиннадцатым и двенадцатым входами элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом пять, четвертый настроечный вход устройства соединен с одиннадцатым входом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом восемь, двенадцатый и тринадцатый входы которого соединены с пятым настроечным входом устройства, шестой настроечный вход которого соединен с одиннадцатым и двенадцатым входами элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом девять, седьмой и восьмой настроечные входы устройства соединены с одиннадцатым и двенадцатым входами элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом одиннадцать. Изобретение относится к области вычислительной техники и микроэлектроники и предназначено для вычисления полиномиальных симметрических булевых функций десяти переменных. Известно устройство для вычисления симметрических булевых функцийпеременных, которое при 10 содержит десять элементов НЕ и сто одиннадцать элементов И-НЕ 1. Недостатками известного устройства являются высокая конструктивная сложность (по числу входов логических элементов), а также низкое быстродействие, определяемое глубиной схемы. Наиболее близким по функциональным возможностям и конструкции техническим решением к предлагаемому является устройство для вычисления фундаментальных симметрических булевых функцийпеременных, содержащее при 10 три элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, элемент И, мажоритарный элемент с порогом восемь и мажоритарный элемент с порогом десять 2. Устройство-прототип, как и заявляемое устройство, содержит элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА. Недостатком устройства-прототипа являются ограниченные функциональные возможности, поскольку устройство не позволяет вычислять полиномиальные симметрические булевы функции десяти переменных. Изобретение направлено на решение технической задачи расширения функциональных возможностей устройства для вычисления фундаментальных симметрических функций за счет вычисления (реализации) полиномиальных симметрических булевых функций десяти переменных. Устройство для вычисления полиномиальных симметрических булевых функций содержит элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом пять, элемент ИСКЛЮЧА 2 13969 1 2011.02.28 ЮЩЕЕ ИЛИ с порогом восемь, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом девять и элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом одиннадцать. Выход элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом одиннадцать соединен с первым входом элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА. Второй вход элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА соединен с выходом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом девять. Третий вход элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА соединен с выходом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом восемь. Четвертый вход элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА соединен с выходом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом пять. Пятый вход элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА соединен с выходом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре. Выход элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА соединен с выходом устройства,-й, где 1, 210, информационный вход которого соединен с -м входом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом одиннадцать, с -м входом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом девять, с -м входом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом восемь, с -м входом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом пять и с -м входом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре. Одиннадцатый вход элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре соединен с первым настроечным входом устройства. Второй настроечный вход устройства соединен с двенадцатым и тринадцатым входами элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре. Третий настроечный вход устройства соединен с одиннадцатым и двенадцатым входами элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом пять. Четвертый настроечный вход устройства соединен с одиннадцатым входом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом восемь. Двенадцатый и тринадцатый входы элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом восемь соединены с пятым настроечным входом устройства. Шестой настроечный вход устройства соединен с одиннадцатым и двенадцатым входами элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом девять. Седьмой и восьмой настроечные входы устройства соединены с одиннадцатым и двенадцатым входами элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом одиннадцать. На чертеже (фигура) представлена логическая схема устройства для вычисления полиномиальных симметрических булевых функций десяти переменных. Устройство для вычисления полиномиальных симметрических булевых функций десяти переменных содержит элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре 1, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом пять 2, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом восемь 3, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом девять 4, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом одиннадцать 5, элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА 6, десять информационных входов 716, восемь настроечных входов 1724 и один выход 25. Устройство для вычисления полиномиальных симметрических булевых функций работает следующим образом. На информационные входы устройства 716 поступают (в произвольном порядке) значения переменных 1, 2 10, а на настроечные входы 1724 сигналы настройки 0, 1 7, значения которых принадлежат множеству 0,1. На выхо де устройства 25 реализуется полиномиальная симметрическая булева функция 10 10 (1, 2 10), определяемая вектором настройки(0, 1 7), где 1, 210. Поясним принцип построения и работы устройства для вычисления полиномиальных симметрических булевых функций десяти переменных. Известно, что произвольная симметрическая булева функцияпеременных(1, 2 ) с рабочими числами 1, 2(0) принимает значение 1 на тех и 13969 1 2011.02.28 только тех наборах значений переменных 1, 2 , которые содержат ровно(1, 2 ) единиц. Такая булева функция обозначается 1 , 2 . Если 1,то симметрическая булева функция(1, 2 ) называется фундаментальной (или элементарной). Симметрическая булева функцияпеременных 1 , 2 называется полиномиальной, если ее полином Жегалкина содержит только элементарные конъюнкции, ранг которых равен(1). Такая полиномиальная симметрическая булева функцияпеременных обозначается. Очевидно, что полином Жегалкина функции содержит(число сочетаний изпо ) элементарных конъюнкций ранга , где 1, 2 . Устройство синтезировано на основании применения следующих аналитических представлений полиномиальных симметрических булевых функций десяти переменных 1010 (1, 2 10) 1 3 5 7 9 11010101010 ,10 2 2 3 6 7 10 101010101010 ,3 3 7 101010 ,4 4 5 6 7 1010101010 ,5 5 7 6 6 7 101010 , 101010 ,7 7 8 8 9 10 1010 , 10101010 ,9 9 10 1010 , 1010 . 10 В таблице представлена настройка устройства на вычисление (реализацию) полиномиальных симметрических булевых функций десяти переменных. Устройство для вычисления полиномиальных симметрических булевых функций Сигналы настройки Выход 0 1 2 3 4 5 6 7 Первообразная функция заявляемого устройства для вычисления полиномиальных симметрических булевых функций имеет вид 4 13969 1 2011.02.28 8 512 (1, 2 10, 2, 2)13 (1, 2 10, 3, 4, 4)9 1112 (1, 2 10, 5, 5)12 (1, 2 10, 6, 7). Рассмотрим пример. Допустим, что на выходе устройства требуется вычислить (реализовать) полиномиальную симметрическую булеву функцию 2 10 (1, 2 10)121314151617181911023242526272829210343536373839310454647484941056575859510676869610787971089810910. В таком случае, согласно таблице настроек, необходимо положить 0360 и 124571. Тогда первообразная функция устройства принимает вид 4(1, 2 10, 0, 1, 1, 0, 1, 1, 0, 1)13 (1, 2 10, 0, 1, 1)8 512 (1, 2 10, 1, 1)13 (1, 2 10, 0, 1, 1)9 1112 (1, 2 10, 1, 1)12 (1, 2 10, 0, 1)2 3 610 (1, 2 10)10 (1, 2 10)10 (1, 2 10)7 1010 (1, 2 10)10 (1, 2 10)2 3 6 7 10 2101010101010 . Дополнительными достоинствами устройства для вычисления полиномиальных симметрических булевых функций десяти переменных являются а) низкая конструктивная сложность (по числу входов логических элементов), равная 67 б) небольшое число внешних выводов, равное 19 в) высокое быстродействие, определяемое глубиной схемы и равное 2, где-задержка на логический элемент. Национальный центр интеллектуальной собственности. 220034, г. Минск, ул. Козлова, 20.