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

(51) МПК (2009) НАЦИОНАЛЬНЫЙ ЦЕНТР ИНТЕЛЛЕКТУАЛЬНОЙ СОБСТВЕННОСТИ УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ ПОЛИНОМИАЛЬНЫХ МОДУЛЯРНЫХ СИММЕТРИЧЕСКИХ БУЛЕВЫХ ФУНКЦИЙПЕРЕМЕННЫХ(72) Автор Авгуль Леонид Болеславович(73) Патентообладатель Общество с ограниченной ответственностью Научнотехнический центр ДЭЛС(57) Устройство для вычисления полиномиальных модулярных симметрических булевых функцийпеременных, где 5, 6, 7 содержащее блок вычисления полиномиальных симметрических булевых функций трех переменных, -й вход которого, где 1, 2, 3, соединен с -м входом устройства, а также 3 группы элементов, -я из которых, где 1,3 , содержит три элемента сложения по модулю два и три элемента И, при этом выход -го элемента И -й группы соединен с первым входом -го элемента сложения по модулю два -й группы, (3)-й вход устройства соединен с первым входом -го элемента И -й группы и вторым входом первого элемента сложения по модулю два -й группы,первый выход блока вычисления полиномиальных симметрических булевых функций трех переменных соединен с третьим входом первого элемента сложения по модулю два первой группы и вторым входом второго элемента И первой группы, второй выход соединен со вторым входом второго элемента сложения по модулю два первой группы и вторым 13176 1 2010.04.30 входом третьего элемента И первой группы, третий выход соединен со вторым входом третьего элемента сложения по модулю два первой группы и вторым входом первого элемента И первой группы, выход первого элемента сложения по модулю два -й группы, где 1,4 , соединен с третьим входом первого элемента сложения по модулю два (1)й группы и вторым входом второго элемента И (1)-й группы, выход второго элемента сложения по модулю два -й группы соединен со вторым входом второго элемента сложения по модулю два (1)-й группы и вторым входом третьего элемента И (1)-й группы, выход третьего элемента сложения по модулю два -й группы соединен со вторым входом третьего элемента сложения по модулю два (1)-й группы и вторым входом первого элемента И (1)-й группы, выход -го элемента сложения по модулю два (3)-й группы соединен с -м выходом устройства. Изобретение относится к вычислительной технике и микроэлектронике и может быть использовано для построения широкого класса цифровых устройств. Известно устройство для вычисления полиномиальных симметрических булевых функций шести переменных, содержащее два одноразрядных двоичных сумматора, одиннадцать элементов И, пять элементов сложения по модулю два, шесть входов и шесть выходов 1. Недостатками устройства являются ограниченное число переменных реализуемых функций, а также невозможность вычисления полиномиальных модулярных симметрических булевых функций. Наиболее близким по конструкции и функциональным возможностям техническим решением к предлагаемому является устройство для вычисления полиномиальных симметрических булевых функций восьми переменных, содержащее четыре полусумматора,двадцать четыре элемента И, пятнадцать элементов сложения по модулю два, восемь входов и восемь выходов 2. Недостатками устройства также являются ограниченное число переменных реализуемых функций и невозможность вычисления полиномиальных модулярных симметрических булевых функций. Изобретение направлено на решение задачи расширения области применения устройства за счет реализации полиномиальных модулярных симметрических булевых функций произвольного числапеременных. Названный технический результат достигается путем введения в состав устройства- 3 групп логических элементов, каждая из которых содержит три элемента сложения по модулю два и три элемента И, а также изменением межсоединений элементов в схеме устройства. Устройство для вычисления полиномиальных модулярных симметрических булевых функцийпеременных, где 5, 6, 7 содержит блок вычисления полиномиальных симметрических булевых функций трех переменных, -й вход которого, где 1, 2, 3, соединен с -м входом устройства. Устройство содержит -3 группы элементов, -я из которых, где 1,3 , содержит три элемента сложения по модулю два и три элемента И. Выход -го элемента И -й группы соединен с первым входом -го элемента сложения по модулю два -й группы. В устройстве (3)-й вход соединен с первым входом -го элемента И -й группы и вторым входом первого элемента сложения по модулю два -й группы. Первый выход блока вычисления полиномиальных симметрических булевых функций трех переменных соединен с третьим входом первого элемента сложения по модулю два первой группы и вторым входом второго элемента И первой группы, второй выход соединен со вторым входом второго элемента сложения по модулю два первой группы и вто 2 13176 1 2010.04.30 рым входом третьего элемента И первой группы, третий выход соединен со вторым входом третьего элемента сложения по модулю два первой группы и вторым входом первого элемента И первой группы. Выход первого элемента сложения по модулю два -й группы, где 1,4 , соединен с третьим входом первого элемента сложения по модулю два (1)-й группы и вторым входом второго элемента И (1)-й группы. Выход второго элемента сложения по модулю два -й группы соединен со вторым входом второго элемента сложения по модулю два (1)-й группы и вторым входом третьего элемента И (1)-й группы. Выход третьего элемента сложения по модулю два -й группы соединен со вторым входом третьего элемента сложения по модулю два (1)-й группы и вторым входом первого элемента И (1)-й группы. Выход -го элемента сложения по модулю два (3)-й группы соединен с -м выходом устройства. На фигуре представлена схема устройства для вычисления полиномиальных модулярных симметрических булевых функцийпеременных при 8. Устройство содержит блок вычисления полиномиальных симметрических булевых функций трех переменных 1, 3-915 элементов И 2-16, 3-915 элементов сложения по модулю два 17-3,8 входов 32-39 и три выхода 40, 41 и 42. Устройство реализует три полиномиальные модулярные симметрические булевы функциипеременных при величине модуля 3. Поясним принцип построения и работы устройства. Обозначим( ,,) - некоторый кортеж длины , содержащий только элемен ты 0, 1, и 0. Булева функция,(х 1, х 2 х), называется симметрической (с.б.ф.), если она симметрична относительно любой пары переменных из . С.б.ф.однозначно определяется своим локальным кодом(0, 1 ),1 0 где,,0, . Таким образом, вес двоичной кодовой комбинации 1 х 2 х однозначно определяет значение с.б.ф.на данном наборе переменных из . С.б.ф.( ), 1, представимая в виде суммы по модулю два всевозможных попарно различных элементарных конъюнкций ранга , составленных из переменных 1,2 х, называется полиномиальной (п.с.б.ф.). Произвольная с.б.ф.отпеременных может быть однозначно представлена в виде положительно поляризованного полиномиального разложения (полинома Жегалки на) посредством п.с.б.ф. где(0, 1 ) - двоичный вектор коэффициентов полинома Жегалкина с.б.ф. . С.б.ф. ФФ(Х),(1, х 2 х), называется модулярной, если ее значение на любом наборе переменных изоднозначно определяется весом(12)двоичной кодовой комбинации по модулю ,Ф 1,0 Ф 1 ,0,.с.б.ф. ФФ(Х) можно задавать -разрядным модулярным локальным кодом 3 Очевидно, что (Ф)(0, 1 -1) и, следовательно, при-1 локальные коды(Ф)(Ф). Необходимо отметить, что один и тот же модулярный локальный код(Ф) вида (2) могут иметь м.с.б.ф., зависящие от различного числапеременных. В классе с.б.ф.переменных количество (2) различных м.с.б.ф. определяется только величиной модуляи не зависит от . Далее будем рассматривать только модулярные симметрические булевы функциипеременных ФФ(Х),(х 1, х 2 х), заданные своим модулярным локальным кодом(Ф)(0, 1, 2) при величине модуля 3,5, 6, 7,Полиномиальное разложение (1) м.с.б.ф. ФФ(Х) имеет вид При этом компоненты вектора (Ф )0 , 1,2 , 3 коэффициентов полиномиального разложения м.с.б.ф. ФФ(Х) могут быть определены из модулярного локального кода(Ф)(0, 1, 2) следующим образом 00 Пример 1. При 8 полиномиальные м.с.б.ф. в разложении (3) согласно (4), (5) и (6) могут быть представлены посредством полиномиальных с.б.ф. следующим образом 4 7 111888 8 8 2 2 2 5888888 3 3 3 68888 . Пример 2. Пусть (Ф)(0, 1 15)(0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0) - локальный код функции младшего разряда пятнадцативходового одноразрядного сумматора по модулю три. В соответствии с (2) модулярный локальный код этой функции имеет вид(Ф)(0, 1, 2)(0, 1, 2)(0,1,0). Из локального кода (Ф) согласно (7) определим коэффициенты полиномиального разложения 13176 1 2010.04.30 Тогда полиномиальное разложение (3) для рассматриваемой функции можно записать в виде 3 ФФ 115 . 15 Предлагаемое устройство реализует три полиномиальные м.с.б.ф.(х 1, х 2 х)1, 2, 3, зависящие от произвольного числапеременных для величины модуля 3. Устройство построено согласно следующим соотношениям 1 1 (,1 )1113 331, 2, 3. В устройстве блок вычисления полиномиальных симметрических булевых функций группа из трех элементов сложения по модулю два и трех элементов И обеспечивает увеличение числа обрабатываемых переменных на единицу согласно (8). Устройство для вычисления полиномиальных модулярных симметрических булевых функций при 8 (фигура) работает следующим образом. На входы 32-39 подаются двоичные переменные х 1, х 2 х 8 (в произвольном порядке), на выходах 40, 41 и 42 реализуются значения полиномиальных м.с.б.ф. соответствен 2 2 3 3 но 11 ,88 и 88 ,( 1,28 ). 8 8 Соответствие между весом 1 х 2 х 8 входной двоичной кодовой комбинации и вектором выходных сигналов устройства приведено в таблице. Достоинствами устройства для вычисления полиномиальных модулярных симметрических булевых функцийпеременных являются простая конструкция, однородная и регулярная структура. Таблица работы устройства при 8 Источники информации 1. Патент РБ 9051, МПК 067/00, 2007. 2. Патент РБ 9147, МПК 067/00, 2007. Национальный центр интеллектуальной собственности. 220034, г. Минск, ул. Козлова, 20.