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

(51) МПК (2009) НАЦИОНАЛЬНЫЙ ЦЕНТР ИНТЕЛЛЕКТУАЛЬНОЙ СОБСТВЕННОСТИ УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ БИСИММЕТРИЧЕСКИХ БУЛЕВЫХ ФУНКЦИЙ(71) Заявитель Белорусский государственный университет(72) Авторы Супрун Валерий Павлович Городецкий Данила Андреевич(73) Патентообладатель Белорусский государственный университет(57) Устройство для вычисления бисимметрических булевых функций четырех переменных, содержащее пять элементов И, полусумматор и первый элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, выход которого соединен с выходом устройства, а первый вход соединен с первым настроечным входом устройства, второй настроечный вход которого соединен с первым входом первого элемента И, выход которого соединен со вторым входом первого элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, третий вход которого соединен с выходом второго элемента И, первый вход которого соединен с выходом суммы полусумматора,первый и второй входы которого соединены с первым и вторым информационными входами устройства, а выход переноса соединен с первым входом третьего элемента И, выход которого соединен с четвертым входом первого элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, первые входы четвертого и пятого элементов И соединены соответственно с третьим и четвертым настроечными входами устройства, отличающееся тем, что дополнительно содержит второй и третий элементы СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, выход второго элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА соединен со вторым входом второго элемента И, а первый вход соединен с пятым настроечным входом устройства, шестой настроечный вход которого соединен со вторым входом первого элемента И, а седьмой настроечный вход устройства соединен со вторым входом четвертого элемента И, выход 13992 1 2011.02.28 которого соединен со вторым входом второго элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА,восьмой настроечный вход устройства соединен со вторым входом пятого элемента И,выход которого соединен с первым входом третьего элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, второй вход которого соединен с девятым настроечным входом устройства, а выход - со вторым входом третьего элемента И. Изобретение относится к области вычислительной техники и микроэлектроники и предназначено для вычисления бисимметрических булевых функций четырех переменных. Известно устройство для вычисления симметрических булевых функций четырех переменных, которое содержит элемент ИСКЛЮЧАЮЩЕЕ ИЛИ, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом четыре, элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, девять входов и один выход 1. Известное устройство, как и предлагаемое, содержит элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, выход которого соединен с выходом устройства. Недостатком известного устройства являются низкие функциональные возможности,поскольку устройство не позволяет вычислить (реализовать) бисимметрические булевы функции четырех переменных. Наиболее близким по функциональным возможностям и конструкции техническим решением к предлагаемому устройству является многофункциональный логический модуль, который содержит два полусумматора, восемь элементов И, элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, четыре информационных и девять настроечных входов, один выход 2. Многофункциональный логический модуль предназначен для вычисления бисимметрических булевых функций четырех переменных. Конструктивная сложность модуля (по числу входов логических элементов) равна 37, а быстродействие составляет 3, гдезадержка на один логический элемент. Устройство-прототип, как и предлагаемое устройство, содержит пять элементов И, полусумматор и элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, выход которого соединен с выходом устройства. Недостатками устройства-прототипа являются а) высокая конструктивная сложность б) большое число внешних выводов. Изобретение направлено на решение следующих технических задач снижение конструктивной сложности и уменьшение числа внешних выводов устройства для вычисления бисимметрических булевых функций четырех переменных. Устройство для вычисления бисимметрических булевых функций четырех переменных содержит пять элементов И, полусумматор и первый элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, выход которого соединен с выходом устройства, а первый вход соединен с первым настроечным входом устройства. Второй настроечный вход устройства соединен с первым входом первого элемента И,выход которого соединен со вторым входом первого элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, третий вход которого соединен с выходом второго элемента И. Первый вход второго элемента И соединен с выходом суммы полусумматора, первый и второй входы которого соединены с первым и вторым информационными входами устройства, а выход переноса соединен с первым входом третьего элемента И. Выход третьего элемента И соединен с четвертым входом первого элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, первые входы четвертого и пятого элементов И соединены соответственно с третьим и четвертым настроечными входами устройства. В отличие от прототипа устройство дополнительно содержит второй и третий элементы СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, выход второго элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА соединен со вторым входом второго элемента И, а первый вход соединен с пятым настроечным входом устройства, шестой настроечный вход которого соединен со вторым входом первого элемента И. 2 13992 1 2011.02.28 Седьмой настроечный вход устройства соединен со вторым входом четвертого элемента И, выход которого соединен со вторым входом второго элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА. Восьмой настроечный вход устройства соединен со вторым входом пятого элемента И, выход которого соединен с первым входом третьего элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, второй вход которого соединен с девятым настроечным входом устройства,а выход - со вторым входом третьего элемента И. Названный технический результат достигается с помощью 1) введения в логическую схему устройства дополнительно двух элементов СЛОЖЕНИЕ ПО МОДУЛЮ ДВА 2) удаления из схемы одного полусумматора и трех элементов И 3) изменения соединений логических элементов в схеме. На чертеже (фигура) представлена логическая схема устройства для вычисления бисимметрических булевых функций четырех переменных. Устройство для вычисления бисимметрических булевых функций четырех переменных содержит пять элементов И 15, три элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА 6, 7 и 8, полусумматор 9, два информационных входа 10 и 11, девять настроечных входов 1220 и выход 21. Устройство для вычисления бисимметрических булевых функций четырех переменных работает следующим образом. На информационные входы устройства 10 и 11 поступают (в произвольном порядке) значения переменных 1 и 2, на настроечные входы 1220 - сигналы настройки 0, 1, ,8, значения которых принадлежат множеству 0, 1,3 ,3 ,4 ,4 . На выходе устройства 21 вычисляется (реализуется) бисимметрическая булева функция(1, 2), где 11,2 и 23, 4, определяемая вектором настройки(0, 1, , 8). Поясним принцип построения и работы устройства для вычисления бисимметрических булевых функций четырех переменных. Произвольная симметрическая булева функцияпеременных(1, 2, , х) характеризуется множеством рабочих чисел 1, 2, , . Функцияпринимает единичные значения на тех и только тех наборах значений переменных 1, 2, , , которые содержат ровноединиц, где 0, 1 и 01. Функцияобозначает ся как 1 ,2 где 1, 2, , . Если 1, то функцияназывается фундаментальной (или элементарной) симметрической булевой функцией. Произвольная симметрическая булева функция(, 2, , ) взаимно однозначно представляется (1)-разрядным (локальным) двоичным кодом(0, 1, , ), где- значение функциина (любом) наборе значенийпеременных, содержащем(0) единиц. Иначе,1 тогда и только тогда, когда- рабочее число . Известно, что отношение частичной симметрии произвольной булевой функциипеременныхразбивает (единственным образом) множество переменных 1, 2, ,на классы симметрии, 1, 2, , , где. Если, то функцияявляется (полностью) симметрической если 2, то- бисимметрическая булева функция если, то функцияне обладает свойством частичной симметрии переменных. Для бисимметрической булевой функции(1, 2), где 11, 2 и 23,4, имеет место формула 0 1 2 где 2 (1,2 )12 , 2 (1,2 )1212 , 2 (1,2 )1,2 и 00 ( 3 ,4 ),11 ( 3 ,4 ),22 ( 3 ,4 ) - симметрические булевы функции, зависящие от переменных х 3, х 4. Двоичный вектор 0 ), (1 ), ( 2(0 , 1 8 ) называется двоичным кодом бисимметрической булевой функции(1,2). Если в формуле (1) заменить 111 и 221, то(,2)0(2)(12)(2) 22(2),где 0(2)0(2), (2)0(2) (2),2(2)0(2)2(2). Обозначим 0), (1), (2(0, 1, , 8). Векторыисвязаны между собой следующими соотношениями(2), 33, 66,где 0, 1, 2. Поясним метод построения вектора(0,1, , 8) - вектора настройки устройства (фигура) на вычисление некоторой заданной бисимметрической булевой функции(1,2). С помощью локальных кодов (0)(0, 1, 2), (1)(3, 4, 5) и (Н 2)(6, 7, 8) из таблицы настройки (таблица) получаем значения векторов (0, 1, 2),(3, 4, 5) и (6, 7, 8),являющихся составными частями вектора настройки(0, 1, , 8). Первообразная функция устройства для вычисления бисимметрических булевых функций четырех переменных (фигура) имеет вид(1, 2, 0, 1, , 8)01,2(12)(345)12(678). Пример. Предположим, что на выходе 21 устройства (фигура) требуется реализовать бисимметрическую булеву функцию Так как 123 4341 2123 41 23 4 , то формула (1) принимает вид 120 ( 3 ,4 )1 2121 ( 3 ,4 )1 22 ( 3 ,4 ),где (0)(0,1,0) и(2)(0,0,1). Отсюда следует, что двоичный код бисимметрической булевой функции(1,2) равен 13992 1 2011.02.28 Используя формулы (2), получаем(0,1,0,0,1,1,0,1,1), т.е. (0)(0,1,0),(1)(0,1,1) и (2)(0,1,1). Принимая во внимание описанную выше процедуру построения вектора настройки(0, 1, , 8), получаем 03,14, 21, 31,43 ,54 , 61,73 и 84. Следовательно, для вычисления на выходе 21 устройства (фигура) функции(1,2 ,3 ,4 )12( 34 )(12 )3 4 необходимо на настроечные входы подать значения 03, 14, 2361,473 и 584 . В таком случае первообразная функция (3) устройства для вычисления бисимметрических булевых функций четырех переменных принимает вид 12( 34 )(12 )3 4 . Основными достоинствами заявляемого устройства для вычисления бисимметрических булевых функций четырех переменных являются небольшая конструктивная сложность, равная 22 (с учетом того что сложность полусумматора равна 4) небольшое число внешних выводов (два информационных и девять настроечных входов, выход). Отметим, что сложность устройства-прототипа равна 37, а число внешних выводов - 14. Национальный центр интеллектуальной собственности. 220034, г. Минск, ул. Козлова, 20.