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

(51) МПК НАЦИОНАЛЬНЫЙ ЦЕНТР ИНТЕЛЛЕКТУАЛЬНОЙ СОБСТВЕННОСТИ УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ МОДУЛЯРНЫХ СИММЕТРИЧЕСКИХ БУЛЕВЫХ ФУНКЦИЙПЕРЕМЕННЫХ(71) Заявитель Общество с ограниченной ответственностью Научнотехнический центр ДЭЛС(72) Автор Авгуль Леонид Болеславович(73) Патентообладатель Общество с ограниченной ответственностью Научнотехнический центр ДЭЛС(57) Устройство для вычисления модулярных симметрических булевых функцийпеременных, где- 1, где 3 - величина модуля, содержащее- 1 элементов И, первый вход -го, где 1,1 , из которых соединен с -м настроечным входом устройства, отличающееся тем, что содержит блок вычисления фундаментальных полиномиальных модулярных симметрических булевых функцийпеременных и элемент сложения по модулю два, выход которого соединен с выходом устройства, а -й вход соединен с выходом -го элемента И, -й вход соединен с -м настроечным входом устройства, -й, где 1,, информационный вход которого соединен с -м входом блока вычисления фундаментальных полиномиальных модулярных симметрических булевых функцийпеременных, -й выход которого соединен со вторым входом -го элемента И. 18322 1 2014.06.30 Изобретение относится к вычислительной технике и микроэлектронике и может быть использовано для построения широкого класса цифровых устройств. Известно устройство для вычисления модулярных симметрических булевых функцийпеременных, содержащее блок вычисления симметрических булевых функций- 1 переменной (- величина модуля),-1 групп элементов 2-2 И-2 ИЛИ поэлементов в каждой,-1 элементов НЕ,информационных входов,настроечных входов и один выход 1. Недостатком устройства является низкое быстродействие, определяемое большой глубиной схемы. Наиболее близким по конструкции и функциональным возможностям техническим решением к предлагаемому является устройство для вычисления модулярных симметрических булевых функцийпеременных (- 13 - величина модуля) содержащее блок вычисления веса двоичных кодовых комбинаций по модулю , элемент ИЛИ,элементов И,информационных входов,настроечных входов и один выход 2. Недостатком известного устройства является низкое быстродействие, определяемое большой глубиной схемы, реализующей блок вычисления веса двоичных кодовых комбинаций по модулю . Изобретение направлено на решение задачи повышения быстродействия устройства для вычисления модулярных симметрических булевых функцийпеременных. Названный технический результат достигается путем введения в состав устройства блока вычисления фундаментальных полиномиальных модулярных симметрических булевых функцийпеременных и элемента сложения по модулю два. Устройство для вычисления модулярных симметрических булевых функцийпеременных, где- 1, где 3 - величина модуля, содержит- 1 элементов И, первый вход -го, где 1,1 , из которых соединен с -м настроечным входом устройства. В отличие от прототипа, устройство содержит блок вычисления фундаментальных полиномиальных модулярных симметрических булевых функцийпеременных и элемент сложения по модулю два. Выход элемента сложения по модулю два соединен с выходом устройства, а -й вход соединен с выходом -го элемента И, -й вход соединен с -м настроечным входом устройства. В устройстве -й, где 1,, информационный вход соединен с -м входом блока вычисления фундаментальных полиномиальных модулярных симметрических булевых функцийпеременных, -й выход которого соединен со вторым входом -го элемента И. На фигуре представлена схема устройства для вычисления модулярных симметрических булевых функцийпеременных. Устройство содержит блок вычисления фундаментальных полиномиальных модулярных симметрических булевых функцийпеременных (- 1,3) 1,- 1 элементов И 21 - 2-1, элемент сложения по модулю два 3,информационных входов 41 - 4,настроечных входов 51 - 5, выход 6. Поясним принцип построения и работы устройства. Обозначим( ,) - некоторый кортеж длины , содержащий только эле менты 0,1, и 0. Булева функция,(1, 2 , называется симметрической (с.б.ф.), если она симметрична относительно любой пары переменных из . С.б.ф.однозначно определяется своим локальным кодом Таким образом, вес двоичной кодовой комбинации 12 однозначно определяет значение с.б.ф.на данном наборе переменных из . 2 18322 1 2014.06.30 С.б.ф.(, 1, представимая в виде суммы по модулю два всевозможных попарно различных элементарных конъюнкций ранга , составленных из переменных 1,2 , называется полиномиальной (п.с.б.ф.). Произвольная с.б.ф.отпеременных может быть однозначно представлена в виде положительно поляризованного полиномиального разложения (полинома Жегалкина) посредством п.с.б.ф. где(0, 1 ) - двоичный вектор коэффициентов полинома Жегалкина с.б.ф. . С.б.ф. ФФ,(1, 2, , ), называется модулярной, если ее значение на любом наборе переменных изоднозначно определяется весом(2)двоичной кодовой комбинации по модулю ,Ф(1,0)Ф(1 ,0),(Ф)(0 , 1 , ,)(Ф)(0 , 1 , ,) . Необходимо отметить, что один и тот же модулярный локальный код (Ф) вида (2) могут иметь м.с.б.ф.,зависящие от различного числапеременных. В классе с.б.ф.переменных количество (2) различных м.с.б.ф. определяется только величиной модуляи не зависит от . Дальнейшее изложение будет вестись для величины модуля 2 - 1. Пусть 2 - 1,2, 3, 4 и ФФ,(1, 2, , ), - некоторая м.с.б.ф.переменных, заданная своим модулярным локальным кодом (Ф)(0 , 1 , ,1 ) . Несложно показать, что при выполнении условия, 1, 1,,(3) имеет место.(4) Из (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) непосредственно следует, что полиномиальное разложение м.с.б.ф. ФФ можно представить в виде Можно показать, что элементполиномиального модулярного локального кода (Ф) может быть вычислен посредством других элементов этого кода, а именно 7121.(8) Тогда, принимая во внимание (8), полиномиальное разложение (7) представим в канонической форме 1 1 Функции, 2 1 назовем фундаментальными полиномиальными м.с.б.ф., а вектор (Ф)(0, 1, , -1) - каноническим полиномиальным модулярным локальным кодом. Предлагаемое устройство для вычисления модулярных симметрических булевых функцийпеременных построено согласно выражению (9). Отметим, что функции, 11 , реализуются на выходах блока вычисления фундаментальных полиномиальных модулярных симметрических булевых функций 1, на входы которого подаются двоичные переменные из . Из (9) также непосредственно следует, что вектором настройки устройства на реализацию конкретной м.с.б.ф ФФ является ее канонический полиномиальный модулярный локальный код (Ф)(0, 1 -1). Устройство для вычисления модулярных симметрических булевых функцийпеременных (фиг. 1) работает следующим образом. На информационные входы 41 - 4 подаются двоичные переменные 1 -(в произвольном порядке), на настроечные входы 51 - 5 - соответственно компоненты 0 - -1 канонического полиномиального модулярного локального кода к(Ф)(0, 1 -1) м.с.б.ф. ФФ, значения которой реализуются на выходе 6 устройства. Таким образом, предлагаемое устройство при настройке сигналами из множества 0,1 реализует 2 модулярных симметрических булевых функцийпеременных для произвольной величины модуля . Достоинствами устройства для вычисления модулярных симметрических булевых функцийпеременных являются высокое быстродействие, простая конструкция, широкие функциональные возможности. 1.12542, МПК 06 7/00, 2009. 2. Заявка 20091875, МПК 06 7/0, 2010 (прототип). Национальный центр интеллектуальной собственности. 220034, г. Минск, ул. Козлова, 20.