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

(51) МПК НАЦИОНАЛЬНЫЙ ЦЕНТР ИНТЕЛЛЕКТУАЛЬНОЙ СОБСТВЕННОСТИ УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ ПОЛИНОМИАЛЬНЫХ СИММЕТРИЧЕСКИХ БУЛЕВЫХ ФУНКЦИЙ ДВЕНАДЦАТИ ПЕРЕМЕННЫХ(71) Заявитель Белорусский государственный университет(72) Автор Супрун Валерий Павлович(73) Патентообладатель Белорусский государственный университет(57) Устройство для вычисления полиномиальных симметрических булевых функций двенадцати переменных, характеризующееся тем, что содержит с первого по четвертый элементы СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре, мажоритарный элемент с порогом два, мажоритарный элемент с порогом четыре,18321 1 2014.06.30 мажоритарный элемент с порогом шесть, мажоритарный элемент с порогом восемь, мажоритарный элемент с порогом десять и с первого по шестой элементы И, -й вход, где 1, 2, , 12, первого из которых соединен с -м входом устройства, с -м входом мажоритарного элемента с порогом два, с -м входом мажоритарного элемента с порогом четыре, с -м входом мажоритарного элемента с порогом шесть, с -м входом мажоритарного элемента с порогом восемь, с -м входом мажоритарного элемента с порогом десять и с -м входом первого элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, выход которого соединен с первым прямым входом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре, с первым прямым входом второго и третьего элементов И, с первым входом четвертого и пятого элементов И и с первым выходом устройства, второй выход которого соединен с выходом второго элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, первый вход которого соединен с выходом мажоритарного элемента с порогом два и со вторым прямым входом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре, выход которого соединен с третьим выходом устройства, четвертый выход которого соединен с выходом третьего элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, первый вход которого соединен с выходом мажоритарного элемента с порогом четыре, со вторым входом второго элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, с первым инверсным входом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре и со вторым входом второго элемента И, выход которого соединен с пятым выходом устройства, шестой выход которого соединен с выходом четвертого элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, первый вход которого соединен с выходом мажоритарного элемента с порогом шесть, с третьим входом второго элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, с третьим прямым входом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре и со вторым прямым входом третьего элемента И, выход которого соединен с седьмым выходом устройства, восьмой выход устройства соединен с выходом мажоритарного элемента с порогом восемь, с четвертым входом второго элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, со вторым инверсным входом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре, со вторым входом третьего и четвертого элементов СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, с инверсным входом второго и третьего элементов И и со вторым входом четвертого элемента И, выход которого соединен с девятым выходом устройства, десятый выход которого соединен с выходом шестого элемента И, прямой вход которого соединен с выходом мажоритарного элемента с порогом десять, с пятым входом второго элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, с четвертым прямым входом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре и со вторым входом пятого элемента И, выход которого соединен с одиннадцатым выходом устройства, двенадцатый выход которого соединен с выходом первого элемента И, с шестым входом второго элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, с третьим входом третьего элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА и с инверсным входом шестого элемента И. Изобретение относится к области вычислительной техники и микроэлектроники и предназначено для вычисления полиномиальных симметрических булевых функций двенадцати переменных. Известно устройство для вычисления симметрических булевых функцийпеременных, которое содержит 21 элементов И-НЕ,элементов НЕ,информационных и 1 настроечных входов, выход 1. Конструктивная сложность устройства (по числу входов логических элементов) равна 3222, а его быстродействие составляет(2), где- задержка на один логический элемент. Известное устройство при 12 содержит 157 элементов И-НЕ и 12 элементов НЕ. Недостатком известного устройства является высокая конструктивная сложность. Наиболее близким по функциональным возможностям и конструкции техническим решением к предлагаемому устройству является устройство для вычисления фундамен 2 18321 1 2014.06.30 тальных симметрических булевых функцийпеременных, содержащее при 12 три элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, элемент И, мажоритарный элемент с порогом десять и мажоритарный элемент с порогом двенадцать 2. Устройство-прототип, как и заявляемое устройство, содержит три элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, мажоритарный элемент с порогом десять и элемент И, выход которого соединен с выходом устройства. Недостатком устройства-прототипа являются ограниченные функциональные возможности, поскольку устройство не позволяет вычислять полиномиальные симметрические булевы функции двенадцати переменных. Изобретение направлено на решение технической задачи расширения функциональных возможностей устройства за счет одновременного вычисления (реализации) всех двенадцати полиномиальных симметрических булевых функций, зависящих от двенадцати переменных. Устройство для вычисления полиномиальных симметрических булевых функций двенадцати переменных характеризуется тем, что содержит с первого по четвертый элементы СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре,мажоритарный элемент с порогом два, мажоритарный элемент с порогом четыре, мажоритарный элемент с порогом шесть, мажоритарный элемент с порогом восемь, мажоритарный элемент с порогом десять и с первого по шестой элементы И. Причем -й вход, где 1, 2, , 12, первого элемента И соединен с -м входом устройства, с -м входом мажоритарного элемента с порогом два, с -м входом мажоритарного элемента с порогом четыре, с -м входом мажоритарного элемента с порогом шесть, с -м входом мажоритарного элемента с порогом восемь, с -м входом мажоритарного элемента с порогом десять и с -м входом первого элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА. Выход первого элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА соединен с первым прямым входом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре, с первым прямым входом второго и третьего элементов И, с первым входом четвертого и пятого элементов И и с первым выходом устройства. Второй выход устройства соединен с выходом второго элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, первый вход которого соединен с выходом мажоритарного элемента с порогом два и со вторым прямым входом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре, выход которого соединен с третьим выходом устройства. Четвертый выход устройства соединен с выходом третьего элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, первый вход которого соединен с выходом мажоритарного элемента с порогом четыре, со вторым входом второго элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, с первым инверсным входом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре и со вторым входом второго элемента И, выход которого соединен с пятым выходом устройства. Шестой выход устройства соединен с выходом четвертого элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, первый вход которого соединен с выходом мажоритарного элемента с порогом шесть, с третьим входом второго элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, с третьим прямым входом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре и со вторым прямым входом третьего элемента И, выход которого соединен с седьмым выходом устройства. Восьмой выход устройства соединен с выходом мажоритарного элемента с порогом восемь, с четвертым входом второго элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, со вторым инверсным входом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре, со вторым входом третьего и четвертого элементов СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, с инверсным входом второго и третьего элементов И и со вторым входом четвертого элемента И, выход которого соединен с девятым выходом устройства. Десятый выход устройства соединен с выходом шестого элемента И, прямой вход которого соединен с выходом мажоритарного элемента с порогом десять, с пятым входом 3 18321 1 2014.06.30 второго элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, с четвертым прямым входом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре и со вторым входом пятого элемента И, выход которого соединен с одиннадцатым выходом устройства. Двенадцатый выход устройства соединен с выходом первого элемента И, с шестым входом второго элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, с третьим входом третьего элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА и с инверсным входом шестого элемента И. Основной технический результат изобретения заключается в расширении функциональных возможностей устройства с целью одновременного вычисления всех 12 полиномиальных симметрических булевых функций двенадцати переменных. Названный эффект достигается путем введения в логическую схему устройствапрототипа новых логических элементов (мажоритарных элементов с порогами два, четыре, шесть и восемь, элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре), а также изменением связей между элементами в логической схеме устройства. На фигуре представлена логическая схема устройства для вычисления полиномиальных симметрических булевых функций двенадцати переменных. Устройство для вычисления полиномиальных симметрических булевых функций содержит четыре элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА 1, 2, 3 и 4, мажоритарный элемент с порогом два 5, мажоритарный элемент с порогом четыре 6, мажоритарный элемент с порогом шесть 7, мажоритарный элемент с порогом восемь 8, мажоритарный элемент с порогом десять 9, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре 10, шесть элементов И 11, 12, , 16, двенадцать входов 17, 18, , 28 и двенадцать выходов 29, 30, , 40. Устройство для вычисления полиномиальных симметрических булевых функций двенадцати переменных работает следующим образом. На входы устройства 17, 18, , 28 поступают (в произвольном порядке) значения переменных , 2 12. На выходах устройства 29, 30, , 40 реализуются полиномиальные симметрические булевы функции 2 1 , 12 , , 12 соответственно. 12 12 Поясним принцип построения и работы устройства для вычисления полиномиальных симметрических булевых функций. Известно, что произвольная симметрическая булева функцияпеременных(,2 ) с рабочими числами 1, 2(0) принимает значение 1 на тех и только тех наборах значений переменных 1, 2 , которые содержат ровно (1, 2 ) единиц. Такая булева функция обозначается через 1 , 2 ( 1,2 ) . Ес ли 1, то симметрическая булева функция( 1 ,2 ) называется фундаментальной (или элементарной). Симметрическая булева функцияпеременных 1 , 2 называется полино миальной, если полином Жегалкинасодержит только(число сочетаний изпо) элементарных конъюнкций ранга , где 1. Такая симметрическая булева функция обозначается( 1 ,2 , ,) . Для полиномиальных симметрических булевых функций двенадцати переменных 1212 ( 1 ,2 , , 12 ) справедливы формулы, выражающие их зависимость от фундаментальных симметрических булевых функций двенадцати переменных 18321 1 2014.06.30 5 5 7 121212 ,7 6 6 121212 ,7 7 1212 ,8 8 9 10 11 12 121212121212 ,11 9 9 121212 ,11 10 101212 ,12 12 11 1112 и 1212. 12 12 Логическая схема устройства (фигура) синтезирована на основе применения следующих аналитических представлений полиномиальных симметрических булевых функций 12123456789101112 ,1, если 1234567891011122,2 120 в противном случае,1, если 1234567891011124,4 120 в противном случае,1, если 1234567891011126,6 120 в противном случае,1, если 1234567891011128,8 120 в противном случае,1, если 12345678910111210,1012 0 в противном случае, 121 23456789 10 1112 . Основным достоинством заявляемого устройства являются широкие функциональные возможности, поскольку устройство позволяет одновременно реализовать (вычислить) все 5 18321 1 2014.06.30 12 полиномиальных симметрических булевых функций, зависящих от двенадцати переменных. Кроме того, устройство имеет относительно невысокую конструктивную сложность,которая (по числу входов логических элементов) равна 113. Заявляемое устройство и устройство-прототип имеют одинаковое быстродействие, определяемое глубиной схемы и равное 2. Национальный центр интеллектуальной собственности. 220034, г. Минск, ул. Козлова, 20.