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

ГОСУДАРСТВЕННЫЙ ПАТЕНТНЫЙ КОМИТЕТ РЕСПУБЛИКИ БЕЛАРУСЬ УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ ФУНДАМЕНТАЛЬНЫХ СИММЕТРИЧЕСКИХ БУЛЕВЫХ ФУНКЦИЙ(71) Заявитель Белорусский государственный университет(73) Патентообладатель Белорусский государственный университет(57) Устройство для вычисления фундаментальных симметрических булевых функций, содержащее элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, входы которого с первого по четвертый соединены с первым по четвертый информационными входами устройства, первый настроечный вход которого соединен с пятым входом элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, отличающееся тем, что содержит элемент равнозначности,мажоритарный элемент с порогом три и мажоритарный элемент с порогом пять, входы которого с первого по четвертый соединены соответственно с первым по четвертый входами мажоритарного элемента с порогом три и с первым по четвертый информационными входами устройства, второй настроечный вход которого соединен с пятым, шестым и седьмым входами мажоритарного элемента с порогом три, а третий настроечный вход соединен с пятым, шестым и седьмым входами мажоритарного элемента с порогом пять, выход которого соединен с инверсным входом элемента равнозначности, первый прямой вход которого соединен с выходом элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, второй прямой вход соединен с выходом мажоритарного элемента с порогом три, а выход соединен с выходом устройства. 1587 1 Изобретение относится к области вычислительной техники и микроэлектроники и предназначено для реализации фундаментальных симметрических булевых функций четырех переменных. Известно устройство для вычисления фундаментальных симметрических булевых функций пяти переменных, содержащее три элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, мажоритарные элементы с порогами два и четыре, элемент ИЛИ-НЕ 1. Недостатком устройства является низкое быстродействие, определяемое глубиной схемы и равное 3, где-задержка на вентиль. Наиболее близким по функциональным возможностям и конструкции техническим решением к предлагаемому является устройство для вычисления фундаментальных симметрических булевых функцийперемен ных, содержащее р элементов СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, р-1 мажоритарных элементов с 2 порогами 2,42 р-2, элемент И,информационных и р настроечных входов, один выход 2. Недостатком известного устройства является низкое быстродействие, определяемое глубиной схемы и равное 3, где -задержка на вентиль. Изобретение направлено на решение технической задачи повышения быстродействия устройства для вычисления фундаментальных симметрических булевых функций четырех переменных. Названный технический результат достигается путем использования нового логического элемента (элемента равнозначности), а также изменением межсоединений элементов в схеме. Устройство для вычисления фундаментальных симметрических булевых функций четырех переменных содержит элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, мажоритарный элемент с порогом три, мажоритарный элемент с порогом пять и элемент равнозначности . Входы элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА с первого по четвертый соединены с первым по четвертый входами мажоритарного элемента с порогом три,мажоритарного элемента с порогом пять и с первым по четвертый информационными входами устройства. Первый настроечный вход устройства соединен с пятым входом элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА,второй настроечный вход соединен с пятым, шестым и седьмым входами мажоритарного элемента с порогом три, а третий настроечный вход соединен с пятым, шестым и седьмым входами мажоритарного элемента с порогом пять. Выход мажоритарного элемента с порогом пять соединен с инверсным входом элемента равнозначности, первый прямой вход которого соединен с выходом элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, второй прямой вход соединен с выходом мажоритарного элемента с порогом три, а выход соединен с выходом устройства. На чертеже (фиг.1) представлена схема устройства для вычисления фундаментальных симметрических булевых функций четырех переменных. Устройство для вычисления фундаментальных симметрических булевых функций содержит элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА 1, мажоритарный элемент с порогом три 2, мажоритарный элемент с порогом пять 3, элемент равнозначности 4, четыре информационных входа 5,6,7 и 8, три настроечных входа 9,10 и 11, выход 12. Устройство для вычисления фундаментальных симметрических булевых функций работает следующим образом. На информационные входы 5,6,7 и 8 поступают двоичные переменные х 1, х 2, х 3 и х 4 (в произвольном порядке), на настроечные входы 9,10 и 11 - сигналы настройки 1, 2 и 3, значения которых принадлежат множеству 0,1. На выходе 12 реализуется фундаментальная симметрическая булевая функция(х 1, х 2, х 3, х 4), определяемая вектором настройки(1, 2, 3). Известно, что произвольная симметрическая булева функцияпеременных(х 1, х 2 х), с рабочими числами, а 1,2 а (о) принимает значение 1 на тех и только тех наборах переменных х 1, х 2 х, которые содержат ровно а (,2) единиц. Такая симметрическая булева функция обозначается через 1 , 2(х 1, х 2 х). Если 1, то симметрическая булева функцияназывается фундаментальной (или элементарной), т.е. 1, если х 1 х 2 х На выходе- входового мажоритарного элемента с порогом а реализуется монотонная симметрическая булева функция М(х 1, х 2 х), 1 (х 1, х 2 х), а на выходе -входового элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА - линейная булева функция(х 1,х 2 х), где 1,3 1 (1 ,2 ), если- четное 1587 1 Первообразная устройства для вычисления фундаментальных симметрических булевых функций четырех переменных имеет вид 7 (х 1, х 2,х 3,х 4,2,2,2),5 (1 ,2 ,3 ,4 ,3 ,3 ,3 ) ), где (ас)- функция равнозначности 7 переменных ас. В таблице (фиг.2) представлена настройка устройства на реализацию фундаментальных симметрических булевых функций четырех переменных. Достоинством устройства для вычисления фундаментальных симметрических булевых функций четырех переменных является высокое быстродействие, которое вычисляется как 2, где- задержка на вентиль (быстродействие прототипа равно 3). При этом сложность устройства по числу входов логических элементов равна 22, в то время как сложность устройства - прототипа (при 4) равна 20. Сигналы настройки Двоичный код фундаментальной симметрической булевой функции, реализуемой на выходе устройства 12 10000 01000 00100 00010 00001 оставитель Л.З. Униговская Редактор В.Н. Позняк Корректор Т.Н. Никитина Заказ 3554 Тираж 20 зкз. Государственный патентный комитет Республики Беларусь. 220072, г. Минск, проспект Ф. Скорины, 66. 3