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

) 4 ГОСУДПО.Д ИСАНИЕ ИЗОБРЕТЕНИЯ ЛЬСТВ АТОРСН 0 СИ у 44(54) ПРЕОБ ЛЕНИЯ ЛОГИЧЕ (57) Изобр вычислител чено для и иэводитель программу, кого урони специализи тение относится к обл ной техники и предназ пользования в высокоп ых ЗВИ, интерпретирующи написанную на языкеа также для постро ованных процессов. Це стиаысония РСТНЕННЫЙ КОМИТЕТ СССР М ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ(56) Авторское свидР 781822, кл. С 06Авторское свидетР 1124281, кл. С 06 АЗОВАТЕЛЬ ФОРМЫ ПРЕДСТАВСКИХ ФУНКЦИЙ изобретения - расширение функциональ- ных воэможностей за счет преобразования дизъюнктивной нормальной формы (д,н.ф,) логических функций в канонические поляризованные полиномы (к,п,п.). Преобразователь содержит п ярусов элементов СЛОЖЕНИЕ ПО МОДУЛО ДВА по 2" элементов в каждом (и - количество логических переменных), п элементов НЕ и и ярусов элементов И-ИЛИ по 2 " 1 элементов в каждом. На информационные входы преобразователя подаются коэффициенты д,н.ф, логической функции, на настроечные входы преобразователя подаются компоненты вектора поляризации, на выхо- эФ дах преобразователя реализуется век" тор коэффициентов поляризованного полиномиального разложения. 1 ил., 1 табл.Изобретение относится к вычислительной технике и предназначено дляиспользования в высокопроизводительных ЭВМ,интерпретирующих программу,написанную на языке высокого уровня,а также для построения специализированных процессоровЦель изобретения - расширениефункциональных возможностей преобразователя формы представления логических функций за счет преобразования дизъюнктивной нормальной формы(д.н,ф.) логических функций н канонические поляризованные полиномы 15(к.п.п.).На чертеже представлена схемапреобразователя при и = 3Преобразователь содержит четыреэлемента 1-4 СЛОЖЕНИЕ ПО МОДЮЛЮ ДВАпервого яруса, четыре элемента 5-8СЛОЖЕНИЕ ПО МОДУЛЮ. ДВА второго яруса,четыре элемента 9-12 СЛОЖЕНИЕ ПОМОДУЛЮ ДВА третьего яруса, четыреэлемента 13-16 И-ИЛИ первого яруса, 25четыре элемента 17-20 И-ИЛИ второгояруса, четыре элемента 21-24 И-ИЛИтретьего яруса, три элемента НЕ 2527, восемь информационных входов28-35 преобразователя, три настроечных входа 36-38 преобразователя,восемь выходов 39-46 преобразователя.Логическую функцию Р = Г (х,х , , х) можно задавать посредством 2"-разрядного булева вектораее значений Я (Р) = (Мог (д г), где Я, - значение Р на2 -гг1.-м наборе (з. = О, 1, , 2 -1),Канонический поляризованный полиномР(Г) логической функции Р задаггется 2 -разрядным вектором - векторомкоэффициентов а 6(Г) = (а, аа), где а = 1 тогда и толькоггг э . сътогда когда слагаемое х." х 6Ф г 1, гевг х " (О( К(п) входит н45ЗкР (Г) й 1 1 , .1 - номераединичных компонент двоичного и-разрядного эквивалента числа 1.Здень вектор (7 =(б э, ,б )является двоичным вектором поляризации полинома. Причем Б 1 = О тогда итолько тогда, когда аргумент х;(- 1,2, , п) входит в слагаемыеполинома Р (Р) без отрицания; Одначасть аргументов функции Г Входит вполином только без отрицания, а другая - только с отрицанием. При п = 3к.п.п, функции Р н общем елучае имеетвид= х если б; = 0 6;и х= х;, если 5, = 1.Преобразователь реализует .ледующий алгоритм,.построения поляризованных конъюктинно-полиномиальных разложений.Исходным для нахождения вектораа;(Р) является вектор 4, = (уо оу 2 г ффг у" ) = (О.1 гг гггИ ) =Ю(Р), где у = И; =1,й2, , 2 . Далее формируется послеУ е-Эцовательность векторов ЧЪ, компоненты которых вычисляютсясогласно следующим рекуррентным соотношениям: Б12 ггг 1 г 1 г 1.к " у(211)щг к г ( К к- к-(1+11 е+Ф 21 ег 16) у (11 г) гК. гг -сгде ш = 2; 1 = О, 1, , 2 -1;1, 2, , т;К = 1, 2, , и.Компоненты вектора Н = (У", , У гОу) совпадают с соотнетствующими коэффициентами поляризованногоконъюктивно-полиномиального разлония г.е. а у ф,1 Ог "г2 -1.В соответстнии с приведенным алгоритмом К-й ярус (К = 1, 2.и)элементов СЛОЖЕНИЕ ПО МОДУЛЮ ДВА иИ-ИЛИ преобразует вектор М, в вектор Ы, причем работа элементовИ-ИЛИ К-го яруса описывается выражением (1), а работа элементов СЛОЖЕНИЕПО МОДУЛЮ ДВА К-го яруса - выражением (2),Преобразователь работает следующимобразом.На 1-й информацИонный вход Ц-йинформационный вход (1 = 1, 2,и2 ) подается значение Сд;, преобразуемой логической функции ГГ(х,х, , х) на (1-1)-м наборе переменных х , хг, , х (фактическина информационные входы преобразователя поступают коэффициенты соверРО(Г) =а,О+ а,х, 9 агхрах х9 а 4 Х 1 Е Б 6 С б Бг 6 бг14413 3щенной д,н,ф, функции Р). Иа 3.-й настроечный вход ( = 1, 2, , и) подается -я компонента 5, вектора поляризации б = (б Б , , Й ) На выходах преобразователя реализует.5 ся вектор коэффициентов поляризованного полиномиального разложенияПреобразователь позволяет получить 10и2 канонических поляризованных полиномов.Для рассматриваемого примера значения преобразуемой функции Г = Г(х, х , х 1) подаются на входы 28-35 соот ветственно, компоненты вектора поляризации б, , Й; , б - на входы 36, 37 и 38 соответственно. На выходах 39-46 реализуются коэффициенты а, , аполяризваннг коньюнк тивно"полиномиального разложения.В качестве примера в таблице представлены значения коэффициентов а , , а полиномиальных разложений логической функции Г = Г(х, х, 25 х) = х, х х Ч х,хч х,х для восьмй возможных комбинаций компонент вектора поляризации б =(б б, 6 ), На выходы 28-35 преобразователя подаются коэффициенты соответственно 30 Я , , И, совершенной д,н,ф составляющие вектор значений Г :И Ю = (а са, , , са,) =О,О,1,о,т, 1,0,1.1Формула изобретения 35 Преобразователь формы представления логических функций, содержащий и ярусов элементов СЛОЖЕНИЕ ПО МОДУЛЮ ДВА по 2 элементов в каждом (и - коли Ьчество логических переменных), причем в каждом Е-м ярусе элементы СЛОЖЕНИЕ ПО МОДУЛЮ ДВА образуют 2" группМ-еи щМ по 2элементов в каждой (Е =1, и), первый вход 1-го элемента СЛОЖЕНИЕ ПО 45 МОДУЛЮ ДВА первого яруса Ц=1,2. ) соединен с (2 3-1)-м информационным входом преобразователя, 2 -й информационный вход которого соединен с вторым входом -го элемента СЛОЖЕНИЕ 50 ПО МОДУЛЮ ДВА первого яруса, выход 1-го элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА 81и-го яруса соединен с 1-м выходом преобразователя, о т л и ч а ю щ н й с я тем, что, с целью расширения функциональных возможностей за счет преобразования дизъюнктивной нормальной формы логических функций в канонические поляризованные полиномы, содержит и элементов НЕ и и ярусов элемен.т-тов И-ИЛИ по 2 элементов в каждом, причем в каждом К-м ярусе элемен. ты И-ИЛИ образуют 2 "групп по 2К-Ф элементов в каждой, вход 1-го элемента НЕ соединен с 1-м настроечным входом преобразователя и первыми входами первой группы всех элементов И-ИЛИ, первые входы второй группы которых соединены с выходом Е-го элемента НЕ, первый вход -го элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА первого яруса соединен с вторым входом первой группы 1-го элемента И-ИЛИ первого яруса, второй вход второй группы которого соединен с вторым входом 1-го элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА первого яруса, первый вход -го элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА р-Й группы г-го яруса (1 = 1,ш, ш 2 ; р1, 2" "; г = Г,и) соединен с выхо-, домго элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА (2 р)-й группы (г)-го яруса и вторым входом первой группы -го элемента И-ИЛИ р-й группы г-го яруса, второй вход второй группы которого соединен с выходом ь-го элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА 2 р-й группы (г)-го яруса и вторым входом -го элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА р-й группы г-го яруса, первый вход (ш+)-го элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА р-й группы г-го яруса соединен с выходом г-го элемента И-ИЛИ (2 р)-й группы (г)-го яруса и вторым входом первой группы (щ+)-го элемента И-ИЛИ р-й группы г-го яруса, второй вход второй группы которого соединен с выходом ь.-го элемента И-КПИ 2 р-й группы (г)-го яруса и вторым входом (ш+1)-го элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА р-й группы г-го яруса, выход -го элемента И-ИЛИ и-го яруса является (2 " + )-м выходом преобразователя.(Уа42 а40 0 0 0 О 1 1 1 0 О 0 0 1 О 0 0 1 1 0 0 0 1 0 1 1 1 1 1 0 0 О 1 1 О 1 0 1 1 0 О 0 х,ух х Ях,О 0 1 О 1 1 1 0 0 0 0 1 1 0 О 1 1 О 0 О 1 О 0 1 1 1 1 0 О 0 1 1 1 1 О 1 1 О О О 1 Вхфх х,Ях ставитель В, Сорокихред М.Дидык Редактор Е, Коп Коррек Э, Лончакова аз 6289/ Производственно-полиграфическое предприятие, г. Ужгород, ул. Проектная Тираж 704 ВНИИПИ Государственног по делам изобретений 3035, Москва, Ж, РаувПодписное комитета СССР открытий кая наб д.