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

(51) МПК НАЦИОНАЛЬНЫЙ ЦЕНТР ИНТЕЛЛЕКТУАЛЬНОЙ СОБСТВЕННОСТИ УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ ФУНДАМЕНТАЛЬНЫХ ПОЛИНОМИАЛЬНЫХ МОДУЛЯРНЫХ СИММЕТРИЧЕСКИХ БУЛЕВЫХ ФУНКЦИЙПЕРЕМЕННЫХ(72) Автор Авгуль Леонид Болеславович(73) Патентообладатель Общество с ограниченной ответственностью Научнотехнический центр ДЭЛС(57) Устройство для вычисления фундаментальных полиномиальных модулярных симметрических булевых функцийпеременных, где 26, а 1, 2, 3, , характеризующееся тем, что содержит блок вычисления полиномиальных симметрических булевых функций шести переменных, -й вход которого, где 1, 6 , соединен с -м входом устрой 18131 1 2014.04.30 18131 1 2014.04.30 шесть элементов сложения по модулю два, двенадцать элементов И,полусумматоров,-й вход -го из которых, где 1, 2, соединен с (24)-м входом устройства, а выход суммы соединен с первым входом -го элемента И -й группы и первым входом первого элемента сложения по модулю два -й группы, выход переноса соединен с первым входом(6)-го элемента И -й группы и первым входом второго элемента сложения по модулю два -й группы, выход первого элемента И -й группы соединен со вторым входом -го элемента сложения по модулю два -й группы и первым входом (2)-го, где 1, 4 ,элемента сложения по модулю два -й группы, выход восьмого элемента И -й группы соединен с третьим входом -го элемента сложения по модулю два -й группы и вторым входом (2)-го элемента сложения по модулю два -й группы, выход седьмого элемента И-й группы соединен с четвертым входом первого элемента сложения по модулю два -й группы, выход второго элемента И -й группы соединен с четвертым входом второго элемента сложения по модулю два -й группы, выход (2)-го элемента И -й группы соединен с третьим входом (2)-го элемента сложения по модулю два -й группы, выход(8)-го элемента И -й группы соединен с четвертым входом (2)-го элемента сложения по модулю два -й группы, -й выход блока вычисления полиномиальных симметрических булевых функций шести переменных соединен с пятым входом -го элемента сложения по модулю два первой группы и вторым входом (76)-го элемента И первой группы, пятый выход блока вычисления полиномиальных симметрических булевых функций шести переменных соединен с пятым входом пятого элемента сложения по модулю два первой группы и вторым входом (24)-го элемента И первой группы, шестой выход блока вычисления полиномиальных симметрических булевых функций шести переменных соединен с пятым входом шестого элемента сложения по модулю два первой группы и вторым входом (65)-го элемента И первой группы, выход -го элемента сложения по модулю два -й группы, где 1,1 , соединен с пятым входом -го элемента сложения по модулю два (1)-й группы и вторым входом (76)-го элемента И(1)-й группы, выход пятого элемента сложения по модулю два -й группы соединен с пятым входом пятого элемента сложения по модулю два (1)-й группы и вторым входом (214)-го элемента И (1)-й группы, выход шестого элемента сложения по модулю два -й группы соединен с пятым входом шестого элемента сложения по модулю два(1)-й группы и вторым входом (65)-го элемента И (1)-й группы, выход -го элемента сложения по модулю два -й группы соединен с -м выходом устройства. Изобретение относится к вычислительной технике и микроэлектронике и может быть использовано для построения широкого класса цифровых устройств. Известно устройство для вычисления полиномиальных симметрических булевых функций шести переменных, содержащее два одноразрядных двоичных сумматора, одиннадцать элементов И, пять элементов сложения по модулю два, шесть входов и шесть выходов 1. Недостатками устройства являются ограниченное число переменных реализуемых функций, а также невозможность вычисления фундаментальных полиномиальных модулярных симметрических булевых функций. Наиболее близким по конструкции и функциональным возможностям техническим решением к предлагаемому является устройство для вычисления полиномиальных модулярных симметрических булевых функцийпеременных (27,2, 3, 4, ) , содержащее блок вычисления полиномиальных симметрических булевых функций семи переменных,полусумматоров игрупп логических элементов, каждая из которых содержит семь элементов сложения по модулю два и четырнадцать элементов И 2. 18131 1 2014.04.30 Недостатком известного устройства является невозможность вычисления фундаментальных полиномиальных модулярных симметрических булевых функций. Изобретение направлено на решение задачи расширения области применения устройства за счет реализации фундаментальных полиномиальных модулярных симметрических булевых функцийпеременных. Названный технический результат достигается путем использования блока вычисления полиномиальных симметрических булевых функций шести переменных, а также изменением межсоединений элементов в схеме устройства. Устройство для вычисления фундаментальных полиномиальных модулярных симметрических булевых функцийпеременных, где 26 , а 1, 2, 3,, содержит блок вычисления полиномиальных симметрических булевых функций шести переменных, -й вход которого, где 1, 6 , соединен с -м входом устройства. Устройство содержитгрупп логических элементов, -я из которых, где 1,, содержит шесть элементов сложения по модулю два и двенадцать элементов И. Устройство содержитполусумматоров, -й вход -го из которых, где 1, 2, соединен с (24) -м входом устройства, а выход суммы соединен с первым входом -го элемента И -й группы и первым входом первого элемента сложения по модулю два -й группы, выход переноса соединен с первым входом (6) -го элемента И -й группы и первым входом второго элемента сложения по модулю два -й группы. Выход первого элемента И -й группы соединен со вторым входом -го элемента сложения по модулю два -й группы и первым входом (2) -го, где 1, 4 , элемента сложения по модулю два -й группы. Выход восьмого элемента И -й группы соединен с третьим входом -го элемента сложения по модулю два -й группы и вторым входом (2) -го элемента сложения по модулю два -й группы. Выход седьмого элемента И -й группы соединен с четвертым входом первого элемента сложения по модулю два -й группы. Выход второго элемента И -й группы соединен с четвертым входом второго элемента сложения по модулю два -й группы. Выход (2) -го элемента И -й группы соединен с третьим входом (2) -го элемента сложения по модулю два -й группы. Выход (8) -го элемента И -й группы соединен с четвертым входом (2) -го элемента сложения по модулю два -й группы. В устройстве -й выход блока вычисления полиномиальных симметрических булевых функций шести переменных соединен с пятым входом -го элемента сложения по модулю два первой группы и вторым входом (76) -го элемента И первой группы. Пятый выход блока вычисления полиномиальных симметрических булевых функций шести переменных соединен с пятым входом пятого элемента сложения по модулю два первой группы и вторым входом (24) -го элемента И первой группы. Шестой выход блока вычисления полиномиальных симметрических булевых функций шести переменных соединен с пятым входом шестого элемента сложения по модулю два первой группы и вторым входом (65) -го элемента И первой группы. Выход -го элемента сложения по модулю два -й группы, где 1,1 , соединен с пятым входом -го элемента сложения по модулю два (1)-й группы и вторым входом(76) -го элемента И (1) -й группы. Выход пятого элемента сложения по модулю два -й группы соединен с пятым входом пятого элемента сложения по модулю два(1) -й группы и вторым входом (24) -го элемента И (1) -й группы. Выход шестого элемента сложения по модулю два -й группы соединен с пятым входом шестого элемента сложения по модулю два (1) -й группы и вторым входом (65) -го элемента И (1) -й 18131 1 2014.04.30 группы. Выход -го элемента сложения по модулю два -й группы соединен с -м выходом устройства. На фигуре представлена схема устройства для вычисления фундаментальных полиномиальных модулярных симметрических булевых функцийпеременных при 2612 (3) . Устройство содержит блок вычисления полиномиальных симметрических булевых функций шести переменных 1,3 полусумматора 2, 3 и 4, 1236 элементов И 5-40,618 элементов сложения по модулю два 41-58,2612 входов 59-70 и шесть выходов 71-76. Поясним принцип построения и работы устройства. Обозначим( , , ,) - некоторый кортеж длины , содержащий только эле менты 0,1, и 0. Булева функция( ) ,( 1 ,2 ) называется симметрической (с.б.ф.), если она симметрична относительно любой пары переменных из . С.б.ф.( ) однозначно определяется своим локальным кодом Таким образом, вес двоичной кодовой комбинации ( )12 однозначно определяет значение с.б.ф.( ) на данном наборе переменных из . С.б.ф., 1, представимая в виде суммы по модулю два всевозможных попарно различных элементарных конъюнкций ранга , составленных из переменных 1 ,2 ,,, называется полиномиальной (п.с.б.ф.). Произвольная с.б.ф.( ) отпеременных может быть однозначно представлена в виде положительно поляризованного полиномиального разложения (полинома Жегалки на) посредством п.с.б.ф. где(0 , 1,,) - двоичный вектор коэффициентов полинома Жегалкина с.б.ф. . С.б.ф. ФФ ,( 1 ,2 ,,) называется модулярной, если ее значение на любом наборе переменных изоднозначно определяется весом( 12)двоичной кодовой комбинации по модулю ,Ф(1 ,0 - )Ф(1 ,0 -) ,(Ф)(Ф). Необходимо отметить, что один и тот же модулярный локальный код (Ф) вида (2) могут иметь м.с.б.ф., зависящие от различного числапеременных. В классе с.б.ф.переменных количество (2 Р) различных м.с.б.ф. определяется только величиной модуляи не зависит от . 18131 1 2014.04.30 Далее будем рассматривать только модулярные симметрические булевы функцийпеременных ФФ ,( 1 ,2 ,,) , заданные своим модулярным локальным кодом (Ф)(0 , 1 , 2 , 3 , 4 , 5 , 6 ) при величине модуля 7,8, 9, 10,Полиномиальное разложение (1) м.с.б.ф. ФФ при 7 можно представить в виде 2 Ф 011223344556677 ,(3) Компоненты вектора(Ф)( 0 , 1 ,2 ,3 ,4 ,5 ,6 ,7 ) коэффициентов полиномиального разложения м.с.б.ф. ФФ могут быть определены из модулярного локального кода (Ф)( 0 , 1 ,2 ,3 ,4 ,5 ,6 ) следующим образом 00 7123456 . Из (4) непосредственно следует, что 7123456 . Принимая во внимание (5), полиномиальное разложение (3) представим в канонической форме 1 Ф 012233445566 ,где 7 ,1,6. 1 2 6 Функции,назовем фундаментальными полиномиальными м.с.б.ф., а вектор(Ф)( 0 , 1,2 ,3 ,4 ,5 ,6 ) - каноническим полиномиальным модулярным локальным кодом. Очевидно, что канонический полиномиальный модулярный локальный код( )( 0 , 1 ,2 ,3 ,4 ,5 ,6 ) функцийимеет только один элемент, равный единице 1,1,6 . Тогда можно записать 1( )(0,1, 0, 0, 0, 0, 0)(2 )(0, 0,1, 0, 0, 0, 0) 18131 1 2014.04.30 1 Фундаментальные полиномиальные м.с.б.ф., 2 6 могут быть непосредственно вычислены согласно (7) посредством полиномиальных м.с.б.ф.1 ,2 , ,7 . Одна ко более эффективным представляется использование иного способа вычисления, котокоторый и реализован в предлагаемом устройстве. Пусть ФФ(,1 ,2 ) ,( 1 ,2 ) - некоторая м.с.б.ф. от 2 переменных. Выполним полиномиальное разложение Ф по переменным 1 и 2(9) Ф(,1 ,2 )012 , где 00, 11 и 22- остаточные м.с.б.ф. отпеременных 1212 . Отметим, что функцииимогут быть реализованы соответственно на выходах суммы и переноса полусумматора. Тогда если(Ф)( 0 , 16 ) - канонический полиномиальный модулярный локальный код м.с.б.ф. ФФ(,1,2 ) при величине модуля 7, то коды остаточных функций 0, 1 и 2 определяются следующим образом(0 )(Ф)( 0 , 1 ,2 ,3 ,4 ,5 ,6 ) Заметим, что в локальных кодах (1) и (2) присутствует элемент 7, который вычисляется согласно (5). Выполним разложение вида (9) фундаментальных полиномиальных м.с.б.ф. 12 (,1 ,2 ), 2 2 (,1 ,2 ), , 6 2 (,1 ,2 )(11)2 (,1 ,2 )012 ,1,6. С учетом (8) и (10) представим остаточные функции в форме канонического полиномиального разложения (6). 1 Выполним разложение функции 2 (,1 ,2 ) . Поскольку локальный код 1(2 (,1,2( 0 , 1 ,2 ,3 ,4 ,5 ,6 )(0, 1, 0, 0, 0, 0, 0) , то локальные коды остаточных функций 1, 1, 1 примут вид 0 1 2(1 (( 0 , 1 ,2 ,3 ,4 ,5 ,6 )(0, 1, 0, 0, 0, 0, 0) 0 1 ((,,,,,,)(1, 0, 0, 0, 0, 0, 1)(1 1 2 3 4 5 6 7 1 ((,,,,,,)(0, 0, 0, 0, 0, 1, 1).(2 2 3 4 5 6 7 1 Откуда согласно (6) можно записать Заметим, что поскольку(2 (,1 ,2( (,1, 6, являются унитарными двоичными кодами, то согласно (5) элементы 71 в локальных кодах(13) 1265 . Аналогичным образом для функций 31 (,1 ), 41 (,1 ), 51 (,1 ) и 61 (,1 ) можно получить следующие аналитические выражения 1 3 2 (,1 ,2 )3265 Заметим, что при величине модуля 7 и числе переменных 6 фундаментальные полиномиальные м.с.б.ф. совпадают с полиномиальными с.б.ф., а именно 66 ,1,6. Предлагаемое устройство построено в соответствии с соотношениями (12)-(17) и реализует шесть фундаментальных полиномиальных м.с.б.ф.,1,6 , зависящих от произвольного числапеременных для величины модуля 7. Блок вычисления полиномиальных симметрических булевых функций шести переменных 1 реализует функции 666 ,1,6 , а каждая группа из шести элементов сложения по модулю два и двенадцати элементов И обеспечивает увеличение числа обрабатываемых переменных на две согласно (12)-(17). Устройство для вычисления фундаментальных полиномиальных модулярных симметрических булевых функций при 12 (фиг. 1) работает следующим образом. На входы 59-70 подаются двоичные переменные 1, 2, , 12 (в произвольном порядке), на выходах 71, 72, , 76 реализуются значения фундаментальных полиномиальных м.с.б.ф. 6 6 1 1 2 2 1212, 1212, , 1212 соответственно,(1, 2 12). Достоинствами устройства для вычисления фундаментальных полиномиальных модулярных симметрических булевых функцийпеременных являются простая конструкция,однородная и регулярная структура. Национальный центр интеллектуальной собственности. 220034, г. Минск, ул. Козлова, 20.