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

(51) МПК НАЦИОНАЛЬНЫЙ ЦЕНТР ИНТЕЛЛЕКТУАЛЬНОЙ СОБСТВЕННОСТИ УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ БИСИММЕТРИЧЕСКИХ БУЛЕВЫХ ФУНКЦИЙ ШЕСТИ ПЕРЕМЕННЫХ(71) Заявитель Белорусский государственный университет(72) Автор Супрун Валерий Павлович(73) Патентообладатель Белорусский государственный университет(57) Устройство для вычисления бисимметрических булевых функций шести переменных,содержащее четыре элемента ИЛИ и первый элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА,выход которого соединен с выходом устройства, первый настроечный вход которого соединен с первым входом первого элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, второй вход которого соединен с выходом первого элемента ИЛИ, первый вход которого соединен со вторым настроечным входом устройства, третий, четвертый и пятый настроечные входы которого соединены с первыми входами второго, третьего и четвертого элементов ИЛИ соответственно, отличающееся тем, что содержит второй, третий, четвертый и пятый элементы СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, мажоритарный элемент с порогом два и с первого по седьмой элементы И, выход первого из которых соединен с третьим входом первого элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, четвертый вход которого соединен с выходом второго элемента И, первый вход которого соединен с выходом второго элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, -й вход которого, где 1, 2, 3, соединен с -м информационным входом устройства, с -м входом мажоритарного элемента с порогом два и 16242 1 2012.08.30 с -м входом третьего элемента И, выход которого соединен с пятым входом первого элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, шестой вход которого соединен с выходом четвертого элемента И, первый вход которого соединен с выходом мажоритарного элемента с порогом два, а второй вход соединен с выходом третьего элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, первый и второй входы которого соединены соответственно с выходом третьего элемента ИЛИ и с выходом пятого элемента И, а третий вход соединен с шестым настроечным входом устройства, седьмой настроечный вход которого соединен с первым входом первого элемента И, -й вход которого, где 2, 3, соединен с (2)-м информационным входом устройства, с -м входом первого, второго, третьего и четвертого элементов ИЛИ и с (-1)-м входом пятого, шестого и седьмого элементов И, третьи входы которых соединены соответственно с восьмым, девятым и десятым настроечными входами устройства, одиннадцатый настроечный вход которого соединен с первым входом четвертого элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, второй и третий входы которого соединены соответственно с выходом второго элемента ИЛИ и с выходом шестого элемента И, а выход соединен со вторым входом второго элемента И двенадцатый настроечный вход устройства соединен с первым входом пятого элемента СЛОЖЕНИЕ ПО МОДУДЮ ДВА, второй и третий входы которого соединены соответственно с выходом четвертого элемента ИЛИ и с выходом седьмого элемента И, а выход соединен с четвертым входом третьего элемента И. Изобретение относится к области вычислительной техники и микроэлектроники и предназначено для вычисления бисимметрических булевых функций шести переменных. Известно устройство для вычисления симметрических булевых функций шести переменных, которое содержит два элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, мажоритарный элемент с порогом два, мажоритарный элемент с порогом четыре, семь элементов И,шесть информационных и семь настроечных входов, выход 1. Известное устройство, как и заявляемое, содержит семь элементов И, мажоритарный элемент с порогом два и два элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, выход первого из которых соединен с выходом устройства, первый настроечный вход которого соединен с первым входом первого элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, входы которого со второго по пятый соединены с выходами первого, второго, третьего и четвертого элементов И. Недостатком известного устройства являются низкие функциональные возможности,поскольку устройство не позволяет вычислять (реализовать) бисимметрические булевы функции шести переменных. Наиболее близким по функциональным возможностям и конструкции техническим решением к предлагаемому устройству является устройство для вычисления бисимметрических булевых функций шести переменных, которое содержит два полных одноразрядных сумматора, пятнадцать элементов ИЛИ, элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА,шесть информационных и шестнадцать настроечных входов, выход 2. Устройство-прототип, как и предлагаемое устройство, содержит четыре элемента ИЛИ и элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, выход которого соединен с выходом устройства, первый настроечный вход которого соединен с первым входом элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, второй вход которого соединен с выходом первого элемента ИЛИ, первый вход которого соединен со вторым настроечным входом устройства, третий, четвертый и пятый настроечные входы которого соединены с первыми входами второго, третьего и четвертого элементов ИЛИ соответственно. Недостатком устройства-прототипа является большое число внешних выводов, равное 23 (двадцать два входа и выход). 16242 1 2012.08.30 Изобретение направлено на решение технической задачи уменьшение числа внешних выводов устройства для вычисления бисимметрических булевых функций шести переменных. Устройство для вычисления бисимметрических булевых функций шести переменных содержит четыре элемента ИЛИ и первый элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, выход которого соединен с выходом устройства, первый настроечный вход которого соединен с первым входом первого элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА. Второй вход первого элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА соединен с выходом первого элемента ИЛИ, первый вход которого соединен со вторым настроечным входом устройства, третий, четвертый и пятый настроечные входы которого соединены с первыми входами второго, третьего и четвертого элементов ИЛИ соответственно. В отличие от прототипа устройство содержит второй, третий, четвертый и пятый элементы СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, мажоритарный элемент с порогом два и с первого по седьмой элементы И, выход первого из которых соединен с третьим входом первого элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА. Четвертый вход первого элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА соединен с выходом второго элемента И, первый вход которого соединен с выходом второго элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, -й вход которого, где 1, 2, 3, соединен с -м информационным входом устройства, с -м входом мажоритарного элемента с порогом два и с-м входом третьего элемента И. Выход третьего элемента И соединен с пятым входом первого элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, шестой вход которого соединен с выходом четвертого элемента И,первый вход которого соединен с выходом мажоритарного элемента с порогом два, а второй вход соединен с выходом третьего элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, первый и второй входы которого соединены соответственно с выходом третьего элемента ИЛИ и с выходом пятого элемента И, а третий вход соединен с шестым настроечным входом устройства. Седьмой настроечный вход устройства соединен с первым входом первого элемента И, -й вход которого, где 2, 3, соединен с (2)-м информационным входом устройства, с -м входом первого, второго, третьего и четвертого элементов ИЛИ и с (-1)-м входом пятого, шестого и седьмого элементов И, третьи входы которых соединены соответственно с восьмым, девятым и десятым настроечными входами устройства. Одиннадцатый настроечный вход устройства соединен с первым входом четвертого элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, второй и третий входы которого соединены соответственно с выходом второго элемента ИЛИ и с выходом шестого элемента И, а выход соединен со вторым входом второго элемента И. Двенадцатый настроечный вход устройства соединен с первым входом пятого элемента СЛОЖЕНИЕ ПО МОДУДЮ ДВА, второй и третий входы которого соединены соответственно с выходом четвертого элемента ИЛИ и с выходом седьмого элемента И, а выход соединен с четвертым входом третьего элемента И. Названный технический результат достигается посредством введения в логическую схему устройства новых логических элементов (элементы И и мажоритарный элемент с порогом два) с последующим изменением соединений между элементами схемы. На фигуре представлена логическая схема устройства для вычисления бисимметрических булевых функций шести переменных. Устройство для вычисления бисимметрических булевых функций содержит семь элементов И 17, четыре элемента ИЛИ 811, мажоритарный элемент с порогом два 12, пять элементов СЛОЖЕНИЕ ПО МОДУЛЮ ДВА 13 17, пять информационных входов 1822, двенадцать настроечных входов 2334 и выход 35. Устройство для вычисления бисимметрических булевых функций шести переменных работает следующим образом. На информационные входы устройства 1822 поступают 3 16242 1 2012.08.30 значения переменных 1, 2, 3, 4, 5 соответственно, на настроечные входы 2334 - сигналы настройки 0, 111, значения которых принадлежат множеству 0, 1, 6,6 . На выходе устройства 35 вычисляется (реализуется) бисимметрическая булева функция(1, 2), где 11, 2, 3 и 24, 5, 6, определяемая вектором настройки(0, 1 11). Поясним принцип построения и работы устройства для вычисления бисимметрических булевых функций шести переменных. Произвольная симметрическая булева функцияпеременных(1, 2 ) характеризуется множеством рабочих чисел 1, 2 . Функцияпринимает единичные значения на тех и только тех наборах значений переменных 1, 2 , которые содержат ровноединиц, где 0, 0 и 01. Функцияобозначается как 1 ,2 , где 1, 2 . Если 1, то функцияназывается фундаментальной (или элементарной) симметрической булевой функцией. Симметрическая булева функция(1, 2 ) взаимно однозначно представляется (1)-разрядным двоичным кодом (вектором)(0, 1 ), где- значение функциина (любом) наборе значенийпеременных, содержащем(0) единиц. Другими словами,1 тогда и только тогда, когда- рабочее число функции . Если произвольная булева функцияпеременныхне меняет своего значения после перестановки любой пары переменныхи(гдеи ,1, 2 ), то функцияявляется симметрической. Если функцияне меняет своего значения после перестановки некоторых пар переменныхи , то булева функцияобладает свойством частичной симметрии переменных. Известно, что отношение частичной симметрии разбивает (единственным образом) множество переменных 1, 2 на классы симметрии 1, 2 , где 1. Если 1, то функцияявляется (полностью) симметрической если 2, то- бисимметрическая булева функция если, то функцияне обладает свойством частичной симметрии переменных. Бисимметрическая булева функция обозначается(, 2), где 1, 2 - классы симметрии. Для булевой функции (Х)(1, 2), где 11, 2, 3 и 24, 5, 6, имеет место формула 1(1) где 30 ( 1 ,2 ,3 )123 ,1 3 ( 1 ,2 ,3 )123123123 , 32 ( 1 ,2 ,3 )123123123 ,33 ( 1 ,2 ,3 )1 23 . В формуле (1) булевы функции 00(4, 5, 6), 11(4, 5, 6), 22(4, 5, 6),33(4, 5, 6) являются симметрическими, каждая из которых задается посредством четырехразрядного двоичного вектора ( 0 , 1 ,,3 ) , где 0, 1, 2, 3. 2 Если в формуле (1) заменить 111,221 и 331 , то после несложных преобразований получим 4(2)( 1 21 323 )2 ( 2 )1 233 ( 2 ),где симметрические булевы функции 0(2), 1(2), 2(2), 3(2) вычисляются по формулам 0(2)0(2), 1(2)0(2)1(2),2(2)0(2)2(2), 3(2)0(2)1(2)2(2)3(2). Следовательно, значения компонент двоичных векторов ( 0 , 1 ,,3 ) и 2( 0 , 1 ,,3 ) связаны между собой следующими соотношениями (0, 1, 2, 3) 2 где 0, 1, 2, 3. Поясним метод построения вектора настройки(0, 1 11) заявляемого устройства (фигура) на вычисление произвольно заданной би-симметрической булевой функции(1, 2). 1. Представим функцию(1, 2) посредством формулы (1) и вычислим значения компонент векторов ( 0 , 1 ,,3 ) для симметрических булевых функций 2(4, 5, 6), где 0, 1, 2, 3. 2. Определим по формулам (3) значения компонент двоичных векторов( 0 , 1 ,,3 ) для симметрических булевых функций(4, 5, 6), входя 2 щих в представление функции(1, 2) посредством формулы (2), где 0, 1, 2, 3. 3. Построим вектор настройки(0, 1 11) следующим образом для каждого из 0 2 2 2 двоичных векторов ( 0 )( 0 , 1 ,0 ,0 ) , (1 )(1 , 1 , 1 , 1 ) , ( 2 )( 0 , 1 ,2 ,3 ) 0 2 3 0 1 2 3 2 3 и ( 3 )( 3 , 1 ,3 ,3 ) вычислим с помощью таблицы настроек (таблица) значения век 0 2 3 торов (0, 1, 2), (3, 4, 5), (6, 7, 8) и (9, 10, 11) соответственно. Первообразная функция заявляемого устройства для вычисления бисимметрических булевых функций шести переменных (фигура) имеет вид(4)(121323)(456(457)8)123(459(4510)11). Рассмотрим три примера построения вектора настройки(0, 1 11) для вычисления (реализации) на выходе 35 устройства бисимметрических булевых функций(1, 2). Пример 1 Предположим, что на выходе устройства 35 требуется вычислить бисимметрическую булеву функцию(1 ,2 )123(45)1 23456 . Так как формула (1), применительно к данной функции, принимает вид 1 32 (1 )2 ( 2 )33 (1 )3 ( 2 )123(456 )( 123123123 )0(123123123 )01 23456 ,то (0)(0, 1, 1, 1), (1)(2)(0, 0, 0, 0) и (3)(0, 0, 0, 1). Если представить функцию(1, 2) формулой (2), то(3)(0)(1)(2)(3) (0,1,1,1)(0,0,0,0)(0,0,0,0)(0,0,0,1)(0,1,1,0). Если (0)(1)(2)(0,1,1,1) и (3)(0,1,1,0), то из таблицы настроек (таблица) получаем 00,6, 20, 30, 46, 50, 60, 76, 80, 96,106 и 110. Следовательно, для вычисления на выходе 35 устройства (фигура) бисимметрической булевой функции(1 ,2 )123(456 )1 23456 необходимо на настроечные входы 23, 25, 26, 28, 29, 31 и 34 подать значение 0, а на настроечные входы 24, 27, 30, 32 и 33 - значение 6. Если 023568110 и 1479106, то первообразная функция (4) заявляемого устройства принимает вид(1, 2, 3, 4, 5, 0, 1 11)450(456)0(123)(450(456)0)(121323)(450(456)0)123(456(456)0)(1123121323123)(455)123(4560)123 (456)123456123 (456)123456. Пример 2. Предположим, требуется вычислить бисимметрическую булеву функцию(3)(0)(1)(2)(3)(0,0,0,0)(0,0,0,0)(1,1,1,0)(1,1,1,1)(0,0,0,1). Если (0)(1)(0,0,0,0), (2)(1,1,1,0) и (3)(0,0,0,1), то из таблицы настроек (таблица) получаем 00, 11, 21, 30, 41, 51, 66, 71, 80,96, 101 и 111. Значит, для вычисления на выходе 35 устройства булевой функции(1, 2) необходимо на настроечные входы 23, 26, 31 подать значение 0, на настроечные входы 24,25, 27, 28, 30, 33 и 34 - значение 1, на настроечные входы 29 и 32 - значение 6. Если 0380, 1245710111 и 696, то первообразная функция (4) заявляемого устройства принимает вид 6(121323)(456 (451)0)123(456(451)1)(121323)(4561)123456(121323)(456 )123456. Пример 3 Допустим, на выходе 35 устройства требуется вычислить бисимметрическую булеву функцию(1 ,2 )123123123123456123456 ,которая в качестве примера была рассмотрена в 2. Принимая во внимание формулу (1), нетрудно установить, что (0)(0,0,0,1),(1)(0,0,0,0), (2)(1,1,1,1) и (3)(1,0,0,0). Для симметрических булевых функций 0(2) 3(2) из разложения (2) с помощью формул (3) получаем (0)(1)(0,0,0,1), (2)(1,1,1,0) и (3)(0,1,1,0). Используя таблицу настроек (таблица), формируем вектор настройки устройства на реализацию заданной бисимметрической функции шести переменных(6, 1, 1, 6, 1, 1, 6, 1, 0, 6, 6, 0). В таком случае для вычисления на выходе 35 устройства бисимметрической булевой функции, приведенной в 2, необходимо на настроечные входы 23, 26, 29, 32 и 33 подать значение переменной х 6, на настроечные входы 24, 25, 27, 28 и 30 - значение 1, на настроечные входы 31 и 34 - значение 0. Основным достоинством заявляемого устройства для вычисления бисимметрических булевых функций шести переменных является небольшое число внешних выводов, равное 18 (пять информационных и двенадцать настроечных входов, выход). Устройствопрототип имеет 23 внешних вывода (шесть информационных и шестнадцать настроечных входов, выход). Дополнительным достоинством устройства для вычисления бисимметрических булевых функций шести переменных является относительно небольшая конструктивная сложность (по числу входов логических элементов), равная 53. Сложность устройствапрототипа составляет 75 (при этом предполагается, что полный одноразрядный сумматор содержит элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА и мажоритарный элемент с порогом два и его сложность равно 6). 16242 1 2012.08.30 Двоичный код симметрической булевой функции(4, 5, 6) Национальный центр интеллектуальной собственности. 220034, г. Минск, ул. Козлова, 20.