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

(51) МПК НАЦИОНАЛЬНЫЙ ЦЕНТР ИНТЕЛЛЕКТУАЛЬНОЙ СОБСТВЕННОСТИ УСТРОЙСТВО ДЛЯ ПОЛИНОМИАЛЬНОГО РАЗЛОЖЕНИЯ МОДУЛЯРНЫХ СИММЕТРИЧЕСКИХ БУЛЕВЫХ ФУНКЦИЙПЕРЕМЕННЫХ(72) Автор Авгуль Леонид Болеславович(73) Патентообладатель Общество с ограниченной ответственностью Научнотехнический центр ДЭЛС(57) Устройство для полиномиального разложения модулярных симметрических булевых функцийпеременных, где, а 21 - величина модуля, где 2, 3, 4, , содержащее блок полиномиального разложения симметрических булевых функцийпеременных, -й вход которого, где 1,, соединен с -м информационным входом устройства 18312 1 2014.06.30 мультиплексоров, первый вход данных первого из которых соединен с (1)-м входом блока полиномиального разложения симметрических булевых функцийпеременных и первым информационным входом устройства, -й управляющий вход которого, где 1,, соединен с -м адресным входом -го мультиплексора, выход которого соединен с выходом устройства, (1)-й вход данных первого мультиплексора, где 1,1 , соединен с -м выходом блока полиномиального разложения симметрических булевых функцийпеременных, -й вход данных (1)-го мультиплексора соединен с 2)1)-м выходом блока полиномиального разложения симметрических булевых функцийпеременных. Изобретение относится к вычислительной технике и микроэлектронике и может быть использовано для построения широкого класса цифровых устройств. Известно устройство для полиномиального разложения симметрических булевых функцийпеременных, содержащее дешифратор, -1 элементов ИЛИ и 2 логических ячеек, каждая из которых содержит два элемента сложения по модулю два и два элемента И 1. Устройство формирует локальные коды остаточных функций при полиномиальном разложении симметрических булевых функций попеременным. Недостатком устройства является высокая конструктивная сложность. Наиболее близким по конструкции и функциональным возможностям техническим решением к предлагаемому является устройство для полиномиального разложения симметрических булевых функцийпеременных, содержащее 2 элементов сложения по модулю два 2. Устройство формирует коэффициенты монотонно поляризованных полиномов симметрических булевых функций. Недостатком устройства является невозможность вычисления локальных кодов остаточных функций при полиномиальном разложении модулярных симметрических булевых функцийпеременных попеременным. Изобретение направлено на решение задачи расширения области применения устройства за счет вычисления локальных кодов остаточных функций при полиномиальном разложении модулярных симметрических булевых функций. Названный технический результат достигается путем введения в состав устройствамультиплексоров ( - величина модуля), а также изменением межсоединений элементов в схеме устройства. Устройство для полиномиального разложения модулярных симметрических булевых функцийпеременных, где, а 21 - величина модуля, где 2, 3, 4, , содержит блок полиномиального разложения симметрических булевых функцийпеременных, -й вход которого, где 1,, соединен с -м информационным входом устройства. Устройство содержит такжемультиплексоров, первый вход данных первого из которых соединен с (1)-м входом блока полиномиального разложения симметрических булевых функцийпеременных и первым информационным входом устройства. В устройстве -й управляющий вход, где 1,, соединен с -м адресным входом -го мультиплексора,выход которого соединен с выходом устройства. При этом (1)-й, где 1,1 , вход данных первого мультиплексора соединен с -м выходом блока полиномиального разложения симметрических булевых функцийпеременных, а -й вход данных (1)-го мультиплексора соединен с 2)1)-м выходом блока полиномиального разложения симметрических булевых функцийпеременных. На фигуре представлена схема устройства для полиномиального разложения модулярных симметрических булевых функцийпеременных для величины модуля 217 (3). 2 18312 1 2014.06.30 Устройство содержит блок полиномиального разложения симметрических булевых функций 7 переменных 1,7 мультиплексоров 2-8,7 информационных входов 9-15,3 управляющих входа 16, 17 и 18,7 выходов 19-25. Поясним принцип построения и работы предлагаемого устройства. Пусть(, , ,) - некоторый кортеж длины , содержащий только элементы 0, 1, и 0. Булева функция,(1, 2, , ) называется симметрической (с.б.ф.), если она симметрична относительно любой пары переменных из . С.б.ф.однозначно определяется своим локальным кодом(0, 1, , ),1 ,0 ),0,. где(Таким образом, вес двоичной кодовой комбинации 12 однозначно определяет значение с.б.ф.на данном наборе переменных из . С.б.ф., 1, представимая в виде суммы по модулю два всевозможных попарно различных элементарных конъюнкций ранга , составленных из переменных 1,2, , , называется полиномиальной (п.с.б.ф.). Произвольная с.б.ф.отпеременных может быть однозначно представлена в виде положительно поляризованного полиномиального разложения (полинома Жегалки на) посредством п.с.б.ф. где(0, 1, , ) - двоичный вектор коэффициентов полинома Жегалкина с.б.ф. . С.б.ф. ФФ,(1, 2, , ) называется модулярной (м.с.б.ф.), если ее значение на любом наборе переменных изоднозначно определяется весом(12) двоичной кодовой комбинации по модулю ,Ф(1 ,0)Ф(1 ,0) ,где, 0, 0,. Очевидно, что в локальном коде (Ф)(0, 1, , ) м.с.б.ф. ФФ элементы, а ее локальный код можно представить в виде(Ф)(0, 1, , -1)(0, 1, , -1),1 0 гдеФ(,) ,, 0,0,1 . Необходимо отметить, что один и тот же модулярный локальный код (Ф) вида (2) может иметь м.с.б.ф., зависящие от различного числапеременных. В классе с.б.ф.переменных количество (2) различных м.с.б.ф. определяется только величиной модуляи не зависит от . Дальнейшее изложение будет вестись для величины модуля 21,2, 3, 4,. Пусть ФФ,(1, 2, , ) - некоторая м.с.б.ф.переменных, заданная своим модулярным локальным кодом (Ф)(0, 1, , -1). Несложно показать, что при выполнении условия, 1, 1,,(3) имеет место. 18312 1 2014.06.30 Из (3) и (4) непосредственно следует, что вектор (Ф)(0, 1, , ) коэффициентов полиномиального разложения (1) м.с.б.ф. ФФ имеет вид(Ф)(0 , 1 , ,)(0 , 1 , ,, 1 , ,, , 1 , ,, ,) ,1 24 1 24 4 3 4 3 1 24 4 3 где/. Тогда с учетом (5) м.с.б.ф. ФФ может быть однозначно задана полиномиальным модулярным локальным кодом к(Ф)(к 0, к 1, , к)(0, 1, , ),(6) элементы которого могут быть вычислены из модулярного локального кода (Ф). Очевидно, что при заданной величине модуляодин и тот же полиномиальный локальный код к(Ф) вида (6) имеет м.с.б.ф. ФФ, зависящие от различного числапеременных. Из (1) и (6) непосредственно следует, что полиномиальное разложение м.с.б.ф. ФФ можно представить в виде Можно показать, что элемент к полиномиального модулярного локального кода к(Ф) может быть вычислен посредством других элементов этого кода, а именно(8) к 7 к 1 к 2 к-1. Тогда, принимая во внимание (8), полиномиальное разложение (7) представим в канонической форме 1 1 Функции, 2 ,, 1 называются фундаментальными полиномиальными м.с.б.ф.,а вектор к(Ф)(к 0, к 1 к-1) - каноническим полиномиальным модулярным локальным кодом. Пусть ФФФ(1,2), 1(1, 2, , ), 2(1,2, , ) - некоторая м.с.б.ф.переменных и к(Ф)(к 0, к 1, , к-1) - канонический полиномиальный модулярный локальный код Ф. М.с.б.ф. ФФФ(1, 2) допускает полиномиальную декомпозицию по 1 переменным из 1 вида 1 где,1,1 - фундаментальные полиномиальные м.с.б.ф. отпеременных(2),0,1 - остаточные м.с.б.ф. от - переменных. Отметим, что количество остаточных функций в (11) не зависит от размерностикортежа 1, по которому выполняется разложение, а определяется только величиной модуля . Очевидно также, что придекомпозиционное разложение (11) примет вид (9). 4 18312 1 2014.06.30 В свою очередь, остаточные м.с.б.ф.(2) из (11) могут быть также представлены в виде полиномиального разложения (9)1) - канонический полиномиальный модулярный локальный код м.с.б.ф. ,0,1 . Канонические полиномиальные модулярные локальные коды к остаточных м.с.б.ф.(2) могут найдены из к(Ф) следующим образом к(0 )к(Ф)(к 0 , к 1 , к 2 , , к 2 , к 1 ) Предлагаемое устройство формирует из модулярного локального кода (Ф)(0, 1, , 1) м.с.б.ф.переменных ФФФ(1, 2) канонические полиномиальные модулярные локальные коды (12) остаточных функций в декомпозиционном разложении (11) при величине модуля 21,2, 3, 4. На 1 входов блока полиномиального разложения симметрических булевых функцийпеременных 1 подается вектор (0, 1, , 1, 0)(0, 1, , 1, 0), составленный из элементов модулярного локального кода (Ф) м.с.б.ф. Ф. На выходах блока 1 формируется вектор (1, 2, , )(к 1, к 2, , к) элементов полиномиального модулярного локального кода к(Ф) м.с.б.ф. Ф. Элементы 0 к 0, к 1, к 2, , к соответствующим образом подаются на входы данных-канальных мультиплексоров, на адресные входы которых поступает -разрядный двоичный код номера остаточной функции ,0,1 , из (11), канонический полиноми альный модулярный локальный код которой к( )(к 0 , к 1 , , к 1 ) формируется,согласно (12), на выходах мультиплексоров. Устройство для полиномиального разложения модулярных симметрических булевых функцийпеременных при величине модуля 7 (фиг. 1) работает следующим образом. На информационные входы устройства 9, 10, , 15 подаются соответственно элементы 0, 1, , 6 модулярного локального кода (Ф)(0, 1, , 6) некоторой м.с.б.ф.переменных ФФФ(1, 2), на управляющие входы 16, 17 и 18 (адресные входы мультиплексоров 2-8) - трехразрядный двоичный код, определяющий номеростаточной м.с.б.ф.(2) в разложении (11),0, 6 . Отметим, что непосредственно на входы блока полиномиального разложения симметрических булевых функций 7 переменных 1 поступают компоненты вектора (0, 1, , 6, 0). На выходах 19-25 устройства формируются соответственно элементы к 0 к 6 канони ческого полиномиального модулярного локального кода к( )(к 0 , к 1 , к 2 , к 3 , к 4 , к 5 , к 6 ) м.с.б.ф.(2). Работа устройства при величине модуля 7 поясняется таблицей. Достоинствами устройства для полиномиального разложения модулярных симметрических булевых функцийпеременных являются простая конструкция и широкие функциональные возможности. 18312 1 2014.06.30 Таблица работы устройства при 7 Номер м.с.б.ф.Сигналы на управляющих входах 16 17 18 0 0 0 0 1 1 1 Сигналы на выходах устройства Национальный центр интеллектуальной собственности. 220034, г. Минск, ул. Козлова, 20.