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

(51) МПК (2006) НАЦИОНАЛЬНЫЙ ЦЕНТР ИНТЕЛЛЕКТУАЛЬНОЙ СОБСТВЕННОСТИ УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ МОДУЛЯРНЫХ СИММЕТРИЧЕСКИХ БУЛЕВЫХ ФУНКЦИЙПЕРЕМЕННЫХ(72) Авторы Авгуль Леонид Болеславович Булаш Юрий Леонидович Курносенко Сергей Васильевич Терешко Сергей Михайлович(73) Патентообладатель Общество с ограниченной ответственностью Научнотехнический центр ДЭЛС(57) Устройство для вычисления модулярных симметрических булевых функцийпеременных, где 6, 7, 8, - число переменных реализуемых функций, содержащееэлементов НЕ игрупп элементов 2-2 И-2 ИЛИ, при этом первая группа содержит один элемент 2-2 И-2 ИЛИ, вторая группа - два элемента 2-2 И-2 ИЛИ, третья группа - три элемента 2-2 И-2 ИЛИ, четвертая группа - четыре элемента 2-2 И-2 ИЛИ, (4)-я группа - пять элементов 2-2 И-2 ИЛИ, где 1,4 , выход первого элемента НЕ соединен с первым входом элемента 2-2 И-2 ИЛИ первой группы, второй вход которого соединен с первым информационным входом устройства и входом первого элемента НЕ, а его третий вход 11888 1 2009.04.30 соединен с выходом первого элемента 2-2 И-2 ИЛИ второй группы, а его четвертый вход соединен с выходом второго элемента 2-2 И-2 ИЛИ второй группы, а его выход соединен с выходом устройства, выход второго элемента НЕ соединен с первым входом первого элемента 2-2 И-2 ИЛИ второй группы и первым входом второго элемента 2-2 И-2 ИЛИ второй группы, второй вход которого соединен со вторым входом первого элемента 2-2 И-2 ИЛИ второй группы, вторым информационным входом устройства и входом второго элемента НЕ, выход третьего элемента НЕ соединен с первым входом первого элемента 2-2 И-2 ИЛИ третьей группы, первым входом второго элемента 2-2 И-2 ИЛИ третьей группы и первым входом третьего элемента 2-2 И-2 ИЛИ третьей группы, второй вход которого соединен со вторым входом первого элемента 2-2 И-2 ИЛИ третьей группы, вторым входом второго элемента 2-2 И-2 ИЛИ третьей группы, третьим информационным входом устройства и входом третьего элемента НЕ, выход первого элемента 2-2 И-2 ИЛИ третьей группы соединен с третьим входом первого элемента 2-2 И-2 ИЛИ второй группы, четвертый вход которого соединен с выходом второго элемента 2-2 И-2 ИЛИ третьей группы и третьим входом второго элемента 2-2 И-2 ИЛИ второй группы, четвертый вход которого соединен с выходом третьего элемента 2-2 И-2 ИЛИ третьей группы, выход четвертого элемента НЕ соединен с первым входом первого элемента 2-2 И-2 ИЛИ четвертой группы, первым входом второго элемента 2-2 И-2 ИЛИ четвертой группы, первым входом третьего элемента 2-2 И 2 ИЛИ четвертой группы и первым входом четвертого элемента 2-2 И-2 ИЛИ четвертой группы, второй вход которого соединен со вторым входом первого элемента 2-2 И-2 ИЛИ четвертой группы, вторым входом второго элемента 2-2 И-2 ИЛИ четвертой группы, вторым входом третьего элемента 2-2 И-2 ИЛИ четвертой группы, четвертым информационным входом устройства и входом четвертого элемента НЕ, выход первого элемента 2-2 И 2 ИЛИ четвертой группы соединен с третьим входом первого элемента 2-2 И-2 ИЛИ третьей группы, четвертый вход которого соединен с выходом второго элемента 2-2 И-2 ИЛИ четвертой группы и третьим входом второго элемента 2-2 И-2 ИЛИ третьей группы, четвертый вход которого соединен с выходом третьего элемента 2-2 И-2 ИЛИ четвертой группы и третьим входом третьего элемента 2-2 И-2 ИЛИ третьей группы, четвертый вход которого соединен с выходом четвертого элемента 2-2 И-2 ИЛИ четвертой группы, выход(4)-го элемента НЕ соединен с первым входом -го, где 1,5 , элемента 2-2 И-2 ИЛИ(4)-й группы, второй вход которого соединен с (4)-м информационным входом устройства и входом (4)-го элемента НЕ, выход первого элемента 2-2 И-2 ИЛИ пятой группы соединен с третьим входом первого элемента 2-2 И-2 ИЛИ четвертой группы, выход(1)-го элемента 2-2 И-2 ИЛИ четвертой группы и четвертым входом -го элемента 2-2 И 2 ИЛИ четвертой группы, выход пятого элемента 2-2 И-2 ИЛИ пятой группы соединен с четвертым входом четвертого элемента 2-2 И-2 ИЛИ четвертой группы, выход первого элемента 2-2 И-2 ИЛИ (5)-й группы, где 1,5 , соединен с третьим входом первого элемента 2-2 И-2 ИЛИ (4)-й группы, выход (1)-го элемента 2-2 И-2 ИЛИ (5)-й группы, где 1, 2, 3, 4, соединен с третьим входом (1)-го элемента 2-2 И-2 ИЛИ(4)-й группы и четвертым входом -го элемента 2-2 И-2 ИЛИ (4)-й группы, первый настроечный вход устройства соединен с третьим входом первого элемента 2-2 И-2 ИЛИ -й группы, (1)-й настроечный вход устройства соединен с третьим входом (1)-го элемента 2-2 И-2 ИЛИ -й группы и четвертым входом -го элемента 2-2 И-2 ИЛИ -й группы, отличающееся тем, что выход первого элемента 2-2 И-2 ИЛИ (5)-й группы соединен с четвертым входом пятого элемента 2-2 И-2 ИЛИ (4)-й группы, первый настроечный вход устройства соединен с четвертым входом пятого элемента 2-2 И-2 ИЛИ -й группы. Изобретение относится к вычислительной технике и микроэлектронике и может быть использовано для построения широкого класса цифровых устройств. Известно устройство для вычисления симметрических булевых функцийпеременных, содержащее -входовый одноразрядный сумматор и (1)-канальный мультиплек 2 11888 1 2009.04.30 сор 1. Устройство реализует симметрические булевы функциипеременных, включая модулярные симметрические булевы функции. Недостатком устройства является высокая конструктивная сложность. Наиболее близким по конструкции и функциональным возможностям техническим решением к предлагаемому является устройство для вычисления симметрических булевых функций, содержащеегрупп элементов 2-2 И-2 ИЛИ,элементов НЕ,информационных входов,настроечных входов и один выход 2. Устройство реализует симметрические (в том числе и модулярные симметрические) булевы функциипеременных. Недостатком известного устройства также является высокая конструктивная сложность. Изобретение направлено на решение задачи упрощения конструкции устройства при вычислении модулярных симметрических булевых функцийпеременных. Названный технический результат достигается путем изменения межсоединений логических элементов в схеме устройства. Устройство для вычисления модулярных симметрических булевых функцийпеременных, где 6, 7, 8, - число переменных реализуемых функций, содержитэлементов НЕ игрупп элементов 2-2 И-2 ИЛИ. При этом первая группа содержит один элемент 2-2 И-2 ИЛИ, вторая группа - два элемента 2-2 И-2 ИЛИ, третья группа - три элемента 2-2 И 2 ИЛИ, четвертая группа - четыре элемента 2-2 И-2 ИЛИ, (4)-я группа - пять элементов 2-2 И-2 ИЛИ, где 1,4 . Выход первого элемента НЕ соединен с первым входом элемента 2-2 И-2 ИЛИ первой группы, второй вход которого соединен с первым информационным входом устройства и входом первого элемента НЕ, третий вход соединен с выходом первого элемента 2-2 И 2 ИЛИ второй группы, четвертый вход соединен с выходом второго элемента 2-2 И-2 ИЛИ второй группы, а выход соединен с выходом устройства. Выход второго элемента НЕ соединен с первым входом первого элемента 2-2 И-2 ИЛИ второй группы и первым входом второго элемента 2-2 И-2 ИЛИ второй группы, второй вход которого соединен со вторым входом первого элемента 2-2 И-2 ИЛИ второй группы,вторым информационным входом устройства и входом второго элемента НЕ. Выход третьего элемента НЕ соединен с первым входом первого элемента 2-2 И-2 ИЛИ третьей группы, первым входом второго элемента 2-2 И-2 ИЛИ третьей группы и первым входом третьего элемента 2-2 И-2 ИЛИ третьей группы, второй вход которого соединен со вторым входом первого элемента 2-2 И-2 ИЛИ третьей группы, вторым входом второго элемента 2-2 И-2 ИЛИ третьей группы, третьим информационным входом устройства и входом третьего элемента НЕ. Выход первого элемента 2-2 И-2 ИЛИ третьей группы соединен с третьим входом первого элемента 2-2 И-2 ИЛИ второй группы, четвертый вход которого соединен с выходом второго элемента 2-2 И-2 ИЛИ третьей группы и третьим входом второго элемента 2-2 И 2 ИЛИ второй группы, четвертый вход которого соединен с выходом третьего элемента 22 И-2 ИЛИ третьей группы. Выход четвертого элемента НЕ соединен с первым входом первого элемента 2-2 И 2 ИЛИ четвертой группы, первым входом второго элемента 2-2 И-2 ИЛИ четвертой группы,первым входом третьего элемента 2-2 И-2 ИЛИ четвертой группы и первым входом четвертого элемента 2-2 И-2 ИЛИ четвертой группы, второй вход которого соединен со вторым входом первого элемента 2-2 И-2 ИЛИ четвертой группы, вторым входом второго элемента 2-2 И-2 ИЛИ четвертой группы, вторым входом третьего элемента 2-2 И-2 ИЛИ четвертой группы, четвертым информационным входом устройства и входом четвертого элемента НЕ. Выход первого элемента 2-2 И-2 ИЛИ четвертой группы соединен с третьим входом первого элемента 2-2 И-2 ИЛИ третьей группы, четвертый вход которого соединен с выходом второго элемента 2-2 И-2 ИЛИ четвертой группы и третьим входом второго элемента 2-2 И-2 ИЛИ третьей группы, четвертый вход которого соединен с выходом третьего элемента 2-2 И-2 ИЛИ четвертой группы и третьим входом третьего элемента 2-2 И-2 ИЛИ 3 11888 1 2009.04.30 третьей группы, четвертый вход которого соединен с выходом четвертого элемента 2-2 И 2 ИЛИ четвертой группы. Выход (4)-го элемента НЕ соединен с первым входом -го, где 1,5 , элемента 22 И-2 ИЛИ (4)-й группы, второй вход которого соединен с (4)-м информационным входом устройства и входом (4)-го элемента НЕ. Выход первого элемента 2-2 И-2 ИЛИ пятой группы соединен с третьим входом первого элемента 2-2 И-2 ИЛИ четвертой группы. Выход (1)-го, где 1, 2, 3, элемента 2-2 И 2 ИЛИ пятой группы соединен с третьим входом (1)-го элемента 2-2 И-2 ИЛИ четвертой группы и четвертым входом -го элемента 2-2 И-2 ИЛИ четвертой группы. Выход пятого элемента 2-2 И-2 ИЛИ пятой группы соединен с четвертым входом четвертого элемента 22 И-2 ИЛИ четвертой группы. Выход первого элемента 2-2 И-2 ИЛИ (5)-й, где 1,5 , группы соединен с третьим входом первого элемента 2-2 И-2 ИЛИ (4)-й группы. Выход (1)-го, где 1, 4 , элемента 2-2 И-2 ИЛИ (5)-й группы соединен с третьим входом (1)-го элемента 2-2 И-2 ИЛИ (4)-й группы и четвертым входом -го элемента 2-2 И-2 ИЛИ (4)-й группы. Первый настроечный вход устройства соединен с третьим входом первого элемента 22 И-2 ИЛИ -й группы, (1)-й настроечный вход устройства соединен с третьим входом-й группы. В отличие от прототипа, выход первого элемента 2-2 И-2 ИЛИ (5)-й группы соединен с четвертым входом пятого элемента 2-2 И-2 ИЛИ (4)-й группы, а первый настроечный вход устройства соединен с четвертым входом пятого элемента 2-2 И-2 ИЛИ -й группы. На фиг. 1 представлена схема устройства для вычисления модулярных симметрических булевых функцийпеременных при 8 и величине модуля р 5. Устройство содержит 8 элементов И 1-8 и 8 групп элементов 2-2 И-2 ИЛИ (один элемент 2-2 И-2 ИЛИ 9 первой группы, два элемента 2-2 И-2 ИЛИ 10 и 11 второй группы,три элемента 2-2 И-2 ИЛИ 12, 13 и 14 третьей группы, четыре элемента 2-2 И-2 ИЛИ 15-18 четвертой группы, пять элементов 2-2 И-2 ИЛИ 19-23 пятой группы, пять элементов 2-2 И 2 ИЛИ 24-28 шестой группы, пять элементов 2-2 И-2 ИЛИ 29-33 седьмой группы и пять элементов 2-2 И-2 ИЛИ 34-38 восьмой группы),8 информационных входов 39-46, р 5 настроечных входов 47-51 и выход 52. Поясним принцип построения и работы устройства для вычисления модулярных симметрических булевых функцийпеременных. Обозначим(,, ,) - некоторый кортеж длины , содержащий только эле менты 0,1, и 0. Булева функция,(1, 2 ), называется симметрической (с.б.ф.), если она симметрична относительно любой пары переменных из . С.б.ф.однозначно определяется своим локальным кодом(0, 1),1 0 где(,),0, . Таким образом, вес двоичной кодовой комбинации 12 однозначно определяет значение с.б.ф.на данном наборе переменных из . В классе симметрических булевых функций выделяется подкласс так называемых модулярных с.б.ф. (м.с.б.ф.). Определение. С.б.ф. ФФ ,(1, 2 ), называется модулярной, если ее значение на любом наборе переменных изоднозначно определяется весом(2)двоичной кодовой комбинации по модулю р, р 11888 1 2009.04.30 В дальнейшем рассматриваем м.с.б.ф. ФФ только для величины модуля 5. Из (1) и (2) непосредственно следует, что при выполнении условия (3) в локальном коде (Ф)(0, 1 ) м.с.б.ф. ФФ элементы. Тогда локальный код м.с.б.ф. ФФ(Х) можно представить в виде где(1)/5. Принимая во внимание (4), м.с.б.ф. ФФ можно задавать пятиразрядным модулярным локальным кодом Один и тот же модулярный локальный код (Ф) вида (5) могут иметь м.с.б.ф., зависящие от различного числапеременных. В классе с.б.ф.переменных количество (2 р 2532) различных м.с.б.ф. определяется только величиной модуля р 5 и не зависит от . Пусть ФФ,(1, 2 ), - некоторая м.с.б.ф.переменных, заданная своим модулярным локальным кодом (Ф)(0, 1, 2, 3, 4). М.с.б.ф. ФФ допускает дизъюнктивное разложение по некоторой переменной ,1, вида(6) Ф 01 ,где 0 и 1 - остаточные м.с.б.ф. от-1 переменной. Модулярные локальные коды м.с.б.ф. 0 и 1 определяются из кода (Ф)(0 )(Ф)( 0 , 1 ,2 , 3 ,4 ) В свою очередь к м.с.б.ф. 0 и 1 также можно применить разложение вида (6) и так далее, вплоть до получения вырожденных остаточных функций (констант нуля или единицы), которыми будут являться элементы модулярного локального кода (Ф). Пример. Пусть 6 и р 5. Выполним последовательное дизъюнктивное разложение (6) м.с.б.ф. ФФ(Х), заданной своим модулярным локальным кодом (Ф)(0, 1, 2, 3, 4),по переменным х 1, 2 6 Ф 1 (2 (3 (4 (5 (6 06 1 )5 (616 2 11888 1 2009.04.30 Предлагаемое устройство строится на основе дизъюнктивного разложения (6) м.с.б.ф ФФ последовательно по всем переменным 1, 2 и группирования тождественных остаточных функций на каждом уровне разложения с учетом их модулярных локальных кодов (7). При этом вектором настройки устройства на реализацию конкретной м.с.б.ф ФФ является ее модулярный локальный код (Ф). Так, например, структура устройства при 6 описывается выражением (8). В общем случае предлагаемое устройство при настройке сигналами из множества 0,1 реализует тридцать две модулярные симметрические булевы функциипеременных для величины модуля р 5. Устройство для вычисления модулярных симметрических булевых функций при 8(фиг. 1) работает следующим образом. На информационные входы 39-46 подаются двоичные переменные 1-8 (в произвольном порядке), на настроечные входы 47-51 - соответственно компоненты 0-4 модулярного локального кода (Ф)(0, 1, 2, 3, 4) м.с.б.ф. ФФФ(1 2 8), значения которой реализуются на выходе 52 устройства. Локальные коды (Ф)(0, 1, 2, 3, 4, 5, 6, 7, 8) м.с.б.ф. ФФ, реализуемых устройством (фиг. 1), представлены в таблице (фиг. 2). Обозначим- сигнал на выходе -го элемента 2-2 И-2 ИЛИ -й группы,1,15. Тогда структура устройства может быть описана следующей системой рекуррентных соотношений 2 Достоинствами предлагаемого устройства для вычисления модулярных симметрических булевых функцийпеременных являются простая конструкция, однородная и регулярная структура. Источники информации 1. А.с. СССР 1833860, МПК 06 7/00, 1993. 2. А.с. СССР 1742811, МПК 06 7/00, 1992 (прототип). 11888 1 2009.04.30 Таблица локальных кодов м.с.б.ф. ФФ при 8 и р 5 Фиг. 2 Национальный центр интеллектуальной собственности. 220034, г. Минск, ул. Козлова, 20. 7