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

(51) МПК НАЦИОНАЛЬНЫЙ ЦЕНТР ИНТЕЛЛЕКТУАЛЬНОЙ СОБСТВЕННОСТИ УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ ПОЛУСИММЕТРИЧЕСКИХ БУЛЕВЫХ ФУНКЦИЙ ЧЕТЫРЕХ ПЕРЕМЕННЫХ(71) Заявитель Белорусский государственный университет(72) Автор Супрун Валерий Павлович(73) Патентообладатель Белорусский государственный университет(57) Устройство для вычисления полусимметрических булевых функций четырех переменных, содержащее элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, выход которого соединен с выходом устройства, первый настроечный вход которого соединен с первым входом элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА с первого по пятый элементы И, -й вход первого из которых, где 1, 2, соединен с -м информационным входом устройства, с -м инверсным входом второго элемента И, с -м входом третьего элемента И и с -м инверсным входом четвертого элемента И, а выход соединен со вторым входом элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, входы которого с третьего по шестой соединены соответственно с выходами второго, третьего, четвертого и пятого элементов И, первый вход последнего из которых соединен с третьими входами третьего и четвертого элементов И и с третьим информационным входом устройства, (1)-й настроечный вход которого соединен с третьим входом -го элемента И (3)-й настроечный вход устройства соединен с четвертым входом (2)-го элемента И, а шестой настроечный вход устройства соединен со вторым входом пятого элемента И. 16357 1 2012.10.30 Изобретение относится к области вычислительной техники и микроэлектроники и предназначено для вычисления полусимметрических булевых функций четырех переменных. Известно устройство для вычисления симметрических булевых функций четырех переменных, которое содержит элемент ИСКЛЮЧАЮЩЕЕ ИЛИ, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом два, элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, двенадцать настроечных входов и один выход 1. Известное устройство, как и заявляемое устройство, содержит элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, выход которого соединен с выходом устройства, первый настроечный вход которого соединен с первым входом элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА. Недостатком известного устройства являются низкие функциональные возможности,поскольку устройство не позволяет вычислять (реализовать) полусимметрические булевы функции четырех переменных. Наиболее близким по функциональным возможностям и конструкции техническим решением к предлагаемому устройству является устройство для вычисления симметрических булевых функций четырех переменных, которое содержит элемент ИСКЛЮЧАЮЩЕЕ ИЛИ, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре, элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, девять информационных входов и один выход 2. Устройство-прототип предназначено для вычисления произвольных симметрических булевых функций четырех переменных. Конструктивная сложность устройства (по числу входов логических элементов) равна 16, а быстродействие составляет 2, где- задержка на один логический элемент. Устройство-прототип, как и предлагаемое устройство, содержит элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, выход которого соединен с выходом устройства, первый настроечный вход которого соединен с первым входом элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА. Недостатком устройства-прототипа являются ограниченные функциональные возможности, поскольку устройство не позволяет вычислять полусимметрические булевы функции четырех переменных. Изобретение направлено на решение задачи расширения функциональных возможностей устройства для вычисления симметрических булевых функций четырех переменных за счет реализации полусимметрических булевых функций четырех переменных. Устройство для вычисления полусимметрических булевых функций четырех переменных содержит элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, выход которого соединен с выходом устройства, первый настроечный вход которого соединен с первым входом элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА. Устройство также содержит с первого по пятый элементы И, -й вход первого из которых, где 1, 2, соединен с -м информационным входом устройства, с -м инверсным входом второго элемента И, с -м входом третьего элемента И и с -м инверсным входом четвертого элемента И. Выход первого элемента И соединен со вторым входом элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, входы которого с третьего по шестой соединены соответственно с выходами второго, третьего, четвертого и пятого элементов И, первый вход последнего из которых соединен с третьими входами третьего и четвертого элементов И и с третьим информационным входом устройства. Причем (1)-й настроечный вход устройства соединен с третьим входом -го элемента И, (3)-й настроечный вход устройства соединен с четвертым входом (2)-го элемента И, а шестой настроечный вход устройства соединен со вторым входом пятого элемента И. Названный технический результат достигается с помощью введения в логическую схему устройства новых элементов (элементов И) с последующим изменением соединений между логическими элементами схемы. 16357 1 2012.10.30 На фигуре представлена логическая схема устройства для вычисления полусимметрических булевых функций четырех переменных. Устройство для вычисления полусимметрических булевых функций четырех переменных содержит пять элементов И 15, элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА 6,три информационных входа 7, 8 и 9, шесть настроечных входов 1015 и выход 16. Устройство для вычисления полусимметрических булевых функций четырех переменных работает следующим образом. На информационные входы устройства 7, 8 и 9 поступают значения переменных 1, 2,4, на настроечные входы 1015 - сигналы настройки 0, 1 5, значения которых принадлежат множеству 0, 1,3 ,3 . На выходе устройства 16 вычисляется полусимметрическая булева функция(1, 4), где 11, 2, 3, определяемая вектором настройки(, 1 5). Поясним принцип построения и работы устройства для вычисления полусимметрических булевых функций четырех переменных. Булева функцияпеременных(1, 2 ) называется симметрической, если она не меняет своего значения после перестановки любой пары переменных 1 и , гдеи ,1, 2 . Симметрическая булева функция(1, 2 ) определяется множеством рабочих чисел 1, 2 . Функцияпринимает единичные значения на тех и только тех наборах значений переменных 1, 2 , которые содержат ровноединиц, где 0,1 и 01. Симметрическая булева функция(1, 2 ) взаимно однозначно представляется (1)-разрядным двоичным вектором (локальным кодом)(0, 1 ), где- значение функциина (любом) наборе значенийпеременных, содержащем(0) единиц, т.е.1 тогда и только тогда, когда- рабочее число . Булева функцияпеременных(1, 2 ) называется полусимметрической, если булевы функции 0(0)0(1, 0) и 1(1)1(1, 1) являются симметрическими, зависящими от -1 переменных множества 11, 2 -1, где 3. Такая булева функция обозначается через(1, ). Любая симметрическая булева функцияпеременныхявляется полусимметрической, а обратное утверждение - не всегда верно. Другими словами, симметрические булевы функцииявляются частным случаем полусимметрических функций(1, ). Для булевой функции(1, ) имеет место формула дизъюнктивного разложения по переменнойвида(1 ,)01 . Симметрические булевы функции -1 переменных 00, 11(1) задаются по 1 1 средством -разрядных двоичных векторов (0 )( 00 , 10 01 ) и (1 )( 0 , 11 1 ) соответственно. Если для компонент векторов (0) и (1) выполняется условие 011 , где 1, 2 -1, то полусимметрическая булева функция(1, ) является симметрической, зависящей отпеременных. Двоичный вектор 0), (1 является локальным кодом булевой функции(1, ). Так как векторимеет 2 разрядов, то число различных функций вида(1, ) равно 224 (число симметрических булевых функцийпеременныхравно 21). Если в формуле (1) заменить 1 , то На фигуре приведена логическая схема устройства для вычисления полусимметрических булевых функций четырех переменных(1, 4). Первообразная функция логической схемы имеет вид(3)1234124454 . Поясним алгоритм настройки устройства (фигура) на вычисление произвольно заданной функции(, 4). Если 4, то формулы (1) и (2) принимают вид(1 ,4 )041 ,(5) где 0(1, 2, 3)0(1, 2, 3) и 1(1, 2, 3)0(1, 2, 3)1(1, 2, 3). Представим функцию(1,4) посредством формул (4), (5) и последовательно вычис 1 1 1 0 0 лим значения векторов (0 )( 00 , 10 ,20 ,30 ) , (1 )( 0 , 11 ,2 ,3 ) , ( 0 )( 0 , 1 ,0 ,3 ) ,0 2 Посредством таблицы (таблица), применительно к векторам ( 0 , 1 ,,3 ) , вы 2 числим значения векторов (3, 31, 32), где 0, 1. Полученные при этом вектора (0, 1, 2),(3, 4, 5) являются составными частями искомого вектора настройки(0, 1 5). Двоичный код симметрической булевой Вектор настройки функции(1, 2, 3) Пример 1. Допустим, что на выходе 16 устройства (фигура) требуется вычислить полусимметрическую булеву функцию(3, 4, 5)(0, 0,1), т.е.(3, 0, 0, 0, 0, 1). Следовательно, для вычисления на выходе 16 устройства функции (1, 4)1234 необходимо на настроечный 10 подать значение 3, на настроечные входы 11, 12, 13 и 14 значение 0, на настроечный вход 15 - значение 1. В качестве проверки подставим в формулу (3) значения вектора настройки(х 3, 0, 0, 0, 0, 1), тогда первообразная функция устройства будет иметь вид(1 ,4 )123120012041204141 234 . Пример 2. Предположим, что на выходе 16 устройства требуется вычислить полусимметрическую булеву функцию т.е.0,3 , 0, 1, 1,3 . Следовательно, для того чтобы на выходе 16 устройства реализовать заданную полусимметрическую булеву функцию(1, 4), необходимо на настроечные входы 10 и 12 подать значения 0, на настроечный вход 11 - значение 3 , на настроечные входы 13 и 14 - значение 1 и на настроечный вход 15 - значение 3. В таком случае первообразная функция (3) принимает вид(1 ,4 )12012301214121434 12334121212123412341234123412341234123412341234 . Основным достоинством заявляемого устройства являются широкие функциональные возможности. Устройство реализует любую из 256 полусимметрических булевых функций, зависящих от переменных 1, 2, 3, 4. Отметим, что устройство-прототип ориентировано на вычисление только симметрических булевых функций четырех переменных 1, 2, 3, 4, число которых равно 32. При этом заявляемое устройство и устройство-прототип имеют одинаковое быстродействие, определяемое глубиной схемы. 1. Патент РБ 8619, МПК 06 7/00, 2006. 2. Патент РБ 10219, МПК 06 7/00, 2008 (прототип). Национальный центр интеллектуальной собственности. 220034, г. Минск, ул. Козлова, 20.