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

СОЮЗ СОВЕТСКИХСОЦИАЛИСТИЧЕСКИХРЕСПУБЛИК 9978 9) (1 ) 06 Р 7/00 ТЕН ГОСУДАРСТВЕННОЕ ПАТЕНТНОВЕДОМСТВО СССРГОСПАТЕНТ СССР) ОПИСАНИЕ ИЗОБ ВТОРСКОМУ СВИДЕТЕЛЬСТ(56) Авторское свидетельство СССР М 1396137, кл, 6 06 Е 7/00, 1987.Авторское свидетельство СССР М 1730616, кл. О 06 Г 7/00, 1990,(54) УСТРОЙСТВО ДЛЯ ВЪЧИСЛЕНИЯ ФУНДАМЕНТАЛЬНЫХ СИММЕТРИЧЕСКИХ БУЛЕВЫХ ФУНКЦИЙ(57) Изобретение относится к вычислительной технике и микроэлектронике и предназначено для вычисления фундаментальных (элементарных) симметрических булевых функций. Цель изобретения - расширение функциональных возможностей за счет реализации фундаментальных симметрических булевых функций и переменных, Поставленная цель достигается тем, что устройство Изобретение относится к вычислительной технике и микроэлектронике и предназначено для вычисления фундаментальных симметрических булевых функций (ф,с.б.ф,) и переменных.Известно устройство для вычисления ф,с.б,ф. четырех переменных, содержащее два элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, элемент РАВ,103 НАЧНОСТЬ, элемент ИЛИ-НЕ и элемент И 1,Недостатком устройства являются низкие функциональные возможности, а также настройка сигналами на множества (О, 1, х 1, х 1, х 4, х 4), что значительно усложняет организацию электронной настройки,для вычисления фундаментальных симметричных булевых функций и переменных содержит Р(Р = и/2 элементов "сложение по модулю 2", Р - 1 мажоритарных элементов, К-й (К = 1, 2, . Р - 1) из которых имеет порог, равный 2 К, элемент И, и информационных входов, Р настроечных входов и один выход;Сложность устройства по числ входов логических элементов равна -2- (и + 3) - 1. НаПинформационные входы поступают двоичные переменные х 1,хп (в произвольном порядке); на настроечные входы - сигналы настройки 01 . 0 р, значения которых принадлежат множеству (О, 1); на выходе устройства реализуется фундаментальная 3 симметрическая булевая функция 1- = Р(х 1, х 2, , хп), определяемая вектором настрой-ь ( ки 0 = (01, 02, , 0 р). 1 ил 1 табл. Наиболее близким по функциональным возможностям и конструкции техническим решением к предлагаемому является устройство для вычисления ф,с,б.ф. пяти переменных, содержащее три элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, мажоритарный элемент с порогом два, мажоритарный элемент с порогом четыре, элемент ИЛИ-НЕ, пять информационных входов, три настроечных входа и выход 2.Недостатком известного устройства являются низкие функциональные возможности, так как его использование не позволяет вычислять ф.с,б.ф. от шести и более переменных,510 15 20 25 30 Цель изобретения - повышение функциональных возможностей устройства за счет реализации ф,с.б,ф, и переменных,Поставленная цель достигается тем, что в устройство для вычисления фундаментальнмх симметрических булевых функций, содержащее три элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА и два мажоритарных элемента, М-й из которых (М = 1, 2) имеет порог, равный 2 К причем первый вход 1-го элемента СЛОЖЕНИЕПО МОДУЛЮ ДВА(1 = 1-2-3) соединен с 1-м настроечным входом устройства, )-й информационный вход которого= 1, 2, , и; и - количество. переменных функции) соединен с 0+ 1)-м входом первого элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА и )-м входом К-го мажоритарного элемента, выход которого соединен с вторым входом (1+ 1)-го элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, введены элемент И, рэлемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА (р = )и(2 и рмажоритарных элемента,1-й из которых ( = 3, 4, ;, р - 1) имеет порог, равный 21, причем в-й настроечный вход(ги = 4,5, р) устройства соединен с первым входом и 1-го элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, второй вход которого соединен с выходом (а - 1)-го мажоритарного элемента, )-й вход которого соединен с )-м информационным входом устройства, выход которого соединен с выходом элемента И, входы которого соединены с выходами всех элементов СЛОЖЕНИЕ ПО МОДУЛЮ ДВА. На чертеже представлена схема устройства для вычисления ф.с,б.ф, при и -7.Устройство содержит р = )и(2(4 элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА 11, 12, 1 з, 14, р - 1 = 3 мажоритарных элемента 21, 22, 2 з, элемент И 3, и = 7 информационных входов 41, 47, р -- 4 настроечных входов 51 , 54, выход 6. При этом мажоритарные элементы 21, 22, 2 з имеют пороги соответственно два, четыре и шесть. Устройство для вычисления ф,с.б.ф. работает следующим образом, На информационные входы 41 , 4, поступают двоичные ПЕРЕМЕННЫЕ Х 1.Хл (В ПРОИЗВОЛЬНОМ ПОРЯД-. ке); на настроечные входы 51 , 5 р - сигналы НаСтРОйКИ О 1 . Ер СООтВЕтСтВЕННО, ЗНаЧЕНИЯ которых принадлежат множеству (О, 1). На выходе 6 реализуется некоторая ф.с,б.ф, Г л = Р п (Х 1, Х 2, Х), ОПРЕДЕЛЯЕМаЯ ВЕКтОром настройки 0 =(ц 1, ц 2. ", цр)Известно; что произвольная симметричная булева функция и переменных Е = =Е(Х 1, Х 2, Хл) МОжЕт бЫтЬ ВЗаИМНО-ОДНО- значно представлена (и + 1)- разрядным ДВОИЧНЫМ КОДОМ И(Г) - (Ио, И 1, , Ил), ГДЕ ъ - значение Г на(любом) наборе перемен- НЫХ Х 1, Х 2, , Хл, СОДЕРжаЩЕМ РОВНО З ЕДИ- ниц(03п) , Для ф.с,б.ф, Г л двоичный код и(Р) имеет только одну единичную компоненту, а именно. и.= 1. Другими словами, имеет местоУстройство для вычисления фундаментальных симметрических булевых функций и переменных содержит р =)и(2(элементов СЛОЖЕНИЕ ПО МОДУЛЮ ДВА р - 1 мажо)ритарных элементов и элемент И, Причем 1-й мажоритарный элемент (т = 1, 2 р - 1) имеет порог, равный 21, а первый вход 1-го элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА (1 = 1, 2, 3) соединен с 1-мнастроечным входом устройства, )-й информационный вход которого= 1, 2 и) соединен с О+ 1)-м входом первого элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА и 1-м входом М-го мажоритарного элемента (к = 1, 2), Выход 1-го мажоритарного элементасоединен с вторым входом (1 + 1)-го элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, а е-й настроечный вход(а = 4, 5, ., р) устройства сбединен с первым входом и 1-го элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, второй вход которого соединен с вы. ходом (а -1)-го мажоритарного элемента, )-й вход которого соединен с )-м информационным входом устройства. Выход устройства соединен с выходом элемента И, входы которого соединены с выходами всех элементов СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, 1, если х 1+х 2+, +хо=1;Р п(х 1, х 2, ., хп) =0 - в противном случае. 40 45 50 55 Первообразная устройства для вычисления ф,с.б,ф. в общем случае имеет вид: 1 (Х 1, Х 2 ", Хп 01 Ц 2 "Ор) = (О 1 9 Х 1 Ж Х 29л - 1 9 хп) Ь А(М 9 о ),К =1 2 К К+1 где р = и(2(; и функция и-входового мажори тарного элемента с порогом з (Ози) определяется следующим образом:1. ЕСЛИ Х 1+х 2+.+ХиЗ; Мв(Х 1 Х 2 Хл)О - в противном случае.В таблице представлены настройки устройства на реализацию ф,с.б,ф, при и = 7.Отметим, что сложность устройства з по числу входов логических элементов может быть рассчитана по формулез - )и (2( (и + 3) - 1, (1)Достоинством устройства являются широкие функциональные возможности, так как его применение позволяет вычислять и+ 1 ф.с,б,ф., зависящих от и переменных.1789978 Таблица настроек устройства для вычисления ф,с.б.ф. при и = 7 В то время, как устройство-прототип ориентировано на вычисление только 6 ф.с.б.ф, пяти переменных. Кроме того, сложность Формула изобретения Устройство для вычисления фундаментальных симметрических булевых функций, содержащее три элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА и два мажоритарных элемента, К-й из которых (К = 1, 2) имеет порог, равный 2 К причем первый вход -го элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА ( = Т, 3 соединен с -м настроечным входом устроиства,й информационный вход которого О = 1, . и, и - количество переменных функций) соединен с (1+ 1)-м входом первого элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА и 1-м входом К-го мажоритарного элемента, выход которого соединен с вторым входом (Е+ 1)-го элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, о т л и ч а ю щ е е с я тем, что, с целью расширения функциональных воэустройства в, вычисленная по формуле (1)при п =- 5, совпадает со сложностью устройства-прототипа и равна 23. можностей за счет реализации фундаментальных симметрических булевых функций и переменных, в него введены элемент И, р -3 элемент СЛ ЖЕНИЕ ПО МОДУЛЮ ДВАП (р - (р = .тт ) ) и р - 3 мажоритарных элемента, -й из которых (= 3, р - 1) имеет порог, равные 2, причем в-й настроечный вход (щ = 4.р) устройства соединен с первым входом в-го элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, второй вход которого соединен с выходом (п 1 -1)-го мажоритарного элемента, )-й вход которого соединен с 1-м информационным входом устройства, выход которого соединен с выходом элемента И. входы которого соединены с выходами всех элементов СЛОЖЕНИЕ ПО МОДУЛЮ ДВА.1789978 ун Редак К тор Н, Король Т. Шагова КНТ СС Пр аз 349 ВНИИ оставитель В, Суехред М.Морген Тираж Подписное Государственного комитета по изобретениям и открытиям 113035, Москва, Ж, Раушская наб., 4/5