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

(51)5 6 06 Е 700 ТЕНТН ГОСУДАРСТВЕННОЕ ВЕДОМСТВО СССР (ГОСПАТЕНТ СССР) ОПИСАНИЕ ИЗОБРЕТЕН К АВТОРСКОМУ СВИДЕТЕЛЬСТ(56) Авторское свидетельство СССРМ 1559337, кл. 6 06 Е 700, 1988.Лухальский Г,ИНовосельцева Т.Я. . Проектирование дискретных устройств на интегральных схемах. Справочник, М,: Радио и связь, 1990, с, 105, рис. 310.(54) УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ СИММЕТРИЧЕСКИХ БУЛЕВЫХ ФУНКЦИЙ (57) Изобретение относится к области вычислительной техники и микроэлектроники и предназначено для реализации симметриИзобретение относится к области вычислительной техники и микроэлектроники и предназначенодля реализациисимметрических булевых функций (с.б,ф.) и переменных,Цель изобретения - упрощение устройства для вычисления симметрических булевых функций.Устройство для вычисления симметрических булевых функций содержит мультиплексор и (и - 1)-входовый одноразрядный сумматор (и - количество аргументов реализуемых симметрических булевых функций). Выход мультиплексора соединен с выходом устройства, а 1-й ( - 1, 2, , и) вход данных соединен с 1-м настроечным входом устройства. Причем, 1-й Ц 1, 2 и - 1) вход сумматора соединен с 1-м информационным входом устройства, а 1-й (1 - 1, 2, 1(; ( = ческих булевых функций (с,б.ф.) и переменных. Цель изобретения - упрощение устройства для вычисления с.б,ф. Поставленная цель достигается тем, что устройство для вычисления с.б.ф, п переменных содержит (и - 1)-входовый одноразрядный сумматор и 2 -канальный мультиплексор, где ( = о 92 п(.кУстройство работает следующим образом.На информационные входы устройства поступают двоичные переменные х 1, ., хп -1(в произвольном порядке), на настроечные входы - сигналы настройки и 1,цп, значения которых принадлежат множеству (О, 1, хп, х). На выходе реализуется некоторая с.б.ф. и переменных Г = Цх 1, х 2, , х), определяемая вектором настройки 0 = 11, ц 2, , ип). 1 ил.=о 92 иО выход соединен с 1-м адресным входом мультиплексора.На чертеже представлена схема предлагаемого устройства,Устройство для вычисления с.б.ф. и переменных содержит (и - 1)-входовый одноразрядный сумматор 1 (ЯМп), мультиплексор 2(МОХ), и -1 информационных входов 31Зп, и настроечных входов 414 п, выход 5,Сумматор 1 обеспечивает подсчет числа единиц, содержащихся во входном информационном слове Х =(х 1, х 2,хп), На входы 313-1 поступают двоичные переменные х 1, х 2, , хМ (в произвольном порядке), на ( -о 92 и выходах сумматора реализуются соответственно функции 0 = ь,(х 1, х 2, , х)тктк(х 1, х 2, , хп), составляющие позиционный двоичный код числа единиц в сло 18338 бО++ Хо =1. При этом функция Е однозначно задается (и +1)-разрядным двоичным кодом П(1-) =(По, П 1, Пп), ТОГДа СИГНаЛ НаотРОйКИ о на -м настроечном входе 4 устройства равен 50 Ш = пн 1 хп . п хп (1)гдето=1,2,. и,55 П р и м е р, Найти вектор настройки Оустройства на реализацию следующейс,б.ф. от шести переменных: ВЕ Х = (Х 1, Х 2, ., Хп), т.Е, Х 1 + Х 2+ . + Хо=1 о + 211 + 412++ 2 Ь.Ь 1Выход сумматора 1, на отором реализуется булева функция 11-1 ( = 1, 21),соединен с адресным входом мультиплексора 1, имеющим вес 2, что и показано на .чертеже.Схемы и-входовых одноразрядных сумматоров достаточно хорошо изучены, Причем оценка их сложности Ябмах = 0(и оцги), а "Обыстродействие практически не зависит оти и равно 2 т или 3 т, где т - задержка навентиль.Мультиплексор 2 имеет К =)ояги адресных входов и 2 входов данных. Однако в 15/заявляемом устройстве для вычисленияс.б.ф, п переменных используются толькопервые и2 входов данных мультиплексора, которые соединены с настроечными входами 41, , 4 п устройства (остальные входы 20данных мультиплексора на чертеже не показаны).Следовательно, -й ( = 1, 2, , и) настроечный вход 4 устройства (1-й вход данныхмультиплексора 2 - вход с номером- 1) 25будет подключен к выходу 5 устройства (вы ходу мультиплексора 2), если на адресныхвходах мультиплексора двоичный код равен-1, или (что тоже самое) на входах 31 Зо сумматора 1 присутствует ровно-1 логических единиц,Устройство для вычисления с.б.ф. работает следующим образом. На информационные входы 31, ., Зп- устройства поступаютдвоичные переменные х 1, ., хп(в произвольном порядке), на настроечные входы41, , 4 П - сигналы настройки ц ., цп, соответственно, значения которых принадлежатмножеству (О, 1, хп, хп). На выходе 5 реализуется некоторая с.б,ф. и переменных Е = 40=г(Х 1, х 2, , хп), определяемая вектором наСтРОйКИ О = (О 1, Цг, , Оо). Цх 1, х 2,хб) = х х 2 хз х 4 х 5х 1 х 2 хз х 4 хбч к х 2 хз х 5 хб чх 1 х 2 х 4 х 5 хб ч х хз х 4 х 5 хбх 2 хз х 4 х 5 хб 4 х х 2 хз х 4 х 5 хб.Очевидно, что здесь п(Р) = (1, 1, О, О, О, О, 1). Отсюда с учетом (1) получаем а = 1, а = = хб, Оз = О 4 = 05 = 0 и Об = хб, Таким образом, имеем О = (1, хб, О, О, О, хб). Следовательно, на настроечные входы устройства 41, 4 г, 4 з, 44, 45 и 46 должны быть поданы сигналы настройки соответственно 1, хб, О, О, О и хб (на информационные входы 31, 32, Зз, 34 и 35 подаются двоичные переменные х 1, хг, хз, х 4 и хб в произвольном порядке).Достоинством заявляемого устройства является простая конструкция, высокое быстродействие, использование в своем составе стандартных элементов (мультиплексор и многовходовый одноразрядный сумматор).Оценка сложности прототипа (2" - канальный мультиплексор) составляет Япр.- =0 (и 2"), в то время как заявляемое устройство имеет сложность, оцениваемую ве- ЛИЧИНОЙ Язаявл, = 0(ИОЯгп), ПРИ ЭТОМ известные устройства для вычисления с.б.ф. и переменных имеют оценку сложности вида Яизв. = 0(иг).Быстродействие заявляемого устройства практически не зависит от и и определяется глубиной схемы сумматора (2 ту известных схем многовходовых одноразрядных сумматоров) и мультиплексора (3 т у классического мультиплексора). Вместе с тем известные устройства для вычисления с,б,ф. имеют оценку быстродействия, определяемую глубиной схемы, равную Тизв. = 0(и),Кроме того, для своей реализации предлагаемое устройство требует использование стандартных элементов, входящих в состав большинства серий интегральных микросхем средней степени интеграции (мультиплексоры, многовходовые одноразрядные сумматорь 1). В то же время известные устройства для вычисления с.б,ф. для своей практической реализации требуют или разработки заказных схем, или использование схем малой степени интеграции (элементы И-Н Е, ИЛИ-Н Е, ИСКЛ ЮЧАЮЩЕЕ ИЛИ и др,). В первом случае необходимы значительные материальные затраты для разработки заказных схем, а во втором - устройство будет иметь довольно-таки высокую конструктивную сложность (по числу корпусов микросхем).Формула изобретенияУстройство для вычисления симметри- .ческих булевых функций, содержащее мультиплексор, выход которого соединен с выходом устройства, -й настроечный вход1833860 Составитель Л.Авгул Техред М.Моргентал орректор М.Тк Редактор аказ 2686 Тираж ПодписноеВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ ССС113035, Москва, Ж, Раушская наб., 4/5 оизводственно-издательский комбинат "Патент", г. Ужгород, ул,Гагарина, 10 которого (1 = 1, и; и - количество переменных) соединен с 1-м входом данных мультиплексора, о тл и ч а ю ще е с я тем, что, с целью упрощения при реализации симмет- . рических булевых функций, оно содержит и - 5 1-входовый одноразрядный сумматор, )-й вход которого 0 - Г о . 1 т соединен с .м информационным входом устройства, 1-й выход сумматора (1, М; М -3 од 2 п 0 соединен с 1-м адресным входом мультиплексора,