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

(51) МПК НАЦИОНАЛЬНЫЙ ЦЕНТР ИНТЕЛЛЕКТУАЛЬНОЙ СОБСТВЕННОСТИ УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ БИСИММЕТРИЧЕСКИХ БУЛЕВЫХ ФУНКЦИЙ ШЕСТИ ПЕРЕМЕННЫХ(71) Заявитель Белорусский государственный университет(72) Автор Супрун Валерий Павлович(73) Патентообладатель Белорусский государственный университет(57) Устройство для вычисления бисимметрических булевых функций шести переменных,характеризующееся тем, что содержит с первого по шестой элементы СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, мажоритарный элемент с порогом два и с первого по десятый элементы И, выход -го из которых, где 1, 2, , 5, соединен с -м входом первого элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, шестой вход которого соединен с первым настроечным входом устройства, а выход - с выходом устройства -й информационный вход устройства, где 1, 2, 3,4 , соединен с -м входом второго элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, с -м входом шестого элемента И и с -м входом мажоритарного элемента с порогом два, выход которого соединен с первыми входами третьего и четвертого элементов И второй и третий настроечные входы устройства соединены с первым и вторым входами 16666 1 2012.12.30 первого элемента И, четвертый настроечный вход устройства соединен с первым входом третьего элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, выход которого соединен с первым входом второго элемента И, второй вход которого соединен с выходом второго элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА и со вторым входом четвертого элемента И пятый и шестой настроечные входы устройства соединены с первым и вторым входами седьмого элемента И, выход которого соединен со вторым входом третьего элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА седьмой настроечный вход устройства соединен с первым входом четвертого элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, выход которого соединен со вторым входом третьего элемента И, инверсный вход которого соединен с выходом шестого элемента И и с первым входом пятого элемента И восьмой и девятый настроечные входы устройства соединены с первым и вторым входами восьмого элемента И, выход которого соединен со вторым входом четвертого элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА десятый настроечный вход устройства соединен с первым входом пятого элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, выход которого соединен с третьим входом четвертого элемента И одиннадцатый и двенадцатый настроечные входы устройства соединены с первым и вторым входами девятого элемента И, выход которого соединен со вторым входом пятого элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА тринадцатый настроечный вход устройства соединен с первым входом шестого элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, выход которого соединен со вторым входом пятого элемента И четырнадцатый и пятнадцатый настроечные входы устройства соединены с первым и вторым входами десятого элемента И, выход которого соединен со вторым входом шестого элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА. Изобретение относится к области вычислительной техники и микроэлектроники и предназначено для вычисления бисимметрических булевых функций шести переменных. Известно устройство для вычисления симметрических булевых функций шести переменных, которое содержит семь элементов И, два элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, мажоритарный элемент с порогом два, мажоритарный элемент с порогом четыре,шесть информационных и семь настроечных входов, выход 1. Известное устройство, как и предлагаемое устройство, содержит семь элементов И,два элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, мажоритарный элемент с порогом два,выход которого соединен с первым входом первого элемента И, выход -го (1, 2, , 5) элемента И соединен с -м входом первого элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА,выход которого соединен с выходом устройства. Недостатком известного устройства являются низкие функциональные возможности,поскольку устройство не позволяет вычислить (реализовать) произвольные бисимметрические булевы функции шести переменных. Наиболее близким по функциональным возможностям и конструкции техническим решением к предлагаемому устройству является многофункциональный логический модуль,содержащий три элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, два мажоритарных элемента с порогом два, семнадцать элементов И, шесть информационных и шестнадцать настроечных входов, выход 2. Логический модуль предназначен для вычисления бисимметрических булевых функций шести переменных(1, 2), определяемой вектором настройки(0, 1, , 15), где 11, 2, 3, 2 х 4, х 5, х 6 и 0, 1, , 150, 1. Многофункциональный логический модуль, выбранный в качестве прототипа, как и заявляемое устройство, содержит мажоритарный элемент с порогом два, десять элементов И и три элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, выход первого из которых соединен с выходом устройства, первый настроечный вход которого соединен с первым входом первого элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, (1)-й вход которого, где 1, 2, , 6,соединен с выходом - го элемента И. 2 16666 1 2012.12.30 Недостатком устройства-прототипа является высокая конструктивная сложность (по числу входов логических элементов), равная 81. Изобретение направлено на решение технической задачи понижения конструктивной сложности устройства для вычисления бисимметрических булевых функций шести переменных(1, 2), где 11, 2, 3, 4 и 2 х 5, х 6. Устройство для вычисления бисимметрических булевых функций шести переменных характеризуется тем, что содержит с первого по шестой элементы СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, мажоритарный элемент с порогом два и с первого по десятый элементы И. Выход -го элемента И, где 1, 2, , 5, соединен с -м входом первого элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, шестой вход которого соединен с первым настроечным входом устройства, а выход - с выходом устройства. Причем -й информационный вход устройства, где 1, 2, 3, 4, соединен с -м входом второго элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, с -м входом шестого элемента И и с-м входом мажоритарного элемента с порогом два, выход которого соединен с первыми входами третьего и четвертого элементов И. Второй и третий настроечные входы устройства соединены с первым и вторым входами первого элемента И. Четвертый настроечный вход устройства соединен с первым входом третьего элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, выход которого соединен с первым входом второго элемента И, второй вход которого соединен с выходом второго элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА и со вторым входом четвертого элемента И. Пятый и шестой настроечные входы устройства соединены с первым и вторым входами седьмого элемента И, выход которого соединен со вторым входом третьего элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА. Седьмой настроечный вход устройства соединен с первым входом четвертого элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, выход которого соединен со вторым входом третьего элемента И, инверсный вход которого соединен с выходом шестого элемента И и с первым входом пятого элемента И. Восьмой и девятый настроечные входы устройства соединены с первым и вторым входами восьмого элемента И, выход которого соединен со вторым входом четвертого элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА. Десятый настроечный вход устройства соединен с первым входом пятого элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, выход которого соединен с третьим входом четвертого элемента И. Одиннадцатый и двенадцатый настроечные входы устройства соединены с первым и вторым входами девятого элемента И, выход которого соединен со вторым входом пятого элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА. Тринадцатый настроечный вход устройства соединен с первым входом шестого элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, выход которого соединен со вторым входом пятого элемента И. Четырнадцатый и пятнадцатый настроечные входы устройства соединены с первым и вторым входами десятого элемента И, выход которого соединен со вторым входом шестого элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА. Названный технический результат достигается посредством введения в логическую схему трех дополнительных элементов СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, удалением из схемы семи элементов И и одного мажоритарного элемента с порогом два, а также с последующим изменением соединений между элементами логической схемы устройства для вычисления бисимметрических булевых функций шести переменных. На чертеже (фигура) представлена логическая схема устройства для вычисления бисимметрических булевых функций шести переменных. 16666 1 2012.12.30 Устройство для вычисления бисимметрических булевых функций содержит десять элементов И 110, шесть элементов СЛОЖЕНИЕ ПО МОДУЛЮ ДВА 1116, мажоритарный элемент с порогом два 17, четыре информационных входа 1821, пятнадцать настроечных входов 2236 и выход 37. Устройство для вычисления бисимметрических булевых функций шести переменных работает следующим образом. На информационные входы устройства 1821 поступают (в произвольном порядке) значения переменных 1, х 2, х 3, х 4, на настроечные входы 2236 - сигналы настройки 0,1, , 14, значения которых принадлежат множеству 0,1,5 ,5 ,6 ,6 . На выходе устройства 37 вычисляется (реализуется) бисимметрическая булева функция(1, 2), где 11, 2, 3, 4 и 25, 6, определяемая вектором настройки(0, 1, , 14). Поясним принцип построения и работы устройства для вычисления бисимметрических булевых функций шести переменных. Произвольная симметрическая булева функцияпеременных(1, 2, , ) характеризуется множеством своих рабочих чисел 1, 2, , . Функцияпринимает единичные значения на тех и только тех наборах значений переменных 1, 2, , ,которые содержат ровноединиц, где 0, 1 и 01. Такая функцияобозначается как 1 ,2 , где 1, 2 . Если 1, то функцияназывается фундаментальной (или элементарной) симметрической булевой функцией. Произвольная симметрическая булева функция(1, 2 ) взаимно однозначно представляется (1)-разрядным двоичным (локальным) кодом(0, 1, , ), гдезначение функциина (любом) наборе значенийпеременных, содержащем(0) единиц. Другими словами,1 тогда и только тогда, когда- рабочее число функции . Если произвольная булева функцияпеременныхне меняет своего значения после перестановки любой пары переменныхи(гдеи ,1, 2 ), то функцияявляется симметрической. В противном случае, говорят, что булева функцияобладает (или не обладает) свойством частичной симметрии переменных. Известно, что отношение частичной симметрии разбивает (единственным образом) множество переменных 1, 2, ,на классы симметрии , 2, , , где 1. Если 1, то функцияявляется (полностью) симметрической если 2, тобисимметрическая булева функция если, то функцияне обладает свойством частичной симметрии переменных. Бисимметрическая булева функция обозначается(1, 2), где 1, 2 - классы симметрии. Здесь рассматривается задача схемной реализации бисимметрической булевой функции(1, 2) при условии, что 6 и 1, 2, 3, 4, 25, 6. Для булевой функции(1, 2) справедливы формулы 16666 1 2012.12.30 42 (1 )123412341234123412341234 , 43 (1 )1234123412341234 ,44 ( 1 ,2 ,3 ,4 )1234 . Отметим, что в формулах (1) и (2) булевы функции 00(5, 6), 11(5, 6),22(5, 6), 33(5, 6), 44(5, 6) являются симметрическими. Двоичный вектор 0), 1), (2), (3), (4(0, 1, , 14) называется двоичным (локальным) кодом бисимметрической булевой функции(1, 2). Если в формуле (2) заменить 111 ,221 ,331 и 441 , то после несложных логических преобразований получаем(3) 3 44 (1 )3 ( 2 )4 (1 )4 ( 2 ), где 1 (1 ) ,2 (1 ) ,3 (1 ) ,4 (1 ) - полиномиальные (или полиномиальнооднородные) 4 4 4 4 симметрические булевы функции четырех переменных, т.е. 1 (1 )1234 ,4,4 (1 )1 23 4 . 4 Для вычисления симметрических булевых функций 0(2), 1(2), 2(2), 3(2) и 4(2) из представления (3) используются формулы 0(2)0(2),1(2)0(2)1(2),2(2)0(2)2(2),(4) 3(2)0(2)1(2)2(2)3(2),4(2)0(2)4(2). Введем в рассмотрение двоичный вектор 0), (1), (2), (3), (4(0, 1, , 14). Из формул (4) следует, что компоненты двоичных векторовисвязаны между собой следующими соотношениями, 33, 66,(5) 9369, 1212,где 0, 1, 2. Устройство для вычисления бисимметрических булевых функций шести переменных Локальный код симметрической булевой Вектор настройки(0, 1, , 14) функции(5, 6) (0, 1, , 4) 3 3 1 3 2 16666 1 2012.12.30 Поясним метод построения вектора(, 1, , 14) - вектора настройки заявляемого устройства (фигура) на вычисление произвольно заданной бисимметрической булевой функции(1, 2). С помощью локальных кодов (0)(0,1,2), (1)(3, 4, 5), (2)(6, 7, 8),(3)(9, 10, 11), (4)(12, 13, 14), из таблицы настройки (таблица), получаем значения фрагментов (0, 1, 2), (3, 4, 5), (6, 7, 8), (9, 10, 11), (12, 13, 14) вектора настройки(0, 1, , 14). Пример. Предположим, что на выходе 37 устройства требуется реализовать бисимметрическую булеву функцию(1,2 )1234561 23 4(56 ) . Так как для данной функции формула (1) принимает вид 1(0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0). Принимая во внимание описанную выше процедуру построения вектора настройки(0,114), находим 00, 15, 26, 30, 45, 56, 60, 75,86, 90, 105, 116, 125, 136, и 141. Следовательно,для реализации на выходе 37 устройства функции(1,2 )1234561 23 4(56 ) необходимо на настроечные входы 22,25, 28, 31 подать значение 0, на настроечный вход 36 - значение 1, на настроечные входы 23, 26, 29, 32, 34 - значение 5 и на настроечные входы 24, 27, 30, 33, 35 - значение 6. Первообразная функция устройства для вычисления бисимметрических булевых функций шести переменных (фигура) имеет вид( 1 ,2 ,3 ,4 )44 ( 1 ,2 ,3 ,4 ) . С целью проверки правильности работы заявляемого устройства подставим в выражение для его первообразной функции значения разрядов вектора настройки(0,5 ,6 ,0,56 ,0,56 ,0,56 ,56 ,1) . В таком случае первообразная функция принимает вид 40 (1 )5644 (1 )(5656 )40 (1 )5644 (1 )(56 )40 (1 )5644 (1 )(56 )1234561 23 4(56 ). Основным достоинством заявляемого устройства для вычисления бисимметрических булевых функций шести переменных является низкая конструктивная сложность, равная 46. Дополнительным достоинством устройства является небольшое число внешних выводов (четыре информационных и пятнадцать настроечных входов, выход). Число внешних выводов устройства-прототипа равно 23 (шесть информационных и шестнадцать настроечных входов, выход). Источники информации Национальный центр интеллектуальной собственности. 220034, г. Минск, ул. Козлова, 20.