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

(51) МПК НАЦИОНАЛЬНЫЙ ЦЕНТР ИНТЕЛЛЕКТУАЛЬНОЙ СОБСТВЕННОСТИ УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ ПОЛИНОМИАЛЬНЫХ СИММЕТРИЧЕСКИХ БУЛЕВЫХ ФУНКЦИЙ ДВЕНАДЦАТИ ПЕРЕМЕННЫХ(71) Заявитель Белорусский государственный университет(72) Авторы Супрун Валерий Павлович Городецкий Данила Андреевич(73) Патентообладатель Белорусский государственный университет(57) Устройство для вычисления полиномиальных симметрических булевых функций двенадцати переменных, характеризующееся тем, что содержит элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА и с первого по шестой элементы ИСКЛЮЧАЮЩЕЕ ИЛИ, выполненные с порогами четыре, восемь, девять, десять, двенадцать и тринадцать соответственно, выход -го из которых, где 1 ,2, , 6, соединен с -м входом элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, выход которого соединен с выходом устройства, -й информационный 16553 1 2012.12.30 вход которого, где 1, 2, , 12, соединен с -м входом -го элемента ИСКЛЮЧАЮЩЕЕ ИЛИ первый настроечный вход устройства соединен с тринадцатым входом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре, четырнадцатый и пятнадцатый входы которого соединены со вторым настроечным входом устройства, а шестнадцатый и семнадцатый входы - с третьим настроечным входом устройства четвертый настроечный вход устройства соединен с тринадцатым входом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом восемь, четырнадцатый и пятнадцатый входы которого соединены с пятым настроечным входом устройства шестой настроечный вход устройства соединен с тринадцатым и четырнадцатым входами элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом девять, пятнадцатый,шестнадцатый, семнадцатый и восемнадцатый входы которого соединены с седьмым настроечным входом устройства восьмой настроечный вход устройства соединен с тринадцатым, четырнадцатым и пятнадцатым входами элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом десять девятый настроечный вход устройства соединен с тринадцатым входом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом двенадцать, четырнадцатый и пятнадцатый входы которого соединены с десятым настроечным входом устройства одиннадцатый настроечный вход устройства соединен с тринадцатым и четырнадцатым входами элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом тринадцать. Изобретение относится к области вычислительной техники и микроэлектроники и предназначено для вычисления полиномиальных симметрических булевых функций двенадцати переменных. Известно устройство для вычисления симметрических булевых функцийпеременных, которое содержит 21 элементов И-НЕ,элементов НЕ,информационных и 1 настроечных входов, выход 1. Конструктивная сложность устройства (по числу входов логических элементов) равна 3222, а его быстродействие, определяемое глубиной схемы, составляет (2), где -задержка на один логический элемент. Известное устройство при 12 содержит 157 элементов И-НЕ и 12 элементов НЕ. Основными недостатками известного устройства при 12 являются 1) высокая конструктивная сложность, равная 458 2) низкое быстродействие, которое составляет 14. Наиболее близким по функциональным возможностям и конструкции техническим решением к предлагаемому устройству является устройство для вычисления полиномиальных симметрических булевых функций одиннадцати переменных, содержащее элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом пять, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом восемь, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом девять и элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом одиннадцать, элемент И и элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА 2. Устройство-прототип, как и заявляемое устройство, содержит элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом восемь и элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом девять, выход каждого из которых соединен со входом элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, выход которого соединен с выходом устройства. Недостатком устройства-прототипа являются ограниченные функциональные возможности, поскольку устройство не позволяет вычислять полиномиальные симметрические булевы функции двенадцати переменных. Изобретение направлено на решение технической задачи расширения функциональных возможностей устройства-прототипа за счет вычисления (реализации) полиномиальных симметрических булевых функций двенадцати переменных. Устройство для вычисления полиномиальных симметрических булевых функций двенадцати переменных характеризуется тем, что содержит элемент СЛОЖЕНИЕ ПО МО 2 16553 1 2012.12.30 ДУЛЮ ДВА и с первого по шестой элементы ИСКЛЮЧАЮЩЕЕ ИЛИ, выполненные с порогами четыре, восемь, девять, десять, двенадцать и тринадцать соответственно. Выход -го элемента ИСКЛЮЧАЮЩЕЕ ИЛИ, где 1, 2, , 6, соединен с -м входом элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, выход которого соединен с выходом устройства, -й информационный вход которого, где 1, 2, , 12, соединен с -м входом -го элемента ИСКЛЮЧАЮЩЕЕ ИЛИ. Первый настроечный вход устройства соединен с тринадцатым входом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре, четырнадцатый и пятнадцатый входы которого соединены со вторым настроечным входом устройства, а шестнадцатый и семнадцатый входы - с третьим настроечным входом устройства. Четвертый настроечный вход устройства соединен с тринадцатым входом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом восемь, четырнадцатый и пятнадцатый входы которого соединены с пятым настроечным входом устройства. Шестой настроечный вход устройства соединен с тринадцатым и четырнадцатым входами элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом девять, пятнадцатый, шестнадцатый,семнадцатый и восемнадцатый входы которого соединены с седьмым настроечным входом устройства. Восьмой настроечный вход устройства соединен с тринадцатым, четырнадцатым и пятнадцатым входами элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом десять. Девятый настроечный вход устройства соединен с тринадцатым входом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом двенадцать, четырнадцатый и пятнадцатый входы которого соединены с десятым настроечным входом устройства. Одиннадцатый настроечный вход устройства соединен с тринадцатым и четырнадцатым входами элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом тринадцать. Основной технический результат изобретения заключается в расширении функциональных возможностей устройства за счет реализации полиномиальных симметрических булевых функций двенадцати переменных. Названный технический эффект достигнут на основе использования новых логических элементов (элементов ИСКЛЮЧАЮЩЕЕ ИЛИ с порогами десять, двенадцать и тринадцать). На фигуре представлена логическая схема устройства для вычисления полиномиальных симметрических булевых функций двенадцати переменных, а посредством таблицы представлен способ его настройки. Устройство для вычисления полиномиальных симметрических булевых функций двенадцати переменных содержит элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре 1, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом восемь 2, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом девять 3, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом десять 4, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом двенадцать 5, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом тринадцать 6, элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА 7, двенадцать информационных входов 819, одиннадцать настроечных входов 2030 и выход 31. Устройство для вычисления полиномиальных симметрических булевых функций двенадцати переменных работает следующим образом. На информационные входы устройства 819 поступают (в произвольном порядке) значения переменных 1, 2, , 12, а на настроечные входы 2030 - сигналы настройки 1, 2, , 11, значения которых принадлежат множеству 0,1. На выходе устройства 31 реализуется полиномиальная симметрическая булева функция 12(1, 2, , 12), определяемая вектором настройки(1, 2, , 11), где 1, 2, , 12. Поясним принцип построения и работы устройства для вычисления полиномиальных симметрических булевых функций двенадцати переменных. Известно, что произвольная симметрическая булева функцияпеременных(1, 2, , ) с рабочими числами 1, 2, ,(01) принимает значение 1 на тех и только тех наборах значений переменных 1, 2, , , которые содержат ров 3 16553 1 2012.12.30 но (1, 2, , ) единиц. Такая булева функция обозначается 1 ,2 , ,( 1 ,2 , ,) . Если 1, то симметрическая булева функция( 1 ,2 , ,) называется фундаментальной (или элементарной). Симметрическая булева функцияпеременных 1 , 2 называется полиномиальной (или полиномиально-однородной), если ее полином Жегалкина содержит ровно(число сочетаний изпо ) различных элементарных конъюнкций ранга , где 1, 2, , . Такая симметрическая булева функция обозначается через. Устройство (фигура) синтезировано на основе применения следующих аналитических представлений полиномиальных симметрических булевых функций двенадцати перемен ных 12 (1,212) 1 3 5 7 9 11 1121212121212 ,12 2 2 3 6 7 10 11 12121212121212 ,3 3 7 11 12121212 ,4 4 5 6 7 12 121212121212 ,5 5 7 121212 ,7 6 6 121212 ,7 7 1212 ,8 8 9 10 11 12 121212121212 ,9 9 11 121212 ,10 11 101212 ,12 11 12 1112 и 1212 . 12 12 Первообразная функция устройства для вычисления полиномиальных симметрических булевых функций двенадцати переменных имеет вид 4( 1 ,2 12 , 1 ,2 11 )17 ( 1 ,2 12 , 1 ,2 ,2 ,3 ,3 )817 ( 1 ,2 12 ,4 ,5 ,5 )9 1018 ( 1 ,2 12 ,6 ,6 ,7 ,7 ,7 ,7 )15 ( 1 ,2 12 ,8 ,8 ,8 )12 1315 ( 1 ,2 12 ,9 , 10 , 10 )14 ( 1 ,2 12 , 11 , 11 ). В таблице представлена настройка устройства на реализацию полиномиальных симметрических булевых функций двенадцати переменных. Рассмотрим пример. Допустим, что на выходе 31 устройства требуется вычислить (реализовать) полиномиальную симметрическую булеву функцию 2 12 ( 1 ,2 12 )1 21 31 41 51 61 71 81 9 110111112232425262728292 102 112 123435363738393 103 113 1245464748494 104 114 12565758595 105 115 126768696 106 116 1278797 107 117 12898 108 118 129 109 119 1210 1110 121112 . В таком случае, согласно таблице настроек (таблица), необходимо положить 13490 и 2567810111. 16553 1 2012.12.30 Тогда первообразная функция устройства принимает вид 4( 1 ,2 , , 12 , 0, 1, 0, 0, 1, 1, 1, 1, 0, 1, 1)17 ( 1 ,2 12 ,0,1,1,0,0)8 915 ( 1 ,2 , , 12 , 0, 1, 1)18 ( 1 ,2 , , 12 , 1, 1, 1, 1, 1, 1)10 12 1315 ( 1 ,2 , , 12 , 1, 1, 1)15 ( 1 ,2 , , 12 , 0, 1, 1)14 ( 1 ,2 , , 12 , 1, 1)2 6 3 7 10 111212121212122 6 3 7 10 11 212121212121212 . Основным достоинством заявляемого устройства являются широкие функциональные возможности, поскольку его применение позволяет вычислить (реализовать) любую полиномиальную симметрическую булеву функцию двенадцати переменных. Дополнительными достоинствами устройства являются а) низкая конструктивная сложность (по числу входов логических элементов), равная 100 б) небольшое число внешних выводов, равное 24 в) высокое быстродействие, определяемое глубиной схемы и равное 2. 1. А.с. СССР 1478208, МПК 06 7/00, 1989. 2. Заявка на патент РБ 20091501, МПК 06 7/00, 2010 (прототип). Национальный центр интеллектуальной собственности. 220034, г. Минск, ул. Козлова, 20.