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

(51) МПК НАЦИОНАЛЬНЫЙ ЦЕНТР ИНТЕЛЛЕКТУАЛЬНОЙ СОБСТВЕННОСТИ УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ ПОЛИНОМИАЛЬНЫХ СИММЕТРИЧЕСКИХ БУЛЕВЫХ ФУНКЦИЙ ВОСЬМИ ПЕРЕМЕННЫХ(71) Заявитель Белорусский государственный университет(72) Авторы Супрун Валерий Павлович Груздев Вадим Геннадьевич(73) Патентообладатель Белорусский государственный университет(57) Устройство для вычисления полиномиальных симметрических булевых функций восьми переменных, характеризующееся тем, что содержит с первого по третий элементы СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, с первого по четвертый элементы И, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом три, мажоритарный элемент с порогом два, мажоритарный элемент с порогом четыре, мажоритарный элемент с порогом шесть, -й вход которого, где 1, 2 8, соединен с -м входом устройства, с -м входом первого элемента И, с -м входом мажоритарного элемента с порогом два, с -м входом мажоритарного элемента с порогом четыре и с -м входом первого элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, выход которого соединен с первым входом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом три, с первым входом второго элемента И, с первым входом третьего элемента И и с первым выходом устройства, второй выход которого соединен с выходом второго элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, первый вход которого соединен с выходом мажоритарного элемента 17700 1 2013.12.30 с порогом два и со вторым входом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом три, выход которого соединен с третьим выходом устройства, четвертый выход которого соединен с выходом третьего элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, первый вход которого соединен с выходом мажоритарного элемента с порогом четыре, со вторым входом второго элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, с инверсным входом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом три и со вторым входом второго элемента И, выход которого соединен с пятым выходом устройства, шестой выход которого соединен с выходом четвертого элемента И, первый вход которого соединен с выходом мажоритарного элемента с порогом шесть, с третьим входом второго элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, с третьим входом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом три и со вторым входом третьего элемента И, выход которого соединен с седьмым выходом устройства, восьмой выход которого соединен с выходом первого элемента И, с четвертым входом второго элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, со вторым входом третьего элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА и с инверсным входом четвертого элемента И. Изобретение относится к области вычислительной техники и микроэлектроники и предназначено для вычисления полиномиальных симметрических булевых функций восьми переменных. Известно устройство для вычисления полиномиальных симметрических булевых функций восьми переменных, содержащее элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом пять, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом шесть, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом восемь, элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, восемь информационных и шесть настроечных входов,выход 1. Известное устройство, как и заявляемое устройство, содержит элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, выход которого соединен с выходом устройства. Недостатком известного устройства являются ограниченные функциональные возможности, поскольку устройство не позволяет одновременно вычислять восемь различных полиномиальных симметрических булевых функций, зависящих от восьми переменных. Наиболее близким по функциональным возможностям и конструкции техническим решением к предлагаемому устройству является устройство для вычисления полиномиальных симметрических булевых функций восьми переменных, которое содержит семь элементов ИСКЛЮЧАЮЩЕЕ ИЛИ с порогами один, два, три, четыре, пять, шесть и семь,элемент И, шесть элементов ИЛИ, восемь входов и восемь выходов 2. Недостатком устройства-прототипа является высокая конструктивная сложность, которая (по числу входов логических элементов) равна 82. Изобретение направлено на решение технической задачи понижение конструктивной сложности устройства для вычисления полиномиальных симметрических булевых функций восьми переменных. Устройство для вычисления полиномиальных симметрических булевых функций характеризуется тем, что содержит с первого по третий элементы СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, с первого по четвертый элементы И, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом три, мажоритарный элемент с порогом два, мажоритарный элемент с порогом четыре, мажоритарный элемент с порогом шесть. Причем -й вход мажоритарного элемента с порогом шесть, где 1,28, соединен с-м входом устройства, с -м входом первого элемента И, с -м входом мажоритарного элемента с порогом два, с -м входом мажоритарного элемента с порогом четыре и с -м входом первого элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА. Выход первого элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА соединен с первым входом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом три, с первым входом второго элемента И, с 2 17700 1 2013.12.30 первым входом третьего элемента И и с первым выходом устройства, второй выход которого соединен с выходом второго элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА. Первый вход второго элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА соединен с выходом мажоритарного элемента с порогом два и со вторым входом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом три, выход которого соединен с третьим выходом устройства. Четвертый выход устройства соединен с выходом третьего элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, первый вход которого соединен с выходом мажоритарного элемента с порогом четыре, со вторым входом второго элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, с инверсным входом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом три и со вторым входом второго элемента И, выход которого соединен с пятым выходом устройства. Шестой выход устройства соединен с выходом четвертого элемента И, первый вход которого соединен с выходом мажоритарного элемента с порогом шесть, с третьим входом второго элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, с третьим входом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом три и со вторым входом третьего элемента И, выход которого соединен с седьмым выходом устройства. Восьмой выход устройства соединен с выходом первого элемента И, с четвертым выходом второго элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, со вторым входом третьего элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА и с инверсным входом четвертого элемента И. Основной технический результат изобретения заключается в понижении конструктивной сложности (по числу входов логических элементов) устройства для вычисления полиномиальных симметрических булевых функций восьми переменных. Названный эффект достигается путем введения в логическую схему устройствапрототипа новых логических элементов (мажоритарных элементов с порогами два, четыре и шесть), а также изменением связей между элементами в логической схеме устройства. На фигуре представлена логическая схема устройства для вычисления полиномиальных симметрических булевых функций восьми переменных. Устройство для вычисления полиномиальных симметрических булевых функций восьми переменных содержит три элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА 1, 2 и 3, мажоритарный элемент с порогом два 4, мажоритарный элемент с порогом четыре 5, мажоритарный элемент с порогом шесть 6, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом три 7, четыре элемента И 8, 9, 10 и 11, восемь входов 12, 1319 и восемь выходов 20, 2127. Устройство для вычисления полиномиальных симметрических булевых функций восьми переменных работает следующим образом. На входы устройства 12, 1319 поступают (в произвольном порядке) значения переменных ,28. На выходах устройства 20,2 21, , 27 реализуются полиномиальные симметрические булевы функции 1 , 8 8 ,8 8 соответственно. Поясним принцип построения и работы устройства для вычисления полиномиальных симметрических булевых функций восьми переменных. Известно, что произвольная симметрическая булева функцияпеременных(1,2) с рабочими числами 1, 2, ,(0) принимает значение 1 на тех и только тех наборах значений переменных 1,2 которые содержат ровно(1, 2 ) единиц. Симметрическая булева функцияс рабочими числами 1,22 Если 1, то симметрическая булева функция( ) называется фундаментальной (или элементарной). Симметрическая булева функция(1,2) называется полиномиальной, если ее полином Жегалкинасодержит(число сочетаний изпо ) элементарных конъюнкций ранга , где 1. Такая булева функция обозначается через( ) . 17700 1 2013.12.30 Полиномиальные симметрические булевы функции восьми переменных 8 (1,2 8 ) выражаются через фундаментальные симметрические булевы функ ции 8 (1,2 8 ) посредством формул где 1,28. При синтезе заявляемого устройства (фигура) были использованы следующие аналитические представления реализуемых полиномиальных симметрических булевых функций восьми переменных 2 2 4 6 1 ( )8 ( ), 8 ( )8 ( )8 ( )8 ( )8 ( ),8 1, если( )2 ( )4 ( )6 ( )3, 3 8 8 8 88 ( )0 в противном случае , 4 4 5 4 8 ( )8 ( )8 ( ), 8 ( )8 ( )8 ( ), 6 6 7 6 8 ( )8 ( )8 ( ), 8 ( )8 ( )8 ( ) и 8 ( )8 ( ),8 8 ( )12345678 , 1, если 123456782,28 ( )0 в противном случае ,1, если 123456784,48 ( )0 в противном случае,1, если 123456786,68 ( )0 в противном случае, 8 ( )1 2345678 . Основным достоинством устройства для вычисления полиномиальных симметрических булевых функций восьми переменных является низкая конструктивная сложность,которая равна 56 (сложность устройства-прототипа составляет 82). Кроме того, заявляемое устройство и устройство-прототип имеют одинаковое быстродействие, определяемое глубиной схемы, и равное 2, где -задержка на один логический элемент. Источники информации Патент РБ 13666, МПК 06 7/00, 2010. Патент РБ 11024, МПК 06 7/00, 2008 (прототип). Национальный центр интеллектуальной собственности. 220034, г. Минск, ул. Козлова, 20.