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

(51) МПК (2009) НАЦИОНАЛЬНЫЙ ЦЕНТР ИНТЕЛЛЕКТУАЛЬНОЙ СОБСТВЕННОСТИ УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ БИСИММЕТРИЧЕСКИХ БУЛЕВЫХ ФУНКЦИЙПЕРЕМЕННЫХ(71) Заявитель Общество с ограниченной ответственностью Научнотехнический центр ДЭЛС(72) Автор Авгуль Леонид Болеславович(73) Патентообладатель Общество с ограниченной ответственностью Научнотехнический центр ДЭЛС(57) Устройство для вычисления бисимметрических булевых функцийпеременных, содержащее 1 группу элементов И, где 1, 2, 3, причем первая группа содержитэлементов И, где, (1)-я группа, где (1, ) , содержитэлементов И, где 13240 1 2010.06.30 соединен с (- 1)-м настроечным входом устройства, а также два блока вычисления полиномиальных симметрических булевых функций и элемент сложения по модулю два,выход которого соединен с выходом устройства, а первый вход соединен с(1)-м настроечным входом устройства, выход -го элемента И первой группы соединен с (1)м входом элемента сложения по модулю два, выход -го элемента И (1)-й группы соединен с -м входом элемента сложения по модулю два, -й вход первой группы информационных входов устройства соединен с -м входом первого блока вычисления полиномиальных симметрических булевых функций, -й вход второй группы информационных входов устройства соединен с -м входом второго блока вычисления полиномиальных симметрических булевых функций, -й выход первого блока вычисления полиномиальных симметрических булевых функций соединен со вторым входом -го элемента И (1)-й группы, -й выход второго блока вычисления полиномиальных симметрических булевых функций соединен со вторым входом -го элемента И первой группы и третьим входом Изобретение относится к вычислительной технике и микроэлектронике и может быть использовано для построения широкого класса цифровых устройств. Известно устройство для вычисления бисимметрических булевых функцийпеременных, содержащее два многовходовых одноразрядных сумматора и мультиплексор 1. Недостатком устройства является высокая конструктивная сложность. Наиболее близким по конструкции и функциональным возможностям техническим решением к предлагаемому является устройство для вычисления бисимметрических булевых функцийпеременных, содержащее два блока вычисления веса двоичных кодовых комбинаций,(1)( -1) элементов И (1,2,3,), элемент ИЛИ,информационных входов инастроечных входов 2. Недостатком известного устройства также является высокая конструктивная сложность. Изобретение направлено на решение задачи упрощения конструкции устройства для вычисления бисимметрических булевых функцийпеременных. Названный технический результат достигается путем использования блоков вычисления полиномиальных симметрических булевых функций и элемента сложения по модулю два, а также изменением межсоединений элементов в схеме устройства. Устройство для вычисления бисимметрических булевых функцийпеременных содержит 1 группу элементов И, где 1,2,3 причем первая группа содержит элементов И, где , (1)-я группа, где 1, , содержитэлементов И, где 1. Первый вход -го элемента И первой группы, где 1,, соединен с -м настроечным входом устройства. Первый вход -го элемента И (1)-й группы, где 1, , соединен с (- 1)-м настроечным входом устройства. Устройство содержит также два блока вычисления полиномиальных симметрических булевых функций и элемент сложения по модулю два, выход которого соединен с выходом устройства, а первый вход соединен с(1)-м настроечным входом устройства. Выход -го элемента И первой группы соединен с (1)-м входом элемента сложения по модулю два, выход -го элемента И (1)-й группы соединен с -м входом элемента сложения по модулю два. В устройстве -й вход первой группы информационных входов соединен с -м входом первого блока вычисления полиномиальных симметрических булевых функций, -й вход второй группы информационных входов соединен с -м входом второго блока вычисления 2 13240 1 2010.06.30 полиномиальных симметрических булевых функций, -й выход первого блока вычисления полиномиальных симметрических булевых функций соединен со вторым входом -го элемента И (1)-й группы, -й выход второго блока вычисления полиномиальных симметрических булевых функций соединен со вторым входом -го элемента И первой группы и третьим входом (1)-го элемента И (1)-й группы. На фиг. 1 представлена схема устройства для вычисления бисимметрических булевых функцийпеременных при 7 и 4. Устройство содержит первый 1 и второй 2 блоки вычисления полиномиальных симметрических булевых функций,15 групп элементов И ( -3 элемента И 3, 4 и 5 первой группы-14 элемента И 6-9 второй группы-14 элемента И 10-13 третьей группы-14 элемента И 14-17 четвертой группы 14 элемента И 18-21 пятой группы), элемент сложения по модулю два 22,4 информационных входа 23-26 первой группы,-3 информационных входа 27, 28 и 29 второй группы, (1)( -1)20 настроечных входов 30-49, выход 50. Поясним принцип работы устройства для вычисления бисимметрических булевых функцийпеременных. Обозначим( ,) - некоторый кортеж длины , содержащий только элемен ты 0,1 и 0. Булева функция,(1,2), называется симметрической (с.б.ф.), если она симметрична относительно любой пары переменных из . С.б.ф.однозначно определяется своим локальным кодом(0,1), где 1 ,0, 0.( ), 1, представимая в виде суммы по модулю два всевозможных С.б.ф. попарно различных элементарных конъюнкций ранга , составленных из переменных,2 называется полиномиальной. Булева функцияназывается бисимметрической (б.с.б.ф.), если вектор ее переменныхдопускает разбиение на два кортежа 1 и 2, и при этомсимметрична относительно любой пары переменных, принадлежащих одному и тому же кортежу 1 и 2. Для определенности полагаем 1(1,2), 2(1,2), 1. При 1,2 будем говорить, что б.с.б.ф.отпеременных принадлежит классу(, -). Б.с.б.ф.(1, 2), принадлежащая классу (, -), однозначно определяется своим локальным кодом , который представляет собой булев вектор длины(1)(-1) бит(00,010,-,10,111,-0,1-),(1) 1 0 1 0 где,,,, 0, 0-. Число б.с.б.ф. класса (, -) равно 2. Бисимметрическая булева функция(1,2) класса (,-) может быть однозначно представлена в виде положительно поляризованного полиномиального разложения где(1 ),( 2 ),0, ,0,- полиномиальные с.б.ф. и 0 (1 )1, 0( 2 )1 Г(00,010,-,10,111,-0,1-) - двоичный вектор коэффициентов полиномиального разложения,0,1. 13240 1 2010.06.30 Вектор Г может быть найден из локального кодаб.с.б.ф.(1, 2) методом,изложенным в статье полиномиальное разложение булевых функций с частичной симметрией на основе принципа локального кодирования //Автоматика и вычислительная техника. - 1997. - 5. - С. 17-28. Пример 1 При 7 и 4 полиномиальное разложение (2) бисимметрической булевой функции(1, 2) примет вид 2( )(1 ,2 )001 ( 2 )013 ( 2 )023 ( 2 )033 3 21 (1 )101 (1 )1 ( 2 )111 (1 )3 ( 2 )121 (1 )3 ( 2 )134 4 3 4 4 3 22 (1 )202 (1 )1 ( 2 )212 (1 )3 ( 2 )222 (1 )3 ( 2 )234 4 3 4 4 3 2 1 ( 2 )5673 ( 2 )5657673 ( 2 )567 . 3 3 Устройство для вычисления бисимметрических булевых функцийпеременных построено в точном соответствии с разложением (2). Схема устройства при 7 и 4,приведенная на чертеже (фиг. 1), описывается выражением (3). Из (2) непосредственно следует, что вектором настройки устройства на реализацию конкретной б.с.б.ф.(1,2) является вектор Г. Устройство при 7 и 4 (фиг. 1) работает следующим образом. На информационные входы 23-26 первой группы поступают (в произвольном порядке) переменные 1 - 4 первого кортежа 1, на информационные входы 27-29 второй группы - (в произвольном порядке) переменные 5 - 7 второго кортежа 2, на настроечные входы 30-49 сигналы настройки соответственно 00, 01, 02, 03, 10, 11, 12, 13, 20, 21, 22, 23, 30, 31, 32, 33,40, 41, 42, 43. На выходе 50 реализуется б.с.б.ф.(1,2), определяемая вектором настройки Г. Пример 2 Найдем вектор настройки устройства при 7 и 4 (фиг. 1) на реализацию бисимметрической булевой функции 1234( 567 )12( 34 )567( 12 )34567 1 234567 . Очевидно, что локальный код (1) данной функции имеет вид(00,01,02,03,10,11,12,13,20,21,22,23,30,31,32,33,40,41,42,43)(0,1,0,1,0,0,0,0,0,0,0,0,0,0,0,1,1,0,0,0). По локальному кодунайдем вектор Г коэффициентов полиномиального разложения реализуемой устройством б.с.б.ф. . С этой целью построим таблицу локальных кодов производных б.с.б.ф.(фиг. 2), из которой и определим элементы вектора Г Г(00,01,02,03,10,11,12,13,20,21,22,23,30,31,32,33,40,41,42,43)(0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,1,1,0,1,1). Таким образом, для реализации устройством (фиг. 1) б.с.б.ф.сигнал логической единицы необходимо подать на настроечные входы 31, 35, 39, 43, 45, 46, 48 и 49, а сигнал логического нуля - на настроечные входы 30, 32, 33, 34, 36, 37, 38, 40, 41, 42, 44 и 47. 13240 1 2010.06.30 Отметим, что с учетом найденного вектора Г выражение (3) для рассматриваемой функции примет вид 1 ( 2 )1 (1 )1 ( 2 )2 (1 )1 ( 2 )3 (1 )1 ( 2 )3 4 3 4 3 4 3 23 (1 )3 ( 2 )4 (1 )4 (1 )3 ( 2 )4 (1 )3 ( 2 ). 4 3 4 4 4 3 Достоинствами устройства для вычисления бисимметрических булевых функцийпеременных являются простая конструкция и высокое быстродействие. Национальный центр интеллектуальной собственности. 220034, г. Минск, ул. Козлова, 20.