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

(57) Изобретен ной технике и м начено для ре булевых функц изобретения - ных возможнос метрических переменных. П ся тем, что устр по ук- ст- ех ГОСУДАРСТВЕННОЕ ПАТЕНТНОЕВЕДОМСТВО СССР(54) УСТРОЙСТВОСИММЕТРИЧЕСКИХ ие относится к вычислительикроэлектронике и предназалиэации симметрических ий пяти переменных. Цель расширение функциональтей за счет реализации симбулевых функций пяти оставленная цель достигаетойство для вычисления симИзобретение относится к вычислительной технике и микроэлектронике и предназначено для реализации симметрических булевых функций (с.б.ф.) пяти переменных,Известно устройство для вычисления с,б.ф, четырех переменных, содержащее четыре элемента НЕ и двадцать один элемент И-НЕ, Устройство при простой настройке реализует все с.б.ф. четырех переменных,Недостатком устройства являются низкие функциональные возможности, так как оно не реализует с.б.ф. с числом переменных пять и более. 1789976 А метрических булевых функций пяти переменных содержит одиннадцать элементов ИЛИ, элемент равнозначности, элемент ИН Е, одноразрядный двоичный сумматор, четыре элемента ИЛИ-НЕ, элементы И и ЗАПРЕТ, пять информационных входов, шесть настроечных входов и выход, Сложность устройства по числу входов логических элементов равна 60, быстродействие, определяемое глубиной схемы, составляет 4 т, где т - задержка на вентиль, На информационные входы поступают двоичные перемен- НЫЕ Х 1, Х 2, ХЗ, Х 4, Х 5 (В ПРОИЗВОЛЬНОМ порядке), на, настроечные входы - сигналы настройки 01, 02, Оз, 04, 05, 06, значения которых принадлежат множеству (О, ). На выходе устройства реализуется симметрическая булева функция Г = 1-(х 1, х 2, хз, х 4, ХБ), определяемая вектором настройки О = (01, (.Л 02, Оз, 04, 05, 06). 1 ил, 1 табл,.Наиболее близким к предлагаемому функциональным воэможностями констр ции техническим решением является у ройство для вычисления с.б,ф. четыр переменных, содержащее два элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА, шесть элементов И, три элемента ИЛИ-НЕ и шесть элементов И-НЕ.Недостатком известного устройства для вычисления с.б.ф,являются низкие функциональные возможности.Цель изобретения - расширение функциональных возможностей устройства за счет реализации с,б,ф, пяти переменных.Поставлднйаяцель достигается тем, что в устройство для вычисления симметрических булевых функций, содержащее элемент И и первый элемент ИЛИ-НЕ, введены со второго по четвертый элементы ИЛИ-НЕ, 5 элемент РАВНОЗНАЧНОСТЬ, элемент ИНЕ, сумматор, два элемента ЗАПРЕТ и одиннадцать элементов ИЛИ, -й ( = 1- 2) вход первого из которых соединен с )-м информационным входом устройства, )-м вхо дом элемента РАВНОЗНАЧНОСТЬ и -м входоМзлемента И-НЕ, а выход первого элемента ИЛИ соединен с первым входом первого элемента ИЛИ-НЕ и первым входом О + 1)-го= 1, 2, 3) элемента ИЛИ, выход 15 элемента РАВНОЗНАЧНОСТЬ соединен с первым входом второго элемента ИЛИ-НЕ и первым входом+ 4)-го элемента ИЛИ, выход элемента И-НЕ соединен с первым входом третьего элемента ИЛИ-НЕ и первым 20 входом+ 7)-го элемента ИЛИ, первый на- строечный вход устройства соединен с вторым входом первого элемента ИЛИ-НЕ, второй настроечный вход устройства соединен с вторым входом второго элемента ИЛИ-НЕ и вторым входом второго элемента ИЛИ, третий настроечный вход устройства соединен со вторым входом третьего элемента ИЛИ-НЕ, вторым входом третьего элемента ИЛИ и вторым входом пятого зле мента ИЛИ, четвертый настроечный вход, устройства соединен с вторым входом четвертого элемента ИЛИ, вторым входом шестого элемента ИЛИ и вторым входомвосьмого элемента ИЛИ, пятый настроечный вход устройства соединен с вторым входом седьмого элемента ИЛИ и вторым входом девятого элемента ИЛИ, шестой настроечный вход устройства соединен со вторым входом десятого элемента ИЛИ, О+ 2)-й 40 информационный вход устройства соединен с )-м входом одноразрядного двоичного сумматора, выход суммы которого соединен с первым входом элемента И, первым прямым входом первого элемента ЗАПРЕТ, ин версным входом второго элемента ЗАПРЕТ и первым входом четвертого элемента ИНЕ, О + 1)-й вход которого соединен с выходом )-го элемента ИЛИ-НЕ, пятый вход четвертого элемента ИЛИ-НЕ соединен с 50 выходом переноса одноразрядного двоичного сумматора, вторым входом элемента И, первым прямым входом второго элемента ЗАПРЕТ и инверсным входом первогоэлемента ЗАПРЕТ,+ 1)-й прямой вход которо го соединен с выходом (3) - 1)-го элемента ИЛИ, а выход первого элемента ЗАПРЕТ соединен с первым входом одиннадцатого элемента ИЛИ, второй вход которого соединен с выходом четвертого элемента ИЛИНЕ, а третий вход одиннадцатого элемента ИЛИ соединен с выходом второго элемента ЗАПРЕТ,+ 1)-й прямой вход которого соединен с выходом 3)-го элемента ИЛИ, выход (3) + 1)-го элемента ИЛИ соединен с О+ 2)-м входом элемента И, выход которого соединен с четвертым входом одиннадцатого элемента ИЛИ, выход которого является выходом устройства,Устройство для вычисления симметрических булевых функций пяти переменных содержит одиннадцать элементов ИЛИ, элемент РАВНОЗНАЧНОСТЬ, элемент И-НЕ, одноразрядный двоичный сумматор, четыре элемента ИЛИ-НЕ, два элемента ЗАПРЕТ, элемент И, Причем, -й( = 1, 2) вход элемента ИЛИ соединен с )-м информационным входом устройства, -м входом элемента РАВНОЗНАЧНОСТЬ и )-м входом элемента И-НЕ. Вь 1 ход первого элемента ИЛИ соединен с первым входом первого элемента ИЛИ-НЕ и первым входом О+ 1)го= 1, 2, 3) элемента ИЛИ, Выход элемента РАВНОЗНАЧНОСТЬ соединен с первым входом второго элемента ИЛИ-НЕ и первым входом+ 4)-го элемента ИЛИ. Выход элемента И-НЕ соединен с первым входом третьего элемента ИЛИ-НЕ и первым входом+7)го элемента ИЛИ, Первый настроечный вход устройства соединен со вторым входом первого элемента ИЛИ-НЕ. Второй настроечный вход устройства соединен с вторым входом второго элемента ИЛИ-НЕ и вторым входом второго элемента ИЛИ. Третий настроечный вход устройства соединен со вторым входом третьего элемента ИЛИ-НЕ, вторым входом третьего элемента ИЛИ и вторым входом пятого элемента ИЛИ, Четвертый настроечный вход устройства соединен с вторым входом четвертого элемента ИЛИ, вторым входом шестого элемента ИЛИ и вторым входом восьмого элемента ИЛИ. Пятый настроечный вход устройства соединен с вторым входом седьмого элемента ИЛИ и вторым входом девятого элемента ИЛИ, Шестой настроечный вход устройства соединен с вторым входом десятого элемента ИЛИ. Далее+ 2)-й информационный вход устройства соединен с )-м входом одноразрядного двоичного сумматора, выход суммы которого соединен с первым входом элемента И, первым прямым входом первого элемента ЗАПРЕТ, инверсным входом второго элемента ЗАПРЕТ и первым входом четвертого элемента ИЛИНЕ, О+ 1)-й вход которого соединен с выходом )-го элемента ИЛИ-НЕ. Пятый вход четвертого элемента ИЛИ-НЕ соединен с выходом переноса одноразрядного двоичного сумматора, вторым входом элемента И,1789976 15 20 25 30 35 40,первым прямым входом второго элемента ЗАПРЕТ и инверсным входом первого элемента ЗАПРЕТ, О+ 1)-й прямой вход которого соединен с выходом (3) - 1)-го элемента ИЛИ. Выход первого элемента ЗАПРЕТ соединен с первым входом одиннадцатого элемента ИЛИ, второй вход которого соединен с выходом четвертого элемента ИЛИНЕ. Третий вход одиннадцатого элемента ИЛИ соединен с выходом второго элемента ЗАПРЕТ, 0 + 1)-й прямой вход которого соединен с выходом 3)-го элемента ИЛИ. Выход (3) + 1)-го элемента ИЛИ соединен с О+ 2)-м вхпдом элемента И, выход которого соединен с четвертым входом одиннадцатого элемента ИЛИ, выход которого является выходом устройства,На чертеже представлена схема устройства для вычисления с.б,ф, пяти переменных.Устройство содержит одиннадцать элементов ИЛИ 1 .11, элемент РАВНОЗНАЧНОСТЬ 12, элемент И-НЕ 13, одноразрядный двоичный сумматор 14, четыре элемента ИЛИ-НЕ 15 .18, два элемента ЗАПРЕТ 19 и 20, элемент И 21, пять информационных входов 2226, шесть настроечных входов 2732, выхсд 33,,Устройство для вычисления с.б,ф. работает следующим образом. На инфо рмационные входы 2226 поступают двоичные переменные х 1.х 5 (в произвольном порядке); на настроечные входы 2732 подаются сигналы настройки и 1 , Об соответственно, значения которых принадлежат множеству (О, 1), На выходе 33 реализуется некоторая с.б.ф, пяти переменных Е = Е(х 1, х 2, , х 5), определяемая вектором настройки О = (ц 1, ц 2, .", Цб) Формула изобретения Устройство для вычисления симметрических булевых функций, содержащее элемент И и первый элемент ИЛИ-НЕ, о т л ич а ю щ е е с я тем, что, с целью расширения функциональных возможностей за счет реализации симметрических булевых функций пяти переменных, оно содержит с второго по четвертый элементы ИЛИ-НЕ, элемент РАВНОЗНАЧНОСТЬ, элемент И-НЕ, одноразрядный двоичный сумматор, два элемента ЗАПРЕТ и одиннадцать элементов ИЛИ, 1-й О = 1, 2) вход первого из которых соедиРассмотрим алгоритм настройки устройства, Известно (см Лупанов О.Б, Об одном подходе к синтезу управляющих систем - принципе локального кодирования О Проблемы кибернетики. - М,: Наука, 1965, вып, 14, с, 31 - 110), что произвольная с.б.ф. и переменных Е = Е(х 1, х 2, , х) может быть однозначно определена (и + 1)-разрядным двоичным кодом п(Е) =(пп, , пл), где п - значение функции Е на (любом) наборе значений переменных х 1, х 2, , хп; содержащем ровно единиц ( = О, 1, ., и), Другими СЛОВаМИ, ЕСЛИ Х 1+ Х 2+ . Хл = 1; тО ЗНаЧЕНИЕ Е на данном наборе переменных равно пьТогда сигналы настройки устройства на реализацию с.б,ф, Е = Е(х 1, х 2 х 5), заданной Двоичным кОДОм п(Е) = (по, п 1, , п 5), вычисляются как щ = п 1-1, где) = 1, 2, 6.П р и м е р. Пусть требуется определить настройку устройства на реализацию с.б,ф. Е = Е(х 1, х 2, , х 5), заданной таблицей истинности И(Е), гдеМ(Е) -- (1110 1000 1000 0001 1000 0001 0001 0110),Нетрудно видеть, что имеет место п(Е) = (1, 1, О, О, 1, 0). Следовательно, для реализации функции Е необходимо на настроечные входы 29, 30 и 32 подать сигнал логического нуля, а на настроечные входы 27, 28 и 31 - сигнал логической единицы,. Достоинством устройства являются широкие функциональные возможности. По сравнению с прототипом устройство реализует в два раза больше с.б.ф. (64 с.б,ф, пяти переменных против 32 с.б.ф. четырех переменных), Отметим, что быстродействие устройства, определяемое глубиной схемы, совпадает с быстродействием прототипа и составляет 4 т, где г - задержка на вентиль,нен с Ем информационным входом устройства, Ем входом элемента равнозначности и 1-м входом элемента И-НЕ, а выход первого элемента ИЛИ соединен с первым входом первого элемента ИЛИ-НЕ, и первым входом)+ 1-го 0 = 1, 2, 3) элемента ИЛИ, выход элемента РАВНОЗНАЧНОСТЬ соединен с первым входом второго элемента ИЛИ-НЕ и первым входом)+4-го элемента ИЛИ, выход элемента И-НЕ соединен с первым входом третьего элемента ИЛИ-НЕ и первым входом) + 7-го элемента ИЛИ, первый настро.ечный вход устройства соединен с вторым1789978 Таблица двоичных номеров реализуемых функций,29 ЦЗ 32 06 33(Х 1,Х 2,ХЗ,Х 4 00000000000000000000000000000000 00000000000000000000000000000001 00000000000000010000000100010110 00000000000000010000000100010111 00000001000101100001011001101000 00000001000101100001011001101001 00000001000101110001011101111110 00000001000101110001011101111111 00010110011010000110100010000000 00010110011010000110100010000001 00010110011010010110100110010110 00010110011010010110100110010111 00010111011111100111111011101000 000101110111111001 Ш 11011101001 00010111011111110111111111111110 00010111011111110111111111111111 01101000100000001 ООООООООООООООО 01101000100000001000000000000001 01101000100000011000000100010110 01101000100000011000000100010111 01101001100101101001011001101000 01101001100101101001011001101001 01101001100101111001011101111110 01101001100101111001011101111111 01111.110111010001110100010000000 01111110111010001110100010000001 О О входом первого элемента ИЛИ-НЕ, второй настроечный вход устройства соединен с вторым входом второго элемента ИЛИ-НЕ и вторым входом второго элемента ИЛИ, третий настроечный вход устройства соединен с вторым входом третьего элемента ИЛИНЕ, вторым входом третьего элемента ИЛИ и вторым входом пятого элемента ИЛИ, четвертый настроечный вход устройства соединен с вторым входом четвертого элемента ИЛИ, вторым входом шестого элемента ИЛИ и вторым входом восьмого элемента ИЛИ, пятый настроечный вход устройства соединен с вторым входом седьмого элемента ИЛИ и вторым входом девятого элемента ИЛИ, шестой настроечный вход устройства соединен с вторым входом десятого элемента ИЛИ, ) + 2-й информационный вход устройства соединен с )-м входом одноразрядного двоичного сумматора, выход суммы которого соединен с первым входом элемента И, первым прямым входом первого элемента ЗАПРЕТ, инверсным входом второго элемента ЗАПРЕТ и первым входом четвертого элемента ИЛИ-НЕ, ) + 1-й вход которого соединен с выходом )-го элемента ИЛИ-НЕ, пятый вход четвертого элемента ИЛИ-НЕ соединен с выходом переноса одноразрядного двоичного сумматора вторым входом элемента И, первым прямым входом второго элемента ЗАПРЕТ и инвер-. сным входом первого элемента ЗАПРЕТ, )+ 1-й прямой вход которого соединен с выходом 3) - 1-го элемента ИЛИ, а выход первого элемента ЗАПРЕТ соединен с первым входом одиннадцатого элемента ИЛИ, второй вход которого соединен с выходом четвертого элемента ИЛИ-НЕ, а третий вход одиннадцатого элемента ИЛИ соединен с выходом второго элемента ЗАПРЕТ, ) + 1-й прямой вход которого соединен с выходом 3)-го элемента ИЛИ, выход 3) + 1-го элемента ИЛИ соединен с ) + 2-м входом элемента И, выход которого соединен с четвертым входом одиннадцатого элемента ИЛИ, выход которого является выходом устройства,1789976 СРедэктор Т; Шагова Т Корректор Н, Коро ГКНТ СССР изводственно-издэтельский комбинэт "Пэтент", г. Ужгор арине, 10 Заказ 349 ВНИИПИ Госудэ остэвитель В, Супрунехред М.Моргентэл Тираж Подписное нного комитвтэ по изобретениям и открытиям 3035, Москва, Ж, Раувскэя наб., 4/5