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

(56) Авторское свидетельство СССР 9 124281, кл, С 06 Р. 5/ОО 1983Авторское свидетельство СССР У 1441380, кл. С 06 Р 5/00, С 06 Р 7/00, 1987 е(54) УСТРОЙСТВО ДЛЯ ПОЛИНОМИАЛЬНОГО РАЗЛОЖЕНИЯ ЛОГИЧЕСКИХ .ФУНКЦИЙ (57) Изобретение относится к вычислительной технике и может быть использованов ЭВМ, интерпретирующих программы высокого уровня, а также в процессорах, ориентированных на эфФективное решение определенных задач, Цель изобретения - расширение Функциональных возможностей устройства за счет конъюнктивно-полиномиального разложения логических Функций по произвольным Мп переменным. Это достигается тем, что .Устройство для полиномиального разложения логичес" Изобретение относится к вычислительной технике и предназначено дляиспользования в ЭВМ с системой команд высокого уровня и в процессо; рах, ориентирование:х на классы решаемых задач.Цель изобретения - расширение функциональных воэможностей устройства для полиномнального разложения логических Функций за счет конъюнк-тивно-.полиномиалъного разложения ких функций содержит и (и - кол-во.переменНых разлагаемых логическойфункции) групп логических ячеек по2" ячеек в каждой, иузлов управления и икоммутаторов, причемкаждая логическая ячейка содержитэлементы И и элемент СЛОЖЕНИЕ ПО МОДУЛИ 2, 2 информационных входов,и настроечных входов и 2 выходов.На информационные входы устройстваподается таблица истинности раэлагаемой логической функции, на настроечные входы устройства поступают компоненты двоичного вектора настройки 7"(11011), определяющие пе менные, по которым осуществляется разложение (единичные компоненты тора Ч определяют переменные, по торым производится разложение), Н выходах устройства последовательн Формируются таблицы истинности ло1 с ческий Функций М (8=0,12 -) на которые разлагается исходная л ческая функция и переменных. 1 з. Ф-лы, 2 табл. 7 ил. логических Функций по произвольным Мп переменным.На Фиг. 1 представлена структурная схема устройства длл полнномиального разложения логических функций прн и 31 на Фиг.2 - Функциональная схема логической ячейки; на Фиг. 3 - функциональнал схема первого узла управления; на Фиг. 4 - Функциональнал схема второго узла управления; на Фиг, 5 - Функциональная "хема первогокоммутатора; на Фиг. 6 - Функциональная схема второго комйутатора; иа Фиг. 7 - графы состояний второго коммутатора для рассматриваемого примерааУстройство для полиномиального разложения.логических Функций (Фнг.1)вв е содержит 2 4 логические ячейки первой группы 1,-1 , 2 =-4 логическее ячейки второй группы 2 1-2,е, 2 "=4 логические ячейки третьей груп.3,-3 , и=2 узла управления 4, и. 42, й2 коммутатора 5, и 51, 2"=8 нформационных входов 6,-6, п=З астроечных входа 7, -7 , 2"=8 выхо- ов 8,-8.,Каждая логическая ячейка 1,2 и 3 фиг.2) содержит два информационных хода 9 и 10, настроечный вход 11, ыход 12, элемент И 13, элемент 14 ,ПОЖЕНИЕ ПО ИОДУПЯ 2.Узел 4 управления содержит два лемента НЕ 15 и 16, элемент ИЛИ-НЕ 7, элемент ИЛИ 18, элемент И 19, .:лемент 20 СЛОЖЕНИЕ ПО МОДУЛЮ 2 20 :( пять выходов 21-25.Узел управления 4 а содержит зле 11 ент ИЛИ 26, элемент НЕ 27, два элемента И 28 и 29 и три выхода 30-32.Коммутатор 5, образуют четыре элемента И-ИЛИ 33-36,Коммутатор 5 2 состоит из шести элементов И-ИЛИ 37-42. Устройство работаег следующим об 35 разом,На 1-й информационный вход Я 1, 2,2") устройства подается значе" ние у разлагаемой логической Функции 1 Е(х х,х ) на (3-1);м наборе 40 переменнйх х,х х . На настроечные входы 7 устройства поступают компоненты двоичного вектора настройки 0 =(П 132. П), определяющие переменные, по которь 1 м осуществляется разложение. При этом, если Н =1 (1=1,2,.ев,п), то выполняется разложение по перемейной х,; если Б.=О, разложение по х; ие производится, На выходах 8 устройства последовательно 5 О Формируются таблицы истинности логической Функции(8=0,1 е.а.е - 1), на которые разлагается исходная ФункЦИЯ(х Х 1 в Х )2-е 55Я(х ех еве ех) Кч(хе е ХЕ еввееХЕ, вка 1 в ев,де 1 К . 1 - множество всевозможных попарно различных конъюнкций ранга г ( 0,11 с) переменных хе ,хф еа вве;,хе , по которым осуществляется конъюнктивно-полиномиальное разложение.ЗНаЧЕНИЕ ФУНКцнн Ь 1 З (Х Еа 1,Х Еа 2е е ,х е ) на ч-м наборе переменньехПев-к хекахека 1.,х е (ч 0,12 -1;кл8=0,1 е 2 -1) Формируется на (2 " 8+ч+)-м выходе устройства,В табл. для п=З представлены виды 2 =8 возможных конъюнктивно-полиномиальных разложений логической Функции трех переменных Г=Г(хе,х ,х ).вв 2 ф 3Известно, что произвольная логическая функция переменных Е Г(хе,х1 ф 2 ф,х) допускает конъюнктивно-йолиномиальное разложение по переменной х; (16 сп) вида:Г(Х ех ееех )Х еехв вх а ее.Н 6(,в ")Г(Х 1 р)Х в еахОех ве вхв.) Ю (х вух-у 1 уХ,в,к)Выполнение разложения (2) по переменным хЕ ,ХЕ ехЕ дает возможв 1 Кность предс 1"авить произвольную логи- ЧЕСКУЮ ФУНКЦИЮ Е(ХХ 2,е,Х) В ВИ- де полиномиальной суммы (1) логических функций и-К переменньвх юз(хЕве,хе ), причем 1 хЕ ,х Еоф к.ее ка 1 в еех 2Х 1 Х 1 е ев ехе/1 Х Е вХ Е е еееХ 2 1 еИсходным для йостроения таблиц ис" тинности Функций является вектор знаЧЕНИй т,=(уу ,Еу К) Ь Еуе 1 Эв,ураэлагаемой Функции Я Г(хх х ,. Полагаем, что разложение производится последовательно по переменным хе,х ех еЛалее Формируется последовательность векторов ю ,ч й, компоненты которых вычисляются согласно следующим рекуррентным соотношениям:С 1 ь 2 ььь Ье,2 1 с, 150.07 В соответствии с принеденным алгоритмом разложения (3) устройство содержит п ярусов логических ячеек (фиг,2), работа которых описывается выражением: упращея который ца сц цх " рныхВыходах сМр 1 руйт унцтлрн 1РВ." рн,"НЫЙ ДВОИЧНЫЙ КОД (В 2,акоторый предназначен днц коммутапцнвходных сигналов коммутатора НО сап р а Вл еьи ям .Услоция Аормиронзн сгалоВь рьь р сцююреЯ, --1 у-ву -Г 0 ьс 1=23 П; у=23сгде Г, =Р (ПГ, Ь .,) - Лун30 даментлльые (элементарные) симметрИЧЕСКИЕ буЛЕНЫ Ьунхщь ЭаниеярСИЕот переменных И 11ь. 1,.гдеВ-Ос 1-1. Прц этом Г ,.-1 тогдаи "олько тогда когда ,+П 35 Ц - Р гфункции Г р (д=01 Р) поступают на вторые входы Р-го узла управления (Р=2,3п) со нторых ньпсодон (Р)-го узла управления и ис пользуются для Ьормировая сигналов .(5). В свои очередь, на своихвторых выходах Р"й уэе управленияреализует исходя из Г р ЬункцииР ,(6=01,Р+1)ь которые посту" 45паит на вторые входы (Р+1)-го узлауправления:6О р., Рр, если 6 =0;50 Гр .1 р Р р с р Рр ь есл ОсссР+1;О рьГ, если Ь =Р+1, (б)Для рассматринаемого примера (и 3)с учетом (5)ь (6) можно записать услония формирования сигналон уэламн 4упранления: х,щЬ,ч 0,в 1 11,0 р, и 5 - соответственно сигналыиа первом и втором инЛормационньх входах логической ячейки; 1.1. (11,2,,и) - сигнал на настроечном. входе логической ячейки(индекс . указывает,что ячейка находитсяв -м ярусе и на нееподается -й компонентвектора настройкиБ =(11 П П)о " сигнал на выходе логической ячейки.Как отмечалось ньшеь если П, =1, то разложение осучестнляется по переменной х,(1 Й.4 п), т.е. х;е 1 х р Хь Х. ОЛЕДОВатЕЛЬЦО, = Р ЭРьи 1-й ярус логических ячеек обеспечивает преобразование входного вектора значений согласно (3), При Б;=0 переменная х; принадлежит множеству х 1 х 1+сь. . х) и ,-й Ярус логических ячеек обеспечивает транзитную передачу входного вектора значений на выход.,ля выделения иэ векторов 7, ьч последовательных кортежей значений Функцийслужат коммутато" ры 5 (их обее количество п),Если сумма значений первых с 1 ком"поиеит П,Ц ь.ь 1 с(с 1=23 ьп)Ф вектора настройки О равна .Е 0=сто (с"1)"й коммутатор 5 обеспечивает ормирование на своих выходах упорядоченного вектора значений, в котором таблицы истинности промежуточных Функций разложенияф (Е 0,1, ,2 , 1, зависяиих От 1 с, переменных, располагаются последовательно в порядке возрастания к меров ЬункяФции, т.е. р, Ч, МаДля управления коммутаторами используются узлы 4 управления. Причем каадомУ (с)-мУ коммУтатоРУ (с 12 ь 3,.ь.п) соответствУет (с 1-1-й Узел ге =1 если и "И 1=Ф =И, -тили ц О, (41в ь- =1, если Е 1,с 1-1; Ьс-11фь ьс в1 вП=2 3с.Узлы 4 упранлеция могут быть построены на основе фудачетлВаго 20симметрического могаг Олюска.Тогда (4) можно представить н ние( 1) О УФ( 1)У 1) фА 3 ф 3( 1) 8 11 у 9 х у Щх 111 Е х х у 6 х 1 ух 1 х 1116 х 1 х.2 м 6 х,х х чееТаблица 2.Таблица истинности логических Функций ы (3 О2 -1; ИпЗ)Ъдля рассматриваемого лрймерв УВ ч; Вектор настройки зВектора эначений Функций Уэ в т ееше ееВ, 8В 1 В Ву,1 О 1 1 О 1 О О О О 1 1 ОО 1 О О О а. О О 1 1О 1ОО О 1 О О 1 ОО1 О О О О 1 ких ячеек (1+1)-й группы, выходы и первые информационные входы и-х логических ячеек которой (иИ+1,В,2 "Ь), выходы (1-)-го коммутатора соеди 1 ены соответственно с пер вым и вторым ипформацнонными входами ю-х логических ячеек (1+)-й группы, щ-й выход (111 ,222) (и)-го коммутатора соединен с (и+)-м вихо 10 дом устройства х-й настроечный вхрд которого (гщ 1,п) соединен с настроечным входом 2.-й логической ячейки х-й группы, первый и второй настроечные входы устройства соединены соответст 5 венно с первым и вторым входами первого узла управления, первые выходы которого соединены соответственно с управляющими входами первого коммутатора, (1+1)"й настроечный вход устройства .соединен с первым входом 1-го узла управления, первые .выходы кото= рого соединены сЬответственно с управляютими входами 1-го коммутатора вторые входы 1-го узла управления соединены с вторыми выходамн (2"1)"го узла управления.г, Устройство по п. 1, о т л ич а ю щ е е с я тем, что каждая логическая ячейка содеркит элемент СЛОЖЕНИЕ ПО МОДУЛИ 2 и элемент И, первый вход которого соединен с первым инормациойным входом логической ячейки, настроечный вход которой соединен с вторым входом элемента И, выход которого соединен с первым входом элемен" та СЛОЖЕНИЕ ПО МОДУЛО 2, второй вход которого соединен с вторым информационным входом логической ячейки, выход которой соединен с выходом эле. мента СЛОЖЕНИЕ ПО МОДУЛО 2.,Пчолннская Техред М.Дидык Коррек мар 1170 ТираГосударственного ком113035, Мос 6 Лодписн ГКНТ СС Производственно-издательскнй комбинат "Патент" г, Уигоро Гагарина, 10 У РедактЗаказ т 1 Х тета по изобретениям и открытиямва, Ж, Раушская наб д, 4/5