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

(51) МПК НАЦИОНАЛЬНЫЙ ЦЕНТР ИНТЕЛЛЕКТУАЛЬНОЙ СОБСТВЕННОСТИ УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ ПОЛУСИММЕТРИЧЕСКИХ БУЛЕВЫХ ФУНКЦИЙ ТРЕХ ПЕРЕМЕННЫХ(71) Заявитель Белорусский государственный университет(72) Автор Супрун Валерий Павлович(73) Патентообладатель Белорусский государственный университет(57) Устройство для вычисления полусимметрических булевых функций трех переменных,содержащее элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, выход которого соединен с выходом устройства, первый настроечный вход которого соединен с первым входом элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА первый, второй и третий элементы И, -й вход первого из которых, где 1, 2, соединен с (1)-м настроечным входом устройства, а выход - со вторым входом элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, третий вход которого соединен с выходом второго элемента И, первый вход которого соединен с четвертым настроечным входом устройства, информационный вход которого соединен со вторым входом второго элемента И и с первым входом третьего элемента И, (1)-й вход которого соединен с (4)-м настроечным входом устройства, а выход - с четвертым входом элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА. Изобретение относится к области вычислительной техники и микроэлектроники и предназначено для вычисления полусимметрических булевых функций трех переменных. Известно устройство для вычисления симметрических булевых функций трех переменных, которое содержит элемент ИСКЛЮЧАЮЩЕЕ ИЛИ, элемент РАВНОЗНАЧНОСТЬ, элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, шесть настроечных входов и один выход 1. 16124 1 2012.08.30 Известное устройство, как и предлагаемое устройство, содержит элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, выход которого соединен с выходом устройства, первый настроечный вход которого соединен с первым входом элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА. Недостатком известного устройства являются низкие функциональные возможности,поскольку устройство не позволяет вычислять (реализовать) полусимметрические булевы функции трех переменных. Наиболее близким по функциональным возможностям и конструкции техническим решением к предлагаемому устройству является устройство для вычисления симметрических булевых функций трех переменных, которое содержит элемент И-НЕ, элемент ИЛИНЕ, элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, два информационных и три настроечных входов, один выход 2. Устройство-прототип предназначено для вычисления произвольных симметрических булевых функций трех переменных. Сложность устройства (по числу входов логических элементов) равна 9, а быстродействие составляет 2, где- задержка на один логический элемент. Устройство-прототип, как и заявляемое устройство, содержит элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, выход которого соединен с выходом устройства, первый настроечный вход которого соединен с первым входом элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА. Недостатком устройства-прототипа являются ограниченные функциональные возможности, поскольку устройство не позволяет вычислять полусимметрические булевы функции трех переменных. Изобретение направлено на решение задачи расширения функциональных возможностей устройства для вычисления симметрических булевых функций трех переменных за счет реализации полусимметрических булевых функций трех переменных. Устройство для вычисления полусимметрических булевых функций трех переменных содержит элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, выход которого соединен с выходом устройства, первый настроечный вход которого соединен с первым входом элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА. Устройство содержит также первый, второй и третий элементы И, -й вход первого из которых, где 1, 2, соединен с (1)-м настроечным входом устройства, а выход - со вторым входом элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА. Третий вход элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА соединен с выходом второго элемента И, первый вход которого соединен с четвертым настроечным входом устройства. Информационный вход устройства соединен со вторым входом второго элемента И и с первым входом третьего элемента И, (1)-й вход которого соединен с (4)-м настроечным входом устройства, а выход - с четвертым входом элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА. Названный технический результат достигается с помощью введения в логическую схему устройства новых элементов (элементов И) с последующим изменением соединений между логическими элементами схемы. На фигуре представлена логическая схема устройства для вычисления полусимметрических булевых функций трех переменных. Устройство для вычисления полусимметрических булевых функций трех переменных содержит три элемента И 1, 2 и 3, элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА 4, информационный вход 5, шесть настроечных входов 611 и выход 12. Устройство для вычисления полусимметрических булевых функций трех переменных работает следующим образом. На информационный вход устройства 5 поступают значения переменной 3, на настроечные входы 611 - сигналы настройки 0,15, значения которых принадлежат множеству 0,1, 1 , 1 ,2 ,2 . 2 16124 1 2012.08.30 На выходе устройства 12 вычисляется (реализуется) полусимметрическая булева функция(1,3), где,2, определяемая вектором настройки(0,15). Поясним принцип построения и работы устройства для вычисления полусимметрических булевых функций трех переменных. Произвольная булева функцийпеременных(,2) называется симметрической, если она не меняет своего значения после перестановки любой пары переменныхи , гдеи ,1,2. Симметрическая булева функция(,2) определяется множеством рабочих чисела 1,а 2 а. Функцияпринимает единичные значения на тех и только тех наборах значений переменных х 1,х 2 х, которые содержат ровноединиц, где 0,1 и 01. Симметрическая булева функция(,2) взаимно однозначно представляется(1)-разрядным двоичным вектором (локальным кодом)(0,1), где- значение функциина (любом) наборе значенийпеременных, содержащем(0) единиц, т.е.1 тогда и только тогда, когда- рабочее число . Булева функцияпеременных(,2) называется полусимметрической, если булевы функции 0(0)0(1,0) и(1)(,1) являются симметрическими, зависящими от -1 переменных множества Х 1 х 1,х 2 х-1, где 3. Такая булева функция обозначается через(1,). Любая симметрическая булева функцияпеременныхявляется полусимметрической, а обратное утверждение - не всегда верно. Другими словами, симметрические булевы функцииявляются частным случаем полусимметрических функций(1,). Для булевой функции(,) имеет место формула дизъюнктивного разложения по переменнойвида(1) Симметрические булевы функции -1 переменных 00(1), 11(1) задаются 0 посредством -разрядных двоичных векторов (0)( 0 , 1 0 -1 ) и (1)( 1 , 1 1 -1 ) 0 соответственно. Если для компонент векторов (0) и (1) выполняется условие 01-11, 2 -1,то полусимметрическая булева функция(1,) является симметрической, зависящей отпеременных. Двоичный 2-разрядный вектор 0), (1 является локальным кодом булевой функции(1,). Так как двоичный векторимеет 2 разрядов, то число различных функций вида(1,) равно 224 (число симметрических булевых функцийпеременныхравно 21). Если в формуле (1) заменить 1 , то На фигуре приведена логическая схема устройства для вычисления полусимметрических булевых функций трех переменных(1,3). Первообразная функция логической схемы имеет вид(0,15,3)01233345. Поясним алгоритм настройки устройства на вычисление произвольно заданной функции(1,3). Если 3, то формулы (1) и (2) принимают вид Посредством таблицы, применительно к вектору( 0 , 1 ,), вычисляем зна 2 чения вектора (3,31,32,), где 0, 1. Полученные вектора (0,1,2),(3,4,5) являются составными частями искомого вектора настройки(0,15). Пример 1 Допустим, что на выходе 12 устройства (фигура) требуется вычислить полусимметрическую булеву функцию(0,1,2)(0,1,2) и (3,4,5)(1,0,0), т.е.(0,1,2,1,0,0). Следовательно, для вычисления на выходе 12 устройства функции(,3) необходимо на настроечные входы 6, 10 и 11 подать значение 0, на настроечный вход 7 значение х 1, на настроечный вход 8 - значение х 2 и на настроечный вход 9 - значение 1. При этом первообразная функция (3) устройства принимает вид(1 ,3 )01 2313001 231 231 231 23( 12 )3 . Пример 2 Допустим, что на выходе 12 устройства требуется вычислить симметрическую булеву функцию( 0 , 1 ,2 )(0, 1 ,2 ), ( 3 ,4 ,5 )(1, 1 ,2 )(0, 1 ,2 ,1, 1 ,2 ). Значит, для реализации на выходе 12 устройства заданной функциинеобходимо на настроечные входы 611 подать значения 0, х 1, х 2, 1, 1 и 2 соответственно. Здесь первообразная функция (3) устройства принимает вид( 1 ,2 ,3 )01 2313121 23(112 )1 23( 121 2 )1 2 (31)3( 12 )123123123 . Основным достоинством заявляемого устройства являются широкие функциональные возможности. Устройство (при подходящей настройке) реализует любую из 64 полусимметрических булевых функций, зависящих от переменных х 1, х 2, х 3. Сложность устройства равна 11. В то время устройство-прототип ориентировано на вычисление только симметрических булевых функций трех переменных х 1, х 2, х 3, число которых равно 16. При этом заявляемое устройство и устройство-прототип имеют одинаковое быстродействие, определяемое глубиной схемы. 16124 1 2012.08.30 Устройство для вычисления полусимметрических булевых функций трех переменных Локальный двоичный код симметрической Сигналы настройки булевой функции(1,2) Национальный центр интеллектуальной собственности. 220034, г. Минск, ул. Козлова, 20.