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

(51) МПК НАЦИОНАЛЬНЫЙ ЦЕНТР ИНТЕЛЛЕКТУАЛЬНОЙ СОБСТВЕННОСТИ УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ БИСИММЕТРИЧЕСКИХ БУЛЕВЫХ ФУНКЦИЙ ПЯТИ ПЕРЕМЕННЫХ(71) Заявитель Белорусский государственный университет(72) Автор Супрун Валерий Павлович(73) Патентообладатель Белорусский государственный университет(57) Устройство для вычисления бисимметрических булевых функций пяти переменных,содержащее первый, второй, третий, четвертый и пятый элементы И, первый, второй и третий элементы СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, выход первого из которых соединен с выходом устройства, первый настроечный вход которого соединен с первым входом первого элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, второй вход которого соединен с выходом первого элемента И, первый вход которого соединен со вторым настроечным входом устройства, третий настроечный вход которого соединен с первым входом второго элемента И, выход которого соединен с первым входом второго элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, выход которого соединен с первым входом третьего элемента И, выход которого соединен с третьим входом первого элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА,четвертый вход которого соединен с выходом четвертого элемента И, первый вход которого соединен с выходом третьего элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, первый 16241 1 2012.08.30 вход которого соединен с выходом пятого элемента И, первый вход которого соединен с четвертым настроечным входом устройства, пятый и шестой настроечные входы которого соединены со вторыми входами второго и третьего элементов СЛОЖЕНИЕ ПО МОДУЛЮ ДВА соответственно первый, второй и третий элементы ИЛИ и четвертый элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, выход которого соединен со вторым входом третьего элемента И, а -й вход, где 1, 2, соединен с (1)-м входом четвертого элемента И и с-м информационным входом устройства, (2)-й информационный вход которого соединен с (1)-м входом первого, второго и пятого элементов И и с -м входом первого, второго и третьего элементов ИЛИ, третьи входы которых соединены соответственно с седьмым, восьмым и девятым настроечными входами устройства. Изобретение относится к области вычислительной техники и микроэлектроники и предназначено для вычисления бисимметрических булевых функций пяти переменных. Известно устройство для вычисления симметрических булевых функций пяти переменных, которое содержит элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом два, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с порогом шесть, мажоритарный элемент с порогом три, элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, двенадцать настроечных входов и выход 1. Известное устройство, как и предлагаемое устройство, содержит элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, выход которого соединен с выходом устройства. Недостатком известного устройства являются низкие функциональные возможности,поскольку устройство не позволяет вычислять (реализовывать) бисимметрические булевы функции пяти переменных. Наиболее близким по функциональным возможностям и конструкции техническим решением к предлагаемому устройству является устройство для вычисления бисимметрических булевых функций пяти переменных, которое содержит семь элементов И, пять элементов СЛОЖЕНИЕ ПО МОДУЛЮ ДВА и мажоритарный элемент с порогом два, а также имеет три информационных и двенадцать настроечных входов, выход 2. Конструктивная сложность устройства (по числу входов логических элементов) равна 33, а быстродействие составляет 4, где- задержка на один логический элемент. Устройство-прототип, как и предлагаемое устройство, содержит пять элементов И и три элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, выход первого из которых соединен с выходом устройства, первый вход соединен с первым настроечным входом устройства, а второй и третий входы - с выходами первого и второго элементов И. Недостатком устройства-прототипа является большое число внешних выводов, равное 16. Изобретение направлено на решение технической задачи уменьшение числа внешних выводов устройства для вычисления бисимметрических булевых функций пяти переменных. Устройство для вычисления бисимметрических булевых функций пяти переменных содержит первый, второй, третий, четвертый и пятый элементы И, первый, второй и третий элементы СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, выход первого из которых соединен с выходом устройства. Первый настроечный вход устройства соединен с первым входом первого элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, второй вход которого соединен с выходом первого элемента И, первый вход которого соединен со вторым настроечным входом устройства. Третий настроечный вход устройства соединен с первым входом второго элемента И,выход которого соединен с первым входом второго элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, выход которого соединен с первым входом третьего элемента И. Выход третьего элемента И соединен с третьим входом первого элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, четвертый вход которого соединен с выходом четвертого элемента И, первый вход которого соединен с выходом третьего элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА. 2 16241 1 2012.08.30 Первый вход третьего элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА соединен с выходом пятого элемента И, первый вход которого соединен с четвертым настроечным входом устройства, пятый и шестой настроечные входы которого соединены со вторыми входами второго и третьего элементов СЛОЖЕНИЕ ПО МОДУЛЮ ДВА соответственно. Устройство содержит также первый, второй, третий элементы ИЛИ и четвертый элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, выход которого соединен со вторым входом третьего элемента И, а -й вход, где 1, 2, соединен с (1)-м входом четвертого элемента И и с -м информационным входом устройства. Причем (2)-й информационный вход устройства соединен с (1)-м входом первого, второго и пятого элементов И и с -м входом первого, второго и третьего элементов ИЛИ, третьи входы которых соединены соответственно с седьмым, восьмым и девятым настроечными входами устройства. Названный технический результат достигается с помощью введения в логическую схему устройства новых логических элементов (элементов ИЛИ) и путем изменения соединений между элементами схемы. На фигуре представлена логическая схема устройства для вычисления бисимметрических булевых функций пяти переменных. Устройство для вычисления бисимметрических булевых функций содержит пять элементов И 15, три элемента ИЛИ 6, 7 и 8, четыре элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА 912, четыре информационных входа1316, девять настроечных входов 1725 и выход 26. Устройство для вычисления бисимметрических булевых функций пяти переменных работает следующим образом. На информационные входы устройства 13, 14, 15 и 16 поступают значения переменных 1, 2, 3, 4 соответственно, на настроечные входы 1725 сигналы настройки 0, 1,, 8, значения которых принадлежат множеству 0, 1,5 ,5 . На выходе устройства 26 вычисляется (реализуется) бисимметрическая булева функция(1, 2), где 11, 2 и 23, 4, 5, определяемая вектором настройки(0, 1,, 8). Поясним принцип построения и работы устройства для вычисления бисимметрических булевых функций пяти переменных. Произвольная симметрическая булева функцияпеременных(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. Если 1, то функцияявляется(полностью) симметрической если 2, то- бисимметрическая булева функция если, то функцияне обладает свойством частичной симметрии переменных. Для бисимметрической булевой функции(1, 2), где 11, 2 и 23,4, 5, имеет место формула 1 где( 1 ,2 )12 ,( 1 ,2 )1 212 и( 1 ,2 )1 2 . В формуле (1) булевы функции 00 (3, 4, 5), 11 (3, 4, 5), 22 (3, 4,5) являются симметрическими, каждая из которых задается посредством четырехразряд ного двоичного вектора ( 0 , 1 ,,3 ) , где 0, 1, 2. 2 0 2 Если в формуле (1) заменить 111 и 221 , то после несложных преобразований получим(1 ,2 )0 (2 )(12 )(2 )1 22 (2 ) ,(2) где симметрические булевы функции 0(2), 1(2) и 2(2) вычисляются по формулам 0(2)0(2), 1 ( 2 )0 ( 2 )( 2 ) и 2 ( 2 )0 ( 2 )2 ( 2 ) . Следовательно, значения компонент двоичных векторов ( 0 , 1 ,,3 ) и 2( 0 , 1 ,,3 ) связаны между собой следующими соотношениями (0, 1, 2) 2 001 , 101 ,202 ,где 0, 1, 2, 3. Поясним метод построения вектора настройки(0, 1,, 8) устройства (фигура) на вычисление произвольно заданной бисимметрической булевой функции(1, 2). 1. Первоначально воспользуемся представлением функции(, 2) посредством формулы (1) и вычислим значения компонент векторов ( 0 , 1 ,,3 ) для сим 2 метрических булевых функций(3, 4, 5), где 0, 1, 2. 2. Затем по формулам (3) определим значения компонент двоичных векторов( 0 , 1 ,,3 ) для симметрических булевых функций(3, 4, 5), входя 2 щих в представление функции(, 2) посредством формулы (2), где 0, 1, 2. 3. С целью построения вектора настройки(0, 1,, 8) для каждого из векто 0 0 2 2 2 ров ( 0 )( 0 , 1 ,0 ,3 ) , (1 )(1 , 1 , 1 , 1 ) и ( 2 )( 0 , 1 ,2 ,3 ) посредством 0 2 0 1 2 3 2 таблицы настроек (таблица) вычислим значения векторов (0, 1, 2), (3, 4, 5) и (6, 7, 8). Первообразная функция заявляемого устройства для вычисления бисимметрических булевых функций пяти переменных (фигура) имеет вид(4)1 2(346(347 )8 ). Рассмотрим два примера построения вектора настройки(0, 1,, 8) устройства для вычисления (реализации) бисимметрических булевых функций(1, 2). Пример 1 Предположим, что на выходе 26 устройства требуется вычислить бисимметрическую булеву функцию(1 ,2 )12(345 )1 2345 . Так как формула (1), применительно к данной функции, принимает вид 1 12(345 )( 1212 )012(345 ) ,то ( 0 )(0, 1, 1, 1) , (1 )(0, 0, 0, 0) , ( 2 )(0, 0, 0, 1) . Если представить функцию(1, 2) формулой (2), то( 2 )( 0 )( 2 )(0, 1, 1, 1)(0, 0, 0, 1)(0, 1, 1, 0). Если ( 0 )(0, 1, 1, 1) , (1 )(0, 1,1, 1) и ( 2 )(0, 1, 1, 0) , то из таблицы настроек(таблица) получаем 00, 15, 20, 30, 45, 50, 6 х 5, 75 и 80. Следовательно, для вычисления на выходе 26 устройства (фигура) бисимметрической булевой функции(1 ,2 )12(345 )1 2345 необходимо на настроечные входы 17, 19, 20, 22 и 25 подать значение 0, а на настроечные входы 18, 21, 23 и 24 - значение 5. В качестве проверки в формуле (4) положим 023580 и 14675. Тогда первообразная функция (4) заявляемого устройства будет иметь вид( 1 ,2 ,3 ,4 ,5 )340(345 )0( 12 )(3 40(345 )0)1 2(345(345 )0)(1121 2 )(345 )1 234512(345 )1 234512(345 )12345 Пример 2 Пусть на выходе 26 устройства требуется вычислить бисимметрическую булеву функцию (1 ,2 )1 2345 . Так как 12345( 1 212 )3451 2(345 )120 (1 )0 ( 2 )2 (1 )( 2 )22 (1 )2 ( 2 ),то ( 0 )(0, 0, 0, 1) , (1 )(0, 0, 0, 1) , ( 2 )(1, 1, 1, 0). Если представить функцию(1, 2) формулой (2), то( 2 )( 0 )( 2 )(0, 0, 0, 1)(1, 1, 1, 0)(1, 1, 1, 1). Если ( 0 )(0, 0, 0, 1) , (1 )(0, 0, 0, 0) и ( 2 )(1, 1, 1, 1) , то из таблицы настроек(таблица) получаем 05, 11, 21, 30, 41, 51, 60, 71 и 80. Значит, для вычисления на выходе 26 устройства булевой функции(1 ,2 )1 2345 необходимо на настроечный вход 17 подать значение 5, на настроечные входы 18, 19, 21, 22 и 24 - значение 1, на настроечные входы 20, 23 и 25 значение 0. Если 05, 124571 и 3680, то первообразная функция (4) принимает вид( 1 ,2 ,3 ,4 ,5 )345(341)1( 12 )(340(341)1)1 2(340(341)0)1 2345 . Основным достоинством заявляемого устройства для вычисления бисимметрических булевых функций пяти переменных является небольшое число внешних выводов, равное 14 (четыре информационных и девять настроечных входов, выход), в то время как устройство-прототип имеет 16 внешних выводов (три информационных и двенадцать настроечных входов, выход). Дополнительным достоинством устройства для вычисления бисимметрических булевых функций пяти переменных является относительно небольшая конструктивная сложность (по числу входов логических элементов), равная 36. При этом сложность устройства-прототипа равна 33. Двоичный код симметрической булевой функции(3, 4, 5) 1. Патент РБ 11275, МПК 06 7/00, 2008. 2. Заявка на Патент РБ а 20090420, МПК 06 7/00, 2009 (прототип). Национальный центр интеллектуальной собственности. 220034, г. Минск, ул. Козлова, 20.