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

(51) МПК (2009) НАЦИОНАЛЬНЫЙ ЦЕНТР ИНТЕЛЛЕКТУАЛЬНОЙ СОБСТВЕННОСТИ УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ ЧАСТИЧНО СИММЕТРИЧЕСКИХ БУЛЕВЫХ ФУНКЦИЙ(72) Авторы Авгуль Леонид Болеславович Кряжев Виктор Иванович Терешко Сергей Михайлович Усов Геннадий Иванович(73) Патентообладатель Общество с ограниченной ответственностью Научнотехнический центр ДЭЛС(57) Устройство для вычисления частично симметрических булевых функций, содержащее три элемента сложения по модулю два, три элемента ИЛИ-НЕ и сорок элементов И-НЕ,выход первого из которых соединен с выходом устройства, а -й вход, где 1, 2, 3, соединен с выходом (1)-го элемента И-НЕ, -й вход которого, где 1, 2, 3, соединен с 13044 1 2010.04.30 выходом (31)-го элемента И-НЕ, -й информационный вход устройства, где 1, 2,первой группы соединен с (3)-м входом четвертого элемента И-НЕ, -м входом первого элемента ИЛИ-НЕ и -м входом первого элемента сложения по модулю два, выход которого соединен с четвертым входом третьего элемента И-НЕ, выход первого элемента ИЛИ-НЕ соединен с четвертым входом второго элемента И-НЕ, -й информационный вход устройства второй группы соединен с -м входом (34)-го элемента И-НЕ, -м входом второго элемента ИЛИ-НЕ и -м входом второго элемента сложения по модулю два,выход которого соединен с первым входом (33)-го элемента И-НЕ, выход второго элемента ИЛИ-НЕ соединен с первым входом (32)-го элемента И-НЕ, первый вход(13)-го элемента И-НЕ, где 1, 27 , соединен с -м настроечным входом устройства, -й информационный вход третьей группы которого соединен с (1)-м входом (313) элемента И-НЕ, где 1, 9 , -м входом третьего элемента ИЛИ-НЕ и -м входом третьего элемента сложения по модулю два, выход которого соединен со вторым входом (312)го элемента И-НЕ, выход третьего элемента ИЛИ-НЕ соединен со вторым входом(310)-го элемента И-НЕ, (2)-й вход седьмого элемента И-НЕ соединен с выходом (19)-го элемента И-НЕ, (1)-й вход (7)-го элемента И-НЕ соединен с выходом(319)-го элемента И-НЕ, (2)-й вход десятого элемента И-НЕ соединен с выходом(328)-го элемента И-НЕ, (2)-й вход тринадцатого элемента И-НЕ соединен с выходом (37)-го элемента И-НЕ. Изобретение относится к вычислительной технике и микроэлектронике и может быть использовано для построения широкого класса цифровых устройств. Известно устройство для вычисления симметрических булевых функций, содержащеегрупп элементов 2-2 И-2 ИЛИ,элементов НЕ,информационных входов,1 настроечных входов и один выход 1. Недостатком устройства являются ограниченные функциональные возможности, поскольку оно не реализует частично симметрические булевы функции. Наиболее близким по конструкции и функциональным возможностям техническим решением к предлагаемому является устройство для вычисления частично симметрических(бисимметрических) булевых функций четырех переменных, содержащее два элемента ИЛИ-НЕ, два элемента сложения по модулю два и тринадцать элементов И-НЕ 2. Недостатком известного устройства для вычисления частично симметрических булевых функций также являются ограниченные функциональные возможности, так как устройство реализует функции, зависящие только от двух кортежей попарно симметрических переменных (бисимметрические булевы функции). Изобретение направлено на решение задачи расширения функциональных возможностей устройства для вычисления частично симметрических булевых функций за счет реализации функций, зависящих от трех кортежей попарно симметрических переменных. Названный технический результат достигается путем введения в состав устройства дополнительно элемента ИЛИ-НЕ, элемента сложения по модулю два и двадцати семи элементов И-НЕ. Устройство для вычисления частично симметрических булевых функций содержит два элемента сложения по модулю два, два элемента ИЛИ-НЕ и тринадцать элементов И-НЕ. Выход первого элемента И-НЕ соединен с выходом устройства, а -й вход, где 1,2,3,соединен с выходом (1)-го элемента И-НЕ, -й вход которого, где 1,2,3, соединен с выходом (31)-го элемента И-НЕ. 2 13044 1 2010.04.30 В устройстве -й информационный вход, где 1,2, первой группы соединен с (3)-м входом четвертого элемента И-НЕ, -м входом первого элемента ИЛИ-НЕ и -м входом первого элемента сложения по модулю два, выход которого соединен с четвертым входом третьего элемента И-НЕ. Выход первого элемента ИЛИ-НЕ соединен с четвертым входом второго элемента И-НЕ. В устройстве -й информационный вход второй группы соединен с -м входом (34)-го элемента И-НЕ, -м входом второго элемента ИЛИ-НЕ и -м входом второго элемента сложения по модулю два, выход которого соединен с первым входом (33)-го элемента И-НЕ. Выход второго элемента ИЛИ-НЕ соединен с первым входом (32)-го элемента И-НЕ. Устройство содержит третий элемент ИЛИ-НЕ, третий элемент сложения по модулю два и элементы И-НЕ с четырнадцатого по сороковой. Первый вход (13)-го элемента И-НЕ, где 1,27, соединен с -м настроечным входом устройства. В устройстве -й информационный вход третьей группы соединен с (1)-м входом(313) элемента И-НЕ, где 1,9, -м входом третьего элемента ИЛИ-НЕ и -м входом третьего элемента сложения по модулю два, выход которого соединен со вторым входом(312)-го элемента И-НЕ. Выход третьего элемента ИЛИ-НЕ соединен со вторым входом (311)-го элемента И-НЕ. При этом (1)-й вход (4)-го элемента И-НЕ соединен с выходом (310)-го элемента И-НЕ, (2)-й вход седьмого элемента И-НЕ соединен с выходом (19)-го элемента И-НЕ, (1)-й вход (7)-го элемента И-НЕ соединен с выходом (319)-го элемента И-НЕ, (2)-й вход десятого элемента И-НЕ соединен с выходом (28)-го элемента И-НЕ, (1)-й вход (10)-го элемента И-НЕ соединен с выходом (328)-го элемента И-НЕ, (2)-й вход тринадцатого элемента И-НЕ соединен с выходом (37)-го элемента И-НЕ. На фигуре представлена схема устройства для вычисления частично симметрических булевых функций. Устройство содержит элементы И-НЕ с первого по сороковой 1-40, первый 41, второй 42 и третий 43 элементы ИЛИ-НЕ, первый 44, второй 45 и третий 46 элементы сложения по модулю два, два информационных входа первой группы 47 и 48, два информационных входа второй группы 49 и 50, два информационных входа третьей группы 51 и 52, двадцать семь настроечных входов 53-79 и выход 80. Поясним принцип работы устройства для вычисления частично симметрических булевых функций. Обозначим( ,) - некоторый кортеж длины , содержащий только элементы 0,1, и 0. Булева функция ,(,2) называется симметрической (с.б.ф.), если она симметрична относительно любой пары переменных из . С.б.ф.однозначно определяется своим локальным кодом(0,1), где 1 ,00. Нетривиальная частичная симметрия индуцирует разбиение вектора переменных(1,2) частично симметрической булевой функции (ч.с.б.ф.)накортежей 1,2 1. При этомсимметрична относительно любой пары переменных, принадлежащих одному и тому же кортежу , 1. Тогда число классов эквивалентности ч.с.б.ф.определяется выражением Каждый класс эквивалентности характеризуется вектором(,2),0,1 1. Локальный кодч.с.б.ф.есть двоичный вектор длины , каждая компонента которого равна значениюна соответствующем классе эквивалентности наборов значений ее аргументов. Упорядочивая векторы , представимв виде где булева константаудовлетворяющих условию равна значению ч.с.б.ф.на наборах переменных из ,Предлагаемое устройство реализует ч.с.б.ф.(1,2,3) шести переменных при 1232 (3) и 1(1,2), 2(3,4), 3(5,6). В этом случае локальный код (2) примет вид(000,001,002,010, 011, 012, 020, 021, 022,100, 101, 102, 110, 111, 112, 120, 121, 122,(3) 200 201 202 210 211 212 220 221 222,,,,,,,,). Вектором настройки устройства на реализацию конкретной ч.с.б.ф. является ее локальный код (3). Поскольку длиналокального кода , определяемая формулой (1), равна(11)(21)(31)27, то предлагаемое устройство реализует 2227 ч.с.б.ф. шести переменных при настройке сигналами из множества 0,1. Устройство для вычисления частично симметрических булевых функций работает следующим образом. На информационные входы 47 и 48 первой группы поступают двоичные переменные 1 и 2 (в произвольном порядке), на информационные входы 49 и 50 второй группы - двоичные переменные 3 и 4 (в произвольном порядке), на информационные входы 51 и 52 третьей группы - двоичные переменные 5 и 6 (в произвольном порядке). На настроечные входы 53,5479 подаются соответственно компоненты 000,001222 локального кода. На выходе 80 реализуется ч.с.б.ф.(1,2,3), определяемая своим локальным кодом . Найдем сигналы настройки предлагаемого устройства на реализацию ч.с.б.ф.( )(1 ,2 ,3 )123456123 456(12 ) 3456(12 ) 3 4 ( 56 )1 2 ( 34 ) 56 . Очевидно, локальный код (3) рассматриваемой ч.с.б.ф.имеет вид(1,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,1,0,0,0,0,1,0,0,0,0,0). Следовательно, для реализации ч.с.б.ф. необходимо подать сигналы логической единицы на настроечные входы 53, 58, 64, 69 и 74 сигнал логического нуля - на настроечные входы 54-57, 59-63, 65-68, 70-73 и 75-79. Отметим, что устройство реализует также и все симметрические булевы функции шести переменных. В этом случае на информационные входы 47-52 устройства подаются (в произвольном порядке) переменные(1,26) с.б.ф.. Сигналы настройки 1 23 , подаваемые на настроечные входы 53-79 устройства, находятся из локального кода(0,16) реализуемой с.б.ф. по правилу 4 13044 1 2010.04.301 23123 ,где 10,1,2, 20,1,2, 30,1,2. Следовательно, вектор настройки устройства при реализации с.б.ф.примет вид( )(0 ,1 ,2 , 1 ,2 , 3 ,2 , 3 ,4 , 1 ,2 , 3 ,2 , 3 ,4 , 3 ,4 ,5 ,2 , 3 ,4 , 3 ,4 , 5 ,4 , 5 ,6 ). Достоинствами устройства для вычисления частично симметрических булевых функций являются простая конструкция, высокое быстродействие, широкие функциональные возможности. Источники информации Национальный центр интеллектуальной собственности. 220034, г. Минск, ул. Козлова, 20.