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

(51) МПК НАЦИОНАЛЬНЫЙ ЦЕНТР ИНТЕЛЛЕКТУАЛЬНОЙ СОБСТВЕННОСТИ УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ ПОЛУСИММЕТРИЧЕСКИХ БУЛЕВЫХ ФУНКЦИЙ ЧЕТЫРЕХ ПЕРЕМЕННЫХ(71) Заявитель Белорусский государственный университет(72) Автор Супрун Валерий Павлович(73) Патентообладатель Белорусский государственный университет(57) Устройство для вычисления полусимметрических булевых функций четырех переменных, содержащее с первого по третий элементы И и первый элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, выход которого соединен с выходом устройства, а первый вход - с первым настроечным входом устройства, (1)-й настроечный вход которого, где 1, 2, 3,соединен с первым входом -го элемента И, выход которого соединен с (1)-м входом первого элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, мажоритарный элемент с порогом два и второй элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, выход которого соединен со вторым входом первого и третьего элементов И, а -й вход - с -м информационным входом устройства и с -м входом мажоритарного элемента с порогом два, выход которого соединен со вторым входом второго элемента И и с третьим входом третьего элемента И. Изобретение относится к области вычислительной техники и микроэлектроники и предназначено для вычисления полусимметрических булевых функций четырех переменных. 16714 1 2012.12.30 Известно устройство для вычисления симметрических булевых функций четырех переменных, которое содержит элемент ИСКЛЮЧАЮЩЕЕ ИЛИ, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре, элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, девять настроечных входов и выход 1. Известное устройство, как и изобретение, содержит элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, выход которого соединен с выходом устройства, первый настроечный вход которого соединен с первым входом элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА. Недостатком известного устройства являются ограниченные функциональные возможности, поскольку устройство не позволяет вычислять полусимметрические булевы функции четырех переменных. Наиболее близким по функциональным возможностям и конструкции техническим решением к заявляемому устройству является устройство для вычисления полусимметрических булевых функций четырех переменных, которое содержит пять элементов И, элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, три информационных и шесть настроечных входов, выход 2. Устройство-прототип предназначено для вычисления полусимметрических булевых функций четырех переменных(1, 4), где 11, 2, 3. Конструктивная сложность устройства (по числу входов логических элементов) равна 22, а быстродействие составляет 2, где- задержка на один логический элемент. Устройство-прототип, как и предлагаемое устройство, содержит с первого по третий элементы И и элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, выход которого соединен с выходом устройства, а первый вход - с первым настроечным входом устройства, (1)-й настроечный вход которого, где 1, 2, 3, соединен с первым входом -го элемента И, выход которого соединен с (1)-м входом элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА. Недостатком устройства-прототипа является большое число внешних выводов, равное 10 (три информационных и шесть настроечных входов, выход). Изобретение направлено на решение следующей технической задачи уменьшение числа внешних выводов устройства для вычисления полусимметрических булевых функций четырех переменных. Устройство для вычисления полусимметрических булевых функций четырех переменных содержит с первого по третий элементы И и первый элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА. Выход первого элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА соединен с выходом устройства, а первый вход - с первым настроечным входом устройства. Причем (1)-й настроечный вход устройства, где 1, 2, 3, соединен с первым входом -го элемента И, выход которого соединен с (1)-м входом первого элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА. Устройство содержит также мажоритарный элемент с порогом два и второй элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА. Выход второго элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА соединен со вторым входом первого и третьего элементов И, а -й вход - с -м информационным входом устройства и с -м входом мажоритарного элемента с порогом два. Выход мажоритарного элемента с порогом два соединен со вторым входом второго элемента И и с третьим входом третьего элемента И. Названный технический результат достигается посредством введения в логическую схему устройства мажоритарного элемента с порогом два и второго элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА с последующим изменением соединений между логическими элементами схемы. На фигуре представлена логическая схема устройства для вычисления полусимметрических булевых функций четырех переменных. 16714 1 2012.12.30 Устройство для вычисления полусимметрических булевых функций четырех переменных содержит два элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА 1 и 2, мажоритарный элемент с порогом два 3, три элемента И 4, 5 и 6, три информационных входа 7, 8 и 9, четыре настроечных входа 1013, выход 14. Устройство для вычисления полусимметрических булевых функций четырех переменных работает следующим образом. На информационные входы 7, 8 и 9 устройства поступают (в произвольном порядке) значения переменных 1, 2 и 3, на настроечные входы 1013 - сигналы настройки 0, 1,2, 3, значения которых принадлежат множеству 0, 1,4 ,4 . На выходе 14 устройства вычисляется (реализуется) полусимметрическая булева функция(, 4), где, 2, 3, определяемая вектором настройки(0, 1, 2, 3). Поясним принцип построения и работы устройства для вычисления полусимметрических булевых функций четырех переменных. Произвольная булева функцияпеременных(1, 2 ) называется симметрической, если она не меняет своего значения после перестановки любой пары переменныхи , гдеи ,1, 2 . Симметрическая булева функция(1, 2 ) определяется множеством рабочих чисел 1, 2 . Функцияпринимает единичные значения на тех и только тех наборах значений переменных 1, 2 , которые содержат ровноединиц, где 0,1 и 0. Такая функция обозначается как 1 , 2 Если 1, то функция(1,2 ) называется фундаментальной (элементарной) симметрической булевой функциейпеременных с рабочим числом, равным . Симметрическая булева функция(1, 2 ) взаимно однозначно представляется (1)-разрядным двоичным вектором (локальным кодом)(0,1), гдезначение функциина (любом) наборе значенийпеременных, содержащем(0) единиц, т.е.1 тогда и только тогда, когда- рабочее число функции . Булева функцияпеременных(, 2 ) называется полусимметрической, если булевы функции 0(0) и 1(х 1) являются симметрическими, зависящими от переменных 11, 2 -1, где 3. Такая булева функция обозначается как(, ). Формула дизъюнктивного разложения функции(1, ) по переменным множества 1 имеет вид 0 11 где 11 (1 ) - фундаментальные симметрические булевы функции от -1 переменных, а булевы функциизависят только от одной переменной . Здесь 0, 1 -1. Двоичный 2-разрядный вектор 0), (1) (-1 называется локальным кодом полусимметрической булевой функции(, ). Наряду с дизъюнктивным разложением (1) существует полиномиальное разложение функции(1, ) по -1 переменным вида где 11 (1 ) - полиномиально-однородные симметрические булевы функции от -1 переменных и 0 1 (1 )1 , а функциизависят от функций, где 16714 1 2012.12.30 децкого Д.А. Реализация бисимметрических булевых функций логическими схемами // Известия вузов. Приборостроение. - 2010. - 5. - С. 17-25. В частности, если 8, то 00, 10,202,30123,(3) 404,50145,60246,70127. Отметим, что локальные кодыибулевых функцийисвязаны между собой, согласно формулам (3), где 0, 1 7. Если 4, то формулы (1)-(3) принимают вид 1(4) где (0)(0), (1)(0)(1), (Н 2)(0)(2) и (3)(0)(1)(2)(3). Логическая схема устройства для вычисления полусимметрических булевых функций четырех переменных, синтезированная на основе применения формулы полиномиального разложения (4), приведена на фигуре. Первообразная функция устройства имеет вид(, 2, 3, 0, , 2, 3)01(1 х 2 х 3)2(121323)3123. Отметим, что при выводе формулы (5) использовалось равенство Если обозначить 0 , 1 , то значения разрядов вектора настройки(0, , 2, 3) устройства на реализацию полусимметрической функции(, 4) вычисляются по формуле(6)0414 ,где 0, 1, 2, 3. Рассмотрим пример вычисления (реализации) на выходе 14 устройства (фигура) некоторой булевой функции(, 4). Допустим, что на выходе 14 устройства требуется вычислить полусимметрическую булеву функцию(Н 3)(0)(0)(2)(3)(0,1). Принимая во внимание формулу (6), получаем 01, 11, 21 и 34. Следовательно, для реализации на выходе 14 устройства полусимметрической булевой функции(1 ,2 ,3 ,4 )1231234 необходимо на его настроечные входы 1013 подать значения разрядов вектора настройки(1, 1, 1, 4). Для проверки правильности функционирования заявляемого устройства подставим в(1 ,2 ,3 , 1, 1, 1,4 )11(123 )1(1 21 323 )1 23411231 21 3231 231 23412312341231234 . Основным достоинством заявляемого устройства является небольшое число внешних выводов, равное 8 (три информационных и четыре настроечных входов, выход). Устройство-прототип имеет 10 внешних выводов (три информационных и шесть настроечных входов, выход). Кроме того, конструктивная сложность заявляемого устройства равна 17, а сложность устройства-прототипа составляет 22. 1. Патент РБ 10219, МПК 06 7/00, 2008. 2. Заявка на патент РБ 20101194, МПК 06 7/00, 2011 (прототип). Национальный центр интеллектуальной собственности. 220034, г. Минск, ул. Козлова, 20.