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

(51) МПК (2006) НАЦИОНАЛЬНЫЙ ЦЕНТР ИНТЕЛЛЕКТУАЛЬНОЙ СОБСТВЕННОСТИ УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ МОДУЛЯРНЫХ СИММЕТРИЧЕСКИХ БУЛЕВЫХ ФУНКЦИЙПЕРЕМЕННЫХ(72) Автор Авгуль Леонид Болеславович(73) Патентообладатель Общество с ограниченной ответственностью Научнотехнический центр ДЭЛС(57) Устройство для вычисления модулярных симметрических булевых функцийпеременных, содержащее первый, второй и третий элементы 2-2 И-2 ИЛИ,- 2, где 3, 4, 5,число переменных реализуемых функций, группы элементов 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 ИЛИ, четвертый вход которого соединен с 11758 1 2009.04.30 выходом третьего элемента 2-2 И-2 ИЛИ первой группы, выход (2)-го, где 1,2 ,элемента НЕ соединен с первым входом -го, где 1, 2, 3, элемента 2-2 И-2 ИЛИ -й группы, второй вход которого соединен с (2)-м информационным входом устройства и входом (2)-го элемента НЕ, выход первого элемента 2-2 И-2 ИЛИ (1)-й, где 1,3 ,группы соединен с третьим входом первого элемента 2-2 И-2 ИЛИ -й группы, выход второго элемента 2-2 И-2 ИЛИ (1)-й группы соединен с третьим входом второго элемента 2-2 И-2 ИЛИ -й группы и четвертым входом первого элемента 2-2 И-2 ИЛИ -й группы, выход третьего элемента 2-2 И-2 ИЛИ (1)-й группы соединен с третьим входом третьего элемента 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 ИЛИ (1)-й группы соединен с четвертым входом третьего элемента 2-2 И 2 ИЛИ -й группы, первый настроечный вход устройства соединен с четвертым входом третьего элемента 2-2 И-2 ИЛИ ( - 2)-й группы. Изобретение относится к вычислительной технике и микроэлектронике и может быть использовано для построения широкого класса цифровых устройств. Известно устройство для вычисления симметрических булевых функцийпеременных, содержащее -входовый одноразрядный сумматор и (1) - канальный мультиплексор 1. Устройство реализует симметрические булевы функциипеременных, включая модулярные симметрические булевы функции. Недостатком устройства является высокая конструктивная сложность. Наиболее близким по конструкции и функциональным возможностям техническим решением к предлагаемому является устройство для вычисления симметрических булевых функций, содержащеегрупп элементов 2-2 И-2 ИЛИ,элементов НЕ,информационных входов,1 настроечных входов и один выход 2. Устройство реализует симметрические (в том числе и модулярные симметрические) булевы функциипеременных. Недостатком известного устройства также является высокая конструктивная сложность. Изобретение направлено на решение задачи упрощения устройства при вычислении модулярных симметрических булевых функцийпеременных. Названный технический результат достигается путем изменения межсоединений логических элементов в схеме устройства. Устройство для вычисления модулярных симметрических булевых функцийпеременных содержит первый, второй и третий элементы 2-2 И-2 ИЛИ, -2, где 3, 4, 5,число переменных реализуемых функций, группы элементов 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 11758 1 2009.04.30 четвертый вход соединен с выходом второго элемента 2-2 И-2 ИЛИ первой группы и третьим входом третьего элемента 2-2 И-2 ИЛИ, четвертый вход которого соединен с выходом третьего элемента 2-2 И-2 ИЛИ первой группы. Выход (2)-го, где 1,2 , элемента НЕ соединен с первым входом -го, где 1, 2, 3, элемента 2-2 И-2 ИЛИ -й группы,второй вход которого соединен с (2)-м информационным входом устройства и входом(2)-го элемента НЕ. Выход первого элемента 2-2 И-2 ИЛИ (1)-й, где 1,3 , группы соединен с третьим входом первого элемента 2-2 И-2 ИЛИ -й группы. Выход второго элемента 2-2 И-2 ИЛИ (1)-й группы соединен с третьим входом второго элемента 2-2 И 2 ИЛИ -й группы и четвертым входом первого элемента 2-2 И-2 ИЛИ -й группы. Выход третьего элемента 2-2 И-2 ИЛИ (1)-й группы соединен с третьим входом третьего элемента 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 ИЛИ (1)-й группы соединен с четвертым входом третьего элемента 2-2 И-2 ИЛИ -й группы, а первый настроечный вход устройства соединен с четвертым входом третьего элемента 2-2 И-2 ИЛИ ( - 2)-й группы. На фиг. 1 представлена схема устройства для вычисления модулярных симметрических булевых функцийпеременных при 8. Устройство содержит 3-321 элемент 2-2 И-2 ИЛИ 1-21 (первый элемент 2-2 И-2 ИЛИ 1,второй элемент 2-2 И-2 ИЛИ 2, третий элемент 2-2 И-2 ИЛИ 3, три элемента 2-2 И-2 ИЛИ первой группы 16, 17 и 18, три элемента 2-2 И-2 ИЛИ второй группы 13, 14 и 15, три элемента 2-2 И-2 ИЛИ третьей группы 10, 11 и 12, три элемента 2-2 И-2 ИЛИ четвертой группы 7, 8 и 9, три элемента 2-2 И-2 ИЛИ пятой группы 4, 5 и 6, три элемента 2-2 И-2 ИЛИ шестой группы 1, 2 и 3),8 элементов НЕ 22-29,8 информационных входов 30-37, три настроечных входа 38, 39 и 40, выход 41. Поясним принцип построения и работы устройства для вычисления модулярных симметрических булевых функцийпеременных. Обозначим(, , , ) - некоторый кортеж длины , содержащий только элементы 0, 1, и 0. Булева функция- ,(х 1, х 2, , х), называется симметрической (с.б.ф.), если она симметрична относительно любой пары переменных из . С.б.ф.однозначно определяется своим локальным кодом Таким образом, вес двоичной кодовой комбинации 1 х 2 однозначно определяет значение с.б.ф.на данном наборе переменных из . В классе симметрических булевых функций выделяется подкласс так называемых модулярных с.б.ф. (м. с.б.ф.). Определение. С.б.ф. ФФ(Х),(х 1, х 2, , х), называется модулярной, если ее значение на любом наборе переменных изоднозначно определяется весом(12)двоичной кодовой комбинации по модулю ,(3), 0, 0,. В дальнейшем рассматриваем м.с.б.ф. ФФ только для величины модуля 3. Из (1) и (2) непосредственно следует, что при выполнении условия (3) в локальном коде (Ф)(0, 1, , ) м.с.б.ф. ФФ(Х) элементы. Тогда локальный код м.с.б.ф. ФФ(Х) можно представить в виде где(1)/3. Принимая во внимание (4), м.с.б.ф. ФФ(Х) можно задавать трехразрядным модулярным локальным кодом Один и тот же модулярный локальный код (Ф) вида (5) могут иметь м.с.б.ф., зависящие от различного числапеременных. В классе с.б.ф.переменных количество (2238) различных м.с.б.ф. определяется только величиной модуля 3 и не зависит от . Пусть ФФ,(1, 2, , ), - некоторая м.с.б.ф.переменных, заданная своим модулярным локальным кодом (Ф)(0, 1, 2). М.с.б.ф. ФФ допускает дизъюнктивное разложение по некоторой переменной ,1, вида Ф 01 где 0 и 1 - остаточные м.с.б.ф. от- 1 переменной. Модулярные локальные коды м.с.б.ф. 0 и 1 определяются из кода (Ф) В свою очередь к м.с.б.ф. 0 и 1 также можно применить разложение вида (6) и так далее, вплоть до получения вырожденных остаточных функций (констант нуля или единицы), которыми будут являться элементы модулярного локального кода (Ф). Пример. Пусть 5 и 3. Выполним последовательное дизъюнктивное разложение(6) м.с.б.ф. ФФ, заданной своим модулярным локальным кодом (Ф)(0, 1, 2), по переменным х 1, х 2, , х 5 11758 1 2009.04.30 Предлагаемое устройство строится на основе дизъюнктивного разложения (6) м.с.б.ф ФФ(Х) последовательно по всем переменным х 1, х 2, , х и группирования тождественных остаточных функций на каждом уровне разложения с учетом их модулярных локальных кодов (7). При этом вектором настройки устройства на реализацию конкретной м.с.б.ф ФФ является ее модулярный локальный код (Ф). Так, например, структура устройства при 5 описывается выражением (8). В общем случае устройство при настройке сигналами из множества 0, 1 реализует восемь модулярных симметрических булевых функцийпеременных для величины модуля 3. Устройство для вычисления модулярных симметрических булевых функций при 8(фиг. 1) работает следующим образом. На информационные входы 30-37 подаются двоичные переменные х 1, х 2, , х 8 (в произвольном порядке), на настроечные входы 38, 39 и 40 - соответственно компоненты 0,и 2 модулярного локального кода (Ф)(0, 1, 2) м.с.б.ф. ФФ(Х)(х 1, х 2, , х 8), значения которой реализуются на выходе 41 устройства. Локальные коды (Ф)(0, 1, 2, 3, 4, 5, 6, 7, 8) м.с.б.ф. ФФ, реализуемых устройством (фиг. 1), представлены в таблице (фиг. 2). Обозначим- сигнал на выходе -го элемента 2-2 И-2 ИЛИ -й группы,1,- 21, 2, 3 . Тогда структура предлагаемого устройства может быть описана следующей системой рекуррентных соотношений Достоинствами устройства для вычисления модулярных симметрических булевых функцийпеременных являются простая конструкция, однородная и регулярная структура. 11758 1 2009.04.30 Таблица локальных кодов м.с.б.ф. ФФ(Х) при 8,3 Национальный центр интеллектуальной собственности. 220034, г. Минск, ул. Козлова, 20.