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

(51) МПК НАЦИОНАЛЬНЫЙ ЦЕНТР ИНТЕЛЛЕКТУАЛЬНОЙ СОБСТВЕННОСТИ УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ ПОЛИНОМИАЛЬНЫХ СИММЕТРИЧЕСКИХ БУЛЕВЫХ ФУНКЦИЙ ВОСЬМИ ПЕРЕМЕННЫХ(71) Заявитель Белорусский государственный университет(72) Автор Супрун Валерий Павлович(73) Патентообладатель Белорусский государственный университет(57) Устройство для вычисления полиномиальных симметрических булевых функций восьми переменных, характеризующееся тем, что содержит с первого по шестой элементы И, мажоритарный элемент с порогом два, мажоритарный элемент с порогом четыре, мажоритарный элемент с порогом шесть, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом пять,первый и второй элементы СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, выход -го, где 1, 2, из которых соединен с -м выходом устройства, (2)-й, где 1, 2 6, выход которого соединен с выходом -го элемента И, причем -й, где 1, 2 8, вход шестого элемента 17011 1 2013.04.30 И соединен с -м входом устройства, с -м входом мажоритарного элемента с порогом два, с -м входом мажоритарного элемента с порогом четыре, с -м входом мажоритарного элемента с порогом шесть, с -м входом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом пять и с -м входом первого элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, выход которого соединен с первыми входами первого, третьего и пятого элементов И, второй вход которого соединен с выходом мажоритарного элемента с порогом шесть, с первым входом четвертого элемента И и с первым входом второго элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, второй вход которого соединен с выходом шестого элемента И, с инверсным входом четвертого элемента И и с инверсным входом второго элемента И, прямой вход которого соединен с выходом мажоритарного элемента с порогом четыре, со вторым входом третьего элемента И и с третьим входом второго элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА,четвертый вход которого соединен с выходом мажоритарного элемента с порогом два и со вторым входом первого элемента И, инверсный вход которого соединен с выходом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом пять. Изобретение относится к области вычислительной техники и предназначено для вычисления полиномиальных симметрических булевых функций восьми переменных. Известно устройство для вычисления полиномиальных симметрических булевых функций восьми переменных, содержащее элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре,элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом пять, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом шесть, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом восемь, элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, восемь информационных и шесть настроечных входов, выход 1. Известное устройство, как и заявляемое устройство, содержит элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом пять и элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, выход которого соединен с выходом устройства. Недостатком известного устройства являются ограниченные функциональные возможности, поскольку устройство не позволяет одновременно вычислять полиномиальные симметрические булевы функции восьми переменных. Наиболее близким по функциональным возможностям и конструкции техническим решением к предлагаемому устройству является устройство для вычисления полиномиальных симметрических булевых функций восьми переменных, которое содержит семь элементов ИСКЛЮЧАЮЩЕЕ ИЛИ с порогами от единицы до семи, элемент И, шесть элементов ИЛИ, восемь входов и восемь выходов 2. Конструктивная сложность устройства (по числу входов логических элементов) равна 82, а его быстродействие, определяемое глубиной схемы, составляет 2, где- задержка на один логический элемент. Устройство-прототип, как и заявляемое устройство, содержит элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом пять и элемент И, выход которого соединен с одним из выходов устройства. Недостатком устройства-прототипа является высокая конструктивная сложность. Изобретение направлено на решение технической задачи уменьшения конструктивной сложности устройства для вычисления полиномиальных симметрических булевых функций восьми переменных. Устройство для вычисления полиномиальных симметрических булевых функций восьми переменных характеризуется тем, что содержит с первого по шестой элементы И,мажоритарный элемент с порогом два, мажоритарный элемент с порогом четыре, мажоритарный элемент с порогом шесть, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом пять, первый и второй элементы СЛОЖЕНИЕ ПО МОДУЛЮ ДВА. Выход -го, где 1, 2, элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА соединен с -м выходом устройства, (2)-й, где 1, 2, , 6, выход которого соединен с выходом -го элемента И. 2 17011 1 2013.04.30 Причем -й, где 1, 2, , 8, вход шестого элемента И соединен с -м входом устройства, с -м входом мажоритарного элемента с порогом два, с -м входом мажоритарного элемента с порогом четыре, с -м входом мажоритарного элемента с порогом шесть, с -м входом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом пять и с -м входом первого элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА. Выход первого элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА соединен с первыми входами первого и третьего элементов И, а также с первым входом пятого элемента И, второй вход которого соединен с выходом мажоритарного элемента с порогом шесть, с первым входом четвертого элемента И и с первым входом второго элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА. Второй вход второго элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА соединен с выходом шестого элемента И, с инверсным входом четвертого элемента И и с инверсным входом второго элемента И, прямой вход которого соединен с выходом мажоритарного элемента с порогом четыре, со вторым входом третьего элемента И и с третьим входом второго элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА. Четвертый вход второго элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА соединен с выходом мажоритарного элемента с порогом два и со вторым входом первого элемента И, инверсный вход которого соединен с выходом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом пять. Названный технический результат достигается путем использования новых логических элементов (элементов СЛОЖЕНИЕ ПО МОДУЛЮ ДВА и мажоритарных элементов с порогами два, четыре и шесть) и с последующим изменением соединений между элементами логической схемы устройства. На фигуре представлена логическая схема устройства для вычисления полиномиальных симметрических булевых функций восьми переменных. Устройство для вычисления полиномиальных симметрических булевых функций содержит два элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА 1 и 2, мажоритарный элемент с порогом два 3, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом пять 4, мажоритарный элемент с порогом четыре 5, мажоритарный элемент с порогом шесть 6, шесть элементов И 7, 8, ,12, восемь входов 1320 и восемь выходов 2128. Устройство для вычисления полиномиальных симметрических булевых функций восьми переменных работает следующим образом. На входы устройства 1320 поступают (в произвольном порядке) значения переменных х 1, х 2, , х 8. На выходах устройства 2128 реализуются полиномиальные симметрические булевы функции 88 ( 1 ,2 , ,8 ) , где 1, 2, , 8. Поясним принцип построения и работы заявляемого устройства для вычисления полиномиальных симметрических булевых функций восьми переменных. Известно, что произвольная симметрическая булева функцияпеременных(1, 2, , ) с рабочими числами 1, 2, ,(0) принимает значение 1 на тех и только тех наборах значений переменных 1, 2, , , которые содержат ровно(1, 2, , ) единиц. Такая булева функция обозначается через 1,2 , ,( ) . Если 1, то симметрическая булева функция( ) называется фундаментальной (или элементарной). Симметрическая булева функцияпеременных 1,2 , ,( ) называется полиномиальной, если ее полином Жегалкина содержит (все) элементарные конъюнкции, ранг которых равен, где 1. Полиномиальная симметрическая булева функцияпере менных обозначается через( ) . Очевидно, что полином Жегалкина функции, где 1, 2, , . Заявляемое устройство (фигура) синтезировано на основе применения следующих аналитических представлений полиномиальных симметрических булевых функций 812345678,1, если х 1 х 2 х 3 х 4 х 5 х 6 х 7 х 82 28 ( )0 в противном случае,1, если х 1 х 2 х 3 х 4 х 5 х 6 х 7 х 84 48 ( )0 в противном случае,1, если х 1 х 2 х 3 х 4 х 5 х 6 х 7 х 86 68 ( )0 в противном случае,1, если х 1 х 2 х 3 х 4 х 5 х 6 х 7 х 85 5 8 ( )0 в противном случае,812345678. Основным достоинством устройства для вычисления полиномиальных симметрических булевых функций восьми переменных является низкая конструктивная сложность(по числу входов логических элементов), равная 63. Кроме того, устройство имеет высокое быстродействие, которое составляет 2, гдезадержка на один логический элемент. Национальный центр интеллектуальной собственности. 220034, г. Минск, ул. Козлова, 20.