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

(51) МПК НАЦИОНАЛЬНЫЙ ЦЕНТР ИНТЕЛЛЕКТУАЛЬНОЙ СОБСТВЕННОСТИ УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ МОДУЛЯРНЫХ СИММЕТРИЧЕСКИХ БУЛЕВЫХ ФУНКЦИЙПЕРЕМЕННЫХ(72) Автор Авгуль Леонид Болеславович(73) Патентообладатель Общество с ограниченной ответственностью Научнотехнический центр ДЭЛС(57) Устройство для вычисления модулярных симметрических булевых функцийпеременных, где 7, характеризующееся тем, что содержит блок вычисления симметрических булевых функций шести переменных и 6 групп логических элементов, каждая из которых содержит семь элементов сложения по модулю два и шесть элементов И, причем первый вход -го элемента И, где 1, 6 , -й группы, где 1,6 , соединен с -м информационным входом устройства, а выход соединен с первым входом -го элемента сложения по модулю два -й группы, второй вход первого элемента сложения по модулю два первой группы соединен с первым настроечным входом устройства, второй вход (1)-го,где 1, 5 , элемента сложения по модулю два первой группы соединен с (1)-м настроечным входом устройства и вторым входом -го элемента И первой группы, первый 18010 1 2014.02.28 вход седьмого элемента сложения по модулю два первой группы соединен с седьмым настроечным входом устройства и вторым входом шестого элемента И первой группы, второй вход первого элемента сложения по модулю два (1)-й группы, где 1,7 ,соединен с выходом первого элемента сложения по модулю два -й группы, второй вход(1)-го элемента сложения по модулю два (1)-й группы соединен с выходом(1)-го элемента сложения по модулю два -й группы и вторым входом -го элемента И(1)-й группы, первый вход седьмого элемента сложения по модулю два (1)-й группы соединен с выходом седьмого элемента сложения по модулю два -й группы и вторым входом шестого элемента И (1)-й группы, выход -го, где 1, 7 , элемента сложения по модулю два (6)-й группы соединен с -м настроечным входом блока вычисления симметрических булевых функций шести переменных, -й информационный вход которого соединен с (6)-м входом устройства, а выход соединен с выходом устройства,причем выход -го элемента И -й группы соединен с (1)-м входом седьмого элемента сложения по модулю два -й группы. Изобретение относится к вычислительной технике и микроэлектронике и может быть использовано для построения широкого класса цифровых устройств. Известно устройство для вычисления модулярных симметрических булевых функцийпеременных, которое при 1 содержит блок вычисления симметрических булевых функций шести переменных,6 элементов НЕ и 6 групп логических элементов, каждая из которых содержит семь элементов 2-2 И-2 ИЛИ,информационных входов, семь настроечных входов и один выход 1. Недостатком устройства является высокая конструктивная сложность. Наиболее близким по конструкции и функциональным возможностям техническим решением к предлагаемому является устройство для вычисления симметрических булевых функцийпеременных, содержащее 33 элементов 2-2 И-2 ИЛИ,элементов НЕ,информационных входов, три настроечных входа и один выход 2. Устройство реализует восемь модулярных симметрических булевых функцийпеременных для величины модуля 3. Недостатком известного устройства является невозможность вычисления модулярных симметрических булевых функцийпеременных для величины модуля 7. Изобретение направлено на решение задачи расширения области применения устройства за счет вычисления модулярных симметрических булевых функцийпеременных для величины модуля 7. Названный технический результат достигается путем ведения в схему устройства блока вычисления симметрических булевых функций шести переменных, а также элементов сложения по модулю два и элементов И. Устройство для вычисления модулярных симметрических булевых функцийпеременных, где 1, содержит блок вычисления симметрических булевых функций шести переменных и 6 групп логических элементов, каждая из которых содержит семь элементов сложения по модулю два и шесть элементов И. Причем первый вход -го элемента И, где 1, 6 , -й группы, где 1,6 , соединен с -м информационным входом устройства, а выход соединен с первым входом -го элемента сложения по модулю два -й группы. Второй вход первого элемента сложения по модулю два первой группы соединен с первым настроечным входом устройства. Второй вход (1)-го, где 1, 5 , элемента сложения по модулю два первой группы соединен с (1)-м настроечным входом устройства и вторым входом -го элемента И первой группы. Первый вход седьмого элемента сложения по модулю два первой группы соединен с седьмым настроечным входом устройства и вторым входом шестого элемента И первой группы. Второй вход первого 2 18010 1 2014.02.28 элемента сложения по модулю два (1)-й группы, где 1,7 ,соединен с выходом первого элемента сложения по модулю два -й группы. Второй вход (1)-го элемента сложения по модулю два (1)-й группы соединен с выходом (1)-го элемента сложения по модулю два -й группы и вторым входом -го элемента И -й группы. Первый вход седьмого элемента сложения по модулю два (1)-й группы соединен с выходом седьмого элемента сложения по модулю два -й группы и вторым входом шестого элемента И-й группы. Выход -го, где 1, 7 , элемента сложения по модулю два (6)-й группы соединен с -м настроечным входом блока вычисления симметрических булевых функций шести переменных, -й информационный вход которого соединен с (- 6)-м входом информационным устройства, а выход соединен с выходом устройства. Причем выход -го элемента И -й группы соединен с (1)-м входом седьмого элемента сложения по модулю два -й группы. На фигуре представлена схема устройства для вычисления модулярных симметрических булевых функцийпеременных при 10. Устройство содержит 63624 элемента И 1-24, 74228 элементов сложения по модулю два 25-52, блок вычисления симметрических булевых функций шести переменных 53,10 информационных входов 54-63, семь настроечных входов 64-70, выход 71. Обозначим(, ) - некоторый кортеж длины , содержащий только элемен ты 0,1, и 0. Булева функция,(1, 2, , ), называется симметрической (с.б.ф.), если она симметрична относительно любой пары переменных из . С.б.ф.однозначно определяется своим локальным кодом С.б.ф., 1, представимая в виде суммы по модулю два всевозможных попарно различных элементарных конъюнкций ранга , составленных из переменных, 2, , , называется полиномиальной (п.с.б.ф.). Произвольная с.б.ф.отпеременных может быть однозначно представлена в виде положительно поляризованного полиномиального разложения (полинома Жегалки на) посредством п.с.б.ф. где(0, 1, , ) - двоичный вектор коэффициентов полинома Жегалкина с.б.ф. . С.б.ф. ФФ,(1, 2 ), называется модулярной, если ее значение на любом наборе переменных изоднозначно определяется весом(12)двоичной кодовой комбинации по модулю ,Ф(1,0)Ф(1 ,0) ,(Ф)(0, 1, , )(Ф)(0, 1, , ). Необходимо отметить, что один и тот же модулярный локальный код (Ф) вида (2) могут иметь м.с.б.ф., зависящие от различного числапеременных. В классе с.б.ф.переменных количество (2) различных м.с.б.ф. определяется только величиной модуляи не зависит от . 3 18010 1 2014.02.28 Пусть 7 и ФФ,(1, 2, , ), - некоторая м.с.б.ф.переменных, заданная своим модулярным локальным кодом (Ф)(0, 1, , 6). Несложно показать, что при выполнении условия 77, 1, 1,(4). Из (3) и (4) непосредственно следует, что вектор (Ф)(0, 1, , ) коэффициентов полиномиального разложения (1) м.с.б.ф. ФФ(Х) имеет вид(Ф)(0 ,1 , ,)(0 ,1 , ,7 ,1 , ,7 , ,1 , ,7 , ,7) ,1 24 1 24 4 3 4 3 1 24 4 3 где( - 7)/7. Тогда с учетом (5) м.с.б.ф. ФФ(Х) может быть однозначно задана полиномиальным локальным кодом(Ф)(0, 1, , 7)(0, 1, , 7),элементы которого могут быть вычислены из модулярного локального кода (Ф) 0 1 2 3 4 5 6 7 Очевидно, что при заданной величине модуляодин и тот же полиномиальный локальный код (Ф) вида (6) имеют м.с.б.ф. ФФ, зависящие от различного числапеременных. Таким образом, при величине модуля 7 полиномиальное разложение (1) м.с.б.ф. ФФ примет вид Ф 01122 3334353637 ,(8)(9) 7123456. Тогда, принимая во внимание (9), полиномиальное разложение (8) представим в канонической форме 1 Ф 012233445566 ,(10) где 18010 1 2014.02.28 1 Функции, 2 , , 6 назовем каноническими полиномиальными м.с.б.ф., а вектор(Ф)(0, 1, 2, 3, 4, 5, 6) - каноническим полиномиальным модулярным локальным кодом. В предлагаемом устройстве блок вычисления симметрических булевых функций 53 реализует все м.с.б.ф. от шести переменных, а каждая из 6 групп логических элементов, содержащих по семь элементов сложения по модулю два и по шесть элементов И,обеспечивает увеличение числа обрабатываемых переменных на единицу. При этом вектором настройки устройства на реализацию конкретной м.с.б.ф ФФ является вектор коэффициентов ее канонического полиномиального разложения(Ф)(0, 1, 2, 3, 4, 5, 6), компоненты которого находятся из модулярного локального кода (Ф) согласно (7). Устройство для вычисления модулярных симметрических булевых функций при 10 (фиг. 1) работает следующим образом. На информационные входы 54-63 подаются двоичные переменные 110 (в произвольном порядке), на настроечные входы 64, 65, , 70 - соответственно компоненты 0, 1, , 6 вектора (Ф)(0, 1, , 6) коэффициентов канонического полиномиального разложения м.с.б.ф. ФФ, значения которой реализуются на выходе 71 устройства. Таким образом, устройство при настройке сигналами из множества 0,1 реализует 227128 модулярных симметрических булевых функцийпеременных для величины модуля 7. Достоинствами устройства для вычисления модулярных симметрических булевых функцийпеременных являются простая конструкция, регулярная и однородная структура и широкие функциональные возможности. Национальный центр интеллектуальной собственности. 220034, г. Минск, ул. Козлова, 20. 5