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

(51) МПК (2009) НАЦИОНАЛЬНЫЙ ЦЕНТР ИНТЕЛЛЕКТУАЛЬНОЙ СОБСТВЕННОСТИ УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ БИСИММЕТРИЧЕСКИХ БУЛЕВЫХ ФУНКЦИЙ(71) Заявитель Белорусский государственный университет(72) Авторы Супрун Валерий Павлович Городецкий Данила Андреевич(73) Патентообладатель Белорусский государственный университет(57) Устройство для вычисления бисимметрических булевых функций пяти переменных,содержащее мажоритарный элемент с порогом два, элементы СЛОЖЕНИЕ ПО МОДУЛЮ ДВА с первого по пятый и элементы И с первого по седьмой, характеризующееся тем, что выход первого элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА соединен с выходом устройства, первый входс первым настроечным входом устройства, -й вход мажоритарного элемента с порогом два, где 1,2,3, соединен с -м информационным входом устройства,с -м входом второго элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА и с -м входом первого элемента И, выход которого соединен со вторым входом первого элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, третий вход которого соединен с выходом второго элемента И,13973 1 2011.02.28 первый вход которого соединен с выходом мажоритарного элемента с порогом два, а второй вход - с выходом третьего элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, первый вход которого соединен со вторым настроечным входом устройства, а второй вход соединен с выходом третьего элемента И, -й, где 1,2, вход которого соединен с (2)-м настроечным входом устройства, (4)-й настроечный вход которого соединен с -м входом четвертого элемента И, выход которого соединен с четвертым входом первого элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, пятый вход которого соединен с выходом пятого элемента И, первый вход которого соединен с выходом второго элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, а второй вход соединен с выходом четвертого элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, первый вход которого соединен с седьмым настроечным входом устройства, а второй вход - с выходом шестого элемента И, -й вход которого соединен с (7)-м настроечным входом устройства, десятый настроечный вход которого соединен с первым входом пятого элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, выход которого соединен с четвертым входом первого элемента И, а второй вход - с выходом седьмого элемента И, й вход которого соединен с (10)-м настроечным входом устройства. Изобретение относится к области вычислительной техники и микроэлектроники и предназначено для вычисления бисимметрических булевых функций пяти переменных. Известно устройство для вычисления симметрических булевых функций пяти переменных, которое содержит мажоритарные элементы с порогами два, три, четыре, пять и шесть, элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, пять информационных и шесть настроечных входов, выход 1. Известное устройство, как и предлагаемое устройство, содержит мажоритарный элемент с порогом два и элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, выход которого соединен с выходом устройства, первый настроечный вход которого соединен с первым входом элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА. Недостатком известного устройства являются низкие функциональные возможности,поскольку устройство не позволяет вычислять (реализовать) бисимметрические булевы функции пяти переменных. Наиболее близким по функциональным возможностям и конструкции техническим решением к предлагаемому устройству является устройство для вычисления бисимметрических булевых функций шести переменных, которое содержит два полных одноразрядных двоичных сумматора, пятнадцать элементов ИЛИ и элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, а также имеет шесть информационных и шестнадцать настроечных входов, один выход 2. Устройство-прототип, как и заявляемое устройство, содержит элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, выход которого соединен с выходом устройства, первый настроечный вход которого соединен с первым входом элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА. Недостатком устройства-прототипа является высокая конструктивная сложность, которая по числу входов логических элементов составляет 75 (при этом предполагается, что полный одноразрядный двоичный сумматор содержит элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА и мажоритарный элемент с порогом два и его сложность равна 6). Изобретение направлено на решение технической задачи понижения конструктивной сложности устройства для вычисления бисимметрических булевых функций пяти переменных. Устройство для вычисления бисимметрических булевых функций пяти переменных содержит мажоритарный элемент с порогом два, элементы СЛОЖЕНИЕ ПО МОДУЛЮ ДВА с первого по пятый, элементы И с первого по седьмой. 13973 1 2011.02.28 Выход первого элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА соединен с выходом устройства, первый вход - с первым настроечным входом устройства, -й вход мажоритарного элемента с порогом два, где 1,2,3, соединен с -м информационным входом устройства, с -м входом второго элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА и с -м входом первого элемента И. Выход первого элемента И соединен со вторым входом первого элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, третий вход которого соединен с выходом второго элемента И,первый вход которого соединен с выходом мажоритарного элемента с порогом два, а второй вход - с выходом третьего элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА. Первый вход третьего элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА соединен со вторым настроечным входом устройства, а второй вход соединен с выходом третьего элемента И,-й, где 1,2, вход которого соединен с (2)-м настроечным входом устройства, (4)й настроечный вход которого соединен с -м входом четвертого элемента И. Выход четвертого элемента И соединен с четвертым входом первого элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, пятый вход которого соединен с выходом пятого элемента И, первый вход которого соединен с выходом второго элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, а второй вход соединен с выходом четвертого элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА. Первый вход четвертого элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА соединен с седьмым настроечным входом устройства, а второй вход - с выходом шестого элемента И, -й вход которого соединен с (7)-м настроечным входом устройства, десятый настроечный вход которого соединен с первым входом пятого элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА. Выход пятого элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА соединен с четвертым входом первого элемента И, а второй вход - с выходом седьмого элемента И, -й вход которого соединен с (10)-м настроечным входом устройства. Названный технический результат достигается с помощью введения в логическую схему устройства для вычисления бисимметрических булевых функций новых логических элементов (мажоритарного элемента с порогом два и элементов И) с последующим изменением соединений логических элементов в схеме. На чертеже (фигура) представлена логическая схема устройства для вычисления бисимметрических булевых функций пяти переменных. Устройство для вычисления бисимметрических булевых функций содержит мажоритарный элемент с порогом два 1, семь элементов И 28, пять элементов СЛОЖЕНИЕ ПО МОДУЛЮ ДВА 913, три информационных входа 14, 15 и 16, двенадцать настроечных входов 1728 и выход 29. Устройство для вычисления бисимметрических булевых функций пяти переменных работает следующим образом. На информационные входы устройства 14, 15 и 16 поступают (в произвольном порядке) значения переменных 1,2,3, на настроечные входы 1728 - сигналы настройки 0,111, значения которых принадлежат множеству 0,1,4 ,4 ,5 ,5 . На выходе устройства 29 вычисляется (реализуется) бисимметрическая булева функция(1,2), где 11,2,3 и 24,5, определяемая вектором настройки(0,111). Поясним принцип построения и работы устройства для вычисления бисимметрических булевых функций пяти переменных. Произвольная симметрическая булева функцияпеременных(1,2) характеризуется множеством рабочих чисел 1,2. Функцияпринимает единичные значения на тех и только тех наборах значений переменных 1,2 которые содержат ровноединиц, где 0, 1 и 0. Функцияобозначается как Если 1, то функцияназывается фундаментальной (или элементарной) симметрической булевой функцией. Произвольная симметрическая булева функция(1,2) взаимно однозначно представляется (1) - разрядным (локальным кодом) двоичным вектором(0,1), где- значение функциина (любом) наборе значенийпеременных, содержащем(0) единиц. Иначе,1 тогда и только тогда, когда- рабочее число функции . Если произвольная булева функцияпеременныхне меняет своего значения после перестановки любой пары переменныхи(гдеи ,1,2), то функцияявляется симметрической. В противном случае говорят, что булева функцияобладает (или не обладает) свойством частичной симметрии переменных. Известно, что отношение частичной симметрии разбивает (единственным образом) множество переменных 1,2 на классы симметрии 1,2 где 1. Если 1, то функцияявляется (полностью) симметрической если 2, то- бисимметрическая булева функция если, то функцияне обладает свойством частичной симметрии переменных. Бисимметрическая булева функция обозначается(1,2), где 1,2 - классы симметрии. Пусть 5 и 11,2,3, 24,5. Тогда для бисимметрической булевой функции(1,2) имеет место формула 0 1 где 0 3 (1 ,2 ,3 )123 ,1 3 (1,2 ,3 )123123123 , 32 (1 ,2 ,3 )123123123 ,33 (1 ,2 ,3 )123 и 00(4,5), 11(4,5), 22(4,5), 33(4,5) - симметрические булевы функции, зависящие от переменных 4 и 5. Двоичный вектор 0),1),2),3(0,1 11) называется двоичным кодом булевой функции(1,2). Если в формуле (1) заменить 111,221 и 331 , то 0),1),2),3(0, 111). Компоненты двоичных векторовисвязаны между собой следующими соотношениями 4 9369 , где 0,1,2. Поясним метод построения вектора(0,111) - вектора настройки заявляемого устройства (фигура) на вычисление заданной бисимметрической булевой функции(1,2). С помощью локальных кодов (0)(0,1,2), (1)(3,4,5), (2)(6,7,8),(3)(9,10,11) из таблицы настройки (таблица), где 0,1,2,3, получаем значения фрагментов (0,1,2), (3,4,5), (6,7,8), (9,10,11) вектора настройки(0,111). Рассмотрим пример. Предположим, что на выходе 29 устройства (фигура) требуется реализовать бисимметрическую булеву функцию( 1 ,2 5 )3 (1 ,2 ,3 )0 ( 4 ,5 )1 (1 ,2 ,3 )1 ( 4 ,5 )3 23 (1 ,2 ,3 )2 ( 4 ,5 )3 (1 ,2 ,3 )3 ( 4 ,5 ),3 где (0)(0,1,1), (1)(0,0,0) и (2)(3)(0,0,1). Отсюда следует, что двоичный код бисимметрической булевой функции(1,2) равен 0),1),2),3(0,1,1,0,0,0,0,0,1,0,0,). Используя формулы (2), получаем(0,1,1,0,1,1,0,1,0,0,1,1), т.е. (0)(0,1,1),(1)(0,1,1), (2)(0,1,0) и (3)(0,1,1). Принимая во внимание описанную выше процедуру построения вектора настройки(0,111), получаем 01, 14 ,25 , 31,44 ,55 , 64, 75, 81, 91, 104 и 115 . Следовательно, для вычисления на выходе 29 устройства (фигура) функции(1 ,2 )123 ( 45 )(121323 )45 необходимо на настроечные входы 17, 20, 25 и 26 подать значение 1, на настроечные входы 18, 21 и 27 - значение 4 , на настроечные входы 19, 22 и 28 - значение 5 , на настроечный вход 23 значение 4 и на настроечный вход 24 - значение 5. Первообразная функция устройства для вычисления бисимметрических булевых функций пяти переменных (фигура) имеет вид(1 ,2 ,3 ,0 , 1 11 )01 2( 123 )( 345 )( 1 21 323 )( 678 )1 23( 910 11 ). В качестве проверки подставим в выражение для первообразной функции устройства значения компонент вектора настройки1,4 ,5 ,1,4 ,5 ,4 ,5 ,1,1,4 ,5 . В таком случае первообразная функция примет вид 123121323(4545 )( 121323 )(45 )123(4545 )( 121323 )45123(45 )( 121323 )45 . Основным достоинством заявляемого устройства для вычисления бисимметрических булевых функций пяти переменных является небольшая конструктивная сложность, равная 33. При этом сложность устройства-прототипа составляет 75. Дополнительным достоинством устройства является небольшое число внешних выводов (три информационных и двенадцать настроечных входов, выход). Число внешних выводов устройства-прототипа равно 23 (двадцать два входа и выход). Локальный код симметрической булевой функции(4,5) Национальный центр интеллектуальной собственности. 220034, г. Минск, ул. Козлова, 20.