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

ГОСУДАРСТВЕННЫЙ ПАТЕНТНЫЙ КОМИТЕТ РЕСПУБЛИКИ БЕЛАРУСЬ УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ СИММЕТРИЧЕСКИХ БУЛЕВЫХ ФУНКЦИЙ(71) Заявитель Белорусский государственный университет(73) Патентообладатель Белорусский государственный университет(57) Устройство для вычисления симметрических булевых функций, содержащее мажоритарный элемент с порогом два, входы которого с первого по третий соединены соответственно с первым по третий информационными входами устройства, элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА и элемент И, первый вход которого соединен с первым настроечным входом устройства, а выход соединен с первым входом элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, второй вход которого соединен со вторым настроечным входом устройства, выход которого соединен с выходом элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, отличающееся тем, что дополнительно введен элемент ИЛИ, входы которого с первого по третий соединены соответственно с первым по третий информационными входами устройства и со вторым по четвертый входами элемента И, третий настроечный вход устройства соединен с четвертым входом элемента ИЛИ, а четвертый настроечный вход - с четвертым и пятым входами мажоритарного элемента с порогом два, выход которого соединен с третьим входом элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, четвертый вход которого соединен с выходом элемента ИЛИ.(56) 1. А.с. СССР 1689943, МКИ -067/00, 1991. 2. А.с. СССР 1767495, МКИ -067/00, 1992 (прототип). 3. Лупанов О.Б. Об одном подходе к синтезу управляющих систем - принципе локального кодирования // Проблемы кибернетики. - М. Наука, 1965, вып.14. 2118 1 Изобретение относится к области вычислительной техники и микроэлектроники и предназначено для реализации симметрических булевых функций трех переменных. Известно устройство для вычисления симметрических булевых функций трех переменных, содержащее шесть элементов И, три элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, три информационных и четыре настроечных входов, один выход 1. Сложность устройства (по числу входов логических элементов) равна 22, а быстродействие, определяемое глубиной схемы, составляет 4, где- задержка на вентиль. Недостатком устройства является высокая конструктивная сложность и низкое быстродействие. Наиболее близким по функциональным возможностям и конструкции техническим решением к предлагаемому является устройство для вычисления симметрических булевых функций, содержащее два элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, мажоритарный элемент с порогом два, три элемента И, семь входов и один выход 2. Устройство при сложной настройке реализует симметрические булевы функции четырех переменных, а при простой настройке - симметрические булевы функции трех переменных. Сложность устройства равна 17, а быстродействие - 3. Недостатком известного устройства для вычисления симметрических булевых функций является низкое быстродействие. Изобретение направлено на решение технической задачи повышения быстродействия устройства для вычисления симметрических булевых функций трех переменных. Устройство для вычисления симметрических булевых функций содержит мажоритарный элемент с порогом два, входы которого с первого по третий соединены соответственно с первым по третий информационными входами устройства, элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА и элемент И. Первый вход элемента И соединен с первым настроечным входом устройства, а выход соединен с первым входом элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА. Второй вход элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА соединен со вторым настроечным входом устройства, выход которого соединен с выходом элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА. В отличие от прототипа в устройство дополнительно введен элемент ИЛИ, входы которого с первого по третий соединены соответственно с первым по третий информационными входами устройства и со вторым по четвертый входами элемента И. Третий настроечный вход устройства соединен с четвертым входом элемента ИЛИ, а четвертый настроечный вход - с четвертым и пятым входами мажоритарного элемента с порогом два, выход которого соединен с третьим входом элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, четвертый вход которого соединен с выходом элемента ИЛИ. Основной технический результат изобретения заключается в повышении быстродействия устройства для вычисления симметрических булевых функций. Названный технический результат достигается путем введения нового элемента ИЛИ, а также изменением меж- соединений в схеме устройства. На чертеже представлена схема устройства для вычисления симметрических булевых функций трех переменных. Устройство для вычисления симметрических булевых функций содержит элемент ИЛИ 1, мажоритарный элемент с порогом два 2, элемент И 3, элемент СЛОЖЕНИЕ ПО МОДУЛЮ ДВА 4, три информационных входа 5,6 и 7, четыре настроечных входов 8,9,10 и 11, выход 12. Устройство для вычисления симметрических булевых функций работает следующим образом. На информационные входы 5,6 и 7 поступают двоичные переменные х 1, х 2 и х 3 (в произвольном порядке) на настроечные входы 8,9,10 и 11 - сигналы настройки 1, 2, 3 и 4, значения которых принадлежат множеству 0,1.На выходе 12 реализуется симметрическая булева функция(х 1, х 2, х 3), определяемая вектором настройки(1, 2, 3, 4). Первообразная устройства для вычисления симметрических булевых функций имеет следующий вид(х 1, х 2, х 3, 1, 2, 3, 4,)1(2123)(3121323)4 12 3. Поясним алгоритм настройки. Известно 3, что произвольная симметрическая булева функцияпеременных(х 1, х 2 х), однозначно определяется (1) -разрядным двоичным кодом(0, 1), где- значение функциина (любом) наборе переменных х 1, х 2 х, содержащем ровноединиц (о). Тогда значения сигналов настройки устройства на реализацию некоторой симметрической булевой функции трех переменных 2118 1(х 1, х 2, х 3), заданной двоичным кодом(0, 1, 2,3), определяются следующим образом 12, 2011, 3121 и 423. Пример. Найти сигналы настройки устройства на реализацию симметрической булевой функции(х 1, х 2, х 3), заданной посредством дизъюнктивной нормальной формы(х 1, х 2, х 3)х 12,13 х 23 Очевидно, что здесь(0, 1, 2,3)(0,1,1,0). Тогда сигналы настройки определяются согласно приведенным выше формулам следующим образом 11,20110, 31111 и 4101. Следовательно, сигнал логического нуля должен быть подан на настроечный вход 9, а сигнал логической единицы - на настроечные входы 8,10 и 11. Достоинством устройства является высокое быстродействие, которое составляет 2, где- задержка на вентиль (быстродействие устройства-прототипа равно 3). Дополнительным достоинством является низкая конструктивная сложность устройства, которая (по числу входов логических элементов) совпадает со сложностью устройства-прототипа и равна 17. оставитель Е.В. Федоров Редактор В.Н. Позняк Корректор Т.Н. Никитина Заказ 0062 Тираж 20 экз. Государственный патентный комитет Республики Беларусь. 220072, г. Минск, проспект Ф. Скорины, 66.