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

,.801441 р 4 Г 06 Г 5/Ортг"ЫЙ НОМИТЕТ СССР РЕТЕНИЙ И ОТКРЫТ ГОСУДАРСТПОДЕЛАМ САНИЕ ИЗОБРЕТЕНИ К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ(56) Авторское свидетельство СССР В 781822, кл. С 06 Р 15/31. 1978.Авторское свидетельство СССР Р 1124281, кл, С 06 Р 5/00, 1983, (54) УСТРОЙСТВО ДЛЯ ПОЛИНОИИАЛЬНОГО РАЗЛОЖЕНИЯ ЛОПИЕСКИХ ФУНКЦИЙ (57) Изобретение относится к области вычислительной техники и предназначено для использования в высокопро:изводительных ЭВИ для аппаратурной реализации системы команд, а также для построения специализированных процессоров. Цель изобретения - расширение функциональных возможностей устройства для:полиномиального разложения логических функции и переменных за счет выполнения коньюнктивнополиномиальных разложений по 1 переменным (1 с = О, 1.и). Поставленная цель достигается тем, что устройство для полиномиального разложениялогических функций и переменныхсодержит и групп элементов, СЛОЖЕНИЕПО МОДУЛЮ ДВА, по 2 . элементов вкаждой, и групп элементов И по 2элементов в каждой, иэлемент ИЛИи дешифратор на я входов, где з =:1 од -(и + 1)1. Устройство имеет 2информационных входов, в управляющихвходов и 2" выходов. На входы устройства подается значение преобразу- Жемой логической функции переменных, фра на входе устройства реализуется %УФ45 переменных х , х, по которым разлагается Функция Г(х , , х).При 1 с = 0 разложения не происходит и на выходах устройства сигналы совпадают с соответствующими коэффициентами СДНФ, подаваемыми на его входы. При 1 с = и происходит преобразование СДНФ в полином Жегалкина55 (сигналы на выходах устройства совпадают с соответствующими коэффициентами полинома), Если 1 с=1, : п, осуществляется конъюнктивно-полиномиИзобретение относится к областивычислительной техники и предназначено для использования в высокопроизводительных ЭВМ для аппаратурнойреализации системы команд, а такжедля построения специализированныхпроцессоров,Цель изобретения - расширениефункциональных возможностей устройст Ова для полиномиального разложениялогических функций эа счет выполненияконъюнктивно-полиномиального разложения по 1 с переменным, где 1 с = О,и. 15Йа чертежепредставлена схемаустройства для полиномиального разложения логических функций для п=З.Устройство содержит дешифратор 1,два элемента ИЛИ 2, и 2, четыреэлемента И 3, -3 первого яруса, четыре элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА4"4 4,первой группы, четыре элементаИ 5 в ,5 второй группы, четыре элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА 6 -64 вто"25рой группы, четыре элемента И 7,-7третьего яруса, четыре элементаСЛОЖЕНИЕ ПО МОДУЛЮ ДВА 8-84 третьейгруппы, два управляющих входа 9,.-и9, восемь информационных входов10,-108 и восемь информационных входов 11,-11Устройство для полиномиальногоразложения логических Функций работает следующим образом, 35На -й информационный вход (х1, , 2") подается значениеу , преобразуемой логической Аункции и переменных Г = Г(х,. , х)на (2 -1)-м наборе, на управляющие 40входы сигналы настройки П, , Бз,значения которых принадлежат множеству 0,1, Сигналы П. , Пз опрезделяют количество 1 с= , Б1=1 альное разложение Функции Е(х,х), которое имеет видкГ(хр ху) Я КС С(хк+ уС:х)1к1 С ( = .2 ) - множество всевозможных попарно не тождественных конъюнк.ций ранга г (г=О, , 1 с)переменных х, х к(коэффициент К 1, т,е.является конъюнкцией ран-га г=0),На выходах устройства Формируютсятаблицы истинности (двоичные номера)логических Функций Ьс переменных2д(х , х), 1=1 2упричем значение д на й-м наборе переменных хк , х, К = О,у1) реализуется на 22" к (1-1) - -м выходе устройства.Для устройства, приведенного начертеже, возможны и = 3 конъюнктивнополиномиальных разложения (при подачена управляющие входы 9 и 9 сигналов соответственно П= О и Ц = 02(1 с = 0) разложения не будет).Если 1 с1 (Ь =0; П =1), тоЕ(х, х х)= (р,(х,х)дхср(х ху)Если 1 с=2(0=1, 0=0), то Г(х, хх ) =(х )Юх у (х )Юх у. (х. )С)9 хх (р, (х ).Если 1 с=З 1, 0=1), то Е(х,х, х) - ЫВх сякхх ыдх, Ы Ях хЫ;х х Ыех х,хЫ 8где ЫЕ 01 и1, , Я.В качестве примера в таблицепредставлены значения сигналов навходах и выходах устройства при раэ"ложении логической, функции й (хх, х) = х,х ч ххЧ х х,Как следует из таблицы, Г(х, х ,х) = х,хч хх ч ххз = (х, ч х)ЭО+ х,(х, ч х ) = 1(В х х Ю х,х, О+О+ххх = 1 Эх х О+х, Юх,х О+Юхх хУстройство реализует следующийалгоритм конъюнктивно-полиномиаль-.ного разложения логических функций.Исходным для нахождения .давичныхномеров Функций Ч 1(х к+ ,., х),1 = 1, , 2 (выражение (1) )является вектор значений раэлагаемой44138 О логической Функции Г(х, , х):ф б 61 р ,ууу у 1) у у у у еу у ). Далее формируется последователь -4 - еность векторов ,., И %=1,, и), 5 компоненты которых вычисляются согласно следующим рекуррентным соотношениям:).2 ю+ у 2 и10 15 20 Формула25 Устройство для полиномиальногоразложения логических функций, содержащее п групп элементов. СЛОЖЕНИЕ ПОМОДУЛИ ДВА по 2 элементов в каждой (и - количество двоичных переменных разлагаемой логической Функции), о т л и ч а ю щ е е с я тем,что, с целью расширения функциональных возможностей за счет выполнения э где к =,К.Б,2.,-э скомпоненты вектоРЗ 1 , с=и, формируются на выходе 1-й группыэлементов СЛОЖЕНИЕ НА МОДУЛЮ ДВА,Дешифратор и иэлемент ИЛИ обеспечивают транзитную передачу компонентвектора У на соответствующие выходыустройства при подаче на его управляющие входы двоичных сигналовП.Б, код которых равен с,сигнал 1 с выходов элементов ИЛИ2, и 2),Если 1 = 2, сигнал "1" присутствует на третьем выходе дешифратора 1 (на первом и втором выходах -сигналы "О"), При этом сформированныйна выходе логических элементов второйгруппы вектор И проходит транзитомна выходе 11,-118 устройства.Если 1 = 3= и) на всех выходах дешифратора присутствуют сигналы ."О", которые поступают на входы элементов И всех групп. На выходах устройстда формируются компоненты вектора У,(Ы), которые являются коэффициентами полинома ЖегалкинаТаким образом, предлагаемое устройство позволяет получить и конъюнктивно-полномиальных разложений произвольной логической функции и переменных,изобретенияДля рассматриваемого примера приО на первом выходе дешифратора 1присутствует сигнал " 1" (на второми третьем выходах - сигналы "О 7,который поступает на входы элементовИ 3,-3, первой группы и через элементы ЙЛИ 2, и 2 - на входы элементов И 51 - 54 и 7, - . 74 Второй итретьей групп соответственно, Приэтом происходит передача коэффициентов СДНФ разлагаемой функции на выходы 11 -11 а устройства без преобразований,Если Е = 1, сигнал "1" присутствует на втором выходе дешифратора 1(на первом и третьем выходах - сигналы "О"). При этом на входы элементовИ 31-3 первой группы подается сигнал"О", что обеспечивает формированиена выходе элементов СЛОЖЕНИЕ ПОМОДУЛЮ ДВА 4-44 компонент вектораУ которые без изменений проходят.на выходы 11,-115 устройства (на первые входы элементов И 5-5 и 7, -74второй и третьей групп пос;упает конъюнктивно-полиномиальных разложе ний по 1 переменных (1=0,1п) содержит и групп элементов И по 2" элементов в каждой,пэлемент ИЛИ и дешиф"ратор, г-й вход которого (г = 1, 2 в;в = 1 ор(и+1)) соединены с г-муправляющим входом, а первый выходсоединен с первыми входами элементовИ первой группы и первым входом пер-,вого элемента ИЛИ, второй вход которого соединен с вторым выходом дешиф 45Фратора, а выход соединен с первыми ".входами элементов И второй группы,1-й выход дешифратора (1 = 3, 4,и) соединен с первым входом (-1)-гоэлемента ИЛИ, выход которого соединен с первыми входами элементов И1-й группы, а второй вход соединен свыходом (1-2)-го элемента ИЛИ, выход1-го элемента И ( = 1, 2, , 2 )р-й группы (р = 1, 2.и) соединен с первым входом -го элементаСЛОЖЕНИЕ ПО МОДУЛЮ ДВА р-й группы,второй вход которого соединен свторым входом х-го элемента И р-й1 Сигналы на информационных входахСингалы на выходахустройства Сигналынастройк ув ут .б у "Ф9 9 1 О 10 101 10 10 10 1 От 108 11 11 11 11 11 1111 т 118 0 0 1 0 1 0 0 1 1 1 1 0 1 0 0 1 1 1 0 10 1 0 0 1 1 1 1 1 0 1 0 1 1 10 1 00 0 1 1 1О 00 1 0 1 0 0 1. 1 1 1 0 1 1 1 0 05 1441380 6 групйы, выход г + ч)-го элемента нен с выходом (мГ)-го элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА о-й группы СЛОЖЕНИЕ ПО МОДУЛЮ ДВА -й группы,о-(г = 2, ч 1, 2, , я, второй и третий входы (1 + 1)-го- 1, 2, , и) соединен с элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА р-й вторым входом ч-го элемента СЛОЖЕНИЕ группы (=2-д, 0=2 ; 1 = 1, 2, ПО МОДУЛЮ ДВА (+1)-й группы, третийЙ) соединены соответственно с вход которого соединен с выходом (2 е+д+1)-м и (2 С+1)-м информацич-го элемента СЛОЖЕНИЕ ПО МОДУЛЮ ДВА онными входами устройства, выходы Ч-й гРУппы, выход ю Г-го элемента 1 О Д 1-х элементов СЛОЖЕНИЕ ПО МОДУЛЮ СЛОЖЕНИЕ ПО МОДУЛЮ ДВА о-й группы ДВА р-й группы соединены с (й +ь-,-1(Г = 2 ф ЪХ = 122+ О,. 2"Р, ) входами (С 0 е1,2. , и -2) соединен с вто" 2"), 2 -й информационный вход устрым входом Ь-го элемента СЛОЖЕНИЕ ройства соединен с 2 "-выводомуст- ПО МОДУЛЮ ДВА (Ь = (2 ч)Ю/2) и-й 5 ройствагруппы, третий вход которого соеди 1 11441380 Сорокин ректор С.Шекмар Дид Реда Заказ 6289/5 Производстве ектн кое предприятие, г, Ужгород, у аф и Составит Е, Конча Техред МТираж ВНИИПИ Госуд по делам 3035, Москва, 4ственного комобретений и оЖ, Раушская Подписноетета СССРкрытийнаб., д, 4/5