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

ГОСУДАРСТВЕННЫЙ ПАТЕНТНЫЙ КОМИТЕТ РЕСПУБЛИКИ БЕЛАРУСЬ УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ СИММЕТРИЧЕСКИХ БУЛЕВЫХ ФУНКЦИЙ(71) Заявитель Белорусский государственный университет(73) Патентообладатель Белорусский государственный университет(57) Устройство для вычисления симметрических булевых функций, содержащее элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, элемент И и элемент ИЛИ, входы которого с первого по четвертый соединены соответственно с первым по четвертый информационными входами устройства, первый настроечный вход которого соединен с первым входом элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, а второй настроечный вход соединен с первым входом элемента И, выход которого соединен со вторым входом элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, выход которого является выходом устройства, отличающееся тем, что дополнительно введены мажоритарный элемент с порогом два и мажоритарный элемент с порогом пять, входы которого с первого по четвертый соединены соответственно с первым по четвертый входами мажоритарного элемента с порогом два, со вторым по пятый входами элемента И и с первым по четвертый информационными входами устройства, третий настроечный вход которого соединен с пятым и шестым входами мажоритарного элемента с порогом два, четвертый настроечный вход соединен с пятым и шестым входами мажоритарного элемента с порогом пять, а пятый настроечный вход - с пятым входом элемента ИЛИ, выход которого соединен с третьим входом элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, четвертый вход которого соединен с выходом мажоритарного элемента с порогом два, а пятый вход - с выходом мажоритарного элемента с порогом пять. Изобретение относится к области вычислительной техники и микроэлектроники и предназначено для реализации симметрических булевых функций четырех переменных. 2119 1 Известно устройство для вычисления симметрических булевых функций четырех переменных, содержащее четыре элемента ИЛИ-, мажоритарные элементы с порогами два и три, четыре элемента И, четыре информационных и пять настроечных входов, один выход 1. Сложность устройства (по числу входов логических элементов) равна 34, а быстродействие, определяемое глубиной схемы, составляет 3, где- задержка на вентиль. Недостатком устройства является высокая конструктивная сложность и низкое быстродействие. Наиболее близким по функциональным возможностям и конструкции техническим решением к предлагаемому является устройство для вычисления симметрических булевых функций четырех переменных, содержащее два элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, мажоритарный элемент с порогом три, четыре элемента И, элемент ИЛИ, четыре информационных и пять настроечных входов, один выход 2. Сложность устройства равна 26, а быстродействие - 3. Недостатком известного устройства для вычисления симметрических нулевых функций является низкое быстродействие. Изобретение направлено на решение технической задачи повышения быстродействия устройства для вычисления симметрических булевых функций четырех переменных. Устройство для вычисления симметрических булевых функций содержит элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, элемент И и элемент ИЛИ, входы которого с первого по четвертый соединены соответственно с первым по четвертый информационными входами устройства. Первый настроечный вход устройства соединен с первым входом элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, а второй настроечный вход соединен с первым входом элемента И, выход которого соединен со вторым входом элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, выход которого является выходом устройства. В отличие от прототипа в устройство дополнительно введены мажоритарный элемент с порогом два и мажоритарный элемент с порогом пять. Входы мажоритарного элемента с порогом пять с первого по четвертый соединены соответственно с первым по четвертый входами мажоритарного элемента с порогом два,со вторым по пятый входами элемента И и с первым по четвертый информационными входами устройства. Третий настроечный вход устройства соединен с пятым и шестым входами мажоритарного элемента с порогом два, четвертый настроечный вход соединен с пятым и шестым входами мажоритарного элемента с порогом пять, а пятый настроечный вход - с пятым входом элемента ИЛИ. Выход элемента ИЛИ соединен с третьим входом элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, четвертый вход которого соединен с выходом мажоритарного элемента с порогом два, а пятый вход - с выходом мажоритарного элемента с порогом пять. Основной технический результат изобретения заключается в повышении быстродействия устройства для вычисления симметрических булевых функций четырех переменных. Названный технический результат достигается путем дополнительного введения мажоритарного элемента с порогом два и мажоритарного элемента с порогом пять, а также изменением межсоединений элементов в схеме устройства. На чертеже представлена схема устройства для вычисления симметрических булевых функций четырех переменных. Устройство для вычисления симметрических булевых функций содержит мажоритарный элемент с порогом два 1, элемент ИЛИ 2, мажоритарный элемент с порогом пять 3, элемент И 4, элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА 5, четыре информационных входов 6, 7, 8 и 9, пять настроечных входов 10, 11, 12, 13 и 14,выход 15. Устройство для вычисления симметрических булевых функций работает следующим образом. На информационные входы 6, 7, 8 и 9 поступают двоичные переменные х 1, х 2, х 3 и х 4 (в произвольном порядке) на настроечные входы 10, 11, 12, 13 и 14 - сигналы настройки 1, 2, 3, 4 и 5, значения которых принадлежат множеству 0,1. На выходе 15 реализуется симметрическая булева функция (х 1, х 2, х 3, х 4), определяемая вектором настройки (1, 2, 3, 4, 5). Первообразная устройства для вычисления симметрических булевых функций четырех переменных имеет следующий вид(х 1, х 2, х 3, х 4, 1, 2, 3, 4, 5) 1(2 х 1 х 2 х 1 х 3 х 1 х 4 х 2 х 3 х 2 х 4 х 3 х 4)(3 х 1 х 2 х 3 х 4)4 (х 1 х 2 х 3 х 1 х 2 х 4 х 1 х 3 х 4 х 2 х 3 х 4)5 х 1 х 2 х 3 х 4. Поясним алгоритм настройки. Известно (см. Лупанов О.Б. Об одном подходе к синтезу управляющих систем принципе локального кодирования // Проблемы кибернетики. - М. Наука, 1965, вып.14), что произвольная симметрическая булева функцияпеременных (1, х 2, , х) однозначно определяется (1)-разрядным двоичным кодом (0, 1, , ), где- значение функциина (любом) наборе переменных 1, х 2, , х, содержащем ровноединиц (0). 2119 1 Тогда значения сигналов настройки устройства на реализацию некоторой симметрической булевой функции четырех переменных (1, х 2, 3, х 4), заданной двоичным кодом (0, 1, 2, 3, 4), определяются следующим образом 12, 2121, 3011, 423 и 534. Пример. Найти сигналы настройки устройства на реализацию симметрической булевой функции (1,х 2, 3, х 4), заданной посредством дизъюнктивной нормальной формы х 1 х 2 х 1 х 3 х 1 х 4 х 2 х 3 х 2 х 4 х 3 х 4 Очевидно, что здесь. (0, 1, 2, 3, 4)(1, 0, 1, 1, 1). Тогда сигналы настройки устройства определяются согласно приведенным выше формулам следующим образом 11, 20110, 31010, 4110, 5110. Следовательно, сигнал логического нуля должен быть подан на настроечные входы 11, 12, 13 и 14, а сигнал логической единицы - на настроечный вход 10. Достоинством устройства является высокое быстродействие, которое составляет 2, где- задержка на вентиль (быстродействие устройства-прототипа равно 3). Дополнительным достоинством является низкая конструктивная сложность устройства, которая (по числу входов логических элементов) составляет 27, в то время как сложность устройства-прототипа равна 26. Заказ 0063 Тираж 20 экз. Государственный патентный комитет Республики Беларусь. 220072, г. Минск, проспект Ф. Скорины, 66.