Устройство для полиномиального разложения логических функций

.8)свидетельств С 06 Р 5/00, идетельство С 06 Р 5/00,СР 3,0 руп- рупОГО ВО ДЛЯ ПОЛИНО"ХАЛГИЧЕСКИХ ФУНКЦИ 11(57) Изолительно бретение относится к выч ть исполь е и може техниЭВМ, иуХ ующих прог е высокого терпретир на язык в специализированных ения - расуров ь изобреальных волиномиал процесс ширение устройс ложения х зможносте нкци для ого разкций за че ическ олиномиальвыполнения конъюнкт менным (1 с = ным векторо ний поМ и ных разложе = О,и поляризаци ных разлага Устройство жения ло) с произвол . (и - количе емой логичес для полиноми ических ф ство пере кой функц альног нкций зл ширениеей устройстзложения ласти т быт ние относится кной техники и моо в ЭВ 11, интерпр у, написанную нвня, а также в с цессорах. Цель изобретения - ра нкциональных воэможнос Изобрет ислител тирую- языке миального а для полиогических спользо т выполнеальных разОф 1 ткции за сч щих программвысокого уро рованных про ния конъюнктивно-пол ложений по 1 с перемен пециализ ГОСУДАРСТВЕННЫЙ КОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТНРЫТИЯМПРИ ГКНТ СССР К АВТОРСКОМУ СВИДЕТЕЛЬСТВ переменных содержит дешифратор, и- элемент ИЛ 11, и групп логических блоков по 2 блоков в каждой, причем каждый блок устройства содержит дьа элемента И, один элемент ИЛИ, один элемент ИЛИ-НЕ, один элемент равнозначности и один элемент СЛОЖЕНИЕ РО РОДУЛР ДВА, з =1 ор (и Ф + 1)управляющих входов первой г пы, и управляющих входов второй г пы, 2 информационных входов и 2 "ивыходов. На управляющие входы первой группы устройства подаются сигналы настройки 1111, определяющие количество 1 переменных Х Х по которым разлагается логическая функция Г = Г(Х 1, Х ,Х ) на управляющие входы второй группы - к поненты двоичного вектора поляризации б = (6 бб,) переменных Х Х,,Х на информационные входы - таблица истинности функции г, Тогда на выходах устройства будут формироваться таблицы истинности логических функций и-Е переменныхК- ф (Х,д,Х),где 3 = 0,1,2 на которые разлагается логическаяфункция Г = Г(Х ,Х .,Хп). 2 ил.,3 табл.)ыО Хс, если Хор если п) с произвольным вектором поляриэа,цни (и - количество двоичных переменных разлагаемой логической функции)На Фиг,1 представлена структурная схема устройства для полиномиального разложения логических Функцийпри и = 3; на Фнг,2 - .функциональнаясхема логического блока. 1 ОУстройство (фиг,1) содержит дешифратор 1, и - 1 = 2 элемента ИЛИ-2.1 и 2.2-; 2" = 4 логических блокапервой группы 3,134, 2= 4и-логических блока второй группы, 4.1, 15(и + 1) 1 = 2 управляющих входа первой группы 6,1 и 6,2, и = 3 управляющих входа второй группы ,1 - 7.3, 2 О2 = 8 информационных входов 8.18,8 и 2" = 8 выходов 9,19.8,Каждый логический блок йиг.2)содержит два элемента И 10 и 11, злемент ИЛИ 12, элемент 13 равнозначности, элемент ИЛИ-НЕ 14, элементСЛОЖЕНИЕ ПО МОДУЛЯ ДВА 15, два настроечных входа 16 и 17, два информационных входа 18 и 19, два выхода 20 и 21 еЗОУстройство работает следующим образом,На Я -Й информационный вход уст 35 ройства (Я = 1,22") поступает значение уреализуемой логической Функции и переменных 1 = К(ХХ,, Х) на (.Я - 1)-и наборе аргументов Х Х 2,рХ . На управляющие входы 4 О первой группы подаются .сигналы настРойки 1),р 1)б, значениЯ котоРых прннадленат множеству 0,11. снтнепы 31)б определяют количество 1 с = , 11 ) 2 переменных Х 1,Х,т,..,Хк5-(С-Опо которым разлагается функция Й(Х,Х 2 р,Х). На управляющие Входы второй группы подаются компоненты двоичного вектора поляризации 1. = 5 О - )6б) переменных Х,Х ХНа выходах устройства формируются таблицы истинности логических функций и-Е переменных Ц(ХХ 1,), где 3 = 0,1. 2" - 1, на которые разлагается исходная логическая функция Г(Х,рХ 2 р,Х)р 42"-1) +1 где 3 , 3. е. , 3(Ой р 1 с) - номера единичних компонент:, двоичного 1 с.- разрядного эквивалента числа 1 и 1 о фПричем 6 = 0 только тогда, когда аргумент Хс(111) входит в конъюнкцию 1 с (3 = 0,12 -1) только без6)отрицания. Если бр = 1, то Х входит в Е только с отрицанием, т,е.Б Переменные ХХ входят вфукции Ц (ХкХ,) только безотрицания независимо ат значения комгонент 5(, вектора поляризации. Значения функций Ц (3к- кна первых 2 выходах устройства формируются значения Функции ( , на- ка рследующих 2 выходах - значения Функции Ц, и т.д, Таким образом, значение Функции Х , ,Х) на ч-мнаборе перемейных Хк Х(3Формируется на (2 1 + ч.+ 1)-мквыходе устройства,Если Б = 1),2 == 1)5 = О, тоЕ = 0 и сигнал на ч-м выходе устройства Ь = 1,2р 2) совпадает с сигналом на его ч-м входе, т.е. коэффициенты совершенной дизъюнктивной нормальной формы (д,н.ф,) Функции Е(Х,ХсеХт) ПЕрЕдаЮтСя траНЗИтОМ Навыход устройства. Поскольку Е = 0,1п, то устройство позволяет получить 2" - 1 разм личных разложений для каждой логической функции и переменных Г = Г(Хр ХрХ), включая транзитную передачу коэффициентов совершенной д,н.ф. на выход.При и = 3 общий вид этих разложений представлен в табл,1, где символом Х обозначено безразличное значе". ние сигнала на соответствующем входе.Устройство реализует следующий алгоритм поляризованного конъюнктивно. полиномиального раэлсжеция,(Х,гу, (Хг, Х) ) 9 Х Ч,(Х 1 Хз)х (Д (хзхз 16) х с,(Кзз)х Р(х ) Ю Х гСР(Х э) Ю Х, СР,Х з ВХ Х, СРз(Х з)СРО(хз ОхзСС (ХЗЮСРг(з З)ЙХ ХсСРз(Х 3)сто(хз)9 ХгСР (Х зВХ СРз(хзх ХгСРз(Х з)х Р,(хз)6)х,сР (Хз ЮХ, сР(хз ВХ, Х, сР(хз)0 СР 9 ХЗСРЯ) Хз(рОхгхз Х,Ч 9 Х ХЗа 6) Х ХгСРз 9 Х Хз ХЗСр,Со ХзФз гЖОХз ХэЧ ОХсРзО Х ХЗСЖ 1 С ХзсР 66 Х, Хз зсРсз ХзсР 6 ХзЖО+ Хз Хзс 1 ХсРР Х ХзсЮ Х )сзРЮ 1 С Хз Хзчс1 СРрйхзс 1 ф 9 Х 1 сЯ) ХзХэР 6 ЗХС 1 Я Х, ХэсРзЮ Х ХзСРзЯХ ХХСРО СДЭХДЮ ХзсР 0+ Х ХэсРЭХ%зз Х Хз РЯ Х ХгРзО+ Х, Х 1 хзсР.,1 С 6 ЭХзсс 9 ХзсС 04 Х Хэссзэ ХсР 0+ Х ХэсРэОХ ХзсР 6 з)Х ХзхсРзО ЩЭхзСРО+ХзсРО+ Х)%с) Х сОХ ХзОзЯХ ХдсРзИ Х Х зсР.ю, де , у 6 ,е, , д,Каноническиеполяризоеанниеполиноиъ Исходным для нахождения двоичных номеров таблиц истинности) логических функциг Ц;(Х Х ), = 0 12 - 1 является вектор зназ з20 чений разлагаемой логической ФункциизГ = 1 (Х с з Х зХ ): с з = (У , У з,". з) =(У , Уэ.,У ). Далее Формируется3 дзаз последовательность векторов зз,ы юк(1 с = 1,2 п), компоненты которшх вычисляются согласно следующим рекуррентным соотношениям: у;гэ зЕ3(а 1 з 1Р-с 1,-ет 1 ЕУа,.) .РЕе 1; ЗС = У,ОО У 2,1,с, (2) ээ- , егде ш = 2 , 1 = 0,12 - 1;- 1,2 пз и 1 = 1,2;,1 с.ЗНаЧЕНИЕ фуНКцИИ Сз 1(Х кз ззХп)на ч-м наборе геременных ХзкЦ = 0,12 - 1; з = О,1. ,2зз--1)совпадает с (2 з е тг е 1)-йкомпонентой вектора зз,В соответствии со сказанным компоненты вектора зз (1 с = 1,2 п)формируются на выходах 20 и 21 логических блоков 1 с-ой группы. Дешифратор и иэлемент ИЛИ обеспечиваютпрохождение компонент сформированного вектора 7 на соответствующие выходы устройства,35 40 45 Обозначим через г(с 1 = 1,2и) сигнал на первом настроечном входе 16 логических блоков с 1-й группы. Тогда на первом 20 и втором 21 выходах логических блоков а-й группы реализуются логические Функции соответствен 55 с(, = 1 Зз(зе)(21, гс Ч сС(1 з з 132) 3х х О х 1 х О О О х 1 0О О О О О 1 О1 О 1 О 1 1 1 1 где Кзг) = зз(е) 3 г - функция равнозначности; 1 и 1 зг - сигналы соответственно на первом 18 и втором 19 информационных входах логического блока; (э - а-й компонент вектора по 3ляризации, который подается на второй настроечный вход 17, логического блока а-й группы.Пусть Ь з(с = 1,2п) в . сигнал на с 1-м выходе дешифратора 1, Причем Ь = 1, если только двоичный код на входах дешифратора равен а - 1, т.е.5.1. 2 = с4:о Тогда г = Ь,; гг = гЧЬ и Г = 2,3п.Очевидно, если код 11,1)з на входах дешифратора 1 равен ,с (осуществляется разложение по переменнымХ 2зХк)з то г = гг = ,= гк = О, а г= г, == г=1. Прн этом для логических блоков 1-й группы (1 1,21 с)реализуемые ими логические функции, как следует из(3) и (4), имеют вид о( = 1 о е ( з1 зг) = 1 (эе 6) г бг з . (5 ) ег =/ Ю (г(6) Сравнивая (5) и (6) соответственно с (1) и (2), можно сделать вывод о том, что логические блоки первыхгрупп осуществляют преобразование исходного вектора коэфсрициентов совер-шшенной д,н.ф. ч в вектор ьзкз составленный из двоичных номеров Функс(ХкезззХзз)301 1 зфдз 2"- 1,Для логических блоков с-й группы (с = 1 с + 1и) гс = 1 и формулы (3) и (4) преобразуются к виду1559335 Соотношения (7) и (8) указывают, что сформированный на выходах логических блоков 1-й группы вектор чк без дальнейших преобразований проходит на выход устройства.Таким образом, устройство выполняет поляризованные разложения произвольной логической функции. (Х,ХХл) заданной посредством таблицы истиннос- О ти, по 1 с = О,1,..,и) переменным Х , Х Х (при 1 с = 0 на выход устройства проходят сигналы с его входов, т,е, осуществляется транзитная передача таблицы истинности логической функции Й (Х Х Х) В качестве примера в табл,2 пред-, ставлены компоненты векторов ю поко лучаемые устройством при п = 3, для функции К (Х Х, Х ) =Х, Х Х Ч Х, Х Ч ХХдля различных значений 1 сЬ = 0,1,2,3) и возможных векторов поляризации 6 =(5 5 ,5). В табл,2 символ Х обозначает безразличное состояние, а жирной линией выделены кортежи из компонент векторов ы , которые составляют таблицы истинности соответствующих логических функций Ч (ХккФ ,Х), где= 0,1. 2 Таблица 2 Значения компонентов вектора ж Вектор поляризации Код числапеременныхразложений ууб ут у 8 У,у у у 999 94. 9 - 96 99 6, 6 х О 0 1 х 0 0 11 О х 0 О 1, х 1 О 0 х 1 1 1 х 0 1 1 0 О 01 0 О 0 0 1 1 1 1 0 1 0 0 1 0 1 1 1 0 О О О 11 1 1 0 45 Таким образом, устройство позволяет выполнить 2 -1 полиномиальныхл+разложений произвольной логическойФункции п переменных.Формула изобретения Значения сигналов на выходах дешифратора 1 при различных комбинациях сигналов на его входах представлены в табл.3. Т а б л и ц а 3 и, 06.1 6,2 Устройство для полиномиального разложения логических функций, содержащее иэлементов ИЛИ (и - количество двоичных переменных разлагаемой логической функции), и дешифратор,. г-й вход которого (г = 1,я; я= 31 о 1(п+1 соединен с г-м управляющим входом устройства первой груп 2 3 0 0 О 0 1 0 0 1 О 0 0 0 О 0 11 0 1 1 О 0пы, первый и второй выходы дешифратора соединены соответственно с первым и вторым входами первого элемента ИЛИ, 3-й вход дешифратора Ц = З,п) соединен с первым входом Ц - 1)-го элемента ИЛИ, второй вход которого соединен с выходом Ц - 2)-го элемента ИЛИ, о т л и ц а ю щ е е с.я тем, что, с целью расширения функцио нальных возможностей за счет выполнения конъюнктивно-полиномиальных разложений по 1 переменным (К = О,п) с произвольным вектором поляризации, оно содержит и групп логических бло-. ков по 2"блоков в каждом, первый настроечный вход каждого логического блока первого яруса соединен с первым выходом дешифратора, первый настроечный вход каждого логического20 блока -й группы ( = 2,п) соединен с выходом (й - )-го элемента ИЛИ, второй настроечный вход каждого логического блока 1-й группы И = 1,п) соединен с х-м управляющим входом 25 устройства второй группы, первый информационный вход Р-го логического блока (Р = 1,2 ) первой группы соединен с Р-м информационным входом устройства, (2" + Р)-й информацион- З 0 ный вход которого соединен с вторым информационным входом Р-го логнческбго блока первой группы, первый выход (а 2 + 1)-го логического блока и-й групры Ь = 1, и - 1; в д О, 2" - 1;1 - 1, 2" ь ) соединен с первым иифори-Ьмационным входом (в 2 + 1)-го логического блока (Ь + 1)-й группы, второй информационный вход которогоИ г соединен с первым выходом 2 2 а+,40 +1) + 11-го логического блока Ь-й группы, второй выход (ш 2 + 1)-го логического блока Ь-й группы соединен с первым информационным входом2 "(2 ш + 1) + 11-го логическогоблока (Ь + 1)-й группы, второй информационный вход которого соединен свторым выходом 2" (2 ш Ф 1) + 1 го логического блока Ь-й группы, первый выход Р-го логического блокаи-й группы соединен с (2 Р)-м выходом устройства, 2 Р-й.выход которогосоединен с вторым выходом Р-го логи рческого блока и-й .группы, причемкаждый логический блок устройствасоДержит два элемента И, элемент ИЛИ,элемент ИЛИ-НЕ, элемент СЛОЖЕНИЕ ПОМОДУЛЮ ДВА и элемент равнозначности,первый вход которого соединен с первым информационным входом логического блока и первым входом элементаСЛОЖЕНИЕ ПО МОДУЛЮ ДВА, выход которого соединен с первым выходом логического блока, второй вход элементаСЛОЖЕНИЕ ПО МОДУЛЮ ДВА соединен с выходом первого элемента И, первыйвход которого соединен с выходом элемента ИЛИ-НЕ и первым входом элемента ИЛИ, выход которого соединен свторым выходом логического блока,второй вход элемента ИЛИ соединенс выходом второго элемента И, первыйвход которого соединен с вторым информационным входом логического блока и вторым входом элемента равнозначности, выход которого соединен спервым входом элемента ИЛИ-НЕ, второй вход .которого соединен с, вторымвходом второго элемента И и первымнастроечным входом логического блока, второй настроечный вход которогосоединен с вторым входом первого эле"мента И.1559335 Составитель В, СорокинТехред А.Кравчук Редакто ратил орректор Л, Бескид Тираж 56 при ГЕНТ СС рственного комитета 113035, Москва,3 оизводственно-издательский комбинат "Патент", г. Ужгород, ул, Гагарина, 101 Заказ 83 ВНИИПИ Г 7 г 7 бретен аушска Подписноеи и открытиянаб д, 4/5