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

(51) МПК НАЦИОНАЛЬНЫЙ ЦЕНТР ИНТЕЛЛЕКТУАЛЬНОЙ СОБСТВЕННОСТИ УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ МОДУЛЯРНЫХ СИММЕТРИЧЕСКИХ БУЛЕВЫХ ФУНКЦИЙПЕРЕМЕННЫХ(71) Заявитель Общество с ограниченной ответственностью Научнотехнический центр ДЭЛС(72) Автор Авгуль Леонид Болеславович(73) Патентообладатель Общество с ограниченной ответственностью Научнотехнический центр ДЭЛС(57) Устройство для вычисления модулярных симметрических булевых функцийпеременных, где 4, содержащее два элемента И и многовходовый одноразрядный сумматор по модулю пять, -й вход которого, где 1,, соединен с -м информационным входом устройства, -й настроечный вход которого, где 1,2, соединен с первым входом -го элемента И, второй вход первого элемента И соединен с выходом младшего разряда многовходового одноразрядного сумматора по модулю пять, выход среднего разряда которого соединен с третьим входом первого элемента И, а выход его старшего разряда соединен со вторым входом второго элемента И, отличающееся тем, что содержит третий и четвертый элементы И и элемент сложения по модулю два, -й вход которого, где 1,4 , соединен с выходом -го элемента И, а его пятый вход соединен с третьим настроечным входом устройства, (3)-й настроечный вход которого соединен с первым входом (2)го элемента И, второй вход третьего элемента И соединен с выходом младшего разряда многовходового одноразрядного сумматора по модулю пять, выход среднего разряда которого соединен со вторым входом четвертого элемента И. 17941 1 2014.02.28 Изобретение относится к вычислительной технике и микроэлектронике и может быть использовано для построения широкого класса цифровых устройств. Известно устройство для вычисления модулярных симметрических булевых функцийпеременных, содержащеегрупп элементов 2-2 И-2 ИЛИ,элементов НЕ,информационных входов, пять настроечных входов и один выход 1. Недостатком устройства является низкое быстродействие, определяемое большой глубиной схемы. Наиболее близким по конструкции и функциональным возможностям техническим решением к предлагаемому является устройство для вычисления модулярных симметрических булевых функцийпеременных, содержащее многовходовый одноразрядный сумматор по модулю пять, два элемента И, три элемента ЗАПРЕТ, элемент ИЛИ,информационных входов, пять настроечных входов и один выход 2. При настройке сигналами из множества 0,1 устройство реализует тридцать две модулярные симметрические булевы функциипеременных для величины модуля 5. Недостатком известного устройства является высокая сложность. Изобретение направлено на решение задачи упрощения конструкции устройства для вычисления модулярных симметрических булевых функцийпеременных. Названный технический результат достигается путем введения в состав устройства элемента сложения по модулю два и двух элементов И, а также изменением межсоединений элементов в схеме устройства. Устройство для вычисления модулярных симметрических булевых функцийпеременных, где 4, содержит два элемента И и многовходовый одноразрядный сумматор по модулю пять, -й, где 1,, вход которого соединен с -м информационным входом устройства, -й настроечный вход которого, где 1,2, соединен с первым входом -го элемента И. Второй вход первого элемента И соединен с выходом младшего разряда многовходового одноразрядного сумматора по модулю пять, выход среднего разряда которого соединен с третьим входом первого элемента И, а выход его старшего разряда соединен со вторым входом второго элемента И. В отличие от прототипа, устройство содержит третий и четвертый элементы И и элемент сложения по модулю два, -й вход которого, где 1, 4 , соединен с выходом -го элемента И, а его пятый вход соединен с третьим настроечным входом устройства, (3)й настроечный вход которого соединен с первым входом (2)-го элемента И. Второй вход третьего элемента И соединен с выходом младшего разряда многовходового одноразрядного сумматора по модулю пять, выход среднего разряда которого соединен со вторым входом четвертого элемента И. На фигуре представлена схема устройства для вычисления модулярных симметрических булевых функцийпеременных. Устройство содержит многовходовый одноразрядный сумматор по модулю пять 1, четыре элемента И 2-5, элемент сложения по модулю два 6,информационных входов 71-7,пять настроечных входов 8-12 и выход 13. Поясним принцип построения и работы предлагаемого устройства для вычисления модулярных симметрических булевых функцийпеременных. Обозначим(, ) - некоторый кортеж длины , содержащий только элементы 0,1, и 0. Булева функция,(1, 2 ), называется симметрической (с.б.ф.), если она симметрична относительно любой пары переменных из . С.б.ф.( однозначно определяется своим локальным кодом 17941 1 2014.02.28 Таким образом, вес двоичной кодовой комбинациих 1 х 2 х однозначно определяет значение с.б.ф.на данном наборе переменных из . В классе симметрических булевых функций выделяется подкласс так называемых модулярных с.б.ф. (м.с.б.ф.). С.б.ф. ФФ,(1, 2 ), называется модулярной, если ее значение на любом наборе переменных изоднозначно определяется весом(12)двоичной кодовой комбинации по модулю ,Ф(1, 0-)Ф(1, 0-),(2) где, 0, 0,.(3) Из (1) и (2) непосредственно следует, что при выполнении условия (3) в локальном коде (Ф)(0, 1 ) м.с.б.ф. ФФ элементы. Тогда локальный код м.с.б.ф. ФФ можно представить в виде где(1)/. Принимая во внимание (4), м.с.б.ф. ФФ можно задавать р-разрядным модулярным локальным кодом(Ф)(Ф). Необходимо отметить, что один и тот же модулярный локальный код (Ф) вида (5) может иметь м.с.б.ф., зависящие от различного числапеременных. В классе с.б.ф.переменных количество (2) различных м.с.б.ф. определяется только величиной модуляи не зависит от . Дальнейшие рассуждения будут вестись только для величины модуля 5 и модулярных симметрических булевых функцийпеременных ФФ, заданных своим модулярным локальным кодом (Ф)(0, р, 2, 3, 4). Произвольная м.с.б.ф. ФФпеременных может быть однозначно представлена в виде канонического полиномиального разложения 4 где к 0,1,0, 4 - коэффициенты полиномиального разложения- фундаментальные полиномиальные м.с.б.ф. и 001. Таким образом, произвольная м.с.б.ф. ФФ может быть представлена суммой по модулю двух фундаментальных полиномиальных м.с.б.ф.. Можно показать, что коэффициенты к полиномиального разложения (6) находятся из модулярного локального кода (Ф)(0, 1, 2, 3, 4) согласно соотношениям При этом модулярные локальные коды функций 1, 2, 3 и 4 имеют вид В общем случае многовходовый одноразрядный сумматор по модулю пять выполняет сложение по модулю пятьодноразрядных двоичных чисел 42210(12)5,где 2, 1, 00,1 - значения м.с.б.ф., формируемых соответственно на выходах старшего, среднего и младшего разрядов сумматора. Очевидно, что модулярные локальные коды функций 00, 11 и 22 многовходового одноразрядного сумматора по модулю пять имеют вид Поскольку при заданных значенияхим.с.б.ф. ФФ однозначно определяется своим модулярным локальным кодом (Ф), то соотношения (10) позволяют записать 1 С учетом (11) каноническое полиномиальное разложение (6) примет вид(12) ФФк 0 к 0 к 21 к 310 к 42. Предлагаемое устройство построено в соответствии с выражением (12), которое и является первообразной (порождающей) функцией. Устройство для вычисления модулярных симметрических булевых функцийпеременных (фиг. 1) работает следующим образом. На информационные входы 71-7 подаются двоичные переменные 1- (в произвольном порядке), на настроечные входы 8-12 - соответственно компоненты к 0-к 4 вектора коэффициентов полиномиального разложения к(Ф) м.с.б.ф. ФФ, значения которой реализуются на выходе 13 устройства. Таким образом, предлагаемое устройство при настройке сигналами из множества (0,1 реализует 22532 модулярных симметрических булевых функцийпеременных для величины модуля 5. Достоинствами устройства для вычисления модулярных симметрических булевых функцийпеременных являются высокое быстродействие, простая конструкция, широкие функциональные возможности. 1. Патент РБ 11888, МПК 06 7/00, 2009. 2. Заявка РБ на выдачу патента 20091871, 2010 (прототип). Национальный центр интеллектуальной собственности. 220034, г. Минск, ул. Козлова, 20.