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

(51) МПК НАЦИОНАЛЬНЫЙ ЦЕНТР ИНТЕЛЛЕКТУАЛЬНОЙ СОБСТВЕННОСТИ УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ ПОЛИНОМИАЛЬНЫХ СИММЕТРИЧЕСКИХ БУЛЕВЫХ ФУНКЦИЙ ДЕВЯТИ ПЕРЕМЕННЫХ(71) Заявитель Белорусский государственный университет(72) Автор Супрун Валерий Павлович(73) Патентообладатель Белорусский государственный университет(57) Устройство для вычисления полиномиальных симметрических булевых функций девяти переменных, характеризующееся тем, что содержит с первого по четвертый элементы СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, первый, второй и третий элементы И, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре, мажоритарный элемент с порогом два, мажоритарный элемент с порогом четыре, мажоритарный элемент с порогом шесть, мажоритарный элемент с порогом восемь, -й вход которого, где 1, 2 9, соединен с -м входом устройства, с -м входом мажоритарного элемента с порогом два, с -м входом мажоритарного элемента с порогом четыре, с -м входом мажоритарного элемента с порогом шесть и с -м входом первого элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, выход которого соединен с первым входом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре, с первым входом -го элемента И, где 1, 2, 3, и с первым выходом устройства, второй выход которого соединен с выходом второго элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, первый 17508 1 2013.08.30 вход которого соединен с выходом мажоритарного элемента с порогом два и со вторым входом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре, выход которого соединен с третьим выходом устройства, четвертый выход которого соединен с выходом третьего элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, первый вход которого соединен со вторым входом второго элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, с первым инверсным входом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре, с выходом мажоритарного элемента с порогом четыре и со вторым входом первого элемента И, выход которого соединен с пятым выходом устройства, шестой выход которого соединен с выходом четвертого элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, первый вход которого соединен с выходом мажоритарного элемента с порогом шесть, с третьим входом второго элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, с третьим входом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре и со вторым входом второго элемента И, выход которого соединен с седьмым выходом устройства, восьмой выход которого соединен с выходом мажоритарного элемента с порогом восемь, с четвертым входом второго элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, со вторым инверсным входом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре,со вторым входом третьего элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, с инверсным входом первого элемента И, со вторым входом четвертого элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, с инверсным входом второго элемента И и со вторым входом третьего элемента И, выход которого соединен с девятым выходом устройства. Изобретение относится к области вычислительной техники и микроэлектроники и предназначено для вычисления полиномиальных симметрических булевых функций девяти переменных. Известно устройство для вычисления фундаментальных симметрических булевых функцийпеременных, содержащее при 9 три элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, элемент И, мажоритарный элемент с порогом шесть и мажоритарный элемент с порогом восемь, девять информационных и пять настроечных входов, один выход 1. Известное устройство, как и заявляемое устройство, содержит мажоритарный элемент с порогом шесть, мажоритарный элемент с порогом восемь, три элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА и элемент И, выход которого соединен с выходом устройства. Недостатком известного устройства являются ограниченные функциональные возможности, поскольку устройство не позволяет вычислять полиномиальные симметрические булевы функции девяти переменных. Наиболее близким по функциональным возможностям и конструкции техническим решением к предлагаемому устройству является устройство для вычисления полиномиальных симметрических булевых функций девяти переменных, содержащее элементы ИСКЛЮЧАЮЩЕЕ ИЛИ с порогами четыре, пять, восемь и девять, элемент И, элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, девять информационных и семь настроечных входов,один выход 2. Устройство-прототип, как и заявляемое устройство, содержит элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре, элемент И и элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА,выход которого соединен с выходом устройства. Недостатком устройства-прототипа являются ограниченные функциональные возможности, поскольку устройство не позволяет одновременно вычислять девять полиномиальных симметрических булевых функций, зависящих от девяти переменных. Изобретение направлено на решение технической задачи расширения функциональных возможностей устройства для вычисления полиномиальных симметрических функций за счет одновременного вычисления (реализации) всех девяти полиномиальных симметрических булевых функций девяти переменных. 2 17508 1 2013.08.30 Устройство для вычисления полиномиальных симметрических булевых функций девяти переменных характеризуется тем, что содержит с первого по четвертый элементы СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, первый, второй и третий элементы И, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре, мажоритарный элемент с порогом два, мажоритарный элемент с порогом четыре, мажоритарный элемент с порогом шесть,мажоритарный элемент с порогом восемь. Причем -й вход мажоритарного элемента с порогом восемь, где 1, 2, , 9, соединен с -м входом устройства, с -м входом мажоритарного элемента с порогом два, с -м входом мажоритарного элемента с порогом четыре, с -м входом мажоритарного элемента с порогом шесть и с -м входом первого элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА. Выход первого элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА соединен с первым входом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре, с первым входом -го элемента И,где 1, 2, 3, и с первым выходом устройства, второй выход которого соединен с выходом второго элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА. Первый вход второго элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА соединен с выходом мажоритарного элемента с порогом два и со вторым входом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре, выход которого соединен с третьим выходом устройства. Четвертый выход устройства соединен с выходом третьего элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, первый вход которого соединен со вторым входом второго элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, с первым инверсным входом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре, с выходом мажоритарного элемента с порогом четыре и со вторым входом первого элемента И. Выход первого элемента И соединен с пятым выходом устройства, шестой вход которого соединен с выходом четвертого элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА. Первый вход четвертого элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА соединен с выходом мажоритарного элемента с порогом шесть, с третьим входом второго элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, с третьим входом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре и со вторым входом второго элемента И, выход которого соединен с седьмым выходом устройства. Восьмой выход устройства соединен с выходом мажоритарного элемента с порогом восемь, с четвертым входом второго элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, со вторым инверсным входом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре, со вторым входом третьего элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, с инверсным входом первого элемента И, со вторым входом четвертого элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, с инверсным входом второго элемента И и со вторым входом третьего элемента И, выход которого соединен с девятым выходом устройства. Названный технический результат достигается путем использования новых логических элементов (мажоритарных элементов с порогами два, четыре, шесть и восемь) с последующим изменением соединений между элементами логической схемы устройства. На фигуре представлена логическая схема устройства для вычисления полиномиальных симметрических булевых функций. Устройство для вычисления полиномиальных симметрических булевых функций девяти переменных содержит четыре элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА 1, 2, 3 и 4,мажоритарный элемент с порогом два 5, мажоритарный элемент с порогом четыре 6, мажоритарный элемент с порогом шесть 7, мажоритарный элемент с порогом восемь 8, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре 9, три элемента И 10, 11 и 12, девять входов 13, 14 21 и девять выходов 22, 23 30. Устройство для вычисления полиномиальных симметрических булевых функций девяти переменных работает следующим образом. 17508 1 2013.08.30 На входы устройства 13, 14 21 поступают (в произвольном порядке) значения переменных , 2 9. На выходах устройства 22, 23 30 реализуются (вычисляются) полиномиальные симметрические булевы функции 9 (1,2 9 ) , где, 2 9. Поясним принцип построения и работы устройства для вычисления полиномиальных симметрических булевых функций девяти переменных. Известно, что произвольная симметрическая булева функцияпеременных(1 ,2 ) с рабочими числами 1, 2 а (0) принимает значение 1 на тех и только тех наборах значений переменных, 2 , которые содержат ровно(1, 2 ) единиц. Такая булева функция обозначается 1 ,2 (1 ,2 ) . Если 1, то симметрическая булева функция(1 ,2 ) называется фундаментальной (или элементарной). Симметрическая булева функцияпеременных( ) называется полиномиальной, если ее полином Жегалкинасодержит(число соче таний изпо ) элементарных конъюнкций ранга , где, 2 . Полиномиальные симметрические булевы функции девяти переменных 9 (1 ,2 , ,9 ) выражаются формулами через элементарные симметрические булевы функции следующим образом 1 3 5 7 9 1 ( )9 ( )9 ( )9 ( )9 ( )9 ( ),9 2 2 3 6 79 ( )9 ( )9 ( )9 ( )9 ( ),3 7 4 4 5 6 73 ( )9 ( )9 ( ),9 ( )9 ( )9 ( )9 ( )9 ( ),9 5 7 6 6 75 ( )9 ( )9 ( ),9 ( )9 ()9 ( ),9 7 7 8 9 99 ( )9 ( ), 8 ( )9 ( )9 ( ),9 ( )9 ( ). 9 9 Заявляемое устройство (фигура) синтезировано на основе применения следующих аналитических представлений полиномиальных симметрических булевых функций 17508 1 2013.08.30 1, если 12345678988 ( )9 0 в противном случае. Основным достоинством устройства для вычисления полиномиальных симметрических булевых функций девяти переменных являются широкие функциональные возможности, поскольку устройство позволяет одновременно вычислять все полиномиальные симметрические булевы функции девяти переменных. Кроме того, устройство имеет относительно небольшую сложность (по числу входов логических элементов), равную 66. При этом быстродействие устройства составляет 2,где- задержка на один логический элемент. Источники информации 1. Патент 2117, МПК 06 7/00, 1998. 2. Патент 13809, МПК 06 7/00, 2010 (прототип). Национальный центр интеллектуальной собственности. 220034, г. Минск, ул. Козлова, 20. 5