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

(56) Авторское свидеВ 781822, кл. С 06 РАвторское свидетелВ 1124 281, кл . С 06 46Супрун ельство СССР 15/31, 1978. ьство СССР5/00, 1983. ласти едназначеи специа- системой ь изобреа для по- мметри- сширение ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ(54) УСТРОЙСТВО ДЛЯ ПОЛИНОМИАПЬНОГРАЗЛОЖЕНИЯ СИММЕТРИЧЕСКИХ БУЛЕВЫХФУНКЦИЙ(57) Изобретение относится к обвычислительной техники и прно для использования в ЭВМлизированных процессорах скоманд высокого уровня. Целтения - упрощение устройствлиномиального разложения сических булевых функций и ра его Функциональных возможностей за счет реализации монотонно поляризо". ванных полиномиальных разложений. Поставленная цель достигается тем, что устройство для полиномиального разложения симметрических булевых Функций от п переменных содержит п групп элементов СЛОЖЕНИЕ ПО МОДУЛЮ 2 по и+1 элементов в ь"й группе (3.=1 2,..,и), и+1 входов, и+1 выходов первой группы выходов и п+1 выходов второй группы выходов. На входы устройства подается буден вектор, однозначно задающий разлагаемую симметрическую булеву функцию, а най выходах устройства первой и второй а групп реализуются булевы векторы, оп-ределяющие соответственно положитепь- Цф но и отрицательно поляризованные полиномы симметрической булевой функци 1 ил,1444 743 гТаблица Т имеет и+1 строку и ее 0-я строка совпадает с некоторым (п+1)-разрядным вектором а( = ( ,), Остальные элементы Т Ы) связаны между собой следующими соотношениями:(К=1п; п=оп-К).Пусть крайние левые (правые) элементы строк таблицы Т (М) образуютбулев вектор Й,(Й), где Й, = (сюь,фэ во) э Й 1 (фарол э ф(Ь 1 ффь)Будем говорить, что булев векторЙ (Й) является результатом преобразования . 2( ) заданного вектора Ы,Работа устройства основана на следующем утверждении,Если Р симметрическая булевая функция (с.б;ф.), то 1(Р) = ( (Г; л (л и с учетом (1) и (2) имеет место:)Ъ) и Р(Р) = Ьо ь) ф то задача полиномиального разложения с,б,ф, Рсводится к преобразованию вектораИ (Р) в булевы векторы фР) и р(Р)соответственно.Введем в рассмотрение специальнуюдвоичную таблицу треугольного вида,которую обозначим через ТЯ )+ ХХХ Ю Х 1 ХХХц Изобретение относится к вычислительной технике и предназначено дляиспользования в ЭВМ и специализированных процессорах с системой командвысокого уровня,Цель изобретения - упрощение устройства и расширение его функциональных возможностей за счет реализациимонотонно поляризованных полиномиальных разложений.На чертеже изображена схема предлагаемого устройства для полиномиального разложения симметрических булевых функций при п = 7. 15Устройство содержит двадцать восемь элементов СЛОЖЕНИЕ ПО МОДУВО 21-28, восемь входов 29-36 устройствавосемь выходов 37-44 первой группы,восемь выходов 45-52 второй группы. 20Симметрическая булевая функция(с,б,ф,) Р = Р(хх) может быть представлена двоичным вектором 7(Р)=( Т, где Р; - значение Р нанаборе (любом) и двоичных переменных с х единицами (1=0;,и) .Пусть Р(Г) и Я(Р) - монотонно поляризованные полиномы с,б.ф. Р, причем панином Р(Р) поляризован по переменным х,х положительно, а поликом Я(Р) - отрицательно, В общемслучае полиномы Р(Р) и Я(Р) для с.б.фможно записать следующим образом:3 14447Устройство работает (согласно (2) и (3 следующим образом.На его -й вход, где з. = (1,п+1), подается (д)-я компонента 7; вектора и(Р) разлагаемой с,б.ф. Р =Р(хх). На х-ом выходе устройства первой группы выходов Формируется (д)-я компонента у;,вектора у(Р), а на 1-ом выходе устройства 10 второй группы выходов - (д)-я компонента р, , вектора А(Р) .Если же на входы устройства подать соответствующие компоненты вектора фР), то учитывая (4), на выхо дах первой группы будут сформированы компоненты вектора р(Р).Так, если на входы 29-36 устройства подать вектор й(Р)=(01100111) некоторой с.б.ф. Р=Р(хх 7), то на 20 его выходах 37-44,первой группы получим вектор у(Р)=(01100001), а на выходах 45-52 второй группы - вектор Р(Р)=(10011111). 25При подаче же на входы 29-36 устройства значения вектора у(Р)(01100001) на выходах 37-44 первой группы получим обратное преобразование - вектор 7/(Р)=(01100111). 30 Таким образом, предлагаемое устройство реализует монотонно поляризованные конъюнктивно-полиномиальные разложения симметрических булевых функций. 434формула изобретенияУстройство для лолиномиального разложения симметрических булевых Функций, содержащее и групп элементов СЛОЖЕНИЕ ПО МОДУЛЮ 2 (и - количество двоичных переменных разлагаемой функции), о т л и ч а ю щ е е - с я тем, что, с целью упрощения и расширения функциональных возможностей за счет реализации монотонно поляризованных полиномиальных разложений, каждая д-я группа содержит по и-+1 элементов СЛОЖЕНИЕ ПО МОДУЛЮ 2 (д = 1п), причем 1-й вход устройстЪа соединен с первым входом хго элемента СЛОЖЕНИЕ ПО МОДУЛЮ 2 первой группы, второй вход которого соединен с (+1).-м входом устройства, первый вход 1-го элемента СЛОЖЕНИЕ ПО МОДУЛЮ 2 К-й группы (1=1и-. К+1; К=2. и) соединен с выходом -го элемента СЛОЖЕНИЕ ПО МОДУЛЮ 2 (К)-й группы, второй вход соединен с выходом (1+1)-го элемента СЛОЖЕНИЕ ПО МОДУЛЮ 2 (К)-й группы, первый вход первого элемента СЛОЖЕНИЕ ПО МОДУЛЮ 2 -й группы соединен с ь-ым выходом устройства первой группы, второй вход (и-ь+1)-го элемента СЛОЖЕНИЕ ПО МОДУЛЮ 2 -й группы соединен с -ым выходом устройства второй группы выходов, (и+1)-й выход которой соединен с (и+1)-ым выходом устройсц- ва первой группы и выходом элемента СЛОЖЕНИЕ ПО МОДУЛЮ 2 и-й группы.акаэ .6506 оизводственно-полиграфическое предприятие, г. Ужгород, ул, Проектная,7 Тираж 704ВНИИПИ Государственногопо делам изобретений035 Москва, Ж, Рауш Подписноеомитета СССоткрытийая наб., д.